1월 알고리즘 연습

Have to Reiview!

  1. 644. Maximum Average Subarray II : $O(N)$
  2. 85. Maximal Rectangle

1월 22일

배럭

  • 그리디로 풀어야 할 것 같은데 그리디 증명을 못찾고 있음.

(완) 버스 노선

  • 정렬 하면 뒤에 있는건 시작지점이 항상 앞쪽 노선에 포함
  • MaxEnd유지하면서 포함시키면 됨
  • 한바퀴 돌고 나서는 N+MaxEnd에 속하는걸 빼야함
  • 정렬한 후 출력

(완) Iroha’s Obsession

  • 간단한 문제 그냥 10만까지 자리수 체크함
  • 근데 10N까지만 해두됨

1월 23일

(완) 1725. 히스토그램 : 스택

(완) 6549. 히스토그램에서 가장 큰 직사각형 : 스택

(완) Number of Boomerangs : Hash로 N^2 만에 풀린다.

(완) House Robber : 2-state DP 쉬운문제

1월 24일

(완) Iroha and a Grid

Iroha and Haiku

  • 풀지는 못했는데 정답을 보고 정말 신선하다고 생각
  • 1 = 1b / 2 = 10b / 3 = 100b .. 로 나타내는 기법
    • 만약에 어떤 array에서 2, 3, 4 합을 가지는 subarray를 찾는 문제라면
    • 위 표기로 shift 하며 2+3+4 bit 만 저장한 뒤 101001000b와 AND 연산을 통해서 확인 가능
    • 예를들어 1,1,3,2,2라면 111001010b라서 위 Filter AND 연산하면 Filter가 다시 나옴
  • 위 문제는 이걸 이용해서 Bit DP를 돌림
  • 나중에 꼭 다시한번 풀어보자.

(완) 316. Remove Duplicate Letters

  • Greedy + Stack 쓰는 문제인데 또 생각 못하고 솔루션 봄 (Greedy 너무 스트레스인듯)
  • 정리하면 아래와 같다.
    • 각 문자의 count를 미리 저장해둔다.
    • Stack을 사용하려면 제외되는 sequence에 대한 검증이 필요
    • c가 stack top이고 지금 a를 비교하고 있다. c에 대한 count가 남았다면 a를 앞에 보내는 것이 무조건 사전순으로 더 빠르다. 즉 ca로 시작하는 sequence에 대한 고려는 모두 불필요하다. 그러므로 c를 버린다.

(완) 308. Range Sum Query 2D - Mutable : 2D Fenwick Tree

1월 25일-26일

(완) 406. Queue Reconstruction by Height

  • 오늘은 Greedy만 무진작 파볼 계획
  • 이 문제의 Greedy 포인트는 작은 사람들 부터 배치하는것, 나중에 배치할 사람들은 모두 크므로, 현재의 배치는 정답인 배치라고 확신할 수 있게 된다.
  • 처음에는 $O(N^2)$ 를 생각했는데, 나중에 Discuss를 보니 BIT를 사용하는 방식이 신선했다.
  • BIT로 특정 위치의 앞자리에 있는 사람 수를 관리한다면 원하는 자리를 $O(\log^2{N})$ 만에 찾을 수 있을 것 같다. 최종적으로는 $O(N\log^2{N})$ 인듯
  • 가장 큰 사람부터 $k$ 번째에 세우는 것도 괜찮아 보인다. 이 방식도 Greedy 인데, 입력이 정확하다면 작은 놈들은 고려되지 않으니, 큰 놈들 부터 $k$ 번째에 항상 세울 수 있다는 가정을 하는 것이다. 다만 이 경우는 List를 쓰거나 Vector를 써야하는데 시간복잡도가 무조건 $O(N)$이다.

(완) 621. Task Scheduler

  • 나름 방법을 찾은것이 가장 개수가 많고 배열 가능한 Task 부터 실행하는 것인데..
  • 그리디 : 가장 개수가 많은것을 배열하는 것이 그렇지 않은 것을 배열하는것 보다 항상 이득이거나 동등하다.
  • 증명 -_- 어떻게 해야할지 모르겠다.
  • $O(1)$ 해법 : $max({num Of Tasks}, {maxNumOftask}*{(n+1)} + {countOfMaxNumOftask})$

(완) 253. Meeting Rooms II

  • 그리디 아닌듯, 그냥 시작시간과 끝시간 나눠서 돌리면 끝

(완) 134. Gas Station

  • Kanade 응용문제, Kanade도 일종의 Greedy로 보는건가.
  • 두번 돌 필요가 없는 부분은 캐치 못함

(완) 45. Jump Game II

  • 몇번의 깨달음을 거쳐서 풀었다. $O(N)$
  • 다음 점프 할 곳을, 다다음 점프를 할 거리가 최대가 되도록 잡으면 된다.
  • 증명 : X=A에서 다다음 점프의 거리가 최대일때, X=B에서 선택할 수 있는 모든 지점들이 X=A에서 뛰는 선택에 포함된다.

(완) 544. Output Contest Matches : 간단한 Recursion, 쉬움

(완) 378. Kth Smallest Element in a Sorted Matrix

  • 퀵셀렉트로 $o(n), O(n\log{n})$ 로 풀었음
  • Priority Queue를 쓰면 O(k\log{n}) 가 가능한 것도 알고 있었음
  • 근데 이게 column으로도 정렬이 되어 있어서 O(k\log{k})가 가능함.

1월 27일

