1 분 소요

Intro

  • 유니티 엔진 공부부터해보자 라고 생각한지 벌써 1년이 넘었고, 이제는 미뤄두었던 코딩 공부를 다시 해야겠다는 생각이 들어 기초부터 다시 쌓아올려보고자 정리하는 글입니다.

  • 그 첫번째로는 다이나믹 프로그래밍(DP)입니다.

DP란?

  • DP(동적 계획법)라는 이름의 알고리즘은 하나의 큰 문제를 작은 문제로 나누어 해결하는 방식의 알고리즘입니다.

  • 분할정복 알고리즘의 방식과 유사하지만 단순히 큰 문제를 작게 나누어 해결하는것이 아닌, 작은 문제를 풀고난 그 결과를 저장해놓고 중복 계산자체를 없애버리는것이 DP 알고리즘입니다.

  • 중복된 연산을 저장하는 과정을 구현 방법에 따라 메모이제이션 혹인 테뷸레이션 이라고 합니다.

  • 변수사이의 관계식을 점화식, 이 점화식을 해결하기 위한 초기값을 기저값이라고 하는데, DP는 기저값을 설정해준 뒤, 점화식을 활용하여 캐시(Cashe)에서 값을 꺼내가며 문제를 해결해나갑니다.

DP 알고리즘 사용 조건

  1. Overlapping Subproblems(작은 문제들의 중복)
    • 큰 문제를 작게 나누었을 때, 작은 문제들에서 중복이 발생해야합니다.
    • 중복이 발생하는점에서 앞에서 말한 캐시에 저장한 데이터(작은문제의 답)로 큰 문제로 해결
    • 즉, 점화식을 활용해야합니다.
  2. Optimal Substructure(최적화된 작은 문제)
    • 작게 나눈 문제들의 결과들이 전체 문제의 최적의 답을 도출해야합니다.
    • 같은 문제에 대해 작게 나눈 문제들로 해결한 문제는 전체 문제에 대해 항상 같은 값을 도출해야합니다.

DP 구현 방법

  1. Top-Down (재귀, Memoization)
    • 큰 문제부터 시작하여 작은 문제를 재귀문을 통하여 해결하는 방식입니다.
    • Top-Down에서는 메모이제이션 방식의 캐싱을 이용하며, 이는 이미 계산된 값이 캐시에 있다면 꺼내 사용하는 방식입니다.

image

  1. Bottom-Up (반복문, Tabulation)
    • 작은 문제부터 큰 문제까지를 반복문을 통해 해결하는 방식입니다.
    • 캐싱방식을 테뷸레이션이라하며, 작은 값부터 캐시에 값을 채워나가는 방식입니다.

image

DP 문제 예시 - 2839번 설탕 배달

image

  1. 문제 이해하기
    • 타겟 Kg가 주어지고, 그 Kg을 정확하게 만족하는 3Kg, 5Kg 봉투의 최소갯수를 구하는 문제입니다.
    • 문제를 해결하는 방법은 여러가지겠지만 DP를 이용하여 해결하려합니다.
  2. 문제 해결하기
    • 18Kg을 3,5Kg 봉투에 담으려면 두가지 경우 (13Kg + 5Kg)과 (15Kg + 3Kg)가 있습니다.
    • 즉, 타겟 Kg을 담을 봉투의 최소갯수를 담는 배열 변수를 dp라고 한다면,
    • dp[target] = (dp[target - 3], dp[target - 5]) + 1 라는 점화식을 구할 수 있습니다.
  3. 코드로 옮기기 
     #include <iostream>
 #include <algorithm>

 using namespace std;

 int dp[5001];				

 int main(void)
 {
     int n;					
     cin >> n;							// 입력: 배달해야하는 목표Kg (3~5000Kg)

     // 문제의 점화식 구하기 : 목표 Kg을 맞추는 최소 봉지갯수 dp[i] = min(dp[i-3] + 1, dp[i-5] +1)
     // ex) 18kg = 15kg + 3kg or 13kg + 5kg 중에 더 최소인 경우를 고르면 된다.
	
     // 기저값 설정
     dp[3] = dp[5] = 1;					// 3kg과 5kg은 최소갯수가 1개
     dp[1] = dp[2] = dp[4] = 99999;		// 변별을 위한 쓰레기값 넣기

     for (int i = 6; i <= n; i++)
     {
     	dp[i] = min(dp[i - 3], dp[i - 5]) + 1;
     }

 	cout << ((dp[n] >= 99999) ? -1 : dp[n]);	// .. 불가능한 경우 -1 출력

     return 0;
 }

댓글남기기

참고