끄적끄적

유형 : dp

 처음에는 dfs를 이용하여 모든 경로를 탐색했으나 당연히 시간초과가 나왔다.

문제풀이

1. dp를 활용해야 하는데, dp[r][c]는 (r,c)에 올 수 있는 경우의 수이다. (r,c)에서 갈 수 있는 길이가 a라 하면, (r+a,c), (r,c+a) 두 가지 경우가 가능하다. 두 경우 가능한 경우의 dp 값에 dp[r][c]를 더해주면 된다.

2. 1의 과정을 (0,0)부터 (n-1,n-1)까지 반복한다.

요약

 모든 경로를 다 고려할 필요 없이, dp를 이용하여 (r,c)에서 (r',c')으로 이동한다고 하면, dp[r'][c'] += dp[r][c]를 해주면 중복되는 경로들을 다시 탐색하지 않아도 된다.

Python Code

line 3 : 0,0에서 시작할 것이니, dp[0][0]은 0이 아닌 1로 해주어야한다.

line 7 : (r,c)에서 갈 수 있는 경우가 0이거나 (r,c)에 도착 할 수 있는 경우의 수가 0이라면 고려할 필요가 없다.

line 12, 14 : 위에서 언급한 dp[r'][c'] += dp[r][c] 과정.

 길이가 N인 정사각형에 대하여 이중 포문을 도므로 시간복잡도는 O(N^2)이 된다.

문제 링크

유형 : dp

첫번째 오답

 동전들의 가치가 1, 2, 5로 주어지는 경우를 예로들면, 단순히 가치 i를 만드는 경우의 수 dp[i] = dp[i-1]+dp[i-2]+dp[i-5] 로 만드는 경우에는, 중복된 경우를 따로 카운트하게 되어 오답이 된다. 예를들면 i=3 인 경우를 예로 들면, dp[2]+dp[1]이 되는데, dp[2]를 사용하는 경우를 살펴보면, dp[2]는 1을 두개 쓴 경우와 2를 한개 쓴 경우 해서 2가지가 되고, 여기에 1을 한개 더 사용하여 3을 만드는 경우이므로 총 2가지 (1을 3개), (1을 1개, 2를 1개)가 된다. dp[1]은 1을 한개 사용하는 경우 한가지가 존재하고, 여기에 2를 한 개 사용하여 3을 만드는 경우가 되므로, (1을 1개, 2를 1개) 한가지가 된다. 따라서 dp[3] = 3 이라고 계산하게 되는데, 위의 세가지를 살펴보면 (1을 1개, 2를 1개) 가 두번 세어진 것을 알 수 있다. 즉, 1을 먼저 쓰고 2를 쓴 경우와, 2를 먼저 쓰고 1을 쓴 경우를 다르게 체크하는 것이다.

 따라서 이러한 중복되는 경우의 수를 피하기 위해 아래에서는 n 종류의 동전만을 사용하는 경우를 나누어서 계산하게 된다.

풀이 및 두번째 오답

 먼저 dp를 n x k+1 사이즈의 리스트로 선언한다. dp[n][k]는 첫 n+1개의 코인(0부터 세니까)을 사용하여 가치 k를 만드는 경우의 수이다. dp[0]의 경우에는 첫번째 동전만을 사용하는 경우이므로, dp[0]의 경우,

[1]+[1 if i%coin[0]==0 else 0 for i in range(1,k+1)] 로 초기화 해준다. 즉, k가 coin[0]으로 나누어지는 경우에만 가치 k를 첫번째 코인만으로 만들수 있다. 그 후의 점화식은 아래와 같다.

$dp[i][j]=\begin{cases}dp[i-1][j], & \mbox{if j < coin[i]} \\ dp[i][j-coin[i]]+dp[i-1][j], & otherwise\end{cases}$

 첫 경우는, 만드려는 가치 j가 i번째 코인의 가치보다 작은 경우로, 이러한 경우에는 i번째 코인을 사용할 수 없으므로, 전의 것을 그냥 사용하면 된다. 두번째 경우에서 dp[i][j-coin[i]]는 i번째 코인도 사용해서 가치 j-coin[i]를 만든 후에 i번째 코인을 사용하는 경우이고, dp[i-1][j]의 경우에는 i번째 코인을 사용하지 않는 경우가 된다. 이렇게 계산하면 위의 오답의 예를 다시 살펴보면 dp[1][3] (첫번째, 두번째 코인을 사용하여 가치 3을 만드는 경우의 수)는 dp[1][1] + dp[0][3] 이 된다. dp[1][1]의 경우에는 dp[0][1]로 주어지므로, 1이 되고, dp[0][3] 역시 1이므로, 위와 같이 중복된 경우는 세지 않을 수 있다. 

Python Code

코드로 나타내면 다음과 같은데, 문제는 dp의 공간 복잡도가 $O(n\dots k)$가 되어 메모리 초과가 된다.

