[백준] 18353번 병사 배치하기

park geonwoo·2024년 10월 17일

코딩테스트

목록 보기

26/32

https://www.acmicpc.net/problem/18353

문제를 효율적이고 간결하게 해결하기 위해 동적 계획법(Dynamic Programming, DP)을 활용한 접근 방식을 사용하겠습니다. 이 접근 방식은 최장 감소 부분 수열(Longest Decreasing Subsequence, LDS)을 찾아, 이를 기반으로 필요한 최소 열외 병사의 수를 계산하는 방법입니다.

문제 이해

문제 요약

목표: N명의 병사가 무작위로 나열되어 있으며, 이들을 전투력이 높은 순서대로 내림차순으로 배치하기 위해 최소한의 병사를 열외시키는 방법을 찾습니다. 최종적으로 남아있는 병사의 수가 최대가 되도록 해야 합니다.
입력:
- 첫 번째 줄: 병사의 수 N (1 ≤ N ≤ 2,000)
- 두 번째 줄: N개의 병사의 전투력 (1 ≤ 전투력 ≤ 10,000,000), 공백으로 구분
출력:
- 첫 번째 줄: 남아있는 병사의 수가 최대가 되도록 열외해야 하는 병사의 수

예제 분석

예제 입력 1:

7
15 11 4 8 5 2 4

예제 출력 1:

해석:

전투력이 내림차순이 되도록 두 명의 병사를 열외시킵니다. 예를 들어, 3번 병사(전투력 4)와 6번 병사(전투력 2)를 열외시키면, 남아있는 병사들의 전투력은 [15, 11, 8, 5, 4]로 내림차순이 됩니다.
따라서, 열외해야 하는 병사의 수는 2입니다.

해결 방법

접근 방식

이 문제는 최장 감소 부분 수열(Longest Decreasing Subsequence, LDS)을 찾는 문제로 변환할 수 있습니다. LDS는 주어진 수열에서 연속되지 않은 원소들을 선택하여, 그 수열이 내림차순이 되도록 하는 가장 긴 부분 수열을 의미합니다.

핵심 아이디어:

*최장 감소 부분 수열의 길이(LDS Length)를 찾고, 이를 기반으로 필요한 열외 병사의 수**를 계산합니다.
필요한 열외 병사의 수는 전체 병사의 수 N에서 LDS Length를 뺀 값입니다.

알고리즘 단계

입력 처리:
- 병사의 수 N과 각 병사의 전투력 리스트를 입력받습니다.
최장 감소 부분 수열(LDS) 계산:
- dp[i]를 정의합니다: i번째 병사를 마지막으로 하는 LDS의 길이.
- 각 병사 i에 대해, 이전 병사 j (j < i) 중 전투력 A[j]가 A[i]보다 큰 경우를 찾아, dp[i]를 업데이트합니다.
- dp[i] = max(dp[i], dp[j] + 1) (단, A[j] > A[i])
결과 도출:
- 모든 dp[i] 중 최댓값을 찾아 LDS Length를 구합니다.
- 필요한 열외 병사의 수는 N - LDS Length입니다.

시간 및 공간 복잡도

시간 복잡도: O(N^2)
- 두 개의 중첩된 반복문을 사용하여 모든 병사 쌍을 비교합니다.
공간 복잡도: O(N)
- dp 배열을 사용하여 각 병사에 대한 LDS Length를 저장합니다.

코드 구현

아래는 위의 접근 방식을 구현한 파이썬 코드입니다.

def longest_decreasing_subsequence(N, combat_powers):
    # DP 배열 초기화: 각 위치에서의 LDS 길이를 저장
    dp = [1] * N

    for i in range(1, N):
        for j in range(i):
            if combat_powers[j] > combat_powers[i]:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
    # LDS의 최대 길이
    lds_length = max(dp)
    # 열외해야 하는 병사의 수
    soldiers_to_remove = N - lds_length
    return soldiers_to_remove

def main():
    import sys
    input = sys.stdin.readline

    # 병사의 수 N 입력
    N_line = ''
    while N_line.strip() == '':
        N_line = input()
    N = int(N_line.strip())

    # 병사의 전투력 입력
    combat_powers = []
    while len(combat_powers) < N:
        line = input()
        if not line:
            break
        parts = line.strip().split()
        combat_powers += list(map(int, parts))

    # 결과 계산
    result = longest_decreasing_subsequence(N, combat_powers)
    print(result)

if __name__ == "__main__":
    main()

코드 분석

1. 함수 정의

`longest_decreasing_subsequence(N, combat_powers)`

목적: 주어진 병사들의 전투력 리스트에서 최장 감소 부분 수열의 길이를 계산하고, 이를 기반으로 필요한 열외 병사의 수를 반환합니다.
매개변수:
- N: 병사의 수
- combat_powers: 병사들의 전투력 리스트
반환값: 필요한 열외 병사의 수 (int)

주요 변수

dp: 각 병사를 마지막으로 하는 LDS의 길이를 저장하는 리스트
lds_length: 전체 병사 중 LDS의 최대 길이
soldiers_to_remove: 필요한 열외 병사의 수

