1. 문제 해결 접근 전략 / 알고리즘 설계 기법 (패러다임) (Algorithm Design Paradigm)
ㅇ 문제를 해결하는 과정에서,
- 어떤 전략과 접근방식으로,
- 그 해법을 찾아가야 하는지에 대한,
- 다양한 방법론/해결법들을 다룸
2. 문제 해결 접근 전략의 분류
ㅇ 무작위 대입 기법 (Brute Force Technique)
ㅇ 분할 정복법
ㅇ 욕심쟁이 방법
ㅇ 동적 계획법
ㅇ 백트래킹 등
※ 문제를 풀 때, 위 각각의 방법론(전략)에 따라,
- 문제를 푸는 독특한 해결 단계/해법 절차를 알고리즘 이라고 함
3. 무작위 대입 기법, 억지 기법 (Brute Force Technique)
ㅇ 단순하고 고지식하지만, 광범위한 문제에 적용 가능한 알고리즘 설계 기법
- 입력 크기가 작은 경우, 오히려 충분히 빠를 수 있음
- 타 효율적인 알고리즘 설계 및 분석의 이론적 기반이 됨
4. 분할 정복/분할 통치 (Divide and Conquer) 전략
ㅇ 풀이 방식
- 문제를 작은 문제로 나눠 순환적으로 푸는 하향식 접근 방식
- 다만, 문제의 해를 구할 때는 상향적으로 구해짐
- 결국, 각 순환 마다, 분할,정복,결합의 단계를 거침
ㅇ 특징
- 분할된 작은 문제들이 항상 독립적이므로, 한번 사용한 소문제의 해는 더이상 필요치 않음
ㅇ 적용 例)
- 이진 탐색, 퀵 정렬, 합병 정렬
- 선택 문제 (최대값/최소값 찾기, n번째 작은 원소 찾기 문제 등)
- 선형 시스템 풀기, 함수의 근 찾기, 보간법, 수치 적분 등
5. 동적 계획법 (Dynamic Programming, 다이내믹 프로그래밍) 전략
ㅇ 풀이 방식
- 아래에서 위로 해결하면서 전체 문제를 해결하는 상향식 접근 방식
. 간단한 하위 문제부터 해결하면서,
. 하위 문제의 해를 테이블에 저장해 놓고,
. 이를 이용하여, 좀더 복잡한 상위 문제를 해결하여 나아감
ㅇ 특징
- 소문제 해들을 저장해놓고 큰문제 해를 구하는, 점진적 상향식 접근 방법
- 주로, 최대/최소값을 구하는 최적화 문제에 사용
ㅇ 적용 例) 최단경로 알고리즘 (플로이드 알고리즘, 벨만 포드 알고리즘) 등
6. 탐욕 알고리즘, 욕심쟁이 알고리즘 (Greedy Algorithm) 전략
ㅇ 풀이 방식
- 그때그때 가장좋은 해결핵을 찾아가는 기법
. 해를 구하는 일련의 선택 과정 마다,
. 가장 좋아보이는 최선을 선택하면, 전체적으로 최적 해를 구할 수 있다는 방법론으로,
. 각 단계 마다 최상으로 보이는 해결책으로 구한 해들을 모아 제시하게 됨
ㅇ 특징
- 항상 소문제 마다 단일 최적해 만을 고려하므로, 전체적인 최적해를 구한다는 보장 없음
- 따라서, 최적 해를 얻는지 확인하는 절차 필요
- 주로, 최대/최소값을 구하는 최적화 문제에 사용
ㅇ 적용 例)
- 동전 거스름돈을 가장 적은 수의 동전으로 주는 문제
- 최단경로 알고리즘 (다익스트라 알고리즘)
- 최소비용 신장트리를 구하는 알고리즘 (크루스칼 알고리즘, 프림 알고리즘) 등
7. 백트래킹 (Backtracking, 되추적) 방법
ㅇ 문제 풀이의 막다른 곳에 다다르면, 호출한 함수로 되돌려 나아가는 방법
ㅇ 특징
- 해를 구할 때까지 모든 가능성을 시도 함
- 갈 수 있는데까지 가보다가 막히면 (더이상 찾던 해가 없으면),
. 되돌아와서 다른 길을 찾아봄
- 되추적을 통해 탐색 대상을 줄여나감
. 되추적이 발생하면, 해당 서브트리들은 탐색대상에서 제외됨
- 주로, 그래프(상태 공간 트리)에 대해 DFS(깊이우선탐색)으로 탐색하며,
. 재귀적으로 구현됨
- 문제가 커질 경우 엄청난 시간이 걸리므로,
. 분기한정법(Branch-and-Bound) 등 탐색 범위를 줄이는 여러 보완을 취함
ㅇ 적용 例) 최적화 문제, 판정 문제 등
8. NP 문제 (NP, Nondeterministic Polynomial Problem), NP 완비 문제 (NP-complete)
ㅇ 아직까지, 다항식 시간 O(nk) 내에,
- 해결 가능한 최적 알고리즘을 찾지 못하였으며,
- 그같은 최적 알고리즘의 존재 여부도 증명을 못하는 경우가 있음
ㅇ 사실상, 꽤 많은 문제가 이같은 성질을 함께 갖음
ㅇ 그러나, 만일 이같은 문제들 중 하나라도 다항식 시간 O(nk) 내에,
- 해결 가능한 알고리즘이 존재하면,
ㅇ 그렇다면, 나머지 모든 문제도,
- 다항식 시간 O(nk) 내에 해결 가능 하다는, 논리적 연결 체계를 갖음
ㅇ 결국, 비결정론적 다항식 시간 내 해결 가능하다고, 확인할 수 있는 문제들을 말함
ㅇ 적용 例) 외판원 문제 (traveling-saleman problem, TSP 문제) 등