분할정복·탐욕법·동적계획법이 뭐예요?
분할정복·탐욕법·동적계획법을, 학생회가 동아리 스무 곳의 축제 예산을 세 가지 서로 다른 방법으로 배정하는 이야기로 풀어봤어요. (알고리즘 설계 기법이라 법·제도와는 결이 다르지만, 학생회도 복잡한 결정을 명확한 절차로 풀어요.)
동아리 스무 곳의 축제 예산을 한 번에 정하기엔 너무 복잡해요.동아리가 너무 많아 한 번에 다 비교할 수가 없어요.
접수 순서대로만 예산을 주면 불합리해요.접수 순서로만 나누면 더 공정한 배분을 놓쳐요.
큰 문제를 푸는 방법은 분할정복·탐욕법·동적계획법, 세 가지예요.학생회도 복잡한 결정을 내릴 땐 명확한 절차를 따라야 해요, 알고리즘처럼.
세 방법을 축제 예산에 적용하면 나누는 방식·고르는 순서·계산 횟수가 달라져요.문제를 쪼갤 수 있는지, 같은 계산이 반복되는지에 따라 어울리는 방법이 달라요.
탐욕법은 모든 조합을 따지지 않아 빠르지만, 늘 최선은 아니에요.탐욕법은 빠르지만, 매번 전체 최선을 보장하진 않아요.
분할정복은 문제를 쪼개서 합치고, 탐욕법은 매번 당장 최선을 고르고, 동적계획법은 이미 푼 답을 기억해 다시 안 풀어요.
분할정복은 문제를 독립된 작은 부분 문제로 나눠 각각 해결한 뒤 결과를 합치는 전략이에요(병합정렬 등). 탐욕법은 전체 최적을 고려하지 않고 매 단계 가장 좋아 보이는 선택을 반복하는 전략으로, 빠르지만 항상 전역 최적을 보장하진 않아요(최소신장트리 등 일부 문제에서는 보장돼요). 동적계획법은 부분 문제들이 겹칠 때 한 번 계산한 결과를 저장해두고(메모이제이션) 재사용함으로써 중복 계산을 피해요(최적부분구조와 중복부분문제가 있는 문제에 적합). 세 전략 모두 큰 문제를 더 작은 단위로 다루지만, 쪼갠 조각을 다루는 방식이 서로 달라요.
어른들은 이렇게 불러요
- 분할정복
Divide and Conquer - 문제를 쪼개 따로 풀고 합치는 전략. 정렬에서 실제로 쓰이는 예시가 있어요. → 크기 순서로 차를 세우는 여러 방법
- 탐욕법
Greedy Algorithm - 매번 지금 가장 좋아 보이는 것을 고르는 전략. 모든 지점을 가장 싸게 잇는 문제에서는 탐욕법이 최선을 보장해요. → 가장 싼 배관만 골라 모든 지점 잇기
- 동적계획법
Dynamic Programming - 이미 푼 답을 기억해두고 재사용하는 전략. 같은 부분 문제를 두 번 풀지 않아요.
- 메모이제이션
Memoization - 한 번 계산한 결과를 저장해두는 기법. 동적계획법을 구현하는 대표적인 방법이에요.
- 최적부분구조
Optimal Substructure - 부분 문제의 최적 답을 모으면 전체 최적이 되는 성질. 동적계획법이 통하려면 이 성질이 있어야 해요.
- 중복부분문제
Overlapping Subproblems - 똑같은 작은 문제가 여러 번 반복해서 나오는 것. 같은 문제가 반복돼야 메모이제이션이 효과가 있어요.
- 백트래킹
Backtracking - 가다가 막히면 되돌아가 다른 길을 찾는 방법. 또 다른 큰 문제 풀이 전략이에요.
- 시간복잡도(Big-O)
Time Complexity (Big-O) - 문제가 커질 때 얼마나 느려지는지 재는 자. 세 방법 모두 이 자로 빠르기를 비교해요. → 차가 많아질 때 얼마나 느려질까