목차
- 기본 아이디어
- 상수만큼 감소(일반적으로 한 개)
- 삽입 정렬, 그래프 탐색
- 순열, 부분집합
- 상수 계수만큼 감소
- 가짜 동전 문제, 루세 곱셈
- 가변 크기만큼 감소
- 결론
기본 아이디어
- 문제 인스턴스를 동일한 문제의 소규모 인스턴스로 축소하고 솔루션 확장
- 관계를 이용하는 것
- 문제의 주어진 예에 대한 해결책과 그 작은 예에 대한 해결책
- 작은 인스턴스를 해결한 다음 작은 인스턴스 솔루션을 확장해 원래 문제에 대한 솔루션을 얻음
- 하향식 또는 상향식 관계를 활용할 수 있음
- 하향식 읽기를 통해 자연스럽게 재귀적으로 구현이 가능
- 상향식은 일반적으로 반복적인 구현 사용 (증분적 접근법)
감소 및 정복의 3가지 주요 변형
- 하나씩 감소:
- 삽입 정렬
- 그래프 검색 알고리즘: DFS 및 BFS
- 위상 정렬
- 순열, 부분 집합 생성 알고리즘
- 상수 계수만큼 감소
- 이진 검색
- 가짜 동전 문제
- 곱셈알루스
- 요세푸스 문제
- 가변 크기 감소
- 유클리드 알고리즘
- 파티션별 선택
Decrease&Conquer v.s. Divide&Conquer
Decrease&Conquer
- 두 부분을 모두 해결할 필요는 없음
Divide&Conquer
- 많은 교과서는 감소와 정복 알고리즘을 분할과 정복 알고리즘 중 하나로 분류함
Decrease by One: Insertion Sort
- 삽입 정렬
- n개 요소를 정렬하는 알고리즘:
- 배열의 n-1 요소 정렬
- n번째 요소를 삽입함
- 복잡성: 최악의 경우 Θ(n^2),
평균적인 경우 Θ(n^2),
거의 정렬된 배열에서는 Θ(n).
Graph
- 주어진 그래프 G = (V,E)
- 방향이 지정되어 있을 수도 없을 수도 있음
- 알고리즘을 표현하는 두 가지 일반적인 방법
- 인접 목록 (Adjacency lists)
- 인접 행렬 (Adjacency matrix)
- 알고리즘의 실행시간을 표현하는 것은 종종 |V|와 |E| 모든 측면에서 함
- 점근 표기법에서만 사용함
- 카디널리티(집합의 크기)를 포기할 것임
- ex) O(V+E)
Adjacency lists
- |V| 목록의 배열 조정(정점당 하나씩).
- 꼭짓점 u의 목록은 (u, v) ∈ E와 같은 모든 꼭짓점 v를 가짐
- 방향 그래프와 방향 없는 그래프 모두에서 작동함
- ex) 방향이 없는 그래프의 경우:
- 가장자리에 가중치가 있는 경우 목록에 가중치를 넣을 수 있음
- ex) Directed Graph
Adjacency matrix
- 가중 그래프의 비트 대신 가중치를 저장할 수 있음
Decrease by one: Graph Search
- DFS & BFS
- DFS 및 BFS의 복잡성: Θ(V^ 2)
- 인접 테이블로 표시되는 경우, 인접 목록으로 표시되는 경우: Θ(|V| + |E|)
- AI 문제 및 그래프 문제의 다양한 응용 프로그램
- ex) 주기 찾기, 관절 지점'
