3장 : 문제 해결 전략

반복전략

루프 (for, while)속에서 조건이 충족될때까지 절차를 반복
병합 : 두 리스트를 합치는 알고리즘
개수에 따른 비용이 선형적으로 증가하므로 병합 알고리즘의 시간복잡도는 o(n)이다

중첩 루프와 멱집합

멱집합 : 어떤 집합의 원소로 만들 수 있는 모든 부분집합의 집합
즉, 집합 s에 대해 s의 멱집합은 s의 모든 부분집합의 집합이다

입력항목이 하나 증가할때마다 필요한 연산이 배로 증가하는 알고리즘은 $o(2^n)$의 시간복잡도를 갖는 지수알고리즘이다
지수적 증가 : $(2^k+1 = 2x2^k)$

재귀를 이용해 반복하기

재귀 : 어떤 함수가 자기 자신이나 자신의 복제본에 작업을 전파하는 것
'자기 자신'을 처리하는 문제를 다루 때 자연스럽게 작성
재귀알고리즘에는 기저가 존재
기저 : 입력데이터가 더이상 작아질수없는 경우

function fib(n){
	if n <=2
    	return 1
    return fib(n - 1) + fib(n - 2)
} 
//fib함수 안에서 fib함수 호출

재귀와 반복의 비교

재귀알고리즘은 반복알고리즘에 비해 간결하다

무식하게 풀기 : 모든 후보 검사하기

답이 될 수 잇는 후보를 전부 조사하여 문제를 해결
무식하게 풀기는 시간복잡도가 $o(n^2)$이므로 비효율적

발견법 : 정답에 가까운 답 구하기

최선, 최적의 답은 아니지만 비슷한 건 찾을 수 있다

탐욕법

이전의 선택으로 절대 돌아가지 않는다
각단계마다 최선의 선택을 추구하되, 일단 선택하고 과거의 선택을 되돌아보지않는다

분할정복 : 더 작은 문제로 나누어 풀기

최적부분구조로 구성된 문제를 해결하기에 적합
최적부분구조 : 비슷한 형태의 더 작은 부분 문제로 나눌 수 있는 문제

분할정렬

리스트를 반으로 나누면 나누어진 각 리스트는 원래 문제의 부분정렬 문제가 된다
절반으로 나뉜 두 부분문제는 또 어떻게 정렬 ? 이들 또한 부분 부분 문제로 나누어 정렬하고 병합
리스트가 하나의 항목으로 이루어졌다는 것은 정렬이 되어있는 상태라는 의미

function merge_sort(list)
if list.length = 1
	return list
left ← list.first_half
right ← list.last_half
return merge(merge_sort(left),
			 merge_sort(right))

재귀알고리즘 = 병합정렬

분할 정복으로 배낭 문제 풀기

n가지 상품중에서 가치 있는것을 골라담기

• $w_i$ = i번째 상품의 무게
• $v_i$ = i번째 상품의 가치
  i = 상품의 번호
  c = 배낭의 용량
  $k(n,c)$ = 배낭에 n가지의 상품중 골라 담을 수 있는 최대 가치

1. $K(n,c)$ : 새 상품이 선택되지 않는 경우
2. $k(n, c-w_n+1)$ : 새 상품이 선택되는 경우

1은 새 상품을 무시 2는 기존 상품을 담을때 새 상품을 담을 만큼의 용량을 남겨야한다

동적계획법 : 계산 결과를 기억하며 풀기

동일한 연산이 여러차례 수행되는 경우, 동적 계획법을 활용하면 반복되는 부분 문제를 실별하여 이들을 한번만 처리

피보나치 수열

계산 결과가 저장되어있다면 그 값을 꺼내 반환하고 없을때만 계산을 수행한 후에 저장하고 반환
부분 계산 결과를 저장해 두었다가 재사용하는것을 메모제이션이라고 한다

M ← [1 → 1; 2 → 2]
function dfib(n)
	if n not in M
    	M[n] ← dfib(n-1) + dfib(n-2)
    return M[n]

대체 뭔말이지

상향식 최적 거래

입력데이터에서 최댓값과 최솟값을 탐색
그 후에 데이터를 절반으로 나누어 재귀호출에 넘기면, 재귀 호출에서는 분할된 데이터에서 또 다시 최댓값과 최솟값을 탐색,,, 탐색반복
기저사례들을 먼저 계산한 뒤 부분 계산 결과들이 최종 정답에 도달할 때 까지 조합해나가는 상향식 접근법으로 풀 수 잇다

분기한정법

어떤 값을 최소화하거나 최대화하는 문제 (ex)최단경로탐색, 이윤 최대화)
최적화 문제에서 구하려는 답이 선택의 연속일때 자주 활용

상한과 하한

어떤 값의 범위를 지정하는 것을 한정이라고 한다

• 상한 : 최대치를 한정
• 하한 : 최소치를 한정

cf) 두 지점 사이를 잇는 경로는 두 지점 사이의 직선 거리보다 짧을 수 없다
=>그러므로 두 지점 사이의 거리는 최단거리의 하한이 된다

분기한정법으로 배낭문제 풀기

분기한정법의 원리
1. 문제를 여러개의 부분 문제로 나눕니다
2. 각 부분 문제의 상한과 하한을 구합니다
3. 각 부분 문제에서 모든 분기의 상하한 범위를 비교합니다

역추척전략은 무식하게 풀기 전략에서 불필요한 탐색을 줄여줍니다
분기한정법은 상한과 하한을 추정할 수 잇는 문제의 답을 빠르게 구할수있게 해줍니다
최적해를 계산하는 비용을 감당할 수 없다면 발견법을 활용할 수 있습니다