[코딩 테스트] - 다이나믹 프로그래밍

Jeonghwan Kim·2022년 11월 8일
다이나믹 프로그래밍코딩테스트
0

코딩 테스트

목록 보기
10/21

다이나믹 프로그래밍

  • 다이나믹 프로그래밍: 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

  • 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않음

  • 일반적으로 두 가지 방식(Top-down, Bottom-up)으로 구현됨

  • 동적 계획법이라고도 부름

  • 다이나믹 프로그래밍의 조건

    1. 최적 부분 구조 (Optimal Substructure)

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

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

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

  • 피보나치 수열 문제를 다이나믹 프로그래밍을 통해 효율적으로 해결할 수 있음

  • 메모이제이션(Memoization)

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

  • Top-down vs Bottom-up

    • Top-down(메모이제이션)은 하향식, Bottom-up은 상향식이라고도 함
    • 다이나믹 프로그래밍의 전형적힌 형태는 Bottom-up 방식
      • 결과 저장용 리스트는 DP 테이블이라고 부름
    • 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미
      • 메모이제이션은 다이나믹 프로그래밍에 국한된 개념이 아님, 한번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍에 활용하지 않을 수 있음

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

    • 모두 최적 부분 구조를 가질 때 사용 (큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황)
    • 차이점은 부분 문제의 중복 여부
      • 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨
      • 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않음

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

    • 문제가 다이나믹 프로그래밍 유형임을 파악
      • 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍 고려
      • 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 (Top-down) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드를 개선하는 방법을 사용할 수 있음
      • 일반적인 코딩테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제됨

다이나믹 프로그래밍 기초 문제 풀이

<문제> 개미 전사

  • 문제 해결 아이디어

    • ‘ai = i번째 식량창고까지의 최적의 해 (얻을 수 있는 식량의 최댓값)’ 으로 정의한다면 다이나믹 프로그래밍을 적용할 수 있음

    • 왼쪽부터 차례대로 식량창고를 턴다고 했을 때, 특정한 i번째 식량창고에 대해서 털지 안 털지의 여부를 결정하면, 2가지 경우 중 더 많은 식량을 털 수 있는 경우를 선택

    • ai = i번째 식량창고까지의 최적의 해 (얻을 수 있는 식량의 최댓값)

    • ki = i번째 식량창고에 있는 식량의 양

    • 점화식: ai = max(ai-1, ai-2 + ki)

      • 앞의 두 경우를 활용해서 현재 문제를 해결할 수 있다는 점에서 ‘최적 부분 구조’ 성립

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

    • 코드

      # 답안 예시

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

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

# 다이나믹 프로그래밍 진행 (Bottom-up)
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])

<문제> 1로 만들기

  • 문제 해결 아이디어

    • 함수가 호출되는 과정을 그림으로 그려보면 최적 부분 구조와 중복되는 부분 문제를 만족하는 것을 알 수 있음
    • 점화식: ai = i를 1로 만들기 위한 최소 연산 횟수
      • 단, 1을 빼는 연산을 제외하고는 해당 수로 나누어떨어질 때에 한해 점화식을 적용할 수 있음

  • 코드

    # 답안 예시

# 정수 X를 입력 받기
x = int(input())

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