2. 최장 감소 부분 수열(LDS) 계산

dp = [1] * N

for i in range(1, N):
    for j in range(i):
        if combat_powers[j] > combat_powers[i]:
            if dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1

설명:
- 모든 병사는 최소한 자기 자신만으로 LDS를 이룰 수 있으므로, dp를 1로 초기화합니다.
- 각 병사 i에 대해, 이전 병사 j (0 ≤ j < i) 중 전투력 combat_powers[j]가 combat_powers[i]보다 큰 경우를 찾아, dp[i]를 업데이트합니다.
- 이는 병사 i를 포함한 LDS의 길이를 갱신하는 과정입니다.

3. 결과 도출

lds_length = max(dp)
soldiers_to_remove = N - lds_length
return soldiers_to_remove

설명:
- 모든 dp[i] 중 최댓값을 찾아 LDS의 최대 길이를 구합니다.
- 필요한 열외 병사의 수는 전체 병사의 수 N에서 LDS의 길이를 뺀 값입니다.

4. 메인 함수

def main():
    import sys
    input = sys.stdin.readline

    # 병사의 수 N 입력
    N_line = ''
    while N_line.strip() == '':
        N_line = input()
    N = int(N_line.strip())

    # 병사의 전투력 입력
    combat_powers = []
    while len(combat_powers) < N:
        line = input()
        if not line:
            break
        parts = line.strip().split()
        combat_powers += list(map(int, parts))

    # 결과 계산
    result = longest_decreasing_subsequence(N, combat_powers)
    print(result)

설명:
1. 입력 처리:
  - 첫 번째 줄에서 병사의 수 N을 입력받습니다.
  - 두 번째 줄부터 N개의 전투력을 입력받아 combat_powers 리스트에 저장합니다.
  - 입력이 여러 줄에 걸쳐 주어질 수 있으므로, 필요한 만큼 반복적으로 입력을 받습니다.
2. 함수 호출 및 결과 출력:
  - longest_decreasing_subsequence 함수를 호출하여 필요한 열외 병사의 수를 계산합니다.
  - 결과를 출력합니다.

5. 코드 실행 예제

예제 입력 1:

코드 복사
7
15 11 4 8 5 2 4

처리 과정:

초기 상태: dp = [1, 1, 1, 1, 1, 1, 1]
병사 1 (15):
- i = 0: 이미 초기화됨
병사 2 (11):
- i = 1
- j = 0: 15 > 11 → dp[1] = max(1, 1 + 1) = 2
- dp = [1, 2, 1, 1, 1, 1, 1]
병사 3 (4):
- i = 2
- j = 0: 15 > 4 → dp[2] = max(1, 1 + 1) = 2
- j = 1: 11 > 4 → dp[2] = max(2, 2 + 1) = 3
- dp = [1, 2, 3, 1, 1, 1, 1]
병사 4 (8):
- i = 3
- j = 0: 15 > 8 → dp[3] = max(1, 1 + 1) = 2
- j = 1: 11 > 8 → dp[3] = max(2, 2 + 1) = 3
- j = 2: 4 > 8 → 조건 불만족
- dp = [1, 2, 3, 3, 1, 1, 1]
병사 5 (5):
- i = 4
- j = 0: 15 > 5 → dp[4] = max(1, 1 + 1) = 2
- j = 1: 11 > 5 → dp[4] = max(2, 2 + 1) = 3
- j = 2: 4 > 5 → 조건 불만족
- j = 3: 8 > 5 → dp[4] = max(3, 3 + 1) = 4
- dp = [1, 2, 3, 3, 4, 1, 1]
병사 6 (2):
- i = 5
- j = 0: 15 > 2 → dp[5] = max(1, 1 + 1) = 2
- j = 1: 11 > 2 → dp[5] = max(2, 2 + 1) = 3
- j = 2: 4 > 2 → dp[5] = max(3, 3 + 1) = 4
- j = 3: 8 > 2 → dp[5] = max(4, 3 + 1) = 4
- j = 4: 5 > 2 → dp[5] = max(4, 4 + 1) = 5
- dp = [1, 2, 3, 3, 4, 5, 1]
병사 7 (4):
- i = 6
- j = 0: 15 > 4 → dp[6] = max(1, 1 + 1) = 2
- j = 1: 11 > 4 → dp[6] = max(2, 2 + 1) = 3
- j = 2: 4 > 4 → 조건 불만족
- j = 3: 8 > 4 → dp[6] = max(3, 3 + 1) = 4
- j = 4: 5 > 4 → dp[6] = max(4, 4 + 1) = 5
- j = 5: 2 > 4 → 조건 불만족
- dp = [1, 2, 3, 3, 4, 5, 5]

최종 dp 배열: [1, 2, 3, 3, 4, 5, 5]

LDS Length: 5 (예: [15, 11, 8, 5, 2] 또는 [15, 11, 8, 5, 4] 등)

열외해야 하는 병사의 수: 7 - 5 = 2

출력:

시간 복잡도 및 효율성

시간 복잡도

