1. 그리디
그리디 : 현재 상황에서 지금 당장 좋은 것만 선택
국내 알고리즘 교재에서 단어 그대로 번역하여 탐욕법이라고 소개됨. 여기서 탐욕적이라는 말을 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음.
거스름돈 500, 100, 50, 10원 동전
거슬러 줘야 할 돈이 n원일 때, 동전의 최소 개수를 구하라.
단, 거슬러 줘야 할 돈 n은 항상 10의 배수
2. DP (Dynamic Programming - 동적 계획법)
2- 트리의 개요
다이나믹 프로그래밍 : 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법
다이나믹 프로그래밍을 사용할 수 있는 조건
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
피보나치 수열은 위의 조건을 만족하는 대표 문제로 메모이제이션을 사용하여 해결이 가능함
- 메모이제이션(Memoization) : 다이나믹 프로그래밍을 구현하는 방법 중 하나로,
한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미. 캐싱(Caching)이라고도 함
HOW?
한 번 구한 정보를 리스트에 저장하고, 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 리스트에서 정보를 가져오면 된다.
피보나치 수열 소스코드 (재귀적)
# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
# 종료 조건(1 혹은 2일 때 1을 반환)
if x == 1 or x == 2:
return 1
# 이미 계산한 적 있는 문제라면 그대로 반환
if d[x] != 0:
return d[x]
# 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
d[x] = fibo(x - 1) + fibo(x - 2)
reutrn d[x]
print(fibo(99))
Happy Hacking!