[Day3-5] 알고리즘 설계 패러다임

완전탐색

: 모든 경우의 수를 다 따져보고 찾음

: brute force

재귀함수

: 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각 수행하고 나머지를 자기 자신 호출 후 수행

기저사례

: 쪼개지지 않는 가장 작은 작업들

* 입력이 잘못되거나 범위에서 벗어난 경우도 기저사례로 택하기

분할정복

: 각개격파

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

: 반복할수록 기저사례에 도달하기까지 걸리는 분할횟수가 줄어들기 때문에 가능한 한 절반에 가깝게 문제를 나누고자 한다.

효율 저하: 부분문제가 중복된다 (여러번 중복되어 계산되면서 시간을 소모하는 부분 문제 존재) -> 동적계획법 고안

재귀: 문제를 한 조각 / 나머지로 나눔

분할정복: 거의 같은 크기의 부분문제로 나눔

- devide : 문제를 더 작은 문제로 분할

- merge : 각 문제에 대한 답을 원래 문제에 대한 답으로 병합

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

Merge Sort : 수열을 가운데에서 쪼개 비슷한 크기의 수열 두개 만들어서 재귀호출 이용, 각각 정렬 후 합침

Quick Sort : 한 쪽의 배열에 포함된 수가 다른 쪽 배열의 수보다 항상 작도록 배열분할

- 파티션: 기준수(pivot) 정해서 기준보다 같거나 작으면 왼쪽, 크면 오른쪽

Merge : 시간이 많이 걸리는 작업을 병합 단계에서 함

Quick : 시간이 많이 걸리는 작업을 분할 단계에서 함

 

동적계획법 Dynamic Programming

: 분할정복과 같은 접근방식 But, 문제를 나누는 방식이 다르다.

이미 계산한 값을 저장할 cache 공간이 필요

두번 이상 계산되는 부분문제 : 중복되는 부분문제 (overlapping subproblems)

조합폭발: 계산의 중복횟수가 깊어질수록 지수적으로 증가

 

이항계수의 계산

: n개의 서로 다른 원소 중 r개의 원소를 순서없이 골라내는 방법의 수

 

1. 주어진 문제를 완전 탐색을 이용해 해결

2. 중복된 부분문제를 한번만 계산하도록 메모이제이션 적용

 

경우의 수 계산하기

1. 모든 답을 직접 만들어서 세어보는 완전탐색 알고리즘 설계

- 재귀호출의 각 단계에서 고르는 각 선택지에 다음 두가지가 포함되어야 함

a) 모든 경우는 이 선택지들에 포함

b) 어떤 경우도 두 개 이상의 선택지에 포함되지 않음

2. 최적화 문제를 해결할 때처럼 이전 조각에서 결정한 요소들에 대한 입력을 없애거나 변형해서 줄인다.

- 재귀함수는 앞으로 남아있는 조각들을 고르는 경우의 수만을 반환해야 한다.

3. 메모이제이션 사용