2월 알고리즘 연습

Have to Review!

  1. 3988.수고르기
  2. 239. Sliding Window Maximum
  3. 857. Minimum Cost to Hire K Workers
  4. 321. Create Maximum Number
  5. 428. Serialize and Deserialize N-ary Tree : DFS
  6. 960. Delete Columns to Make Sorted III : $N^2$ LIS
  7. 765. Couples Holding Hands : Greedy
  8. 302. Smallest Rectangle Enclosing Black Pixels : Binary Search
  9. 527. Word Abbreviation : 4가지의 다른 풀이
  10. 312. Burst Balloons
  11. 847. Shortest Path Visiting All Nodes : Iterative

2월 2일

(완) 10. Regular Expression Matching

  • 컴파일러 전공자라면 반드시 배우는 정규식이다. 풀어서 자존심을 지켰다!
  • 대학원 시절 REX로 state machine 그리던 기억이 났다.
  • Recursion 으로 짠 뒤에 Memo해서 DP로 풀면 된다.
  • 다만 +나 ?같은 기능들이 복잡하지 않아서 2차원 Iterative DP로도 풀린다. (나중에 풀어보자)

(완) 297. Serialize and Deserialize Binary Tree

  • Tree, DFS/BFS문제를 실수없이 한방에 통과해서 기분좋다.
  • string을 고정된 포맷으로만 만들어야 하는줄 알았는데, 걍 아무렇게나 만들어도 무방한거였다.
  • BFS로 해서 풀었는데, DFS로 하는게 훨씬 빠를것 같다.

(완) 273. Integer to English Words : 역대급 노잼문제.. 그냥 영어문제다.

(완) 25. Reverse Nodes in k-Group : 이것도 노잼.. 걍 Linked List

(완) 224. Basic Calculator : 스택쓰는 노잼문제, 근데 괄호를 미리 풀어서 계산하는 흥미로운 풀이도 있었음

(완) 85. Maximal Rectangle

  • 한참 고민했는데, 해법이 딱 생각이 났다.
  • row를 한칸씩 늘려나가면서 histogram 에서 최대 사각형 찾는 문제를 풀면 된다. $O(N)$
  • 히스토그램도 제출함
  • DP + stack 문제

(완) 295. Find Median from Data Stream

  • Running Median이란걸 활용할 때가 올줄 몰랐다. 지난번에 우연히 기억해두었는데 딱 그문제.
  • Heap 두개를 이용하면 add시에는 $O(\log{N})$ ~ $O(3\log{N})$로 풀리고, median Query는 상수시간에 가능하다.
  • 아래에 follow-up 문제가 있는데 모든 입력이 1~100이면 어떨까에 대한 문제.
    • 당연히 원래 방식대로 풀린다. 이때는 쿼리당 $O(\log{N})$
    • (풀어보기) BST에 pointer를 2개 두고 count를 value로 유지하면 풀릴듯, 이때는 $O(\log{100})$

239. Sliding Window Maximum

  • Stack이 아니라 deque을 이용하는 문제. 처음봤다
  • (다시 풀자) 아예 접근조차 못함.. $O(N)$만에 풀리는 문제.
  • 덱 문제 모아보기
  • 스택 문제라도 좀 풀어야겠다..

2월 3일

3988.수고르기

  • 어제 저녁에 덱 문제라고 골라놨는데, 매우 어렵다.

(완) 985. Sum of Even Numbers After Queries : 짝수 합을 구해놓고 diff를 갱신해주면됨, 매우 쉽다. $O(N)$

(완) 988. Smallest String Starting From Leaf : DFS로 leafNode까지 찾아서 문장 완성한 뒤에, minSoFar과 비교하면서 최종 min 찾으면 됨. $O(N)$

(완) 986. Interval List Intersections : 쉬운 two pointer 문제. $O(A+B)$

(완) 987. Vertical Order Traversal of a Binary Tree

  • 문제를 제대로 읽지 않고 방심하다가 3번이나 WA 맞음.
  • 처음에 DFS로 풀었는데, 깊이 순으로 정렬 조건이 있었음..
  • 깊이 순 정렬 위해서 BFS로 바꿨는데, 깊이가 같을때는 오름차순 조건을 또 놓침..
  • 결국 BFS에 queue대신 priority_queue를 쓰도록 해서 맞음. $O(NlogN)$

(완) 72. Edit Distance : 전형적인 string DP, $O(NM), O(max(N,M))$에 풀 수 있다.

(복습) 857. Minimum Cost to Hire K Workers

  • N이 10000인데.. 아무리 생각해서 $O(N^2)$ 밖에 생각이 안났다.
  • priority Queue 문제… 최소가 되는 K-subseq를 유지하는 문제였다.
  • 반드시 복습해야겠다.