공간복잡도 줄이기

 그런데, 위의 코드를 살펴보면 실질적으로 dp[i][j]를 계산하는 13, 15 line에서 dp[i-1][j]가 계속 반복되는 것을 볼 수 있다. 즉, dp를 길이 k+1인 리스트로 선언한 후 15번째 줄의 우항의 마지막 항을 버리면 된다.

Python Code

문제링크

유형 : dp라고 쓰여있지만 완전탐색...

문제풀이

 10,21,321 처럼 큰 자리의 숫자가 작은 자리의 숫자보다 큰 숫자를 구하는 문제로, 결국 [0,1,2,3,4,5,6,7,8,9] 만들 수 있는 모든 subset을 구하는 문제와 동일하다.

 무슨 말인가 하니, 위의 0 ~ 9 숫자 중 중복되지 않는 n개의 숫자를 뽑으면 그 숫자들로 만들 수 있는 감소하는 숫자는 1개밖에 존재하지 않는다. 예를 들어 1,3,5를 골랐다면 531 이외의 가능한 감소하는 수는 없다. 따라서 1 ~ 9로 만들수 있는 감소하는 수의 총개수는 $2^{10} -1$ 개가 되는데, 그 이유는 0 ~ 9 총 10개의 숫자 모두 선택한다, 안 한다 두 개의 경우가 존재하기 때문이다. 따라서 입력값 n이 1024 이상인 경우에는 -1을 반환하면 된다(실제 구현할 때는 0부터 셈으로 1023 이상). 1023 이하인 경우에는, 10개의 숫자 중 뽑는 n개의 숫자를 1개부터 10개까지 늘리며 모든 가능한 조합으로 숫자를 만든 후, 정렬하여 n번째 수를 반환하면 된다.

Python Code

21 line 은, depth번째 수 i 로 가능한 것들의 조건인데, i는 depth-1보다는 작아야 하고, 앞으로 digit-depth 만큼의 수를 더 뽑아야 하기 때문에, 뒤에 digit-depth만큼의 수는 남겨두어야 한다.

29 line의 digit이 위에서 말한 n(몇 개를 선택할 것인지로 몇 자릿수의 숫자를 만들지를 의미)이다.

문제 링크

유형 : dp

문제풀이

* 지금 설명할 풀이는 효율이 좋지 못합니다.

 b 도시에 i번째로 도착했을 때, 가능한 기내식 점수들의 합은 dp[a][i-1]+air[a][b] 가 됩니다. (air[a][b]는 a에서 b 구간 비행기의 기내식의 점수)

 따라서 dp[b][i]의 점화식은 아래와 같이 쓸 수 있습니다.

 dp[b][i] = max(dp[a][i-1]+air[a][b] for b보다 작은 모든 a)

 다만 위의 식을 진행하는 데에 있어서, i-1번째로 a에 도착한 경우와 a에서 b구간의 비행기가 있다는 조건을 위한 조건문이 추가로 들어가야합니다.

 위의 점화식을 b를 n까지, i는 m까지 반복 한 후, dp[n]의 최댓값을 반환하면 됩니다.

Python Code

line13에 try 문이 들어간 이유는 if문을 만족하는 a가 하나도 없는 경우 max함수에서 에러가 발생하기 때문입니다.

문제링크

유형 : dp

문제풀이

 포도주 시식 문제와 유사하지만, 마지막 계단을 반드시 밟아야한다는 제한이 있다. 

 따라서 i번째 계단의 점수가 s[i]라 하면, i번째 계단을 밟았을 때의 최대 점수 dp[i]는 다음과 같이 주어진다.

 dp[i] = max(dp[i-2]+s[i], dp[i-3]+s[i-1]+s[i])

 즉, 2칸 전 계단을 밟고 이번 계단을 밟거나, 3칸 전 계단을 밟고 전칸을 밟고 이번 계단을 밟거나 두가지 조건이 가능하다.

list 초기화와 append

 위의 문제를 해결하는데 있어서, dp를 먼저 빈 list로 선언한 후 append로 하나씩 채워갈 수도 있고, dp를 길이가 n인 리스트로 선언한 후, i번째 요소를 바꿔가는 방법이 있는데, 후자가 효율적이다. 전자로 통과한 후, 후자의 방법으로 바꾸었더니 80ms 에서 56ms로 줄었다.

Python Code

유형 : dp

카드 n장을 살 때, 지불할 수 있는 최대 금액을 구하는 문제이다.

풀이과정

 카드 i 장을 구매하는데 필요한 금액을 dp[i] 이고, 카드 n장이 들어있는 팩의 가격이 p[n]라 하면, dp[i]는 아래와 같다.

 dp[i] = dp[i-n] + p[n]

 가능한 모든 n에 대하여 dp[i]가 최대값이 되도록 update해나가면 된다.

Python Code

유형 : 그리디

