[백준] - 다이나믹 프로그래밍 병사 배치하기, 가장 긴 증가하는 부분 수열 2

병사 배치하기

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

6064

2393

1834

41.093%

문제

N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다.

또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다.

예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자.

이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다.

병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력한다.

예제 입력 1 복사

7
15 11 4 8 5 2 4

예제 출력 1 복사

2

 

---

LIS , 즉 증가하는 가장 긴 수열이라는 알고리즘은 사실 그냥 떠올리는 것도 어렵지 않다. 

해당 문제도 그냥 떠올려서 풀었다. 

import sys 
input = sys.stdin.readline 

N = int(input())
sol = list(map(int,input().split()))
sol = [[1,i] for i in sol]

for i in range(1, N):
    for j in range(i-1,-1,-1):
        if sol[i][1] < sol[j][1]:
            sol[i][0] = max(sol[i][0], sol[j][0]+1)


print(N-max([i[0] for i in sol]))

증가하는 가장 긴 수열이 아니라 감소하는 가장 긴 수열로 풀었다. 

매번 원소마다 그전의 길이를 참고하여 최대 길이를 업데이트 하는 방식이다. 

워낙 쉬운 문제라 별다른 설명은 달지 않는다. 

 

그러나, 이 문제를 해결하고 다른 사람들의 답안을 살피다가 놀란 결과를 확인했다. 

사람들이 나보다 약 20배의 빠른 속도로 문제를 해결했다. 

 

살펴보니, binary search 를 사용하여 문제를 해결할 수 있다는 것을 확인했다. 

본 문제보다 input 값이 훨씬 많고, 동시에 구하고자 하는 것이 단지 길이일 때 binary search 를 통해 해결 가능하다. 

 

이해한 알고리즘은 아래와 같다. 

1 3 5 9 

위와 같은 수열이 있다고 하자. 

추후 들어오는 수가 1 ~ 9 사이의 값이라면 input 값 보다 값이 크면서 가장 가까운 수를 선택해서 input값으로 대체한다. 

 

이를 대체하는 이유는 대체 과정을 통해 추후 들어오는 수가 뒤에 이어 붙을 수 있도록 최소 값으로 대체하는 것이다. 

 

1 3 5 9 에 2가 들어왔다고 예를 들어보자. 

 

이 경우 1 2 5 9 가 된다. 이는 2를 그냥 대체하는 것은 실제 구하게 될 수열과 다르다고 할 수 있으나, 길이는 동일하다. 

추후 3이 들어오게되면 기존에는 3 이후 5 위치에 들어올 수 없었으나 이제 들어올 수 있다. 

 

1 2 3 9 

 

추후 4,5 와 같이 3보다 큰 숫자만 들어오면 이어붙여서 가장 긴 수열을 이어나갈 수 있도록 한다. 

 

 

가장 긴 증가하는 부분 수열 2

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

30486

12399

8658

42.092%

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1 복사

6
10 20 10 30 20 50

예제 출력 1 복사

4

---

binary search 를 수행하며 다음의 경우가 필요할 때가 있다. 

• 찾는 값이 없으나 찾고자 하는 값보다 크면서 가장 가까운 값 
• 찾는 값이 없으나 찾고자 하는 값보다 작으면서 가장 가까운 값 

해당 문제는 찾는 값이 없으나 찾고자 하는 값보다 크면서 가장 가까운 값을 찾으면 된다 .

아래 블로그에 잘 정리되어있다! 

https://yiyj1030.tistory.com/230

이진 검색 binary search의 여러 가지 형태(파이썬 코드)

위 블로그에서 틀린 부분이 있어서 수정. 

 

import sys 
input = sys.stdin.readline 

N = int(input())
lst = list(map(int,input().split()))
dp = [lst[0]] 


def bisearch(dp, c):
    start = 0 
    end = len(dp)-1

    while(start <= end):
        mid = (start + end) // 2
        if dp[mid] == c:
            return mid 
        elif dp[mid] > c:
            result = mid 
            end = mid -1 
        elif dp[mid] < c: 
            start = mid + 1

    return result 


for i,c in enumerate(lst[1:]):
    if c > dp[-1]:
        dp.append(c)
    else:
        idx = bisearch(dp, c)
        dp[idx] = c


print(len(dp))

 

알고리즘의 골자는 다음과 같다. 

해당 알고리즘은 개수를 구할 때만 사용 가능하다. 

 

• 첫 원소를 리스트에 추가한다. 
• input 원소가 리스트의 최종 원소보다 크면 추가한다. 
• 만약 최종 원소보다 input원소가 작으면 리스트내 input 원소보다 크면서 가장 가까운 원소를 택하여 값을 교체한다. 

여기서 골자는 input 원소보다 크면서 가장 가까운 원소를 택하여 값을 교체 이 부분이 왜 가능하냐이다. 

한마디로만 적자면, input 원소로 대체하여도 어차피 뒤에 있는 원소들이 더 크기가 크기에 원소 대소 비교하여 추가하는 상황에서 문제가 발생하지 않고, 교체하여 리스트가 전반적으로 달라지면 실제로 해당 원소들로 리스트를 꾸릴 수 있는 상황이다. 

좀 설명이 어려운데, 직접 손으로 해보면 금방 이해된다.