(완) 843. Guess the Word

  • 고심끝에 풀었는데 정해와 완벽하게 맞았다.
  • 40분이나 걸린건.. 문제가 좀 있다. 속도를 올려야 한다.
  • 다 풀고 보니 Minimax라고 하는데, 가능한 최대 답변을 최소화 하기 때문이다. 이론 자체에 대한 공부는 필요한듯

(복습) 321. Create Maximum Number

  • 고심한 끝에 $O(NMK)$ 풀이를 했는데.. Memory 초과가 났다.
  • 공간을 $O(NM)$ 으로 줄이던지, 그리디를 활용하던지 해야한다.
  • 다시풀어보자.

2월 4일

(완) 759. Employee Free Time

  • Interval 합치기는 정렬하면 쉽게 가능하다. 버스 노선과 유사하다.
  • 다만 이미 정렬되어 있으므로 priority queue정도를 사용하면 $logK$ 정도 만에 구간을 합칠 수 있다.

(완) 296. Best Meeting Point

  • 비슷한 문제(Shortest Distance from All Buildings)를 푼 적이 있어서 그냥 각 점에서 시작하는 BFS를 돌렸는데.. 4.4초가 걸려서 뭐지.. 했다
  • 이 문제는 장애물이 없어서 훨씬 쉽게 푸는 방법이 있었다.
  • 1차원으로 각각 median을 구해서 더하면 되는거였다.
  • 장애물이 없을 시 온전한 Manhatan dist는 x와 y를 따로 계산한뒤 더해줘도 가능하다는 교훈
  • 그리고 1차원에서 median 까지 거리 계산할때는 양 끝점 쌍의 거리를 싹 더해주면 된다.

(완) 732. My Calendar III

  • 759. Employee Free Time 문제와 같은 유형으로 구간을 활용하는 문제.
  • 겹쳐진 최대값만 구하면 되므로 시작시점과 끝시점을 분리해서 생각하면 된다.

(완) 428. Serialize and Deserialize N-ary Tree

  • Tree 유형을 풀때 현재 가장 문제점은 구현에 시간이 걸린다는 점..
  • (복습) BFS로 풀었는데, DFS로 풀어보는것도 중요하다.

(완) 960. Delete Columns to Make Sorted III

  • 고심해서 보면 LIS 찾는 문제로 바꿀 수 있다.
  • LIS 를 $O(NlogN)$으로만 찾을 줄 알았는데, $O(N^2)$ 솔루션은 상당히 짧아서 구현이 쉽다. 제곱 버전으로 풀어볼만 한듯하다. (복습)
  • std algorithm 헤더에 all_of, any_of, none_of 란게 있는데 편한것 같다. 사용법을 익혀두자.

(완) 975. Odd Even Jump

  • Map을 이용하는 문제이다. 큰 원소 중 가장 가까운 원소와, 작은 원소중 가장 가장 가까운 원소를 찾을때 쓴다.
  • 내 풀이는 Map을 이용해서 jump 할 곳을 찾은 뒤, DP를 하는 방식이었는데, Solution은 Map을 이용해서 바로 dp를 하는 방식을 사용했다.

(완) 765. Couples Holding Hands

  • 사이클 찾기 문제, 풀이 자체는 꽤 빠르게 눈치챘는데 구현에서 매우 오래걸렸다.
  • (복습) Greedy로 풀면 $O(1)$ space로 풀 수 있다고 한다. 풀어보자.

(완) 773. Sliding Puzzle

  • BFS 로 풀린다. 다만 16진법 Int로 바꿔서 bit swap하고 별짓을 다했는데 string으로 표현하면 매우 쉽게 풀리는 문제였다. 심지어 string이 더빠름…
  • 역시나 오래 걸렸다.

(완) 302. Smallest Rectangle Enclosing Black Pixels

  • DFS로 풀었는데.. 정해는 Binary Search였다. DFS는 1의 개수가 작을때 유리하다. 다만 worst case가 $O(X^2)$
  • (복습) Binary Search는 특정 케이스에서는 DFS보다 느리지만 평균 $O(X\log{X})$만에 해를 찾는다.

2월 5일

527. Word Abbreviation

  • 첫 문제부터 못풀었다. Trie를 사용하려고 했는데, 처음 설계한 방법은 길이가 다른 문자열에 대한 고려를 못하는 문제가 있었다.
  • (복습) Solution 보니 풀이가 매우 다양한다.
    • Greedy
    • Sorting을 이용한 풀이
    • LCP를 이용한 풀이
    • Trie 를 제대로 이용한 경우
    • 등등 엄청나게 많다.

