WEEK. 02 2022.04.22 TIL

다이나믹 프로그래밍

다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법.
이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함.
다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 바텀업)으로 구성됨.

다이나믹 프로그래밍은 동적 계획법이라고도 부르는데 자료구조에서 동적 할당은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미함.

문제가 특정 조건을 만족할 때 사용할 수 있음.
1. 최적 부분 구조(Optimal Substructure)

• 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음.

2. 중복되는 부분 문제 (Overlapping Subproblem)

• 동일한 작은 문제를 반복적으로 해결해야 함.

피보나치 수열 ( 1, 1, 2, 3, 5, 8, 13 ,,,,)

• 단순 재귀 소스코드

def fibo(x):
	if x == 1 or x == 2:
    	ruturn 1
    return fibo(x-1) + fibo(x-2)

피보나치 수열의 시간 복잡도 분석

• 단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가짐
• 다음과 같이 f(2)가 여러 번 호출되는 것을 확인할 수 있음(빅오 표기법 기준 f(30)을 계산하기 위해 약 10억 가량의 연산을 수행해야 함)
  

메모이제이션(Memoization)

• 메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 하나
• 한 번 계산한 결과를 메모리 공간에 메모하는 기법
  - 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴.
  • 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 합니다.

탑다운 vs 보텀업

• 탑다운 방식: 하향식
  큰 문제를 해결하기 위해 작은 문제들을 재귀적으로 호출하여 작은 문제들이 모두 해결되었을 떄 큰 문제도 해결될 수 있도록 코드를 작성하고, 한번 계산했던 값을 기록하기 위해 메모이제이션 기법을 사용함
• 보텀업 방식: 상향식
  아래쪽에서부터 작은 문제를 하나씩 해결해가면서 먼저 계산한 문제들의 값을 활용해서 다음 문제들을 계산하는 방식으로 반복문을 사용함)
• 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식임.
  - 결과 저장용 리스트는 DP 테이블이라고 부름
• 엄밀히 말하면 메모이제이션은 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미함.
  - 따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아님.
  • 한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수 있음.

피보나치 수열: 탑다운 다이나믹 프로그래밍 소스코드 (Python)

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
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) # 해당 피보나치 수열의 값을 인덱스 기준으로 저장함.
    return d[x]
    

피보나치 수열: 바텀업 다이나믹 프로그래밍 소스코드 (Python)

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수 반복문으로 구현
for i in range(3, n+1):
	d[i] = d[i-1] + d[i-2]

print(d[n])

다이나믹 프로그래밍 vs 분할 정복

• 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있음.
  - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황
• 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복
  - 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨.
  • 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않음.
• 예를 들어 퀵 정렬의 경우 피벗 값 기준으로 분할하면 피벗 값은 전체 배열의 중앙으로 위치하게 되고, 이 원소의 위치는 변하지 않음. 이처럼 한번 분할하고 난 후 해당 피벗 값은 위치가 변하지 않기 때문에 부분 문제가 중복되지 않음. 이러한 특징으로 인해 다이나믹 프로그래밍이 아닌 분할 정복으로 분류됨.

다이나믹 프로그래밍 문제에 접근하는 방법

• 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요함.
• 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토할 수 있음.
  - 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려해봄
• 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용할 수 있음
• 일반적인 코딩 테스트 수준에서는 기본 유형의 DP 문제가 출제되는 경우가 많음

개미 전사 - 개미전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

• 개미 전사가 메뚜기 마을 식량창고를 몰래 공격하려 하는데 메뚜기 마을에는 여러 개의 식량 창고가 있음. 식량창고는 일직선으로 이어져 있음.
• 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 빼앗을 예정.
• 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있음.
• 따라서, 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 함.

• i 번째 식량창고를 털지 안털지를 고려할 때 i-1번째 최적의 해와 i-2번째 최적의 해를 비교하여 결정한다라고 설명하는데 각각의 부분 문제의 최적의 해가 i-1번째와 i-2번째의 식량 창고를 털었다고 어떻게 확신하지? 예를 들어, i-1번째까지의 최적의 해가 i-1번째 식량 창고를 안터는 경우일수도 있는거 아닌가???

• i번째까지의 식량을 얻을 수 있는 최댓값은 앞 위치까지의 최적의 해와 두칸 앞까지의 최적의 해와 현재 식량 창고의 값을 더한 후에 더 큰 값을 고르면 됨.

