알고리즘 문제 해결 전략 - 7장 분할 정복(Divide & Conquer)

분할 정복(Divide & Conquer)

주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산

※ 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것입니다.

※ 분할 정복은 많은 경우 같은 작업을 더 빠르게 처리해 줍니다.

1. 분할 정복을 사용하는 알고리즘 세 가지의 구성 요소

- 문제를 더 작은 문제로 분할하는 과정(divide)

- 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)

- 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)

ex1) 1부터 n까지의 합 속도 비교 (일반적인 재귀 호출 vs 분할 정복 vs 반복문)

if) n==1000

reference) 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략

알고리즘 문제 해결 전략 - 6장 무식하게 풀기(brute-force)

무식하게 풀기(brute-force)

- 완전 탐색(exhaustive search) : 가능한 방법을 전부 만들어 보는 알고리즘



1. 반복문

-  입력 개수가 적다면 간결하고 단순하지만 골라야 하는 원소의 수가 늘어날수록 코드가 길고 복잡해지는데다, 골아야 할 원소의 수가 입력에 따라 달라질 수 있는 경우에는 사용할 수 없다.

2. 재귀 함수(recursive function) 혹은 재귀 호출(recursion)

- 재귀 호출은 위와 같은 문제의 경우에 단순한 반복문보다 간결하고 유연한 코드를 작성할 수 있도록 해줍니다.

※ 기저 사례(base case)
모든 재귀 함수는 '더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 합니다. 쪼개지지 않는 가장 작은 작업들을 가리켜 기저 사례(base case)라고 합니다.


ex1) n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘
if) n==7, m==4

ex1-1) 반복문 이용









ex1-2) 재귀 함수 이용

ex2) 보글 게임: 주어진 칸에서 시작해서 특정 단어를 찾을 수 있는지 확인하는 문제






reference) 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략

알고리즘 문제 해결 전략 - 3장

• 정렬되지 않은 정수 배열에 중복 원소가 존재하는지 확인하는 함수

• [자주하는 실수] - < 연산자의 성질 (strict weak ordering)

1. a<a는 항상 거짓입니다. - 비반사성(irreflexivity)

2. a<b가 참이면 b<a는 거짓입니다. - 비대칭성(asymmetry)

3. a<b가 참이고 b<c가 참이면 a<c입니다. - 전이성(transitivity)

4. a<b와 b<a가 모두 거짓이면 a와 b는 같은 값으로 간주합니다. - 상등 관계의 전이성(transitivity of equivalence)

=> a와 b가 같고, b와 c가 같다면 a와 c도 같아야 합니다.

ex)

- 두 정수 집합의 포함 관계를 파악하는 잘못된 비교 함수

{1}, {2}, {2,3}

{1} < {2,3} false

{2} < {2,3} true

{1} < {2} false

{2} < {1} false

4번 성질에 의해 {1} = {2} 

{1} < {2, 3} false

{2, 3} < {1} false

4번 성질에 의해 {1} = {2,3}

{1} = {2} = {2,3} ?

- 두 정수 집합의 포함 관계를 파악하는 비교 함수

a와 b가 완전히 같은 경우를 제외하고는 어느 때도 두 집합이 같다고 판단하지 않는 것입니다. 우리가 원하는 조건이 성립하지 않는 두 집합에 대해서도 별도의 순서를 정해 줘야 합니다.

※ 사실 진부분집합 확인은 의미가 없다.

• [디버깅과 테스팅] - 스캐폴딩(scaffolding)

프로그램을 테스트할 때 유용하게 사용할 수 있는 기법

알고리즘 문제 해결에서 스캐폴딩은 코드의 정당성을 확인하거나 반례를 찾는데 유용하게 쓰입니다.

reference) 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략