Week 07 알고리즘 공부 기록 [KMP, 이분 매칭, 최대 유량, 뫼비우스 함수]

 

12.16 ~ 12.22

 

KMP

이분 매칭 문제와 DFS 솔루션

최대 유량 문제와 BFS 솔루션 (에드몬드 카프)

뫼비우스 함수

 

6주차가 애매하게 어려워서 자꾸 그쪽만 파다보니 PS를 할 시간이 없었다면, 이번주는 정반대였다.

 

원래 뭔가 막히는 부분이 있으면 낭비하게 되는 시간이 싫어서 잠시 옆에 치워두고 다른 걸 손대는 편이다.

개인적으론 7주차 과제인 웹 서버가 지금까지중에 제일 어렵고 깊게 들어갔다고 생각하는데, 그래서인지 매일같이 알고리즘에 자꾸 손이 가서 오히려 문제를 푸는 시간이 더 많아지는 선순환? 같은 일이 벌어져서 결국 풀다보니 40문제 넘게 풀었다.

 

이번주에 다룬 주제는 크게 KMP, 이분매칭, 최대유량 이 셋인데, 이분 매칭은 세그먼트 트리처럼 일단 베이스만 이해해도 테크닉적인 부분만 조금씩 바꿔가며 풀 수 있는 문제가 줄줄이 나오다 보니 그것들을 계속 풀었다.

 

최대 유량을 이해하면 모든 이분 매칭 문제는 최대 유량 문제로 치환해서 풀 수 있는데, 그럼 이분 매칭을 해결하는 DFS를 안보고 넘어가게 될 것 같아서 최대 유량은 의도적으로 이분 매칭보다 나중에 봤다. 이분그래프의 두 집단 옆에 소스와 싱크 점만 찍으면 최대 유량 문제가 된다는 설명을 읽었을땐 진심으로 감탄했다. 이런걸 대체 어떻게 생각하는걸까ㅋㅋ

 

KMP는 4주차에 공부했던 suffix array와 마찬가지로 문자열의 탐색에 목적을 둔 알고리즘이라 쉽게 와닿았던 것 같다. KMP가 굴러가는 로직을 하나하나 친절하게 설명해준 페이지를 구글링으로 발견해서 거의 단박에 이해하고 구현으로 넘어갔는데, 정말 큰 도움이 됐다.

 

각각의 알고리즘에 대한 정리는 언제나처럼 "나중에" 할 계획인데, 이게 계속 밀리기만 하는 것 같다... 과제하다 막히면 알고리즘으로 넘어오고, 알고리즘도 영 안되거나 큰거 하나 해결했다 싶으면 그제서야 블로그에 정리를 하다보니 자주 손대지 않게 되는듯.

 

위로 계속 뚫다보니 드는 느낌이 있는데, 내 경우에는 CLASS 7까지는 자원을 투자하는 만큼 성과가 나올 것 같고 7과 8 사이의 어딘가에 큰 벽이 하나 있는 기분이 든다. 조만간 이 벽에 닿을텐데 그때가 되면 공부해왔던 것들을 다시 돌아보며 정리하는 시간을 자주 갖게 되지 않을까 싶다.