루프 (for, while)속에서 조건이 충족될때까지 절차를 반복
병합 : 두 리스트를 합치는 알고리즘
개수에 따른 비용이 선형적으로 증가하므로 병합 알고리즘의 시간복잡도는 o(n)이다
멱집합 : 어떤 집합의 원소로 만들 수 있는 모든 부분집합의 집합
즉, 집합 s에 대해 s의 멱집합은 s의 모든 부분집합의 집합이다
입력항목이 하나 증가할때마다 필요한 연산이 배로 증가하는 알고리즘은 의 시간복잡도를 갖는 지수알고리즘이다
지수적 증가 :
재귀 : 어떤 함수가 자기 자신이나 자신의 복제본에 작업을 전파하는 것
'자기 자신'을 처리하는 문제를 다루 때 자연스럽게 작성
재귀알고리즘에는 기저가 존재
기저 : 입력데이터가 더이상 작아질수없는 경우
function fib(n){
if n <=2
return 1
return fib(n - 1) + fib(n - 2)
}
//fib함수 안에서 fib함수 호출
재귀알고리즘은 반복알고리즘에 비해 간결하다
답이 될 수 잇는 후보를 전부 조사하여 문제를 해결
무식하게 풀기는 시간복잡도가 이므로 비효율적
최선, 최적의 답은 아니지만 비슷한 건 찾을 수 있다
이전의 선택으로 절대 돌아가지 않는다
각단계마다 최선의 선택을 추구하되, 일단 선택하고 과거의 선택을 되돌아보지않는다
최적부분구조로 구성된 문제를 해결하기에 적합
최적부분구조 : 비슷한 형태의 더 작은 부분 문제로 나눌 수 있는 문제
리스트를 반으로 나누면 나누어진 각 리스트는 원래 문제의 부분정렬 문제가 된다
절반으로 나뉜 두 부분문제는 또 어떻게 정렬 ? 이들 또한 부분 부분 문제로 나누어 정렬하고 병합
리스트가 하나의 항목으로 이루어졌다는 것은 정렬이 되어있는 상태라는 의미
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가지 상품중에서 가치 있는것을 골라담기
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. 각 부분 문제에서 모든 분기의 상하한 범위를 비교합니다
역추척전략은 무식하게 풀기 전략에서 불필요한 탐색을 줄여줍니다
분기한정법은 상한과 하한을 추정할 수 잇는 문제의 답을 빠르게 구할수있게 해줍니다
최적해를 계산하는 비용을 감당할 수 없다면 발견법을 활용할 수 있습니다