[항해99 취업리부트 TIL] 4주차 3일

학습한 내용은 무엇인가요?

동적 프로그래밍(DP) 알고리즘 개요

• DP는 문제를 작은 하위 문제로 나누어 해결한 후 그 결과를 결합하여 원래 문제를 해결하는 기법이다.
• 두 가지 특징:
  • 중복되는 하위 문제
  • 최적 부분 구조
• 구현 방식:
  • 탑다운(메모이제이션)
  • 바텀업(테이블화)

피보나치 수열

• 피보나치 수열은 DP의 대표적인 예제이다.
• 점화식: F(n) = F(n-1) + F(n-2)
• 초기 조건: F(0) = 0, F(1) = 1

탑다운 방식

• 재귀와 메모이제이션을 이용해 구현.
• 중복 계산을 피하기 위해 이미 계산된 결과를 저장.

1. int[] memo = new int[n + 1]; 배열을 -1로 초기화.
2. fib(n, memo) 함수 호출:
   • if (n <= 1) return n;
   • if (memo[n] != -1) return memo[n];
   • memo[n] = fib(n - 1, memo) + fib(n - 2, memo);

바텀업 방식

• 반복문을 이용해 작은 문제부터 차례대로 해결.

1. int[] dp = new int[n + 1]; 배열 초기화.
2. dp[0] = 0; dp[1] = 1;
3. 반복문을 통해 dp[i] = dp[i - 1] + dp[i - 2]; 계산.

0/1 배낭 문제

• 주어진 물건들을 배낭에 넣을지 말지 결정하여 최대 가치를 얻는 문제.
• DP 테이블을 이용해 해결.

1. int[][] dp = new int[n + 1][W + 1]; 배열 초기화.
2. 두 개의 중첩 반복문을 통해 DP 테이블 채움:
   • if (weights[i - 1] <= w) dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
   • else dp[i][w] = dp[i - 1][w];

가장 긴 증가하는 부분 수열 (LIS)

• 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾는 문제.
• DP를 이용하여 해결.

1. int[] dp = new int[N]; 배열을 1로 초기화.
2. 두 개의 중첩 반복문을 통해 LIS 계산:
   • if (A[i] > A[j]) dp[i] = Math.max(dp[i], dp[j] + 1);

이를 통해 얻은 인사이트

동적 프로그래밍의 중요성

• DP는 복잡한 문제를 효율적으로 해결할 수 있는 강력한 기법으로, 특히 중복되는 계산이 많은 문제에서 유용하다.

탑다운과 바텀업 방식의 차이

• 탑다운 방식은 재귀와 메모이제이션을 이용하여 간결하게 코드를 작성할 수 있지만, 스택 오버플로우의 위험이 있다.
• 바텀업 방식은 반복문을 이용하여 스택 오버플로우 문제를 피할 수 있으며, 일반적으로 메모리 사용이 더 효율적이다.

다양한 문제에의 적용

• 피보나치 수열, 배낭 문제, LIS 문제 등 다양한 문제에 DP를 적용할 수 있으며, 각 문제의 특성에 맞는 적절한 DP 기법을 선택하는 것이 중요하다.

복잡한 문제의 단순화

• DP를 통해 복잡한 문제를 작은 하위 문제로 나누어 해결함으로써 문제를 단순화할 수 있다.
• 이 과정에서 문제의 최적 부분 구조와 중복되는 하위 문제를 잘 이해하는 것이 핵심이다.

이 인사이트를 바탕으로, 복잡한 문제를 해결할 때 DP를 적용하여 효율적으로 접근할 수 있습니다.