안녕하세요? 이번 달 PS 문제는 여러 알고리즘 대회에서도 자주 등장하고 있으며, 2022년 고등학교 비버챌린지 문제에도 나온 “동적계획법(DP; Dynamic Programming)을 통해 문제를 해결하는 방법”에 대해서 소개해 드리려고 합니다.
문제설명
N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 뒤쪽에 있는 병사의 전투력보다 항상 높아야 한다.
또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.
예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자.
이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다.
병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력하는 프로그램을 작성해 보자.
입력설명
첫째 줄에 N이 주어진다.(1 ≤ N ≤ 2,000)
둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다.
각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.
출력설명
첫째 줄에 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력한다.
입출력 예시
7
15 11 4 8 5 2 4
2
문제 이해 및 분석
•
문제에서 해결하고자 하는 것은?
: 남아있는 병사의 수가 최대가 되도록 하기 위해 열외해야 하는 병사의 수
•
문제의 현재 상태와 목표 상태는?
현재 상태 : 병사의 수(N)와 각 병사의 전투력이 주어짐
목표 상태 : 전투력이 높은 병사부터 내림차순으로 배치하여 최대로 배치할 수 있는 병사의 수를 구하려고 함
알고리즘 설계 및 프로그래밍(최장 증가 부분 수열)
이 문제를 해결하기 위해 2가지 알고리즘에 대해 간단히 소개하겠습니다.
•
동적계획법(Dynamic Programming)이란?
어떤 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법입니다.
여기서 핵심은 실행 중에 결과를 저장하면서, 해당 값을 다시 구하지 않고 저장한 값을 바로 재활용하는 것입니다.•
최장 증가 부분 수열(LIS: Longest Increasing Subsequence)이란?
어떤 수열의 앞에서부터 차례대로 숫자들을 뽑아 만들 수 있는 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 의미한다.
예를 들어, [1, 5, 6, 2, 7, 1] 이라는 수열에서 증가하는 부분수열이 [1, 5], [1, 5, 6], [1, 5, 6, 7], [2, 7] 등 다양하게 있지만 이 중 가장 긴 수열은 [1, 5, 6, 7] 이다.
여기서 핵심은 이 문제는 병사의 전투력 배치를 내림차순으로 배치한다는 점이며, 오름차순이나 내림차순이나 과정을 동일하게 구할 수 있습니다. 따라서, 파이썬으로는 오름차순 방식으로, C++로는 내림차순 방식으로 풀이해 보도록 하겠습니다.C++(내림차순 방식)
사용하는 변수에 대한 설명은 다음과 같습니다.
•
knight : 병사들의 전투력을 저장
•
memo : 메모장처럼 가장 긴 내림차순 길이를 저장
(이때, LIS의 최솟값은 1이기 때문에, memo에 1을 초기화)
2번째 병사(int back =1)부터 자신보다 앞에 있는 병사(front)와 전투력을 비교하였을 때 더 작다면 내림차순의 길이를 증가시켜 memo[front] + 1값을 memo[back]에 최댓값을 기록해둡니다.
여기서 max()라는 함수는 c++의 표준함수로 max(a,b) 형태를 가지고 있고, a,b 중에 큰 값을 리턴해 줍니다.7
15 11 4 8 5 2 4
Plain Text
복사
위 입출력 예시를 기준으로, 이중 for문을 모두 실행하게 되고 나면
memo = [ 1, 2, 3, 3, 4, 5, 5, 0… ] 의 값을 가지게 됩니다.
memo[0]의 1이라는 값은 자기 자신이 LIS라는 뜻이며, memo[1]의 2는 [15, 11]이 LIS.. 이렇게 해석될 수 있습니다.
따라서, memo에서 가장 큰 값인 5는 memo[5], memo[6]에서 볼 수 있는데, 이미 memo[5]에서 [15, 11, 8, 5, 2]이라는 수열을 구성했기 때문입니다.
문제를 해결하기 위해서는 전체(7)라는 값에서 LIS(5)를 빼줘야 하기 때문에 다시 max값을 찾아서 정답을 구했습니다.
#include<iostream>
#include<vector>
using namespace std;
vector<int> knight; // 병사의 전투력 담아둘 곳
int memo[2001]; // 병사 수를 저장할 메모장
int main()
{
// === input ===
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int vx;
cin >> vx;
knight.push_back(vx);
}
// 길이의 최솟값은 1이기 때문에 모든 병사 기준 길이를 1이라고 초기화
for (int i = 0; i < n; i++)
memo[i] = 1;
// LIS AL
for (int back = 1; back < n; back++)
{
for (int front = 0; front < back; front++)
{
// 두번째 병사부터 자신보다 앞에 있는 병사들과 비교하여
// 내림차순이기 때문에 앞의 병사보다 작다면, 메모장에 기록
if (knight[front] > knight[back])
{
// 자신이 기록한 병사 수와 해당 병사까지의 수 + 1 중
// 최대값을 저장
memo[back] = max(memo[front] + 1, memo[back]);
}
}
}
// 가장 큰 값 찾기
int LIS = 0;
for (int i = 0; i < n; i++)
{
LIS = max(LIS, memo[i]);
}
// === output ===
cout << n - LIS;
}
C++
복사
Python(오름차순 방식)
사용하는 변수에 대한 설명은 다음과 같습니다.
•
soldier : 병사들의 전투력을 저장
•
length : 각 인덱스별로 soldier 리스트의 동일한 인덱스까지의 최장 증가 부분 순열의 길이를 저장
가장 작은 최장 증가 부분 순열은 본인 1개로 끝나는 순열이므로 1로 초기화함
# 사실 파이썬의 경우 리스트의 동적 할당이 가능하여, 입력될 병사의 숫자를 저장할 필요는 없다.
num = int(input())
soldier = list(map(int, input().split()))
count = [1]*num
# LIS를 구하여 문제를 해결하기 위해서는 soldier 리스트를 역순으로 정렬해야 한다.
soldier.reverse()
for next in range(1, len(soldier), 1):
for prev in range(0, next, 1):
if soldier[next] > soldier[prev] :
# 오름차순으로 해결하기 때문에 마찬가지로 앞선 병사의 군사력보다 뒷 병사의 군사력이 큰 경우를 확인한다.
count[next] = max(count[next], count[prev]+1)
print(N-max(count))
Python
복사