[WEEK04] DAY30

DAY30

2021.11.30 TUE

컴퓨팅 사고로의 전환 마지막 주가 지나고 있습니다.
어떠신가요? 이미 소프트웨어 개발자가 된 것 같나요? 아직 뭐가 뭔지 모르겠나요?

1. 혹시 아직도 뭐가 뭔지 모르겠다면
   내가 생각한 것을 프로그램으로 만들 수 있는지 자기 자신에게 질문해 보십시오.
   이 과정의 가장 근본적인 목표는 내가 원하는 작업을 컴퓨터에게 시키는 능력을 키우는 것입니다.
   일단, 내가 원하는 것을 컴퓨터에게 쉽게 시킬 수 있다면 잘 따라가고 있다고 생각합니다.
   미래에 내가 원하는 것, 해내야 할 작업이 뭐가 될지 모르기 때문에 정형화된 문제들로 연습하는 것이고
   이왕이면 효율적으로 빠르게 컴퓨터에게 일을 시키기 위해
   계산 복잡도를 고려하고, 문제 유형을 나누어 익히고,
   정해진 시간 안에 프로그램을 짜는 연습을 하는 것입니다.

2. 눈치 빠른 분들은 알고 계시겠지만 각 주의 keyword 들은 서로 연관이 있습니다.
   분할 정복은 재귀함수로 구현하기 좋습니다.
   이분 탐색은 분할 정복의 한 가지 방법입니다.
   재귀 함수를 반복문(loop)으로 바꿀 때 스택을 사용하면 쉽게 바꿀 수 있습니다. (문제에 따라서는 스택을 안 쓰고도 바꿀 수 있습니다.)
   DFS는 재귀로 구현하면 매우 쉽게 구현할 수 있고 반복문으로 구현하려면 스택을 사용하면 됩니다.
   BFS를 구현할 때 큐(queue)를 사용하며, 큐를 priority queue로 바꾸면 Dijkstra 알고리즘이 됩니다.
   DP(dynamic programming)도 분할 정복을 구현하는 방법들 중 한 가지 방법이며, 따라서 재귀 함수로 구현하기 좋습니다. (솔직히 점화식이 보이는데 이걸 깨닫지 못한다면...)
   DP 문제를 단순 재귀 함수로 구현하면 같은 함수가 여러번 불리는 경우가 있으므로 한번 계산한 함수는 그 결과값을 저장하는 기법을 사용하는데 그 기법을 memoization이라고 부릅니다.
   1주차의 완전탐색 문제를 3주차에 다시 보면 문제의 graph를 탐색하는 방법으로 생각할 수 있다는 걸 깨달을 수 있습니다.
   각각의 풀이 방법을 외우려고 하지 않고 이런 연관성을 가지고 보면, 컴퓨터로 풀 수 있는 문제의 모양을 보는 데 도움이 되리라고 생각합니다.

3. DP에 대해서 좀 더 이야기 하자면 
   k-차원 array를 만들고 array를 채워 나가는 DP의 풀이 방식, 소위 bottom-up 방식의 풀이는 가끔 이해하기 어려운 경우가 있습니다. 사실 bottom-up 방식은 재귀를 이용한 top-down 방식을 (stack 없이) 반복문으로 만든 겁니다. 이렇게 만들어 놓고 보면 상당량의 최적화, 특히 공간 최적화를 더 할 수 있는 경우가 많기 때문에 이 방식의 풀이를 좋아하시는 분들이 계신데... 일단은 이해가 중요합니다. 이해 할 수 있는 풀이를 먼저 찾는 것을 권장합니다.
   Python은 cache decorator를 제공하여 top-down DP 구현을 쉽게 만듭니다. (function argument == array index)
   "점화식을 알면 DP를 쉽게 짤 수 있는데 점화식을 어떻게 만들지 모르겠다"라고 하시는 분들 계실텐데, 맞습니다. 점화식을 만드는 것 자체가 문제를 푸는 것이고, 좀 더 정확하게는 문제를 어떻게 잘 자를 수 있는가를 찾는 과정입니다. 사실 1주차 재귀, 2주차 분할정복에서부터 필요했던 능력입니다.
   가끔 보면 문제를 딱 보고 어떻게 자르면 되는지 알아차리기를 원하시는 분이 계시는데, 그 정도의 능력은 저는 재능의 영역으로 봅니다. 솔직히 이게 되면 못 풀 문제 없죠. 특정 사람들만 알아듣는 말로 "직사의 마안"을 가졌다고 표현합니다. 그렇다고, 노력해도 기를 수 없는 능력이냐 하면... 뭐, 하다 보면 늘기는 합니다.

다음 주 부터는 다른 과정이 시작됩니다.
컴퓨팅 사고로의 전환 마무리 잘 하시길 바랍니다.

.
.

2098 외판원 순회 (DP)

2진법이 나올 줄은 몰랐지...

9251 LCS (DP)

코드

import sys

string1 = ' ' + sys.stdin.readline().rstrip()
string2 = ' ' + sys.stdin.readline().rstrip()
LCS = [[0 for _ in range(len(string2))] for _ in range(len(string1))]

for i in range(1, len(string1)):
    for j in range(1, len(string2)):
        if string1[i] == string2[j]:
            LCS[i][j] = LCS[i - 1][j - 1] + 1
        else:
            LCS[i][j] = max(LCS[i][j - 1], LCS[i - 1][j])

print(LCS[-1][-1])

.
.

2253 점프 (DP)

코드

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
TF = [True for i in range(n + 1)]
for i in range(m) :
    TF[int(input())] = False
jump = int((2 * n - 2) ** 0.5) + 1
DP = [[n for i in range(jump + 1)] for i in range(n + 1)]
DP[1][0] = 0
for i in range(2, n+ 1) :
    if TF[i] :
        jump = int((2 * i - 2) ** 0.5)
        for j in range(1, jump + 1) :
            if i > j :
                DP[i][j] = min(DP[i-j][j-1], DP[i-j][j], DP[i-j][j+1]) + 1
ans = min(DP[n])
if ans == n :
    print(-1)
else :
    print(ans)

이건 지훈오빠의 설명을 들었다.