Koala 2주차 : DP(동적계획법)과 LIS(최장부문 증가 수열)

 

본격적으로 이번주차 공부를 시작하기 전에 그 전 주의 피드백을 진행해야 될 것 같다.

 

일단 가장 큰 문제는 내가 알고리즘 공부를 잘못하고 있었다는 것이고, 제대하고 나서 오랜만에 코딩을 한다고 해도 저번주는 코딩에 시간을 많이 쏟지 못한 부분인 것 같다. 잘못 공부한다는 것은 많이 고민하지 않고 잘모르겠으면 일단 솔루션을 계속 외우는 식의 공부를 했는데, 그 문제만 맞추고 다른 유형의 새로운 문제를 봤을 때 창의적으로 문제를 해결하는 능력이 떨어진다는 것을 알게 되었다. 또한 재귀함수가 너무 어렵고 내가 잘 못다룬다는 것도.

 

따라서 이번주부터는 모르는 문제는 구글을 통해 솔루션을 보고 암기를 하되, 배우는 유형에 대해서 이런 부분에서 이런 알고리즘을 이용해야 겠다는 생각을 해야하며 그 이후에 풀이 과정들은 구현의 영역에 더 가까움으로 문제 풀이 수를 늘려야겠다는 셀프 피드백을 진행하게 되었다.

 

코알라 스터디에서 매주 주말마다 진행되는 모의 테스트는 정말로 테스트처럼 보고자 한다. 5문제 정도 있는데, 최대 5시간 정도 잡고 구글로 솔루션을 보지 않고 풀 수 있는 것들만 해결한 후 그 다음주에 못 푼 문제들에 대해서 리뷰하고자 한다. 첫 주는 5문제 중 아무 문제도 맞히지 못했지만, 앞으로는 점점 더 나아지는 모습을 스스로 기대해본다.

 

 

 

 

* DP 관련 백준 문제

 

1. 1463 : 1로 만들기

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

 

n = int(input())
dp = [0]*(n+1)