# 다이나믹 프로그래밍 진행 (Bottom-up)
for i in range(2, x+1):
	# 현재의 수에서 1을 빼는 경우
	d[i] = d[i-1] + 1
	# 현재의 수가 2로 나누어 떨어지는 경우
	if i % 2 == 0:
		d[i] = min(d[i], d[i//2] + 1)
	# 현재의 수가 3으로 나누어 떨어지는 경우
	if i % 3 == 0:
		d[i] = min(d[i], d[i//3] + 1)
	# 현재의 수가 5로 나누어 떨어지는 경우
	if i % 5 == 0:
		d[i] = min(d[i], d[i//5] +1)

print(d[x])

<문제> 효율적인 화폐 구성

  • 문제 해결 아이디어
    • ai = 금액 i를 만들 수 있는 최소한의 화폐 개수
    • k = 각 화폐의 단위
    • 점화식: 각 화폐 단위인 k를 하나씩 확인하며
      • ai-k를 만드는 방법이 존재하는 경우: ai = min(ai, ai-k + 1)
      • ai-k를 만드는 방법이 존재하지 않는 경우: ai = INF(무한대 값)

  • N = 3, M = 7 이고, 각 화폐의 단위가 2, 3, 5인 경우

    • Step 0 (초기화)
      • 먼저 각 인덱스에 해당하는 값으로 INF(무한) 값 설정
      • INF는 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다는 의미
      • M이 10,000까지인 본 문제에서는 10,001 이상의 수 사용
      • 0원의 경우, 화폐를 하나도 사용하지 않았을 때 만들 수 있으므로 값 0 설정
    • Step 1 화폐 단위 2 확인
    • Step 2 화폐 단위 3 확인
    • Step 3 화폐 단위 5 확인

  • 코드

    # 정수 N,M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력받기
array = []
for i in range(n):
	array.append(int(input())

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍 진행 (바텀업)
d[0] = 0
for i in range(n):
	for j in range(array[i], m+1): # j는 금액을 의미
		if d[j - array[i]] != 10001: # (i-k) 원을 만드는 방법이 존재하는 경우
			d[j] = min(d[j], d[j-array[i]] + 1)
# 계산된 결과 출력
if d[m] = 10001: # 최종적으로 m원을 만드는 방법이 없는 경우
	print(-1)
else:
	print(d[m])

<문제> 금광

  • 문제 해결 아이디어
    • 금강의 모든 위치에 대하여 세 가지만 고려하면 됨
      1. 왼쪽 위에서 오는 경우
      2. 왼쪽 아래에서 오는 경우
      3. 왼쪽에서 오는 경우
    • 세 가지 경우 중 가장 많은 금을 가지고 있는 경우를 테이블에 갱신해주어 문제를 해결
  • 코드
    # Test Case 입력
for tc in range(int(input())):
	# 금광 정보 입력
	n, m = map(int, input().split())
	array = list(map(int, input().split()))
	# 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
	dp = []
	index = 0
	for i in range(n):
		dp.append(array[index:index+m])
	index += m
	# 다이나믹 프로그래밍 진행
	for j in range(1,m): # 열 기준 확인
		for i in range(n):
		# 왼쪽 위에서 오는 경우
		if i == 0: left_up = 0 # 인덱스를 벗어나면 해당 경로의 값을 0 으로 초기화
		else: left_up = dp[i-1][j-1]
		# 왼쪽 아래에서 오는 경우
		if i == n - 1: left down = 0 # 인덱스를 벗어나면 해당 경로의 값을 0 으로 초기화
		else: left down = dp[i+1][j-1]
		# 왼쪽에서 오는 경우
		left = dp[i][j-1]
		dp[i][j] = dp[i][j] + max(left_up, leftdown, left)
result = 0
for i in range(n):
	result = max(result, dp[i][m-1]
print(result)

<문제> 병사 배치하기

  • 문제 해결 아이디어

    • Long Increasing Subsequence(LIS, ‘가장 긴 증가하는 부분 수열’)로 알려진 전형적인 다이나믹 프로그래밍 문제의 아이디어로 해결
    • 예를 들어 수열 ‘array = (4,2,5,8,4,11,15}’ 가 있다고 할 때, 이 수열의 LIS는 {4,5,8,11,15}임
    • 해당 문제는 가장 긴 감소하는 부분 수열을 찾는 문제로 치환할 수 있으므로, LIS 알고리즘을 조금 수정하여 적용하여 답을 구함
    • LIS 알고리즘
      • D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이
      • 점화식
    • 가장 먼저 입력 받은 병사 정보의 순서를 뒤집고, LIS 알고리즘을 수행하여 답 도출함

  • 코드

    n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 'LIS' 문제로 변환
array.reverse()

# 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
dp = [1] * n

# LIS 알고리즘 수행
for i in range(1, n):
		for j in range(0, i):
			if array[j] < array[i]:
				dp[i] = max(dp[i], dp[j] + 1)

# 열외해야 하는 병사의 최소 수를 출력
print(n-max(dp))

참고: 이것이 취업을 위한 코딩 테스트다 with 파이썬 (취업과 이직을 결정하는 알고리즘 인터뷰 완벽 가이드), 유튜브 강의 영상

profile
Jeonghwan Kim
이전 포스트

[코딩 테스트] - 이진 탐색

다음 포스트

[코딩 테스트] - 다익스트라 최단 경로 알고리즘

0개의 댓글