(완) Design Search Autocomplete System

  • 쉬울 줄 알았는데 꽤 복잡한 자료구조 문제였음.
    • Trie의 각 Node가 set<string*>을 가지고 있도록 설계
    • 각 string의 빈도수는 hash table로 구현, 검색속도를 빠르게 하기 위해 key를 pointer로 사용
    • pointer만 있으면 실제 string과 matching 되는 여부를 판단하기 어려우므로, 처음 한번의 판단을 위해서 unordered_map<string, string*>을 사용.
    • history 리스트 중 count가 최대인것 3개를 찾기 위해, priority queue를 사용 O(Nlog3);
  • 시간 자체는 굉장히 빡빡하게 품, 실수하면 금새 시간이 지나간다.

(완) 303. Range Sum Query - Immutable : 부분합, 쉬움

(완) 276. Paint Fence : 1/2-DP, 쉬움

(완) 984. String Without AAA or BBB

  • 가장 힘든 Greedy, 풀면서도 항상 찝찝하다.
  • 해법은 쉽게 생각이 났다. 같은 문자가 3개 이상 나오면 안되므로
    • A와 B중 큰 놈으로 시작한다. 작은 놈으로 시작하면 나중에 그 문자가 모자란다.
    • 큰놈을 2개 쓰고, 작은놈은 1개 쓴다. 같을 경우는 1개씩 쓴다.
  • 증명은 귀류법
    • A > B 인데 B를 먼저 사용한다면, B가 먼저 0이 된다. A가 3개 이상 붙게 되므로 모순
    • A > B 인데 (1,2)나 (1,1)로 계속 사용한다면, B가 먼저 0이 된다. A가 3개 이상 붙게 되므로 모순
  • 다른사람이 푼것 보는데, 정말 깔끔하게 푼다. 깔끔하게 푸는 연습을 해야할듯

(완) 981. Time Based Key-Value Store : 초간단 자료구조, 쉬움

(완) 983. Minimum Cost For Tickets

644. Maximum Average Subarray II

  • $o(N), O(N^2)$까지는 줄였는데, $O(N)$까지는 못 줄였다.
    • 내가 한 접근은 현재 max 평균보다 작은 원소는 빼도 좋다는 것이다.
    • 1.2s 정도 나오는데 정해는 20ms 대에 풀린다.
  • 푼 사람들은 Convex Hull을 쓴 사람도 있고, 뭔가 요상한 Two Point를 쓴 사람도 있다.
  • 출제자의 의도는 Floating point Binary Search
  • 복습 필요

85. Maximal Rectangle

  • DP문제라고 하는데 아직도 이해가 안감
  • 복습 필요

(완) 891. Sum of Subsequence Widths

  • 두 문제 연속 해법를 못잡고 시간만 보내고 나서, 겨우 맨탈 잡고 풀었다.
  • 완전 수학문제다. 소팅해도 결과가 같은것을 확인하고, 직접 써가면서 규칙을 파악하면 된다.
  • 완전 Cool한 풀이가 있는데 역시나 수학이다. 경우의 수를 매우 잘 세어야 한다.

1월 28일

(완) 123. Best Time to Buy and Sell Stock III

  • 4 State DP 문제다.
  • 살때 가격을 뺀다고 생각을 못하니 문제가 굉장히 어려워진다.
  • 결국 state에 최근 산 가격을 저장하는 식으로 풀었는데, 식도 복잡하고 마음에 들지 않는다.
  • 살때 가격을 뺀다고 생각을 Discuss로 보고 Recursion으로 다시 풀었다.
  • 작은 아이디어가 코딩 양을 어마무시하게 차이나게 만든다.
  • 나중에는 Iterative로 풀어보자.

(완) 689. Maximum Sum of 3 Non-Overlapping Subarrays

  • $O(N)$짜리 문제, lmax와 rmax를 이용하는 수족관과 같은 형태의 문제이다.
  • 공간복잡도를 $O(N)$으로 두면 lmax와 rmax 배열을 잡아서 간단한 코드로 풀 수 있다.
  • 공간복잡도 $O(1)$의 경우는 고민이 필요하다.
    • 수족관 같은 경우는 포위하는 형태의 two pointer로 풀 수 있었다.
    • 이 경우는… 복습 필요.

1월 29일

(완) 788. Rotated Digits

  • 쉬운 문제라고 나왔는데, 쉽지 않았다.
  • 처음에는 N으로 풀었고, 나중에는 N보다는 좋은 백트래킹을 했다.
  • 잘 생각해보니 N에 근접한 케이스를 제외하고는 모두 결과 재사용이 가능한 것 같아서 이걸 이용해 Memoization을 했더니 $O(logN)$으로 잘 풀린다.

1월 30일

(완) 128. Longest Consecutive Sequence

  • Hash를 이용하는 문제, O(n)을 찾으라고 처음부터 문제에 나와있어서 쉬웠다.
  • 그렇지만 해가 바로 생각난것은 아니고 나름 한참 걸림..

1월 31일

(완) 301. Remove Invalid Parentheses

  • 백트래킹 문제였는데 DP 하겠답시고 무려 2시간을 넘게 풀었다.
  • Debugger까지 동원해 끝까지 풀긴 풀었으나, WA가 무려 9번…
  • 풀리는 Naive Solution까지는 최소한 생각하고 풀어야 한다.

(완) 51. N-Queens : 기분 전환용 백트래킹

(완) 815. Bus Routes : Hash와 묘하게 결합된 그냥 BFS

926. Flip String to Monotone Increasing : 역시나 간단한 배열 문제