DP 배열 초기화:
- dp = [1] * N
- 시간 복잡도: O(N)
최장 감소 부분 수열 계산:
```
for i in range(1, N):
    for j in range(i):
        if combat_powers[j] > combat_powers[i]:
            if dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
```
- 반복문:
  - 외부 반복문: O(N)
  - 내부 반복문: O(N) (각 i마다 최대 i번)
- 총 시간 복잡도: O(N^2)
- 설명: 각 병사 i에 대해 이전 모든 병사 j를 확인하여 LDS를 갱신합니다.
최대 LDS 길이 찾기:
- lds_length = max(dp)
- 시간 복잡도: O(N)
결과 계산:
- soldiers_to_remove = N - lds_length
- 시간 복잡도: O(1)

총 시간 복잡도: O(N^2)

적용 가능성: N ≤ 2,000이므로, O(N^2) 알고리즘은 약 4,000,000 연산을 수행하며, 이는 충분히 빠르게 처리 가능합니다.

공간 복잡도

DP 배열:
- dp = [1] * N
- 공간 복잡도: O(N)
전투력 리스트:
- combat_powers
- 공간 복잡도: O(N)

총 공간 복잡도: O(N)

설명: dp 배열과 전투력 리스트를 저장하기 위해 O(N)의 공간을 사용합니다.

알고리즘 및 자료구조 설명

알고리즘: 동적 계획법(Dynamic Programming, DP)

특징:
- 부분 문제의 최적 해를 이용하여 전체 문제의 최적 해를 구합니다.
- 메모이제이션(Memoization) 또는 타뷸레이션(Tabulation) 방식을 사용합니다.
이 문제에서의 적용:
- 부분 문제 정의: dp[i]는 i번째 병사를 마지막으로 하는 LDS의 길이입니다.
- 점화식:
```
dp[i] = max(dp[j] + 1) for all j < i where combat_powers[j] > combat_powers[i]
```
- 초기 조건: 모든 dp[i]는 최소 1로 시작 (자기 자신만으로 LDS를 이룰 수 있으므로).

자료구조: 배열(Array)

용도:
- DP 배열(dp)을 사용하여 각 병사에 대한 LDS 길이를 저장합니다.
장점:
- 인덱스 접근이 빠르며, 순차적인 저장이 용이합니다.
단점:
- 동적 크기 변경이 불가능하므로, 미리 크기를 정해야 합니다. 그러나 이 문제에서는 병사의 수가 고정되어 있으므로 문제가 되지 않습니다.

결론

제공된 파이썬 코드는 동적 계획법(DP)을 사용하여, 주어진 병사들의 전투력 리스트에서 최장 감소 부분 수열(LDS)의 길이를 계산하고, 이를 기반으로 필요한 열외 병사의 수를 정확하게 구합니다. 시간 복잡도는 O(N^2), 공간 복잡도는 O(N)으로, 주어진 문제의 제한 사항 (N ≤ 2,000) 내에서 매우 효율적으로 동작합니다.

알고리즘: 동적 계획법을 사용한 최장 감소 부분 수열(LDS) 계산
자료구조: 배열(Array) 활용
시간 복잡도: O(N^2)
공간 복잡도: O(N)

이 접근 방식은 병사의 전투력 리스트를 순차적으로 처리하면서, 가능한 최대한 많은 병사를 남기기 위해 효율적으로 열외 병사를 결정합니다. 코드가 간결하고 이해하기 쉬우며, 동적 계획법의 기본 개념을 잘 활용하고 있어 코딩 테스트 환경에서도 효과적으로 사용할 수 있습니다.

추가 팁

*최장 증가 부분 수열(Longest Increasing Subsequence, LIS)과 최장 감소 부분 수열(LDS)**의 차이:
- LIS: 수열에서 증가하는 부분 수열 중 가장 긴 것을 찾습니다.
- LDS: 수열에서 감소하는 부분 수열 중 가장 긴 것을 찾습니다.
- 응용: LIS와 LDS는 많은 알고리즘 문제에서 중요한 역할을 합니다. 비슷한 접근 방식을 사용하여 다양한 변형 문제를 해결할 수 있습니다.
효율적인 LDS 계산:
- 위의 O(N^2) 방법 외에도, 이진 탐색(Binary Search)을 활용한 O(N log N) 시간 복잡도의 방법도 존재합니다. 하지만, 현재 문제의 제한 사항에서는 O(N^2) 방법이 충분히 효율적입니다.
DP 배열의 활용:
- DP 배열을 사용할 때는 상태 정의(State Definition)와 점화식(Recurrence Relation)을 명확하게 이해하는 것이 중요합니다. 이는 문제 해결의 핵심입니다.
문제의 최적화:
- N이 매우 큰 경우, O(N^2) 알고리즘은 비효율적일 수 있으므로, O(N log N) 알고리즘을 사용하는 것이 필요합니다. 예를 들어, 이진 탐색을 활용하여 LDS를 계산할 수 있습니다.

park geonwoo

이전 포스트

[백준] 26069 붙임성 좋은 총총이

다음 포스트