코테 연습) 다이나믹 프로그래밍 : 피보나치 수열(문제 : 병사 배치하기).python
q5) 병사 배치하기
- N명의 병사가 무작위로 나열되어있다 각 병사는 특정한 값의 전투력을 보유하고 있다
- 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치하고자 한다 다시말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야한다
- 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다 그러면서도 남아 있는 병사의 수가 최대가 되도록 하고싶다
ed) 예를들어, N = 7일 때 나열된 병사들의 전투력이 다음과 같다고 가정
- 이때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아 있는 병사의 수가 내림차순의 형태가 되어 5명이 된다 이는 남아 있는 병사의 수가 최대가 되도록 하는 방법이다
- 병사에 대한 정보가 주어 졌을 때, 남아 있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수를 출력
조건) 첫째줄에 남아 있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야하는 병사의 수를 출력
N = 7이면
7
15 11 4 8 5 2 4
를 입력하면 출력이 2
- 이 문제의 기본 아이디어는 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)로 알려진 전형적인 다이나믹 프로그래밍 문제의 아이디어와 같다
- 예를 들어 하나의 수열 array = {4, 2, 5, 8, 4, 11, 15}이 있다고 하면
- 이 수열의 가장 긴 증가하는 부분 수열은 {4, 5, 8, 11, 15}이다
- 본 문제는 가장 긴 감소하는 부분 수열을 찾는 문제로 치환할 수 있으므로, LIS 알고리즘을 조금 수정하여 적용함으로써 정답을 도출할 수 있다
- 가장 긴 증가하는 부분 수열(LIS) 알고리즘을 확인해 보자
- D[i] = array[i]를 마지막 ㅁ원소로 가지는 부분 수열의 최대 길이
- 점화식은 다음과 같다
- 가장 먼저 입력 받은 병사 정보의 순서를 뒤집는다
- 가장 긴 증가하는 부분 수열 (LIS) 알고리즘을 수행하여 정답을 도출
->입력창
n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환
array.reverse()
# 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
dp = [1] * n
# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1, n):
for j in range(0, i):
if array[j] < array[i]:
dp[i] = max(dp[i], dp[j] + 1)
# 열외해야 하는 병사의 최소 수를 출력
print(n - max(dp))
->출력창
C:\Users\admin\PycharmProjects\ML_EX\venv\Scripts\python.exe C:/Users/admin/PycharmProjects/ML_EX/study06.py
7
15 11 4 8 5 2 4
2
종료 코드 0(으)로 완료된 프로세스
풀이)
n = int(input())
array = list(map(int, input().split()))
- 병사의 수 입력 받고
- 병사의 정보를 공백 기준으로 병사의 수만큼 입력 받는다
# 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환
array.reverse()
- array을내림차순으로 정렬한다
# 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
dp = [1] * n
- 리스트의 1차원 초기화 방법으로 모든 수를 1로 초기화한다
# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1, n):
- 1 부터 n-1까지 해당 문제에서는 7을 입력 받았으므로 1 부터 6까지 하나씩 꺼낸 수를 i라하고 아래조건문 반복
for j in range(0, i):
- 0부터 위에서 꺼낸 i-1까지 하나씩 꺼낸 수를 j라고 하고 아래 반복
if array[j] < array[i]:
dp[i] = max(dp[i], dp[j] + 1)
- 만약 array의 j번째 인덱스의 값이 array의 i번째 인덱스의 값보다 작으면
dp의 i번째 인덱스의 값은 (dp의 i번째 인덱스의 값, dp의 j번째 인덱스의 값 + 1)의 최대값
# 열외해야 하는 병사의 최소 수를 출력
print(n - max(dp))
| 인덱스 0 | 인덱스 1 | 인덱스 2 | 인덱스 3 | 인덱스 4 | 인덱스 5 | 인덱스 6 | |
| 4 | 2 | 5 | 8 | 4 | 11 | 15 | |
| i = 0 (초기값) | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| i = 1 | 1 | 4 < 2 = F 1 유지 |
1 | 1 | 1 | 1 | 1 |
| i = 2 | 1 | 1 | 2 < 5 = T 2 갱신 |
1 | 1 | 1 | 1 |
| i = 3 | 1 | 1 | 2 유지 | 5 < 8 = T 3 갱신 |
1 | 1 | 1 |
| i = 4 | 1 | 1 | 2 유지 | 3 유지 | 8 < 4 = F 5 < 4 = F 2 < 4 = T 2 갱신 |
1 | 1 |
| i = 5 | 1 | 1 | 2 유지 | 3 유지 | 2 유지 | 8 < 11 = T 4 갱신 (바로 앞의 값은 n-3번째 값이랑 연관되어 있으니 pass) |
1 |
| i = 6 | 1 | 1 | 2 갱신 | 3 갱신 | 2 유지 | 4 유지 | 11 < 15 = T 5 갱신 |
출처 / 유튜브 [동빈나 - (이코테2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬]