코드잇 알고리즘 강의를 수강하며 배운 것들을 적은 공간입니다.
1. 알고리즘 패러다임
1-1. Greedy(탐욕법)
💡 매 순간 현재 상황에서 최선의 선택을 하는 방법으로 최종 해답을 구하는 방법
그리디 알고리즘은 항상 최적해를 구할 수 있는 것은 아니며, 예외적인 경우에는 최적해가 아닌 해를 구할 수 있다. 따라서 그리디 알고리즘을 적용할 때에는 항상 예외적인 경우를 고려하여 검토해야 한다.
그리디 알고리즘은 빠르게 답을 구해야 할 경우, 혹은 최적의 답이 필요 없는(적당한 답만 필요한) 경우에 주로 사용한다.
💡 그리디 알고리즘이 최적의 해를 보장하는 조건(최적 부분 구조 + 탐욕적 선택 속성)
1. 최적 부분 구조: 부분 문제들의 최적의 답으로 기존 문제의 최적의 답을 구할 수 있다.
2. 탐욕적 선택 속성: 각 단계의 탐욕적 선택이 최종 답을 구하기 위한 최적의 선택이다.
e.g.) 거스름돈 문제(가장 적은 수의 동전으로 거스름돈을 줄 수 있는 경우 찾기 → 각 동전이 서로 배수로 이루어질 경우에만 최적해), 다익스트라 알고리즘(최단 경로를 구하는 알고리즘)
1-2. Brute Force(무차별 대입)
💡 가능한 모든 경우를 시도하면서 최적의 해답을 찾는 방법
문제가 커질수록 처리 시간이 급격히 증가하여 계산량이 많은 문제에서는 사용이 어렵기 때문에, Brute Force를 사용할 때는 가능한 경우의 수가 적은 문제나 최적해를 찾는 것이 굉장히 중요한 문제에 한하여 사용하는 것이 적절하다.
시간 제한이 있는 PS에서는 Brute Force로 문제를 해결하는 방법을 찾은 뒤, 시간 복잡도가 낮은 다른 알고리즘을 생각하는 방법으로 문제를 해결할 수 있다.
1-3. Divide and Conquer(분할 정복)
💡 큰 문제를 작은 문제로 나누고 해결한 후 결과를 조합하여 기존 문제를 해결하는 방식. 즉, Divide → Conquer → Combine의 단계를 거쳐 해답을 찾는 방법
문제가 너무 클 때 문제를 부분 문제로 나누고 각 부분 문제의 답을 이용해 기존 문제를 해결할 수 있다.
Divide and Conquer의 세 단계
- Divide: 큰 문제를 작은 부분 문제로 나눈다.
- Conquer: 각각의 부분 문제를 해결한다. 부분 문제를 해결하기 위해 알고리즘이 사용되며, 일반적으로 재귀적으로 구현된다.
- Combine: 부분 문제의 결과를 조합하여 원래 문제를 해결한다.
특징
- 문제를 더 작은 문제로 분할하여 해결하는 재귀적인 방식을 사용한다.
- 각각의 부분 문제는 독립적으로, 같은 방식으로 해결된다.
- 부분 문제의 해결 방법을 조합하여 전체 문제를 해결한다.
e.g.) 합병 정렬(merge sort), 퀵 정렬(quick sort), 이진 탐색(binery search) 등
1-4. Dynamic Programming(동적 계획법)
💡 최적 부분 구조와 중복되는 부분 문제가 있을 때 해답을 찾는 방법. 한 번 계산한 결과를 다시 활용하는 방식
동적 계획법의 두 가지 조건
- 최적 부분 구조 : 부분 문제의 최적의 답으로 기존 문제의 최적의 답을 구할 수 있다. (피보나치 수열, 최단 경로 문제)
- 중복되는 부분 문제(Ovelapping subproblem) : 부분 문제를 해결할 때 이미 계산한 값을 또 계산해야 한다.
💡 동적 계획법을 구현하는 두 가지 방법
- Memoization
- 재귀 기반 콜스택 사용으로, 스택 오버플로우 가능성이 있다
- 필요 없는 계산은 안해도 된다
- 하향식 접근 (Top-down Approach)
- Tabulation
- 반복문 기반으로 스택 오버플로우 가능성이 없다.
- 중간에 필요 없는 값까지 모두 계산해야 한다
- 상향식 접근 (Bottom-up Approach)
💡 Memoization으로 피보나치 수열 문제 해결하기
def fib_memo(n, cache):
if n in cache:
return cache[n]
if n == 1 or n == 2:
cache[n] = 1
return 1
else:
cache[n] = fib_memo(n-1, cache) + fib_memo(n-2, cache)
return cache[n]
def fib(n):
fib_cache = {}
return fib_memo(n, fib_cache)