07 28 - nolsigan/nolsigan.github.io GitHub Wiki

Algorithm

분할 정복

가장 유명한 알고리즘 디자인 패러다임, 한 마디로 설명하면 각개 격파!

총 3단계로 알고리즘을 정의할 수 있다.

1. 문제를 더 작은 문제로 분할하는 과정 (divide)
2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합 (merge)
3. 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (base case)

시간복잡도는 divide, merge에 지배적이다.

ex ) merge sort, quick sort, 카라츠바의 빠른 곱셈 알고리즘

문제 풀이 팁

string이나 배열을 다루며 재귀 호출을 통해 문제를 해결하려 할 때, 함수에 필요한 범위만큼 잘라 인자로 넣는 방법도 있지만
그보다 iterator를 사용해 필요한 만큼 가져다 쓰면 깔끔하게 코드를 작성할 수 있다.

Thread나 process 기반 concurrency issue가 없기 때문에 재귀 호출을 하더라도 iterator는 하나씩 전진한다는 사실을 기억하자.