시간복잡도 : 입력값과 수행 시간의 상관관계
-Big-O : 최악의 경우
-Big-Ω: 최선의 경우
-Big-θ : 평균
주로 빅오를 사용한다.
코딩테스트에서는 주어진 데이터 크기 제한에 따라 목표로 하는 시간 복잡도를 예상할 수 있고, 그것과 같거나 그거보다 낮은 시간복잡도를 목표로 코드를 작성해야 한다.
탐욕 알고리즘Greedy Algorithm : 각 단계에서 가장 최선의 선택을 하는 방식으로 접근하는 알고리즘.
그리디 알고리즘이 항상 최적해를 보장하지는 않는다. 그리디 알고리즘을 적용하려면
1. 앞의 선택이 이후의 선택에 영향을 주지 않아야하고
2. 문제의 최적 해답은 부분 문제의 최적 해답으로 구성되어야 한다.
그리디 알고리즘은 최적에 '근사'한 값을 빠르게 도출할 수 있다.
구현
-시뮬레이션 : 모든 과정과 조건을 제시한다. 문제 해결은 쉬우나, 길고 자세해서 코드로 옮기는 과정이 까다롭다.
-완전 탐색Brute Force Algorithm : 무차별 적으로 모든 가능성을 시도하는 방법. 시간 복잡도가 관건.
동전 탐색 알고리즘
0, 1, 2, 5 원짜리 동전으로 10원을 만들어야 한다고 가정해보자.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
0원짜리로 각 금액을 만드는 경우의 수는 0원을 만들 때를 제외하고는 모두 0이다.
1원 짜리와 0원짜리를 사용해서 0원을 만드는 경우는
0(1원짜리를 사용했을 때 만들 수 없다) + 1(0원짜리를 사용했을 때) = 1이다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 6 |
2원을 만들 수 있는 경우의 수는
0원에 2원 짜리 1개 추가하여 만드는 경우 1,
1원 짜리로 만든 2원의 경우의 가짓수 1, 둘을 합하여 2이다.
3원을 만들 수 있는 경우의 수는
기존에 만든 1원을 만든 가짓수에 2원 짜리 동전 하나를 더한 경우 1가지,
1원짜리로 만든 3원의 가짓수 1가지를 합하여 2
즉, 2원으로 0 ~ 10 원을 만드는 가짓수를 저장하는 배열을 채우는 방법은,
answer[2][i] = answer[2][i - 2] + answer[1][i]
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 6 |
| 5 | 1 | 1 | 2 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 10 |
j번째 동전으로 만드는 방법은
answer[j][i] = answer[j][i - j.worth] + answer[j - 1][i]
