이번 글에서는 동적 계획법(Dynamic Programming, DP) 및 최장증가부분수열(LIS)을 활용하여 백준 온라인 저지의 “1965 상자 넣기” 문제를 해결하는 방법에 대해 알아보겠습니다. 제가 직접 체크해본 결과, 이 문제는 상당히 흥미로우면서도 도전적인 문제입니다. 따라서 이 글을 통해 문제 해결 과정과 풀이 코드를 상세히 안내해 드리겠습니다.
문제 설명 및 접근 방식
상자 넣기 문제는 주어진 일렬의 상자들에서, 앞에 있는 상자가 뒤에 있는 상자보다 작으면 상자를 넣을 수 있다는 조건 하에 가장 많이 넣을 수 있는 상자의 개수를 찾는 문제입니다. 제가 직접 경험해본 바로는 이 문제는 최장증가부분수열 문제와 밀접한 관련이 있어, 해결하는 방식이 유사합니다.
- 문제 이해하기
- 주어진 입력에 대해서 각 상자의 크기가 주어지고, 그 중에서 길이가 가장 긴 증가하는 부분 수열을 찾아야 합니다.
- 이때 각 상자의 개수를 적절히 카운트하여 최종적으로 출력해야 합니다.
- 풀이 접근법
- 동적계획법을 통해 각 상자에서 시작해 최대로 넣을 수 있는 상자 개수를 계산합니다.
- 각 상자 크기보다 작은 상자의 개수를 찾아 최대값을 갱신하여 최종 값을 도출합니다.
동적 계획법(DP) 구현
저는 이 문제를 해결하기 위해 Java 언어를 사용하여 DP 배열을 구성한 후, 입력받은 상자 크기 배열을 기준으로 상자 넣기 문제를 풀었습니다. 아래 코드를 통해 자세한 실행 과정을 확인해 보세요.
“`java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
int[] dp = new int[N];
int answer = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
for(int i = 0; i < N; i++) {
dp[i] = 1; // 각 상자는 최소 1개를 갖는다.
for(int j = 0; j < i; j++) {
if(arr[j] < arr[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
for(int i = 0; i < N; i++) {
answer = Math.max(answer, dp[i]);
}
System.out.println(answer);
}
}
``dp`를 사용하여 각 상자에서 최대 넣을 수 있는 상자의 개수를 계산하였습니다. 그래야 최대값을 찾을 수 있습니다.
위 코드에서 DP 배열
개선할 사항
해당 문제를 해결하는 데 있어 몇 가지 개선점이 있을 수 있습니다:
- 메모이제이션 활용: 저는 메모이제이션을 통해 중복 계산을 피할 수 있었고, 이를 통해 성능 개선을 경험했습니다.
- 코드의 가독성: 변수의 네이밍과 주석을 추가하여 코드의 이해를 돕는 것이 좋습니다.
메모이제이션을 활용한 최장증가부분수열 구현
아래는 메모이제이션 기법을 통해 최장증가부분수열을 계산하는 방법입니다.
“`java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static int[] arr;
public static int[] cache;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N];
cache = new int[N + 1];
Arrays.fill(cache, -1);
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
System.out.println(LIS(-1) - 1);
}
public static int LIS(int idx) {
if(cache[idx + 1] != -1) return cache[idx + 1]; // 캐시에서 값을 가져옴
int ret = 1;
for(int next = idx + 1; next < N; next++) {
if(idx == -1 || arr[idx] < arr[next]) {
ret = Math.max(ret, LIS(next) + 1);
}
}
return cache[idx + 1] = ret; // 새로운 값을 캐시에 저장
}
}
“`
이 코드에서는 재귀적으로 호출하여 최장증가부분수열의 길이를 계산하였습니다. 제가 직접 경험해본 결과, 메모이제이션 기법을 사용하면 성능이 상당히 향상되는 것을 확인했습니다.
작성한 코드를 통해 느낀 점
이 문제를 해결하는 과정에서 느낀 것은, 단순히 코드를 작성하는 것뿐만 아니라 문제를 이해하고 개선점을 찾는 것이 얼마나 중요한지를 깨달았어요. 여러분도 이와 같은 문제를 다룰 기회가 있다면, 여러 관점에서 접근하며 해결해 보시길 추천합니다.
자주 묻는 질문 (FAQ)
문제를 풀기 위해 꼭 필요한 데이터 구조는 무엇인가요?
동적 계획법과 최장증가부분수열을 구현하기 위해 배열과 리스트를 사용하는 것이 필요합니다. 특히 DP 배열이 중요합니다.
상자의 크기가 모두 같을 때는 어떻게 처리하나요?
모든 상자의 크기가 같다면, 최장증가부분수열의 길이는 1이 됩니다. 상자를 넣을 수 있는 경우가 없기 때문입니다.
프로그래밍 언어에 따른 문제 풀이 차이는 있나요?
각 프로그래밍 언어는 특성이 있지만, 알고리즘의 기본 원리는 같습니다. Java, Python, C++등에서 검증된 알고리즘을 이용하면 됩니다.
문제가 너무 어렵다면 어떻게 해야 하나요?
문제의 조건을 다시 한번 읽어보고, 다른 사람의 예시를 참고하거나 간단한 문제부터 단계적으로 해결해보는 것이 도움이 됩니다.
상자의 크기를 비교하고 최장증가 부분 수열을 찾는 이 문제를 통해 동적 계획법의 유용성을 다시 한 번 깨달았습니다. 여러분도 이 알고리즘을 통해 새로운 도전을 해보시길 바랍니다.
키워드: 백준, 동적계획법, 최장증가부분수열, Java, 알고리즘, 상자넣기, 문제해결, 프로그래밍, 메모이제이션, DP, LIS