(완) 145. Binary Tree Postorder Traversal

  • 예전에 연습한 적이 있는 아는문제라서 빨리 풀었다.
  • Iterative로 Postorder할때는 역순(R->L)으로 넣어야 L->R 순으로 탐색된다.

(완) 778. Swim in Rising Water

  • 해법을 빠르게 생각해내서 풀었다.
  • BFS 탐색과 유사하게 가져가는데, queue 대신 Priority Queue를 사용하는 문제이다. 엇그제 풀었던 987. Vertical Order Traversal of a Binary Tree 과 매우 유사하다.

312. Burst Balloons

  • 또 다시 해법 생각해내지 못하고 Fail..
  • 처음에는 DP로 접근하다가, 결국 Greedy로 틀었는데 반례가 있었다. Greedy 공포증이 한층 더 심해진느것 같다.
  • 해법은 양쪽을 범위로 잡는 DP이다. 확실히 Transition 함수를 구성하는 능력이 떨어지는것 같다. 연습과 정리가 필요하다.

(완) 632. Smallest Range

  • 전형적인 K-sorted 배열문제라 Priority queue를 바로 생각해냈다. 다만 Priority queue로는 back을 찾기가 어려워서 결국 multiset으로 바꿔서 풀었다. 복잡도 자체는 똑같지만, 용도에 맞는 Priority queue를 사용했어야 했다. $O(NlogK)$
  • 다른 사람의 풀이를 보니 back(최대값)을 구하는것을 그냥 넣은 것 중에 최대값으로 바꿔서 풀었다. K-sorted 배열문제에서 heap 쓸때 back을 구하는 테크닉을 알아 둘 필요가 있겠다.

(완) 847. Shortest Path Visiting All Nodes

  • TSP를 못알아보고 30분을 고민하다니.. 반성해야한다. N의 제한이 12인것만 봐도 TSP인데.. ㅠㅠ
  • TSP를 돌리려면 모든 노드 사이의 비용이 있어야 하는데, Floyd-Warshell로 찾으면 된다.
  • (복습) BFS 풀이, Iterative 풀이, Floyd-Warshell 없이 DP

(완) 768. Max Chunks To Make Sorted II

  • 지난번에 못풀었던 stack 사용하는 문제. 뒤섞인 녀석들 사이의 연산은 하지 않고 최대값 하나로 대체하는게 키포인트이다.

2월 9일

(완) 695. Max Area of Island : FloodFill, 문제를 읽자

(완) 49. Group Anagrams : Count Sort, Hash (13m)

(완) 46. Permutations

  • 두가지 풀이로 품
    • (6분) 단순하게 O(N*N!)짜리 backtracking으로 풀기 공간복잡도가 O(N)
    • (25분) NextPermutation 사용 O(1) 공간복잡도

(완) 8. String to Integer (atoi): 노잼 구현문제

(완) 151. Reverse Words in a String: 그지같은 노잼문제.. 구현 + 아이디어, 각 단어를 뒤집은뒤에 다시 뒤집으면 된다.

(완) 127. Word Ladder

  • BFS로 풀면 된다. (14분)
  • 모든 BFS경로 다 찾는것도 풀어봄 (23분) 126. Word Ladder II
    • 이때 주의할점은 visit 표시를 한 depth 끝날때 몰아서 해줘야한다는 점임
    • 그래야 1>2>3>4와 1>5>3>4 두 경우 모두를 찾을 수 있음.

(완) 381. Insert Delete GetRandom O(1) - Duplicates allowed

  • 중복 허용 안하는 버전은 여기 380. Insert Delete GetRandom O(1)
  • vector에서 정확한 위치를 알고있고, 순서가 상관없을때, last랑 스왑한 뒤에 지우는것은.. 충격 O(1)만에 지울수 있다니 ㅠㅠ
  • 위에 사실만 알면 중복 허용 / 비허용은 List로 각 위치의 정보를 가지고 있으면 쉽다.
  • 중복 금지 :
    1
    2
    vector<int> nums;
    unordered_map<int,int> valToPos
    
  • 중복 허용 :
    1
    2
    3
    vector<int> nums;
    unordered_map<int, list<int>> valToPos;
    vector<list<int>::iterator> pointers;
    

(완) 173. Binary Search Tree Iterator

  • 이것도 재미있었음, 나는 DFS를 시뮬레이션 하는 식으로 품
  • Iterative 기반의 DFS를 잘 이해해게 된 것 같다. 뭐 대충 이런식
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    stack<Node> st;
    st.push({root, PRE});
    while(st.size()) {
      Node& cur = st.top();
      if(cur.state == PRE) {
        if(cur.node->left) st.push({cur.node->left, PRE});
        cur.state = IN;
      } else if(cur.state == IN) {
        if(cur.node->right) st.push({cur.node->right, PRE});
        cur.state = POST;
      } else if(cur.state == POST)
        st.pop();
    }
    
  • 근데 생각을 조금만 더 해보면 더 쿨한 방법이 존재함.
  • (복습) stack을 유지하면서 top을 기준으로 right의 left들을 쭉넣기

