[알고리즘] 동적 계획법(Dynamic Programming) - 상태 전이(State Transition)
카테고리: Algorithm Theory
태그: algorithm coding test state transition dynamic programming
1. 🔍 상태 전이(State Transition)
상태 전이(State Transition)는 동적 계획법의 핵심 개념으로, 문제를 해결하기 위해 현재 상태를 이전 상태로부터 어떻게 도출해낼지를 정의하는 과정이다. 이는 복잡한 문제를 더 간단한 하위 문제로 나누어 해결하는 데 사용된다.
1.1. 상태 정의
- 상태: 문제의 특정 조건이나 상황을 나타내는 변수 또는 배열이다. 각 상태는 문제의 진행 상황을 나타내며, 이를 통해 최적의 해답을 찾는다.
- 상태 전이: 한 상태에서 다른 상태로의 변화를 나타내며, 이를 통해 문제를 해결하는 방법을 정의한다.
1.2. 점화식
- 상태 전이의 경우 항상 초기 값(initial value)이 존재하고 $n$번째 원소의 값을 구하기 위해 $n-1$번째 원소(혹은 추가적인 이전 원소들)의 값을 사용한다.
- 예를 들어 피보나치 수열의 경우, 점화식은 다음과 같다.
1.3. 상태 전이의 중요성
상태 전이는 동적 계획법에서 문제를 해결하는 데 있어 매우 중요한 역할을 한다. 다음은 상태 전이가 중요한 이유이다:
- 문제 단순화: 복잡한 문제를 더 간단한 하위 문제로 나누어 해결할 수 있다. 이를 통해 문제를 보다 쉽게 이해하고 접근할 수 있다.
- 최적화: 상태 전이를 통해 최적의 해답을 찾기 위한 경로를 정의할 수 있다. 이는 알고리즘의 효율성을 높이는 데 기여한다.
- 재사용성: 이전 상태의 결과를 활용하여 새로운 상태를 계산함으로써 중복 계산을 피할 수 있다. 이는 메모리와 시간을 절약하는 데 도움이 된다.
2. 📈 상태 전이의 예시
상태 전이를 이해하기 위해 몇 가지 예시를 살펴보자.
2.1. 피보나치 수열
피보나치 수열을 계산할 때, 각 수는 이전 두 수의 합으로 정의된다. 이 경우 상태 전이는 다음과 같이 표현할 수 있다:
\[F(n) = F(n-1) + F(n-2)\]여기서 $F(n)$은 $n$번째 피보나치 수를 나타낸다.
2.2. 최장 증가 부분 수열 (LIS)
주어진 수열에서 가장 긴 증가하는 부분 수열을 찾는 문제에서 상태 전이는 다음과 같이 정의된다:
\[dp[i] = \max(dp[i], dp[j] + 1) \quad \text{(단, } j < i \text{이고 } arr[j] < arr[i])\]이 점화식은 $i$번째 원소가 포함된 증가 부분 수열의 길이를 계산하는 방법을 나타낸다.
3. 📚 결론
상태 전이는 이전 상태를 활용하여 복잡한 문제를 단순화하고, 최적의 해답을 찾는 것이 핵심이다.