Algorithm

백준 No.11053 : 가장 긴 증가하는 부분 수열(LIS) [파이썬]

개발하길잘햇다 2021. 3. 18. 00:37
반응형

가장 긴 증가하는 부분수열(LIS)

DP 문제이다.

풀이 방법을 그림으로 자세히 보려면 아래 블로그를 참고하면 된다.

 

https://bitwise.tistory.com/215

 

포스팅 목적은 풀이 방식을 코드로 표현한 부분이 잘 이해가 되지 않아서 시작하게 되었다.

 

LIS(시작전)
LIS(완료)

# 그림 설명

1. 입력값 배열에 맞는 DP 배열을 처음에 1 값으로 모두 세팅을 해둔다.

2. 입력값 배열과 DP 배열을 이용해서 조건에 맞는 부분만 카운트를 증가시켜 준다.

    (여기서 말하는 조건 : 이전 값들과 비교해서 자신이 크면 작은 값들의 DP값 중 가장 큰 값에 +1 한 값을 갖는다.)

 

3. 좌측 부터 우측으로 입력값 배열을 하나씩 보며 넘어감

  (예를 들어 입력값 배열의 값이 동그라미 친 '20' 인 경우)

20의 좌측 값들 중 20보다 작은 값은 '10' 이므로 10에 해당되는 'DP 배열' 값(1)에 +1 해준다.

(그래서 2가 됨)

 

4. 이번엔 30을 예로 들어 보겠다.

  • 30 보다 좌측에있는 값들 중에 30보다 작은 모든 값들과 비교를 한다.
  • 그러면 10 보다는 크고 이어서 20보다도 크기 때문에 가장 큰 DP값을 가진 20의 DP 값에서 +1 해준다.
  • 사이에 껴있는 10은 가지고 있는 DP값이 좌측 20의 DP값보다 작기때문에 탈락이다.
  • 그러면 30의 값은 3이 된다.

연습 : 동그라미가 쳐져있지 않은 20의 DP 값을 매겨보기

좌측에 20보다 작은 값들은 '10', '10' 두개 뿐이다. 이 둘 중에 DP 값이 큰 값에 1을 더해서 가지면 되는데 둘 다 1이므로 (1 + 1)이 되어 2의 DP값을 갖는다.

5. 마찬가지로 마지막 '50' 까지 일련의 과정을 수행한다.

  •   여기서 DP의 값이 곧 증가하는 수열의 길이가 된다.

# 한줄 요약


   입력값 배열에서 해당되는 값보다 좌측에 있는 작은 수들 중, DP값이 가장 큰 값을 고르고 그값에 +1 해주면 됨.  

(DP 값이 가장 크다는 말은 증가해온 수열의 길이가 가장 긴 것일 테니 거기에 더 길게 해서 가장 긴 상태로 만들어주는 것)

 

 

코드

from sys import stdin

N = int(input())
nums = list(map(int, stdin.readline().split()))

dp = [1]*N

for i in range(N):
    for j in range(i):
        if nums[j] < nums[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

코드 의미

# N = 6 [range: 0~5]
for i in range(N): 

    # i 가 0일때 j는 1번, 1일때 j는 2번, 2일때 3번반복... 
    # 즉 위치가 옮겨질때마다 자기위치숫자포함 지나온 숫자들만큼 반복을 돌면서 확인한다.
    for j in range(i): 
        # i 가 지나쳐온 숫자들과 일일히 비교하고 앞에 숫자들중 작은게 있을때마다 
        # 여기 if문에 들어와서 dp[i] 값 후보중 가장 큰값을 입력한다.
        if num_list[j] < num_list[i]:      
            dp[i] = max(dp[i], dp[j] + 1)   


# 후보들은 
# dp[i] : 시작부터 1로 dp 전체를 초기화했으니 1일것이다.
# dp[j] + 1 : 이전 값보다 커서 여기 조건에 왔으니 앞에 갚(카운트)보다 +1 해준것

# 그럼 전부 dp[j]+1 이 되는거 아니냐?

# 아닌 경우가 생긴다. ex.동그라미 안쳐진 값을 지나칠때

# 예시

# i = 값이 '30'인 곳

# j = '30'보다 좌측에 있는 모든 값들(우측으로 이동하면서 비교계속해나감)

# 30보다 작은 좌측값들은 10, 20, 10 이 있음

# j 가 처음 10 위치일때 dp[3] = max(dp[3], dp[0] + 1) 이 들어가고 비교를 할것임. 

# 그러면 아무것도 없는 4번째는 dp[0]+1 에 해당 될것이고 / *dp[0] = 1

# dp[3] = 2의 값을 임시로 갖게됨.

# 그리고 이제 j가 우측으로 한칸 더 움직여 '20'으로 가게 되면 다시 조건에 들어갈테고 

# 이때는 dp[3]=2 상태로 들어감 *[이후에 괄호()로 추가 표시하겠음]

# dp[3](2) = max(dp[4](2), dp[2](2) + 1) 그럼 당연히 큰건 후자(3)

# 다시 dp[3]의 값은 3으로 조정됨 그리고 j 는 다시 우측으로 이동해서 1로 감

# 그럼 다시 조건문에 들어가고 dp[3](3) = max(dp[3](3), dp[3](1) + 1) 둘을 비교하면 

# 이때는 dp[3] 이게 더 큼

# 이런식으로 쭉쭉 가중치를 가져가면서 DP 로 올라가게 되어지고 그림처럼 DP배열이 채워짐
반응형