for i in range(2,n+1):
    dp[i] = dp[i-1]+1
    if i%2==0:
        dp[i] = min(dp[i//2]+1, dp[i])
    if i%3==0:
        dp[i] = min(dp[i//3]+1, dp[i])

print(dp[n])

 

4달 전에 풀어본 문제인데 다시 보니 막혔었다. 문제를 풀지 못했을 때 단순히 코드를 암기하는 것이 아니라 다음에 비슷한 유형이 나왔을 때 그 유형인지 아닌지를 판별할 수 있는 능력과 그러한 유형들을 새로운 문제로 보았을 때 해결하는 힘이 필요한 것 같다.

 

여기서 약간 헤멘 부분은 if i%3==0을 eilf i%3이라고 한 점이다. 6 같이 2와 3 둘다 나눠떨어지는 수는 2와 3(보통 이 문제에서는 3으로 나누는 것이 합리적)을 둘 다 체크해봐야하기 때문에 eilf가 아니라 if 로 봐야했다. 

 

10처럼 1을 먼저 뺀 다음 3으로 계속 나누는 것이  효율적인 만큼 그 전단계의 결과가 그 다음 단계의 결과에 영향을 미치는 것을 보아 이 문제는 dp로 해결해야 하는 구나가 생각이 나야 했다. 그다음 메모이제이션(dp 리스트 만들기)을 활용한 다음 단순히 전 단계를 -1하는 것과 2로 나누는 것 3으로 나누는 것을 선택하는 것이 이 문제의 핵심이었다. 

 

 

 

 

 

 

2. 11057 : 오르막 수

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

 

import sys
input = sys.stdin.readline

n = int(input())
dp = [1]*10

for j in range(n-1):
    for i in range(1,10):
        dp[i] = dp[i]+dp[i-1]

print(sum(dp)%10007)

 

 

일단 교훈 : 문제 출력 조건을 잘보자!! 예제도 잘 나오고 아무 문제 없어보이는 코드가 왜 안되나했는데 출력 조건 자체가 10007로 나눈 수를 출력하라고 했다.

 

문제 자체를 이해하지 못해서 구글로 문제만 이해하고 풀기 시작했다. 자릿수가 1일 때는 10, 2일때는 55 ...으로 그 전 자릿수의 자기순서에 해당하는 수와 그 전의 숫자들을 모두 더하면 나오는 문제였다. 여기서 당연하게 dp를 써야하는구나하는 생각을 가져야했다.

 

그리고 나머지 풀이들은 아래 사진으로 대체하겠다.

 

출처: https://velog.io/@black_han26/%EB%B0%B1%EC%A4%80Python-11057-%EC%98%A4%EB%A5%B4%EB%A7%89-%EC%88%98-%EC%A7%81%EA%B4%80%EC%84%B1-vs-%EA%B0%80%EB%8F%85%EC%84%B1

 

 

 

 

 

 

 

3. 9465 : 스티커

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

 

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    ans = 0
    n = int(input())
    list1=[]
    list1.append(list(map(int, input().split())))
    list1.append(list(map(int, input().split())))
    dp = [[0]*n for _ in range(2)]
    dp[0][0] = list1[0][0]
    dp[1][0] = list1[1][0]

    if n ==1:
        ans = max(list1[0][0],list1[1][0])
    elif n ==2:
        ans = max(list1[0][0]+list1[1][1],list1[1][0]+list1[0][1])
    else:
        dp[0][1] = list1[1][0] + list1[0][1]
        dp[1][1] = list1[0][0] + list1[1][1]
        for i in range(2,n):
            dp[0][i] = max(dp[1][i-2],dp[1][i-1])+list1[0][i]
            dp[1][i] = max(dp[0][i-2],dp[0][i-1])+list1[1][i]
            ans = max(dp[0][i],dp[1][i])

    print(ans)

 

 

본격적으로 dp를 사용할 수 있는 부분은 n이 3이상으로 넘어가는 부분이기 때문에 n이 1일 때와 2일때 그리고 3이상일때 구분을 잘해주고, n이 3이상일때 구현하는 부분에서 제일 핵심적인 부분은 가장 마지막 열을 꼭 선택해야 최대가 되는 부분에 있어서 max값을 어떻게 결정해주냐인데 그것에 관련해서는 아래의 블로그의 도움을 많이 받아 이해를 했다.

 

 

 

https://beyond-common-sense.tistory.com/10

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

* LIS, LCS(주어진 리스트에서 감소 혹은 증가 방향으로 최대 부분수열 구하기)

 

1. 11053 : 가장 긴 증가하는 부분 수열

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

 

import sys
input = sys.stdin.readline

n = int(input())
list1 = list(map(int, input().split()))
dp = [1 for _ in range(n)]

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

print(max(dp))

 

풀이방법 : 부분 수열을 구할 때 가장 중요한 구현 포인트는 "이중 for문"을 사용한다는 것이다. 자기 차례(i번째)에서 자기보다 앞 순서와 비교해야 하므로 하나는 범위값(range)을 입력값인 n으로, 그 안에는 i로 두어야한다. 그 후에 if문을 통해서 비교가 가능하다.

 

 

 

 

2.  14002 : 가장 긴 증가하는 부분 수열 4

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

 

import sys
input = sys.stdin.readline

n = int(input())
list1 = list(map(int, input().split()))
dp = [1]*n

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

str = max(dp)
print(str)
ans = []

for i in range(n-1,-1,-1):
    if dp[i] == str:
        ans.append(list1[i])
        str -= 1

print(*ans[::-1])

 

 

위의 문제와 거의 비슷하지만 리스트를 출력하는 과정의 아이디어를 찾는 것이 생각보다 쉽지 않았던 것 같다. dp 리스트의 가장 높은 숫자부터 뒤로 확인하는 for i in range(n-1,-1,-1): 이게 진짜 빡센 듯.

for문은 정말 많이 사용하지만 거꾸로 확인할 때 돌려보는 for문은 잘 사용하지 않아서, 앞으로 참고하면 될 듯하다.

나머지 부분 구현은 그냥 할만했던 것 같다.

 

 

 

 

 

 

 

 

 

 

 

* 테스트 문제

1. 2156 : 포도주 시식

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

 

이 문제의 풀이법을 떠올리기는 상당히 쉬웠는데, 백준 2579번 : 계단오르기(https://www.acmicpc.net/problem/2579)와 문제가 그냥 똑같았기 때문이다. 근데 처음에는 2%에서 틀렸다하고, 고친 이후에는 90%에서 런타임 에러가 났다. 2%에서 틀린 이유는 dp[3]에서 고려해야할 사항이 3가지인데, 1가지를 빼먹어서, 90%에서 런타임에러가 난 이유는 요소의 개수를 고려해서 개수가 1일때, 2일때, 3일때를 따로 빼서 생각해줘야 했는데 그러지 않아서였다.

 

import sys
input = sys.stdin.readline

n = int(input())
list1 = []
for _ in range(n):
    list1.append(int(input()))

dp = [0]*(n+1)

if n>=1:
    dp[1] = list1[0]
if n>=2:
    dp[2] = list1[0]+list1[1]
if n>=3:
    dp[3] = max(list1[0]+list1[2],list1[1]+list1[2],list1[0]+list1[1])

    for i in range(4,n+1):
        dp[i] = max(dp[i-2]+list1[i-1],dp[i-3]+list1[i-2]+list1[i-1],dp[i-1])

print(dp[-1])

 

 

 

2. 1890 : 점프

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

 

이 문제를 해결하면서 제일 좋았던 건 행과 열을 이중 for문으로 탐색해야할 경우가 요즘에 많이 생겼는데 어떻게 해야할지를 명확하게 배운 것이다. 바깥쪽 for문에 행의 개수만큼, 안쪽 for문에 열의 개수만큼 반복문을 돌려주면 된다!

이 문제를 보고 dp보다는 저번주에 했던 백트래킹이 먼저 생각났다. 그런데 이건 가지치기 유형이 아니라 갈 수 있는 경우의 수를 모두 구해야 했으므로 다이내믹 프로그래밍을 활용해야 했다. 근데 구현하다가 막힌 부분이 간 부분들은 표시를 할 수 있겠는데 나머지 부분에 걸리면 어떻게해야 하나였는데 그냥 continue로 패스하면 되었다. 

갈 수 있는 부분은 dp리스트를 이용해 갈 수 있는 만큼 count하면 되었다.

 

n행m열의 행렬같은 이중 리스트를 만든 뒤 같은 형태의 dp 리스트를 만들어준다. 그런 다음 종착해야 하는 숫자인 0에 도달하거나 아예도달하지 않은 경우(dp[i][j]가 0일때)를 제외하고 칸 안에서 돌아다닐 수 있는 경우를 고려해 에 리스트에 숫자들을 카운트해준다.

 

그다음 가장 마지막에 있는, n행m열의 숫자를 읽어주면 정답이 된다.

 

import sys
input = sys.stdin.readline

n = int(input())
list1 = [input().split() for _ in range(n)]
m = len(list1[0])
dp = [[0]*m for _ in range(n)]
dp[0][0] =1

for i in range(n):
    for j in range(m):
        k = int(list1[i][j])
        if k==0 or dp[i][j]==0:
            continue
        if i+k<m:
            dp[i+k][j] += dp[i][j]
        if j+k<n:
            dp[i][j+k] += dp[i][j]
print(dp[-1][-1])

 

https://code-angie.tistory.com/12

[백준 BOJ / Python] 1890번 점프 DP

 

여기 위의 블로그에서 나온 그림이 이해하는데 큰 도움을 주었다.