• 큰 문제를 해결하기 위해 작은 부분 문제들을 해결해야 한다는 점에서 DP 문제 조건 충족함.

ai = i번째 식량창고까지의 최적의 해 (얻을 수 있는 식량의 최댓값)
k_i = i번째 식량창고에 있는 식량의 양
점화식 = a_i = max(a(i-1), a_(i-2)+k)

• 한 칸 이상 떨어진 식량창고는 항상 털 수 있으므로 (i-3)번째 이하는 고려할 필요 없음.

• 점화식을 보면 i번째 식량창고를 털지 안털지를 고려할 때, 인접 식량창고는 털 수가 없으므로 한 칸 이하의 최적의 값과 두 칸 이하의 최적의 값에서 i번째 식량창고의 양을 더한 값과 비교하는 것 같은데....그럼 자연스럽게 해당 칸의 식량창고를 안터는게 최적의 해가 될 수도 있는거 아닌가???

# 정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 다이나믹 프로그래밍 진행 (바텀업)
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
	d[i] = max(d[i-1], d[i-2] + array[i])
    
계산된 결과 출력
print(d[n-1])

흠... d[i-1]의 값과 d[i-2]+a[i] 값을 비교해서 더 큰 값으로 한다는게 아직 이해가 잘 안감...
i번째 식량을 털 수 있는 경우와 없는 경우를 비교해서 생각하면 간단한 문제인듯. i번째 식량을 털지 않는다고 가정을 하면 i-1번째의 최댓값이 최선일거고, i번째 식량을 턴다고 가정하면 인접 식량창고인 i-1번째 식량창고를 털지 못하기 때문에 이를 배제한 i-2번째의 최댓값에 현 식량창고의 식량을 더한 값이 최선이 될것임. 따라서, 최종적으로 i-1번째의 최댓값과 i-2번째 최댓값에 현재 식량창고의 식량을 더한 값 중에 큰 값이 i번째 식량창고의 맥시멈 식량 값이 되는 것. 헷갈렸던 i-1번째 및 i-2번째 맥시멈 식량 값을 고려할 때 해당 식량창고가 털렸는지 털리지 않았는지는 중요한 부분이 아니었음.

1로 만들기: 주어진 숫자를 1로 만들 수 있는 최소 연산의 수

• 정수 x에 사용할 수 있는 연산은 다음과 같이 4가지

1. x가 5로 나누어 떨어지면, 5로 나눔
2. x가 3으로 나누어 떨어지면, 3으로 나눔
3. x가 2로 나누어 떨어지면, 2로 나눔
4. x에서 1을 뺌

• ex) 26 - 25 - 5 - 1

• 최적 부분 구조와 중복되는 부분 문제를 만족한다는 예시
  - 예를 들어 6의 최소 연산 횟수를 계산한다고 했을 때, 6보다 작은 수에서 주어진 연산 조건을 만족할 수 있는 루트는 다음과 같음.
  • 6에서 3을 나눈 f(2), 6에서 2를 나눈 f(3), 6에서 1을 뺀 f(5), 즉, 각 루트의 횟수는 1로 동일하기 때문에 f(2), f(3), f(5) 중에서 최소 연산 횟수를 가지는 루트를 선택하면 되는 것.

1로 만들기: 문제 해결 아이디어

• a[i] = i를 1로 만들기 위한 최소 연산 횟수
• a[i] = min(a[i-1], a[i/2], a[i/3], a[i/5]) + 1
• 단, 1을 빼는 연산을 제외하고는 해당 수로 나누어떨어질 때에 한해 점화식을 사용 가능

효율적인 화폐 구성

• 화폐의 값을 M으로 만들기 위해 필요한 최소한의 화폐 개수를 구하는 것(화폐는 N 종류)

문제 해결 아이디어

• a[i] = 금액 i를 만들 수 있는 최소한의 화폐 개수
• k = 각 화폐의 단위
• 점화식: 각 화폐 단위인 k를 하나씩 확인하며
  - a[i-k]를 만드는 방법이 존재하는 경우, a[i] = min(a[i], a[i-k]+1)
  • a[i-k]를 만드는 방법이 존재하지 않는 경우, a[i] = INF
• 1부터의 DP 테이블에는 아직 만들 수 있는 방법이 없다는 의미로 모두 INF로 초기화 해줌