요즘 알고리즘 공부에 재미가 붙어서 다양한 문제들을 풀어보고 있는데, 그중에서도 다이나믹 프로그래밍(Dynamic Programming)을 활용하는 문제들이 특히 매력적이더라고요. 오늘은 그중에서도 대표적인 예시 중 하나인 "증가하거나 감소하는 가장 긴 수열" 문제를 풀면서 다이나믹 프로그래밍의 매력을 여러분과 함께 나누고자 합니다. 문제는 간단합니다. 0부터 9까지의 숫자로 이루어진 수열이 주어졌을 때, 연속해서 증가하거나(같은 수 포함) 감소하는(같은 수 포함) 수열 중 가장 긴 수열의 길이를 찾는 것이죠. 예를 들어, 1, 2, 2, 4, 4, 5, 7, 7, 2 라는 수열이 있다면 1 ≤ 2 ≤ 2 ≤ 4 ≤ 4 ≤ 5 ≤ 7 ≤ 7 이 가장 긴 증가하는 수열이 되어 길이가 8이 됩니다. 반대로 4, 1, 3, 3, 2, 2, 9, 2, 3 이라는 수열에서는 3 ≥ 3 ≥ 2 ≥ 2 가 가장 긴 감소하는 수열이고, 길이는 4가 되겠죠.
자, 그럼 이 문제를 다이나믹 프로그래밍으로 어떻게 해결할 수 있을까요? 핵심은 이전 상태를 이용해서 현재 상태를 효율적으로 계산하는 것입니다. 우선, 두 개의 배열, increasing 과 decreasing 을 만듭니다. increasing[i] 는 i번째 숫자를 끝으로 하는 가장 긴 증가 수열의 길이를, decreasing[i] 는 i번째 숫자를 끝으로 하는 가장 긴 감소 수열의 길이를 저장합니다.
처음 숫자부터 순차적으로 확인하면서, 이전 숫자와 비교합니다. 만약 현재 숫자가 이전 숫자보다 크거나 같다면, increasing[i] 는 increasing[i-1] + 1 이 됩니다. 만약 현재 숫자가 이전 숫자보다 작거나 같다면, decreasing[i] 는 decreasing[i-1] + 1 이 됩니다. 모든 숫자를 확인한 후, increasing 배열과 decreasing 배열의 최대값을 찾으면 그 값이 바로 답이 됩니다. 이는 각 위치에서 최대 길이를 저장해두고, 다음 위치를 계산할 때 이전 위치의 정보를 재활용하는 다이나믹 프로그래밍의 전형적인 방식입니다. 물론, 실제 코드 구현에서는 몇 가지 추가적인 고려사항이 있겠지만, 기본적인 아이디어는 이것입니다.
결론적으로, "증가하거나 감소하는 가장 긴 수열" 문제는 다이나믹 프로그래밍을 통해 효율적으로 해결할 수 있는 좋은 예시입니다. 이 문제를 통해 다이나믹 프로그래밍의 기본 원리를 이해하고, 이를 응용하여 다른 유사한 문제들을 풀어볼 수 있는 좋은 계기가 될 것입니다. 다이나믹 프로그래밍은 처음 접하면 어렵게 느껴질 수 있지만, 다양한 문제들을 풀어보면서 감을 익히다 보면 어느새 자연스럽게 익숙해질 수 있습니다. 저 또한 앞으로 다양한 다이나믹 프로그래밍 문제들을 풀어보며 실력을 키워나갈 예정입니다!