CP Algorithm & Knowledge (30) 썸네일형 리스트형 편집 거리(Edit Distance) 알고리즘 다음 문제를 생각해보자. 문자열 a와 b가 있다. 여기서 각 문자열의 임의 위치를 삭제하거나 다른 문자로 교체, 그리고 임의의 문자를 삽입하는 행위의 비용을 1이라고 할 때 a와 b를 같은 문자열로 만드는 최소 비용을 구하라. 예를 들어 "abc"와 "abd"가 있을 때 세 번째 글자를 동일하게 만들면 되므로 편집 거리는 1이다. "ABCD"와 "ABd"는 'D'를 삭제하고 'C'를 'd'로 바꾸면 되므로 편집 거리는 2이다. 혹은 "ABd"에서 'd'를 'C'로 바꾸고 'D'를 추가해도 된다. 이 문제는 2차원 dp로 풀 수 있음이 널리 알려져 있다. 어떻게 dp로 풀 수 있는지 같이 살펴보도록 하자. 우선 단어를 하나 이해해야 한다. align: 보통 맞추다 혹은 정렬(sort가 아님을 유의)이라고 .. Rerooting Technique on Tree 이 게시글에서는 트리에서 할 수 있는 rerooting technique라는 것을 다뤄본다. Rerooting? 자연수 N개의 노드로 구성되고 루트가 정해진 트리가 주어져 있고 배열에 다음과 같은 정보가 담기길 원한다고 해보자. sub[i] = i번째 노드가 루트인 서브 트리에 대해 해당 트리에 속한 노드의 개수 이 배열을 완성하기 위해서 어떻게 해야 할까? 먼저 생각나는 단순한 방법으로는 각 노드마다 dfs를 돌아 노드의 개수를 세는 $O(N^{2})$ 방법을 떠올릴 수 있다. 하지만 당연하게도 이런 글을 쓴다는 것은 $O(N^{2})$ 시간 복잡도로 해결할 수 없도록 N의 크기가 $10^{5}$ 이상인 경우에 대해 푸는 방법을 알아보는 것이므로 위 방법은 쓸 수 없다. 게다가 각 노드가 루트라고 할 .. 0-1 BFS(0-1 Breadth First Search) 이 게시글에서는 특정한 상황에 놓인 그래프에서 최단 경로를 찾을 때 $O(V + E)$의 시간 복잡도로 해결할 수 있는 0-1 BFS에 대해 다룬다. 거기! 혹시 코테를 준비하신다면? 딱 말할 수 있다. 0-1 BFS를 공부할 것을 강력히 권한다. 본인은 어떤 기업의 코딩 테스트에서 0-1 BFS를 사용할 수 있는 문제를 목격한 뒤로 이 글을 쓰기로 마음먹었기 때문이다. 문제에 비공개 조약이 걸려 있으므로 어떤 기업인지 자세히 말할 수 없지만 전통적인 대기업의 계열사이다. 따라서 대회에 초점을 맞춘 사람이 아니어도 0-1 BFS를 공부해서 손해를 볼 일은 없을 것이다. 0-1 BFS란? BFS는 BFS인데 특수한 환경에서 작동할 수 있는 BFS이다. 그 특수한 환경이 뭐냐고? 0-1을 보면 무엇인지 추측.. 최장 증가 부분 수열 LIS(Longest Incresing Sequence) 본론에 들어가기 앞서 작성자는 기존의 LIS를 구하는 법을 알려주던 블로그에서 알려주지 않았던 내용에 대해 한 번 데고 분노하여 직접 LIS에 대해 다루기로 했다. 평소였으면 이런 글에는 사족을 달지 않으나 어떤 문제에 대해 큰 충격을 받고 잠을 설쳤기에 블로그에서라도 하소연을 하고 싶었다. 어찌 되었든 이 게시글은 읽는 사람이 어느 정도 수준의 DP, lower bound, 세그먼트 트리, 펜윅 트리를 알고 있다고 가정하고 작성하였으며 LIS와 관련된 토픽을 내가 알고 있는 범위에서 방대하게 다룰 것이다. 물론 위에서 언급한 것들의 일부를 몰라도 되며, 모르는 것을 사용하는 때가 오면 잠시 건너뛰어도 될 것이다. 하지만 나와 같은 일을 겪으면 매우 억울할 것이니 모르는 토픽은 공부하고 와서 다시 이 글.. Shortest Path Faster Algorithm(SPFA) 이 게시글에서는 벨만 포드 알고리즘의 평균 시간 복잡도를 크게 개선한 SPFA의 구현법과 특징을 알아본다. SPFA의 사용 의의 SPFA의 시간 복잡도는 벨만 포드와 동일하게 $O(VE)$이지만 SPFA 저격 데이터가 없는 경우 $O(V + E)$의 성능을 낸다고 알려져 있다. 따라서 채점 데이터가 약하다고 추정되는 문제에서 최단 경로를 찾을 때는 SPFA의 사용을 고려할 수 있다. 단, 저격 데이터가 있는 경우 SPFA의 큐 사용에서 발생하는 상수 시간이 더 크기 때문에 벨만 포드보다 느린 퍼포먼스를 보여준다는 것을 유의해야 한다. SPFA는 MCMF의 구현에 많이 이용하므로 플로우와 관련된 알고리즘을 배우기 전에 꼭 숙지해야 하는 알고리즘이다. C++ 구현 SPFA는 큐를 이용해서 BFS와 유사하게 .. 이전 1 2 3 4 5 6 다음
