문제 설명
주어진 배열에서 가장 긴 증가하는 부분 수열의 길이를 찾는 문제를 해결해 보겠습니다. 증가하는 부분 수열은 배열에서 서로 다른 인덱스를 가지는 요소들 중에서, 해당 요소들이 오름차순으로 정렬된 부분 배열입니다. 예를 들어, 배열 [10, 22, 9, 33, 21, 50, 41, 60, 80]에 대해 가장 긴 증가하는 부분 수열은 [10, 22, 33, 50, 60, 80]로 길이는 6입니다.
문제 정의
주어진 정수 배열 arr이 있을 때, 가장 긴 증가하는 부분 수열의 길이를 반환하는 메서드를 작성하시오.
입력
- 첫 번째 줄에 배열의 길이
n이 주어집니다. (1 ≤ n ≤ 1000) - 두 번째 줄에
n개의 정수가 주어집니다. 각 정수는-10^6 ≤ arr[i] ≤ 10^6입니다.
출력
가장 긴 증가하는 부분 수열의 길이를 출력합니다.
예제
입력
9
10 22 9 33 21 50 41 60 80출력
6문제 풀이 방법
가장 긴 증가하는 부분 수열을 찾는 여러 알고리즘 중 가장 많이 사용되는 방법은 동적 프로그래밍(Dynamic Programming)입니다. 이 방법은 문제를 작은 부분 문제로 나누어 해결하고, 이 결과를 바탕으로 전체 문제를 해결하는 접근법입니다.
단계별 설명
- 배열 초기화: 주어진 배열
arr의 길이를n이라 가정합니다. 동적 프로그래밍 배열dp를 초기화하여 각 인덱스i에 대해, 그 인덱스까지의 가장 긴 증가하는 부분 수열의 길이를 저장할 것입니다. 우선 각 요소가 자기 자신만으로도 수열이 될 수 있으므로 초기값을 1로 설정합니다. - 이중 반복문: 중첩 반복문을 사용하여 모든 쌍의 인덱스
i와j를 비교합니다. 이때i는j보다 크고,arr[i]가arr[j]보다 클 경우 (즉, 증가하는 조건을 만족하는 경우),dp[i]값을 업데이트합니다. 구체적으로,dp[i] = max(dp[i], dp[j] + 1)로 설정합니다. 이것은j를 포함한 수열의 길이에 1을 추가하는 것입니다. - 최대 길이 찾기: 모든 수열 길이를 계산한 후
dp배열에서 최대값을 찾아 반환합니다.
C# 구현
using System;
class Program
{
static void Main()
{
int n = int.Parse(Console.ReadLine());
int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
int[] dp = new int[n];
for (int i = 0; i < n; i++)
{
dp[i] = 1; // 각 요소는 최소 1개의 수열을 형성할 수 있음
}
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (arr[i] > arr[j] && dp[i] < dp[j] + 1)
{
dp[i] = dp[j] + 1;
}
}
}
int maxLength = dp[0];
for (int i = 1; i < n; i++)
{
if (dp[i] > maxLength)
{
maxLength = dp[i];
}
}
Console.WriteLine(maxLength);
}
}
시간 복잡도
이 알고리즘의 시간 복잡도는 O(n^2)입니다. 이는 두 개의 중첩 반복문을 사용하기 때문입니다. 외부 반복문과 내부 반복문 모두 각각 배열의 길이만큼 실행되므로 최악의 경우 총 n * n의 연산이 필요합니다. 공간 복잡도는 O(n)이며, 이는 dp 배열을 저장하기 위해 필요한 공간입니다.
결론
이번 강좌에서는 가장 긴 증가하는 부분 수열을 찾는 알고리즘을 C#으로 구현해 보았습니다. 이 문제는 코딩 테스트에서 자주 출제되며, 동적 프로그래밍의 기초를 배우고 익히는 데 매우 유용합니다. 꾸준한 연습을 통해 다양한 문제를 해결하는 데 필요한 사고력과 접근 방식을 기를 수 있습니다.