[모의고사] DP 1회차 복기

• 주제: DP
• 시간: 2시간
• 4/2
• DP 모의고사인데 DP로 푼 문제가 하나밖에 없다 ㅋㅋ…

문제 1: 추월

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

import sys
input = sys.stdin.readline

def isSkipped(idx, before, after):
    for bIdx in range(idx):
        if after[before[idx]] < after[before[bIdx]]:
            return False
    return True

def solution():
    n = int(input())
    before = dict()
    after = dict()
    for idx in range(n):
        number = input().rstrip()
        before[idx] = number
    
    for idx in range(n):
        number = input().rstrip()
        after[number] = idx
    
    skipped = 0
    for idx in range(n):
        if not isSkipped(idx, before, after):
            skipped += 1

    return skipped

print(solution())

• 완전탐색으로 풀었다. 터널 전의 인덱스와 터널 후의 인덱스를 비교할 때, 자신보다 앞에 있던 차들보다 인덱스값이 증가했다면 무조건 추월차량이다. 시간복잡도는 O(n^2)이다.

다시 풀기

• 뭐야..? 분류가 DP가 아닌뎈ㅋㅋㅋ..? 해시 사용했으니 맞게 푼 거라고 해주라…

문제 2: 행운의 문자열

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

• 풀다가 시간이 없어서 종료된 뒤에 풀었다.

import sys
input = sys.stdin.readline

def recursion(pre, l, d):
    answer = 0
    if l == n:
        return 1
    
    for i in d.keys():
        if d[i] == 0 or i == pre:
            continue
        d[i] -= 1
        answer += recursion(i, l + 1, d)
        d[i] += 1
    
    return answer

def solution():
    global n
    s = list(input().rstrip())
    n = len(s)
    d = dict()
    for i in s:
        d[i] = d.get(i, 0) + 1

    return recursion("", 0, d)

print(solution())

• 경우의 수에만 집중해서 처음에는 고유한 문자열이 n개일 때 n!, 고유한 문자로만 만든 문자열에 나머지를 덧붙이는 방식을 생각했는데, 구현 자체가 좀 더러워져서 다른 답을 찾아봤다.
• 우선 위처럼 완전탐색을 하면 아슬아슬하게 통과한다.
• 추가로 모든 문자열이 고유할 경우, 행운의 문자열은 n!이다. 어떤 방식으로 문자열을 연결해도 전부 행운의 문자열이기 때문이다. 팩토리얼을 구현하면 시간이 절반 이상 줄어든다.
• 파이썬 풀이를 찾아보다가, 다른 풀이보다 말도 안 되게 빠른 코드가 있어서 봤더니 캐시를 사용하는 방식이었다.
  • 처음에 문제를 풀 때 메모이제이션을 어디에 적용해야 할지 고민했는데, 접두사를 키값으로 했더니 실제 경우의 수보다 캐시 테이블이 더 커지는 문제가 생겼다… 실제 경우의 수는 길이가 n인 문자열만 세는데 캐시 테이블은 길이가 1부터 n인 문자열을 전부 세서 생기는 문제였다. 즉 캐시 미스가 날 가능성이 높다는 얘기이다. 실제로 캐시를 사용하지 않은 방식보다 시간이 더 걸렸다…
    • 다시 생각해보니 캐시를 사용할 일이 없었다. 접두사는 현재까지 선택한 문자열이지 앞으로 선택할 때 필요한 정보가 아니다…
  • 대신 발견한 방법에서는 접두사 대신 현재 문자열과 아직 선택하지 않은 원소들을 튜플화해 키값으로 사용했다. 대신 순서를 동일하게 가져가야 하므로 정렬을 사용했다. 즉 현재 기준 제일 마지막에 있는 문자열과 남아있는 문자열들은 여러 번 같은 연산을 반복할 가능성이 높다. 정렬을 유지한 채로 캐시값을 저장하므로 중복되는 (’A’, 1, ‘B’, 0)과 (’B’, 0, ‘A’, 1)이 다르게 저장되지도 않는다.
    • 공간이나 시간복잡도도 문제가 되지 않는다. 문자열의 길이가 최대 10이기 때문에, d의 크기도 최대 10이다(애초에 전부 고유할 경우 팩토리얼로 처리하기 때문에 10이 나올 일도 없다).
• 배운 점은 캐시 테이블을 딕셔너리로 사용할 수 있다는 점이다. 메모이제이션을 사용할 때는 중복 호출이 많이 일어나는 경우를 주로 생각하면서 찾아 보자.

문제 3: 가장 큰 증가하는 부분 수열

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

• 증가부분수열의 변형 문제이다. 종만북에 나왔던 풀이를 기반으로 재귀함수를 작성했다.

import sys
input = sys.stdin.readline

def recursion(n):
    if cache[n] != -1:
        return cache[n]
    
    ret = 0
    for i in range(n + 1, N):
        if a[n] < a[i]:
            ret = recursion(i)
            cache[n] = max(cache[n], ret + a[n])
    cache[n] = max(cache[n], a[n])
    return cache[n]

def solution():
    global a, cache, N, maxSum
    N = int(input())
    a = list(map(int, input().split()))
    maxSum = [0] * N
    cache = [-1] * N
    for i in range(N):
        recursion(i)
    return max(cache)

print(solution())

복기하기

• 제대로 설계하고 짠 게 아니라 조금 즉석으로 코드를 짜서 디버깅하는 데 시간이 좀 걸렸다… 일단 다시 구조를 세워 보자.
  • recursion(n)은 n을 포함하는 증가하는 부분 수열의 합 중 가장 큰 값을 반환한다. 1 ~ N까지 cache값이 가장 큰 값이 전체 문제의 최댓값이다.
  • 본인보다 큰 값이 나올 때마다 재귀를 호출해 현재까지의 최댓값과 비교한다. 메모이제이션을 사용해 중복 호출을 줄인다.
  • 중요한 점은 배열의 맨 앞에 [0]을 패딩 처리하는 부분이다. 처음 제출한 코드에서는 해당 부분 없이 반복문으로 매 인덱스별 시작으로 하는 recursion을 호출했는데, 패딩을 0 으로 주면 무조건 0번째 인덱스에서 시작하게 된다. 또한 합을 구하는 문제이므로 정답에도 영향을 주지 않는다.
    • 패딩을 주지 않으면 예시로 100 1 2 98 99의 경우 100 이상으로 넘어가지 않아 정답이 200임에도 100을 반환하는 오류가 생긴다.
    • 사실 반복문을 사용해도 캐시 덕분에 큰 시간 차이가 생기지는 않는다.

문제 4: 최대공약수

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

• 시간 내에 못 풀었다.
• A와 B의 최대공약수를 구해 1을 그만큼 반복하면 정답이 나온다고 한다… 이런 걸 코테에서 풀고 있어야 할까

import sys
input = sys.stdin.readline

def gcd(a, b):
    if b == 0:
        return a
    
    return gcd(b, a % b)

def solution():
    a, b = sorted(map(int, input().split()))
    return gcd(a, b) * "1"

print(solution())

• 뭐지 DP로 문제 검색했는데 자꾸 이상한 애들이 튀어나온다…