17 동적 계획법

공부하는 감자·2024년 5월 28일
0

코딩 테스트

목록 보기
17/17

『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.

동적 계획법 (Dynamic Programming)

사실 모든 알고리즘 문제들은 완전 탐색을 이용해 정답을 도출할 수 있다. 단지 비효율적인 연산과 시간을 없애고, 답을 효율적으로 도출하기 위해 여러 알고리즘 기법이 생긴 것이다.

  • 동적 계획법(DP)은 가장 광범위한 여러 유형의 문제를 논리적인 사고를 이용해 효율적으로 풀 수 있는 알고리즘이다.
  • 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법이다.

핵심 이론

원리와 구현 방식

  1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
  2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.
  3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다.
    • 이를 메모이제이션(Memoization) 기법이라고 한다.
  4. 동적 계획법은 Top-down 방식과 Bottom-up 방식으로 구현할 수 있다.

피보나치 수열

동적 계획법의 가장 대표적인 문제이다.

  • 피보나치 수열의 공식은 다음과 같다.
D[N]=D[N1]+D[N2]D[N]=D[N-1]+D[N-2]
  1. 동적 계획법으로 풀 수 있는지 확인하기

    • N번째 피보나치 수열은 N-1번째 피보나치 수열과 N-2번째 피보나치 수열의 합이다.
    • 즉, N번째 피보나치 수열을 구하는 문제는 N-1번째 피보나치 수열과 N-2번째 피보나치 수열을 구하는 작은 문제로 나눌 수 있다.
    • 수열의 값은 항상 같다.
    • 따라서 동적 계획법으로 풀 수 있다.
  2. 점화식 세우기

    • 점화식을 세울 때는 논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악하는 훈련이 필요하다.
    • 피보나치 수열의 점화식은 D[i]=D[i1]+D[i2]D[i]=D[i-1]+D[i-2]이 된다.
  3. 메모이제이션 원리 이해하기

    • 메모이제이션은 부분 문제를 풀었을 때 이 문제를 DP 테이블에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산하지 않고 DP 테이블의 값을 이용하는 것을 말한다.
    • 피보나치 수열은 맨 왼쪽 탐색 부분에서 최초로 값이 구해지고, 이때 DP 테이블에 값이 저장된다. 나중에 앞의 피보나치 수열의 값이 필요할 때 재연산을 이용해 구하지 않고, DP 테이블에서 바로 값을 추출한다.
    • 이러한 방식을 사용하면 불필요한 연산과 탐색이 줄어들어 시간 복잡도 측변에서 많은 이점을 가질 수 있다.
  4. 톱-다운 구현 방식 이해하기

    • 말 그대로 위에서부터 문제를 파악해 내려오는 방식으로, 주로 재귀 함수를 사용해 코드를 구현한다.
    • 코드의 가독성이 좋고, 이해하기가 편하다는 장점이 있다.
    • 재귀의 깊이가 매우 깊어질 경우 런타임 에러가 발생할 수 있다.
    /**
    * Top-down 방식의 피보나치 수열
    */
    
    static int[] D;
    public static void main(String[] args) {
    	
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	
    	D = new int[n+1];
    	for(int i=0; i<=n; i++) {
    		D[i] = -1;
    	}
    	
    	D[0] = 0;
    	D[1] = 1;
    	fibo(n);
    	
    	System.out.println(D[n]);
    }
    
    static int fibo(int n) {
    	// 기존에 계산한 적이 있는 부분의 문제일 경우
    	if (D[n] != -1) {
    		return D[n];
    	}
    	// 메모이제이션: 구한 값을 바로 리턴하지 않고
    	// DP 테이블에 저장한 후 리턴하도록 구현
    	return D[n] = fibo(n-2) + fibo(n-1);
    }
  5. 바텀-업 구현 방식 이해하기

    • 가장 작은 부분 문제부터 문제를 해결하면서 점점 큰 문제로 확장해 나가는 방식이다.
    • 주로 반복문의 형태로 구현한다.
    • 톱-다운 방식보다는 바텀-업 방식이 좀 더 안전한 방식이다.
    /**
    * Bottom-up 방식의 피보나치 수열
    */
    
    static int[] D;
    public static void main(String[] args) {
    	
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	
    	D = new int[n+1];
    	for(int i=0; i<=n; i++) {
    		D[i] = -1;
    	}
    	
    	D[0] = 0;
    	D[1] = 1;
    	for(int i=2; i<=n; i++) {
    		D[i] = D[i-1]+D[i-2];
    	}
    	
    	System.out.println(D[n]);
    }
    
    static int fibo(int n) {
    	// 기존에 계산한 적이 있는 부분의 문제일 경우
    	if (D[n] != -1) {
    		return D[n];
    	}
    	// 메모이제이션: 구한 값을 바로 리턴하지 않고
    	// DP 테이블에 저장한 후 리턴하도록 구현
    	return D[n] = fibo(n-2) + fibo(n-1);
    }

Reference

[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런

profile
책을 읽거나 강의를 들으며 공부한 내용을 정리합니다. 가끔 개발하는데 있었던 이슈도 올립니다.

0개의 댓글