(완) 79. Word Search : 노잼 백트래킹

(완) 528. Random Pick with Weight

  • 1,4가 있는데 바이너리 서치를 하면
    • upperbound는 0/1,2,3 으로 쪼개지고
    • lowerbound는 1/2,3,4로 쪼개진다.

(완) 50. Pow(x, n): 익숙한 문제, 지수를 이진법으로 만들면 Iterative가능

(완) 103. Binary Tree Zigzag Level Order Traversal : BFS로 돌면서 홀수 level에서 뒤집어주면된다.

(완) 43. Multiply Strings : BigInt 곱하기 문제, 풀어봄직 했다. Int Vector 만들어서 풀고 다시 string으로 바꿔주면 됨.

(완) 16. 3Sum Closest: triplet 문제, 하나를 고정시키고 나머지 두개를 two pointer로 옮겨보면 풀린다. 등차중항, 등비중항 찾듯이 생각하자.

(완) 394. Decode String: Iterative로 풀었는데 솔직히 너무 복잡하게 코드를 작성한듯. recursive로 풀었으면 더 쉬웠을 수도 있겠다.

(완) 636. Exclusive Time of Functions: 두문제 연속 스택문제 였는데, 이번에는 Iterative가 더 쉽다. ㅠㅠ 더 간단한 구현에 대한 감이 필요할듯

(완) 347. Top K Frequent Elements: 이제는 익숙한 k-min/k-max 문제, heap을 써서 푼다.

(완) 133. Clone Graph : 이것도 이제는 익숙한 그래프 클론문제, hash로 address를 mapping 하면 된다.

143. Reorder List

  • O(N) 공간으로 풀었는데.. O(1) 방법이 있었다. 다시 풀자.

(완) 48. Rotate Image : 머리써서 swap하는 문제, 사각형을 그리며 돌려야 한다.

2월 10일

834. Sum of Distances in Tree

  • 점점 멘탈에 금이간다. 왼쪽 오른쪽 subtree의 값을 가지고 와서 구하는 식으로 풀었는데, 아이디어가 부족했다. 구체적인 아이디어가 떠오를 때까지, 코딩을 하기보다는 아이디어를 구체화시키는게 더 중요하다.
  • 정해: 카운트까지 고려해서 풀면 더 쉽게 풀린다. 처음에는 count와 자녀 노드까지의 거리 합을 알기 위해서 dfs를 돌리고, 이후에 각 노드마다 부모 노드의 카운트에다가 값을 빼주면 된다. 근데 답을 봐도 이걸 어떻게 알지 싶다 -_-
    • https://leetcode.com/problems/sum-of-distances-in-tree/solution/

761. Special Binary String

  • 두 문제 연속 참패.. string + 재귀 문제였는데, DP로 접근하려다가 망했다. 코드가 점점 복잡해지더니 결국 실수하면서 망한듯.
  • 오늘 Leetcode 상태가 완전 메롱이라서. COCI풀러 백준 가야할듯

(완) 피터팬 프레임

  • 속도가 이슈인 문제, 빠른 코딩! 21분

(완) SLIKAR

  • BFS로 시뮬레이션 하는 문제 29분 걸림
  • 사소한 실수 줄이기.

(완) 007

  • TSP가 dp[N][1<<N] 인 이유는 마지막 노드 정보가 필요하기 때문
  • 이 문제는 마지막 노드 정보가 필요없으니 dp[1<<N]으로 충분함

(완) 410. Split Array Largest Sum

  • 다행히 이분탐색이 생각나서 풀 수 있었다. (17분)
  • 근데 DP로도 풀리네.. 못푸는 줄 알았는데
    • N까지 끝나는 K개 집합의 최대합으로 dp state를 주면 풀린다.
    • 요새 보니 점화식을 너무 못세운다.. ㅠㅠ
    • 심지어 부분합도 생각이 안났다.. 미친 반성해야함
  • 결국 DP로도 풀어봄, 전형적인 점화식 패턴이니 익숙해질 것

465. Optimal Account Balancing

  • 전혀 감도 못잡음.. Array로 정리한 뒤에 DFS해야한다.

(완) 341. Flatten Nested List Iterator

(완) 780. Reaching Points

  • 이것도 오늘 아침에 풀다가 맨붕온 991. Broken Calculator 이거랑 완전 유사하다.
  • S에서 T를 찾아갈때 역방향으로 찾으면 문제가 엄청 간단해지는 아이디어다.