빨리 끝나는 회의부터 처리해야 한다. 이때, 끝나는 시간이 똑같은 회의의 경우, 시작 시간이 빠른 회의부터 처리한다.

코드

import sys

n=int(sys.stdin.readline())
times = []
for _ in range(n):
    times.append(tuple(map(int,sys.stdin.readline().split())))
  
times.sort()
times.sort(key=lambda x: x[1])
now,ans=0,0
for time in times:
    if time[0]>=now:
        ans+=1
        now=time[1]
print(ans)

정렬

 위의 코드에서는 times.sort()로 회의 시작 시간을 기준으로 정렬을 한 후, 회의 종료 시간을 기준으로 한번 더 정렬을 함으로써 위에서 언급한 규칙을 만족시켰다.

 하지만, 아래와 같이 comparator를 직접 정의함으로써 한번에 정렬할 수도 있는데, 내장함수로 두번 정렬하는 위의 방법이 훨씬 효율적이었다. ( 위의 방법 : 메모리 44944kb, 시간 328ms, 아래의 방법 : 메모리 50360kb, 시간 552ms)

from functools import cmp_to_key

def compare(x, y):
    if x[1] < y[1] :
        return -1 
    elif x[1] > y[1] :
        return 1
    else: 
        if x[0] < y[0] :
            return -1
        else:
            return 1
times.sort(key=cmp_to_key(compare))

문제풀기

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

유형 : dp

 LIS(Longest Increasing Subsequence)로 알려진 유명한 문제이다. 주어진 배열에서 몇 개의 요소들을 제거하여 만들 수 있는 가장 긴 증가하는 수열을 찾는 문제로, 배열이 [1,3,5,2,1,6] 으로 주어진 경우 [1,3,5,6]이 가장 긴 증가하는 부분 수열이 된다.

 아래의 풀이는 나무위키의 최장 증가 부분 수열을 Python으로 구현한 것이다.

 풀이를 살펴보면, 먼저 시간복잡도를 O(nlogn) 으로 하기 위해서는 이진탐색을 활용해야하므로, 먼저 이진탐색을 정의한다. bin_search 함수는 이진탐색으로 원하는 값보다 같거나 큰 가장 작은 수의 인덱스를 반환한다. dp[i]는 i+1번째 요소까지를 고려했을 때 가장 긴 부분 수열의 길이가 되며, p_i[i]는 길이가 i인 증가하는 부분수열의 마지막 수(가장 큰 수)이며, 이 값을 가장 작게 유지하는 것이 나중에 유리하다는 것을 알 수 있다.

풀이과정

1. bin_search를 통하여 p_i에서 a보다 크거나 같은 가장 작은 수의 인덱스를 찾는다(idx).

2-1. 이 idx가 배열 p_i의 길이와 같다면, 이는 가장 큰 수가 들어왔다는 것으로, 가장 긴 증가하는 부분 수열의 뒤에 붙으므로써 가장 긴 증가하는 부분 수열의 길이가 1 증가하게 된다. 즉, dp에는 idx 값을 넣어주고, p_i 에는 a 값을 추가로 넣어준다.(p_i의 길이가 늘어났다는 것은, dp의 최댓값 역시 늘어났다는 것을 의미한다.) 

2-2. idx가 배열 p_i의 길이보다 작다면, 이는 a 값을 마지막으로 하는 증가하는 부분 수열은 기존의 부분 수열보다 길이가 크지 않다는 것이고, idx는 a를 마지막으로 넣었을 때 만들수 있는 가장 긴 부분 수열의 길이를 나타낸다. 이 때, 기존의 길이가 idx인 부분 수열의 마지막 보다는 a가 작거나 같으므로 p_i[idx]의 값을 a로 바꾸어준다.

3. 이렇게 모든 요소에 대하여 반복한 후 dp의 최댓값을 반환한다.

시간복잡도

 1의 과정(이진탐색)의 시간 복잡도가 logn이고, 이 과정을 모든 요소에 대하여 반복해야 하므로 총 n번 진행하면 된다. 따라서 시간복잡도는 O(nlogn)이 된다.

코드

import sys

#t보다 크거나 같은 가장 작은 수 반환
def bin_search(arr, t):
    l=0
    r=len(arr)
    if t > arr[-1]:return len(arr)
    elif t<arr[0]:return 0
    mid = (l+r)//2
    while l<=r:
        if arr[mid] > t:
            r=mid-1
        elif arr[mid] < t:
            l = mid+1
        else:
            return mid
        mid = (l+r)//2
    return mid+1

n=map(int,sys.stdin.readline())
a_i = list(map(int,sys.stdin.readline().split()))

dp=[0]
p_i=[0]

for a in a_i:
    idx = bin_search(p_i,a)
    # 가장 큰 수가 들어왔다
    if idx == len(p_i):
        p_i.append(a)
    else:
        p_i[idx] = a
    dp.append(idx)
print(max(dp))

문제 풀기