SW정글 7기 3주차 알고리즘 후기

목차

2주 차 시험 후기

3주 차 문제 복기

2주 차 시험 후기

90분간 하, 중, 상 문제를 1문제씩 푸는 시험이다.

하 문제는 숨바꼭질 문제가 나왔는데, 전날에 풀었던 숨바꼭질 2의 쉬운 버전이라서 A가 B를 찾는 가장 빠른 시간만 출력해 주면 되는 문제였다. 그래서 단순히 A가 갈 수 있는 경우의 수를 가지치기한 결과를 큐에 넣어서 돌렸고, bfs 풀이이기 때문에 가장 처음으로 B에 도달하는 순간이 우리가 찾는 가장 빠른 시간이다.

 

중 문제는 PPAP수열 문제였고 못 풀었다. 스택을 사용한 풀이를 고민했지만 답을 구하지 못했다. 풀지 못한 이유는 스택에 문자를 하나씩 쌓아야겠다는 생각은 했지만, 쌓다가 PPAP가 되는 순간을 어떻게 감지할지 생각하지 못했기 때문이다. 스택이라는 자료구조에 사고가 갇혀있었기 때문에 스택의 TOP 지점만 접근할 수 있다고 무의식적으로 생각했었고, 이로 인해 스택을 그저 파이썬의 리스트로 구현했었다는 사실을 인지하지 못했다. 그 결과 스택을 인덱스로 접근할 생각이 떠오르지 않았다.

 

상 문제는 각 도시가 그래프 형태로 있고 트럭은 도시를 방문하면서 짐을 날라야 한다. 이때, 도시 사이에 연결된 간선이 있고, 트럭의 무게가 간선의 가중치를 초과하면 다리(간선)가 무너지기 때문에 트럭은 가중치 이하일 때만 도시를 넘나들 수 있다. 이때 A도시에서 B도시로 트럭이 짐을 싣고 갈 때 가장 많이 실을 수 있는 짐의 무게를 구하는 문제다. 처음에 문제에 접근할 때는 시간을 생각하지 않고 단순히 BFS를 돌렸다. 이 BFS는 "A에서 모든 도시로 출발할 때, 도착 도시별 최저 가중치를 저장하는 배열 ARR"을 채우게 된다. ARR[4] = 4라면, A에서 4번 도시로 가는 경로들이 많이 있을 텐데, 이 경로들마다의 최저 가중치들 중, 가장 큰 값이 배열에 저장된다. bfs 내부에서는 최대힙을 사용하여 초기값을 (-무한대, 출발지)로 넣어줬고, 해당 위치와 연결된 다른 도시들을 방문하면서 연결된 간선의 가중치와 ARR[현재 노드] 값 중 더 작은 값을 X로 한 후, X > ARR[다음 노드]인 경우만 ARR을 갱신하고 다시 큐에 넣어줬다. BFS가 끝나고 ARR[도착노드]를 출력해 주면 된다. 결과적으로 이 풀이는 메모리초과가 났다. 최대힙이 넘치는 경우를 방지하기 위해 조건을 많이 달았지만 역부족이었다. 

 

답은 BFS와 이진탐색을 이용했다. 트럭의 중량이 무거워질수록 더 적은 도시만 방문할 수 있고, 가벼워질수록 더 많은 도시를 방문할 수 있다. 따라서 그래프의 x축이 트럭 무게라면 y축에 해당하는 값은 도달 가능의 True, 불가의 False로 2개 뿐이다. 이때 True가 되는 무게 중 가장 오른쪽에 위치한 경우를 구하면 된다. 트럭이 최대로 실을 수 있는 중량은 파라메트릭 서치 기법을 이용해서 해당 무게로 도착지점까지 갈 수 있다면 start, mid, end가 있을 때 start = mid + 1로 해서 다시 이진탐색을 하고, 갈 수 없다면 end = mid - 1을 해주면서 최대 무게를 구할 수 있다.

3주 차 문제 복기

DP 문제들은 거의 대부분 스스로 풀지 못하고 답을 보면서 이해하는 식으로 진행했다.

---

동적 프로그래밍

동적 프로그래밍

피보나치 수 2

피보나치 수는 fn = fn-1 + fn-2이다. 일반적인 탑다운식 재귀호출로 피보나치 수를 구하면 호출이 가지치기되면서 인자가 같은 fk 호출이 반복해서 일어나게 된다. 반복되는 호출 결과를 배열에 저장해 둔다면 해당 인자를 넣은 반환값이 필요할 경우 굳이 호출하지 않고 저장해 두었던 값을 꺼내 사용하면 되므로 시간이 절약된다. 

 

01타일

타일을 채우는 공간을 1에서부터 하나씩 증가시켜 가면서 규칙을 찾아보면, 크기가 1일 때는 1타일 하나만 채울 수 있어서 f1 = 1, 크기가 2면 (11, 00) 따라서 f2 = 2, 크기가 3이면 (111, 100, 001 ), 따라서 총 3개. 그런데 맨 처음에 공간을 채우는 경우의 수는 1짜리 타일 1개를 채우거나 00짜리 타일 하나를 채우는 것 이렇게 2가지뿐이다. dp문제는 기본적으로 분할정복과 재귀의 아이디어가 요구되므로 이 문제에 적용해 보면, 3짜리 크기의 공간의 첫 칸에 1을 채운 이후 남은 2칸에 대해서는 2칸을 채우는 경우의 수를 구하는 것과도 같고, 첫 칸과 둘째 칸에 00을 채웠을 경우 한 칸만 남게 되고 이는 한 칸을 채우는 경우와 같다. 따라서 3칸을 채우는 경우의 수는 2칸을 채우는 경우의 수 + 1칸을 채우는 경우의 수이다. 이제 규칙을 발견했으니 점화식을 세워보면 fn = fn-1 + fn-2이다. 이후로는 이전 문제를 풀 때처럼 값을 저장해 놓고 필요시 받아오면 된다.

 

돌 게임

돌 게임은 참여자가 2명이고, 자신의 턴일 때 무조건 돌 1개 혹은 돌 3개만 가져갈 수 있다. 두 사람은 모두 자기가 이기려고 최선의 수를 둔다. 돌이 2개가 남았다면 1개만 가져갈 수 있고, 3개 이상 남았다면 1개 혹은 3개만 가져갈 수 있다. 규칙을 찾기 위해 돌이 1개 있을 때, 2개 있을 때, 이런 식으로 증가시키다 보면 규칙을 찾을 수 있는데, 먼저 가져가는 사람의 승패를 적어보면, 돌 1개: 승, 2개:패, 3개:승, 4개:패... 이런 식으로 승과 패를 번갈아가면서 하게 된다. 따라서 돌이 짝수개 있을 때는 두 번째로 두는 사람이 이기고, 홀수개 있을 때는 첫 번째로 두는 사람이 이긴다. 이런 식으로 홀짝으로 구하는 방법도 있지만 DP를 이용해서 풀어보면, 우선 DP[i]: 돌이 i개 있을 때 먼저 두는 사람이 이기면 1, 지면 0 인 1차원 DP 배열을 만든다. 이후 i = 3까지는 수작업으로 채워 넣고, 이후에는 규칙대로 넣는다. 규칙은, DP[i - 1]와 DP[i - 3] 둘 중 하나라도 값이 1이면 DP[i] = 0인 것이다. 왜냐하면, 처음에 돌이 i개 있을 때 첫 번째 사람이 1개를 가져간 후, 두 번째 사람이 최선을 다해서 이기는 경우가 있으면 DP[i - 1] = 1이고, 3개를 가져갔는데 두 번째 사람이 이기는 경우가 있으면 DP[i - 3] = 1이라서, 결국, DP[i - 1], DP[i - 3] 둘 중 하나라도 1이기만 해도 두 번째 사람이 이기므로, 첫 번째 사람은 무조건 지기 때문이다.    

 

동전 바꿔주기

동전이 K개 주어지고, 각 동전 별 가치가 주어진다. 이때 T원을 거슬러 주기 위한 동전 조합의 가지 수를 구하면 되는 문제다. 핵심은 각 동전별로 만들 수 있는 금액을 구해서 이를 해당 금액을 만들 수 있는 경우의 수에 + 1을 해주는 것이다. 그런데 이걸 어떻게 구현할 수 있느냐가 문제이다. 답은 2차원 DP 테이블을 만들어서 타깃값을 T부터 1까지 내려가며 DP[money] += DP[money - coin_value]를 해주면 된다. DP테이블의 초기값은 모두 0이고 오직 DP[0] = 1이다. 이렇게 초기값을 설정해주어야 하는 이유는 money == coin_value인 경우 해당 동전만 가지고 원하는 money만큼을 만들 수 있기 때문이다. 이 문제는 동전별 개수까지 주어졌기 때문에 개수도 하나씩 증가시키면서 DP 테이블을 채워 넣어야 한다.

 

동전

이전 문제와의 차이점은 동전의 주어진 개수가 제한이 없다는 것이다. while문을 돌려서 money - value * cnts >= 0일 때까지만 돌려서 풀었다.

 

동전 2

동전의 합이 K가 되도록 하는 문제. 이전, 그 이전 문제는 합이 K가 되는 경우의 수가 몇 개인지를 구하는 문제였다. 지금 문제는, 합이 K가 되는 경우 중 동전을 가장 적게 쓰는 경우를 구하는 문제다.

 

dp[i]: 금액 i를 만드는 데 필요한 최소 동전의 개수

dp[money] = min(dp[money], dp[money - value] + 1)

 

점화식을 만드는 사고과정은 우선 현재 dp에 저장된 dp[money]와 비교할 값을 찾아야 하는데, 만약 동전가치 5원짜리를 사용해서 10원을 만든다고 하면, 해당 동전 이전까지의 동전들로 만든 5원을 만드는데 필요한 최소 개수인 dp[5] 값에다가 5원을 하나 쓰므로 + 1을 해주면 dp[10]을 구할 수 있다. 초기값: dp[0] = 0, 나머지값: maxsize. 동전 하나씩 돌면서 dp를 채워준다.

 

LCS

LCS문제는 알파벳으로 이루어진 두 문자열이 주어졌을 때, 가장 긴 공통부분수열을 구하는 문제다. 부분수열은 서로 인접해 있을 필요가 없다. 이 문제를 풀기 위해서는 두 가지 아이디어가 필요하다. 첫 번째는 문자열을 분할해서 LCS를 만들어보려는 것이고, 두 번째는 어떻게 이 분할해서 얻은 LCS를 다음 LCS를 구할 때 사용하느냐는 것이다. 우선, 두 문자열을 2중 for문으로 돌아보려는 생각은 해야 한다. 이후, 2차원 DP 테이블은 DP[i][j]: 문자열 1은 i번째까지, 문자열 2는 j번째까지 나눴을 때의 LCS 길이이다. 그리고 손수 DP 테이블을 채워나가다 보면 규칙이 보일 수 있다. 문자열1[i] == 문자열2[j]인 경우 오른쪽 위 대각선 위치의 값에 + 1 한 값과 같다는 것이다. 그리고 같지 않을 때는 위와 왼쪽 값 중 더 큰 값을 취한다는 것이다. 이를 이용해서 DP[s1의 길이][s2의 길이] 값까지 구해서 제출하면 된다. 몇 차의 DP 테이블을 만들지, 인덱스에 담는 정보는 무엇으로 할지, 테이블 내에 담기는 값은 무엇을 의미해야 할지, 이후 채워 넣으면서 어떤 규칙을 발견하는지 등 어려운 문제이다. 이런 과정을 먼저 수행하는 게 아니라 S1[i] == S2[j]일 경우, 두 문자열 각각 바로 전 인덱스까지의 문자열로 만들 수 있는 LCS에 + 1을 하면 LCS를 구할 수 있다는 생각을 할 수도 있고, 같지 않을 경우는 S1에서는 i번째를 추가하고, S2에서는 j번째를 빼고 LCS를 구하고, 그 반대로도 해서 LCS 길이를 구한 후 두 값 중 더 큰 값을 취하면 된다는 아이디어도 생각할 수 있지만 어렵다.  

 

LCS 2

이전의 LCS 문제는 LCS의 길이를 구하는 문제였다면, 이 문제는 LCS를 실제로 구해보는 문제다. 2중 for문을 진행하면서 각 상태별 LCS를 저장해 두었다가 테이블이 모두 채워지면 DP[맨밑][맨오른쪽]을 출력하는 방법을 사용할 수도 있고, LCS문제처럼 DP 테이블을 채워 넣은 후 거꾸로 추적해 나가면서 LCS를 찾는 방법도 있다. 전자는 생각하기 쉽지만 시간이 후자에 비해 6배 정도 더 소요되었고, 후자는 떠올리기 어려운 답이었다. 우선, 전자의 방법 같은 경우, 같은 문자를 발견했을 경우 왼쪽 위 대각선에 담겨 있는 LCS에 해당 문자를 더해주면 되고, 다른 문자를 발견했을 경우에는 왼쪽 LCS와 위쪽 LCS 중 길이가 더 긴 걸 택해서 거기에 문자를 더해주면 된다. 문제에서 길이가 같기만 하면 된다고 했으므로 두 LCS의 길이가 같은 경우는 고려할 필요가 없다. 후자의 방법은 굳이 DP테이블에 LCS들을 다 넣어줄 필요 없이 이전 문제처럼 DP테이블을 만든 후, (맨 밑, 맨 오른쪽)에서부터 왼쪽으로 갈지, 위로 갈지, 대각선으로 갈지를 정해주면 되는데, 우리가 구하고자 하는 LCS는 대각선으로 진입할 때 (출발지, 도착지)가 있으면 출발지에 해당되는 문자이기 때문에 대각선으로 가는 경우에 출발지를 따로 저장해 두었다가 LCS의 맨 처음 문자에 도달했을 때 저장해 놓았던 문자를 LCS로 만들어서 출력해 주면 된다. 추적하는 방향을 정하는 방법은 현재 위치한 값이 대각선에 위치한 값 + 1이면 대각선으로 가고, 위쪽 값과 같으면 위로 가고, 왼쪽 값과 같으면 왼쪽으로 간다.

 

가장 긴 증가하는 부분 수열

이 문제는 숫자들이 주어졌을 때 만들 수 있는 모든 부분수열을 만들고 이 중에서 값이 증가하는 수열이 있을 텐데 이것들 중 가장 길이가 긴, 가장 숫자 개수가 많은 수열의 길이를 구하는 문제다. 이 문제를 풀기 위해서 생각해야 하는 DP테이블은, DP[i]: i번째 숫자가 부분수열에서 가장 큰 숫자일 때 이 부분수열의 길이. DP의 초기값은 전부 1로 해준다. 왜냐하면 i번째 숫자 하나로 이루어진 크기 1의 부분수열이 있기 때문이다. 이후, 만약 DP[X](X번째 숫자가 부분수열에서 가장 큰 숫자일 때 이 부분수열의 길이)를 구하기 위해서는 우선, 수열[X]이 해당 부분수열에서 가장 큰 숫자이어야 하고, 수열[X] 이전 숫자는 수열[X]보다 작아야 한다. 이 수열[X] 값의 후보자를 구했고 위치를 Y라고 한다면, DP[Y]도 있을 것이다. DP[Y]를 구하기 위해서는 마찬가지로 수열[Y]보다 작은 값을 찾고 이렇게 반복해 나가는 게 분할하는 과정이다. 이를 이해하면 DP[X] = min(DP[X], DP[Y] + 1)이라는 점화식이 나온다.

 

문자열 판별

이 문제는 문자열을 순회하면서 그 안에서 단어들을 순회하면서, 단어 크기만큼의 범위 내의 문자열 = 단어인 경우에 체크를 하고 다음에 사용해서 재확인하지 않는 방법으로 풀면 된다.

 

양팔저울

아이템들의 무게가 주어진다. 이때 관점을 바꾸어서, 해당 추를 가지고 구별할 수 있는 무게들을 전부 찾아낸 후, 이것에 속하는 아이템들만 반환해 주면 된다. 특정 무게를 감별하기 위해서는 양팔저울의 왼쪽 접시와 오른쪽 접시의 차이가 해당 특정 무게이어야 한다. 즉, 왼쪽 접시와 오른쪽 접시의 무게 차이만큼을 감별할 수 있다. 재귀 호출하는 방식으로 풀었는데, 인자로 (현재 체크할 무게추의 인덱스, 왼쪽 접시의 무게합, 오른쪽 접시의 무게합) 이렇게 3가지가 들어간다. 이후, 내부에서 우선 무게차이를 구한 후, 이 무게는 구별할 수 있다는 것이므로, 구별 가능한 무게들이 저장되어 있는 result = set()에 넣는다. 이후 재귀의 탈출구문인 (현재 무게추의 인덱스 == 마지막)인지를 체크해서 끝에 도달했으면 리턴하도록 한다. 아직 탈출하기 전이면 재귀호출이 진행되도록 재귀호출을 할 조건을 설정한다. 조건은 DP[무게추 인덱스][구별가능한 무게] == 0인 경우 수행한다. 왜냐하면 이 조건을 만족하면 3개의 재귀호출이 진행되는데, 각각 이전 호출에서 이미 DP[무게추 인덱스][구별가능한 무게] = 1로 채워졌다면 다음에는 호출해 봤자 이미 이후 결과들도 다 DP에 반영이 되어있는 상태이기 때문이다. 따라서 해당 조건 내부에서 DP = 1로 채워준다.

 

펠린드롬?

이 문제는 문자열과 (시작점, 끝나는 점)이 주어졌을 때, 문자열[시작점:끝점] 값이 펠린드롬인지 확인하는 문제다. 이 문제를 풀기 위해서는 펠린드롬을 어떻게 분할하여 정복할 수 있는지 생각해내어야 한다. 그건 바로, 문자열의 양 끝이 같은 문자라면, 양 끝을 제외한 나머지 안쪽 문자열이 펠린드롬이라면 전체 문자열도 펠린드롬이라는 특성이다. 이에 따라 결국 분할의 종착지는 문자열의 길이가 1인 때이고, 2차원 DP[시작점][끝점]: (1 or 0, 문자열의 시작점~끝점의 부분문자열이 펠린드롬이면 1, 아니면 0)을 만들어서 문자열의 길이가 1일 때부터 최대가 될 때까지 늘려가며 DP를 채워주면 전체 DP 테이블을 다 채워줄 수 있다.

 

펠린드롬 분할

이 문제는 문자열 하나가 주어질 때, 펠린드롬으로 분할한 결과 가장 펠린드롬 개수가 적을 때의 개수를 구하는 문제다. 이 문제를 풀기 위해서는 우선 문자열 내의 특정 구간이 펠린드롬인지를 판단할 수 있어야 한다. 따라서 이전 문제에서 채운 DP 테이블을 사용한다. 이후, 1차원 DP[i](0~ i번째까지의 문자열의 최저 펠린드롬 분할 개수) 테이블을 만든다. 그리고 0~X번째까지의 문자열의 최저 펠린드롬 분할 개수를 구하기 위해서는 (DP[0] + 1~X번째까지의 문자열이 펠린드롬이면 + 1), (DP[1] + 2~X번째까지의 문자열이 펠린드롬이면 + 1),... (DP[X-1] + X~X번째 문자열이 펠린드롬이면 + 1) 값들 중 가장 작은 값을 취하면 된다. 이렇게 하고 DP[0] = 1로 초기값 넣어주고 돌리면 순차적으로 DP값이 결정되면서 마지막에 우리가 구하고자 하는 값이 들어 있는 DP[문자열길이]도 채워진다.

 

행렬 곱셈 순서

입력으로 행렬들의 (행 열)들이 주어질 때, 인접한 행렬들끼리 어떤 순서로 곱하는지에 따라 행렬이 1개 남았을 때 총 연산 횟수가 달라진다. 이때, 최소 연산횟수를 구하는 문제다. 이 문제는 행렬들끼리 곱해서 또 하나의 행렬을 만들고, 이걸 또 곱해서 하나의 행렬로 만드는 특징에서 분할을 확인할 수 있다. 분할 결과 가장 작은 단위는 하나의 행렬만 남았을 때고, 이때는 해당 행렬을 반환하면 된다. 두 개가 남았을 때는 그냥 행렬끼리 곱해주면 된다. 세 개가 남았을 때는 중간에 위치한 행렬을 앞 행렬과 먼저 곱해주는 경우, 뒷 행렬과 먼저 곱해주는 경우로 했을 때의 결과 중 연산 횟수가 작은 쪽을 택하면 된다. 네 개가 남았을 때부터는 이런 식으로 구하기가 어렵다. 따라서 DP를 적용해야 한다.

DP 테이블을 이런식으로 설계한다.

 

DP[i][j]: i번째 행렬 ~ j번째 행렬까지의 최저 행렬곱 연산 횟수.

 

이렇게 설계를 하면, 일단 i <=j라고 할 때, i <= k < j 인 k를 나열해서 DP[i][j] = DP[i][k] + DP[k + 1][j] + X(이후 설명)라는 점화식을 구할 수 있다. 해당 점화식의 뜻은 (i번째 행렬 ~ j번째 행렬까지의 최저 행렬곱 연산 횟수) = (i~k 행렬곱 최저 연산 횟수) + ((k+1~j 행렬곱 최저 연산 횟수) + X이고, k는 i부터 j-1까지 순회한다. DP[x][y]라는게 x번째~y번째 행렬들을 다 곱해서 하나의 행렬로 만들었을 때, 가장 연산 횟수가 작은 값이 담기는 곳이므로, (i번째~k번째 행렬들을 다 곱해서 만든 하나의 행렬을 만드는데 필요했던 최저 연산 횟수) + (k+1번째~j번째 행렬들을 다 곱해서 만든 하나의 행렬을 만드는데 필요했던 최저 연산 횟수) + (이제 저 두 행렬을 곱해서 하나의 행렬로 만드는데 필요한 연산 횟수 = X)이다. 이제 X를 구하면 된다.

 

          행 열

행렬 0: 5  3

행렬 1: 3  2

행렬 2: 2  6

 

이렇게 행렬의 행과 열이 주어질 때, DP[0][2] = min(DP[0][0] + DP[1][2] + X1, DP[0][1] + DP[2][2] + X2)이다. min에서 첫 항은 행렬 0 * (행렬 1*행렬 2)이고, 두 번째 항은 (행렬 0*행렬 1) * 행렬 2이다. 행렬 1*행렬 2의 연산 횟수는 3*2*6, 행렬0*행렬1의 연산횟수는 5*3*2이다. 규칙성을 찾을 수 있는데, 첫 번째 행렬의 행의 개수와 열의 개수를 곱하고, 두 번째 행렬의 열의 개수를 곱해주면 된다. 따라서 X1은 k = 0일 때이고, X1 = 5 * 3 * 6, 여기서 5 = 행렬 0의 행 개수, 3 = 행렬0의 열 개수, 6 = 행렬2의 열 개수이고, X2는 k = 1일 때이고, X2 = 5 * 2 * 6, 여기서 5 = 행렬0의 행 개수, 2 = 행렬 1의 열 개수, 6 = 행렬 2의 열 개수이다. k의 변화에 따라 가운데 곱해지는 숫자만 변경되었다. 여기서 가운데 숫자는 행렬 k의 열 개수임을 확인할 수 있다. 따라서 DP[i][j] = DP[i][k] + DP[k + 1][j] + X(행렬i의 행 개수 * 행렬k의 열 개수 * 행렬j의 열 개수)이다. 이제 i~j 영역에 속하는 행렬이 1개일 때부터 N개일 때까지 돌려주면서 전체 DP 테이블을 채운 후, DP[0][N-1]에 행렬0부터 행렬N-1까지 행렬곱의 최저 연산 횟수가 저장되어 있으므로 반환해 주면 된다.

 

로봇 조종하기

N*N 크기의 2차원 배열에 숫자가 들어가 있고, 초기 위치 (0,0)에 로봇이 있고, (N-1, N-1)까지 한 칸씩 이동하면서 칸에 쓰여있는 숫자들을 다 더해갈 때, (N-1, N-1)에 도달했을 때 그 합의 최댓값을 구하는 문제다. 여기서 중요한 점은 로봇은 (왼쪽, 오른쪽, 아래) 이렇게 총 3방향으로 1칸 움직일 수 있다는 것이다. 그래서 DP[i][j]: "로봇이 (i, j)에 있을 때 만들 수 있는 최댓값" 이렇게 DP 테이블을 설계했다. 이후 DP의 초기값은 배열의 맨 윗줄은 무조건 오른쪽으로 전진해서밖에 도달할 수 없으므로 오른쪽으로 가면서 누적한 값을 DP테이블에 저장하면 되고 나머지는 음의 무한대값으로 초기화한다. 그리고 (i,j)와 인접한 칸은 (i-1, j), (i, j-1), (i, j+1) 이렇게 3칸이 있고, 이 중 어디에서 (i, j)로 가야 (i, j)에서 가장 큰 값을 만들 수 있는지를 따져봐야 한다. 그래서 위의 후보 3칸 각각의 DP값들 중 가장 큰 값을 구해야 하는데, DP[i-1][j]를 알기 위해서는 DP[i-2][j](위), DP[i-1][j-1](왼쪽), DP[i-1][j+1](오른쪽)을 미리 구해놓아야 하고 나머지 2개도 마찬가지다. 이런 식으로 계속 분할하다 보면 결국 양 끝에서부터 반대쪽으로 가면서 DP테이블을 채워주어야 한다.

우리가 지금까지 구한 값으로 위에서 아래로 접근하는 건 구했다. 이제 왼쪽에서 접근할 때, 오른쪽에서 접근할 때를 각각 구해서 이 셋 중 더 큰 값을 해당 셀의 DP값으로 지정해 주면 된다. 왼쪽에서 접근할 때는 해당 셀의 (위쪽 셀의 DP값, 왼쪽 셀의 DP값) 중 더 큰 값 + 해당 셀에 들어 있는 값이 DP[해당 셀]의 후보값이 되고, 오른쪽에서 접근할 때는 (한 칸 위 셀의 DP값, 한 칸 오른쪽 셀의 DP값) 중 더 큰 값 + 해당 셀에 들어 있는 값이 DP[해당 셀]의 후보값이 된다. 이후 두 후보값 중 더 큰 값을 DP에 담으면 된다.

 

평범한 배낭

N개의 물건이 있고 각 물건은 무게 W와 가치 V를 가지는데, 가방에 최대 K만큼의 무게를 담을 수 있을 때 가치의 최대 총합을 구하는 문제다. 물건을 순회하면서 이 물건을 안 넣을 때는 남는 가방무게로 넣을 수 있는 가치 중 최대값을 취하고, 넣을 때는 이 물건을 넣고 + 남은 무게로 넣을 수 있는 최대 가치를 넣으면 된다. 이걸 식으로 세우면 2중 for문으로 첫 for문으로 물건을 순회하고, 두 번째 for문으로는 가방 무게 1부터 K까지 순회한다. 이런 식으로 하는 이유는 앞서 설명했던, 남은 무게로 넣을 수 있는 최대 가치를 구하기 위해서 물건을 돌면서 모든 무게에 대해 미리 그 최댓값을 구해놓기 위해서이다. 

 

평범한 배낭 2

이전 문제와 다른 점은 각 물건별 개수까지 고려해야 한다는 것이다. 처음에 이 문제를 풀 때는 이전문제와 거의 코드는 같게 하고, 물건의 개수를 1개씩 추가해주기만 했다. 결과는 시간초과가 났다. 답을 보니 A물건이 7개 있으면 이걸 1개, 2개, 4개 8개... 이런식으로 2의 거듭제곱만큼으로 묶어서 하나의 물건으로 취급하라는 것이다. 7개: 1개 묶음 + 2개 묶음 + 4개 묶음, 9개: 1개 묶음 + 2개 묶음 + 4개 묶음 + 나머지 2개 묶음. 이렇게 해서 1차원 DP에 DP[weight_goal] = max(DP[채울 가방무게], DP[채울 가방무게 - 해당 아이템 무게] + 가치)를 해주면 신기하게도 for문이 끝났을 때 DP에 해당 아이템을 1개 사용한 경우, 2개 사용한 경우,... 7개 사용한 경우 모두 오름차순으로 들어있는 것을 확인할 수 있다.

 

외판원 순회

처음에 이 문제랑 같은데 N <= 10 인 경우 DFS로 접근해서 풀었다. 하지만 이번 버전은 N <= 16이다. 따라서 똑같이 DFS로 풀 경우 시간초과가 나게 된다. 그래서 다른 방법이 필요한데, 그것은 지금까지 방문한 도시들을 비트마스킹 기법으로 체크하고, DP[현재도시][지금까지 방문한 도시] = -1(초기값) or (아직 방문하지 않은 도시들을 전부 돌아서 시작도시로 가는데 필요한 최소비용)  테이블을 만들어서 현재 도시에 왔는데 이전에 같은 상태(지금까지 방문한 도시)였을 때가 있었다면 DP[현재도시][지금까지 방문한 도시] 값을 그대로 쓰고 처음인 상태라면 구하면 된다. 구하는 방법은 visited에 현재까지 방문한 도시들이 저장되어 있는데, 이걸 이용해서 아직 방문하지 않은 도시들을 갈 수 있다. 이걸 재귀적으로 호출하면, min_dist = min(min_dist, Weight[cur][i] + recur(i, visited | (1 << i)) 식을 구할 수 있다.

 

여기서 min_dist는 DP[cur][visited]에 들어갈 값이고, i는 0부터 N-1 도시 중 아직 방문하지 않은 도시들이고, Weight[cur][i]는 현재 도시에서 i도시로 가는데 필요한 비용, recur(i, visited | (1 << i))는 현재 도시가 i이고 visited에 i를 방문했다는 기록을 비트마스킹 기법을 이용해서 추가시켜서,  recur(i, visited | (1 << i)) = (i에서 visited+i까지 방문했을 때 나머지 도시를 돌아 초기 도시로 돌아오는데 필요할 최소비용)이다. 결국 cur에서 i로 갈 때의 최소비용이 min_dist에 담기고 i는 0번째 도시부터 N-1번째 도시까지 반복되므로 반복하면서 얻은 최소비용이 min_dist에 담기게 되고 dp[cur][visited]에 담기게 된다.

 

recur 재귀함수의 탈출구문은, 모든 도시를 방문했을 경우이고, 모든 도시를 방문했을 때 다시 초기도시로 가야한다. 이때 초기도시로 가는 경로가 없으면 못 가므로 무한대값을 리턴 시키고, 있으면 DP[현재도시][지금까지 방문한 도시들] = Weight[현재도시][초기위치]을 해주는데, DP[city][visited]의 뜻이 city도시에서 지금까지 visited에 담긴 모든 도시들을 방문했을 때 초기도시로 가는 비용인데, 지금 모든 도시를 방문한 경우이므로 이제 초기도시로 가는 것 밖에 없기 때문에 저렇게 넣어준 것이다.

이렇게 recur() 함수를 만들고, recur(0, 1)을 호출한 결과를 출력한다.

 

점프

N개의 돌이 일자로 깔려 있고 1번째 돌에서 점프해가면서 다음 돌로 이동해서 결국 N번째 돌까지 갈 때, 방법들 중에 가장 점프를 적게 했을 경우의 횟수를 구하는 문제다. 이것도 DP 문제이므로 DP적인 사고를 해야 한다. 우선, 해당 돌을 스피드가 몇이었을 때 방문했는지를 따져야 하기 때문에, 돌을 가리키는 차원, 스피드를 가리키는 차원 이렇게 2차원이 필요해서 DP[i][j]로 만들고, 여기에 들어가는 값의 의미는 "i번째 돌을 스피드 j로 도달했을 경우에 점프한 횟수"이다. X번째 돌을 speed로 방문하려면 그전에 X - speed번째 돌에서 speed -1의 속도 or speed or speed + 1의 속도였어야 한다. 따라서 DP[i][speed] = min(DP[i-speed][speed - 1], DP[i-speed][speed], DP[i-speed][speed + 1]) + 1이다. 이때 문제에서 1번째 돌에서 시작하므로 DP[1][0] = 0으로 두고 시작한다.

---

그리디

그리디

동전 0

그리디 문제다. 가치가 여러 개인 동전들이 주어지고 사용횟수는 제한이 없을 때, 가치의 합을 K로 만들 때 필요한 동전 개수의 최솟값을 구하는 문제다. 문제에서 일단 큰 가치들은 작은 가치의 배수이기 때문에, 100의 가치의 동전 x개는 100*x가치의 동전 1개와 총 가치합이 같다. 따라서 작은 가치들을 여러 개 쓸 바에는 큰 가치를 하나 쓰는 게 맞으므로 결과적으로 큰 가치부터 차례대로 사용하면서 K에서 남은 가치를 현재 사용하려는 가치로 만들 수 없을 때 내려가면서 K를 만들어주어야 한다.

 

잃어버린 괄호

숫자, +, -로 이루어진 식이 주어진다. 이후 괄호를 적당히 쳐서 식의 값을 최소로 하는 문제다. 연산자 중 +와 -밖에 없기 때문에 -가 나온 이후의 식들은 모두 괄호안에 넣어 감싸줘서 다 빼준다면 이때 가장 작은 값을 구할 수 있다.

 

회의실 배정

하나의 회의실이 있고, 입력으로 회의 예약 리스트들이 들어온다. 이 리스트의 요소는 (시작시간, 끝나는시간) 형태이다. 이때 회의가 겹치지 않는 선에서 최대 몇 개의 회의를 진행할 수 있는지 구하는 문제다. 이전 회의가 끝나는 시간과 다음 회의가 시작하는 시간은 같아도 되지만 회의가 서로 겹치면 안 된다. 이 문제 역시 그리디인데, 결국 하나의 회의가 끝나야 다음 회의를 진행할 수 있기 때문에, 가장 빨리 끝나는 회의부터 진행하고 이 회의가 끝났을 시점 이후에 가장 빨리 끝나는 회의를 진행하는 방식으로 하면 된다. 중요한 것은 (3, 3)과 (2, 3)처럼 끝나는 시간은 동일하지만 시작하는 시간은 다른 경우인데, (3,3) 먼저 진행했을 경우 다음 회의의 시작시간은 3과 같거나 커야 하기 때문에 (2, 3)은 진행할 수 없지만, (2, 3)을 먼저 진행한 경우 (3, 3)는 이전 회의의 끝나는 시간과 자신의 시작시간이 같기 때문에 할 수 있다. 따라서 끝나는 시간이 같은 경우 시작시간이 빠른 것부터 정렬되도록 해주어야 한다. lambda meeting : (meeting[1], meeting[0])

 

신입사원

이 문제는 신입사원을 뽑는 문제인데, 신입사원들은 서류심사와 면접시험을 본 후 등수를 얻는다. 이렇게 두 테스트에 대한 등수를 매긴 후,  자기보다 두 테스트 모두 더 좋은 등수를 맞춘 사람이 한 명이라도 있으면 입사를 하지 못한다. 결론은 두 테스트 다 자신보다 잘 본 사람이 1명이라도 있으면 입사를 못한다는 것이다. 그래서 우선, 서류심사 등수를 기준으로 오름차순 정렬을 해줬다. 이후, 사람들을 순회하는데, 첫번째 사람은 이미 서류심사 등수가 1등이므로 무조건 합격이라서 패스하고 이사람의 면접시험 등수를 min_score로 저장해 놓는다. 이후 다음 사람은 이미 서류심사는 자기보다 잘본 사람이 있으므로 무조건 면접시험을 그사람보다 잘봐야 한다. 따라서 min_score보다 자신의 면접시험 등수가 높으면 합격, 낮으면 불합격이다. 높을 경우 합격처리하고 새로운 min_score를 갱신해준다. 이렇게 하면, 지금까지 나온 사람들보다는 무조건 서류심사는 잘 못봤고, 면접시험은 앞선 사람들중 가장 잘본 사람인 min_score보다 더 잘 봤어야 한다. 이런 식으로 하면 합격자수를 구할 수 있다.

 

컵라면

이 문제는 조교가 학생에게 문제 리스트들을 주고 풀라고 시키는 문제다. 문제에는 데드라인과 풀었을 때 받을 수 있는 컵라면 수가 주어진다. 문제는 하루에 1문제 풀 수 있을 때 최대 받을 수 있는 컵라면 개수를 구하면 된다. 처음에 접근할 때는 경과한 시간을 업데이트해 주면서 아직 데드라인을 지나지 않은 문제들 중 가장 컵라면을 많이 주는 순서대로 풀어서 결과를 냈다. 하지만 이렇게 하면 틀린다. 해결의 아이디어는 데드라인이 긴 문제일수록 풀릴 기회를 많이 주는 것이다. 우선 최대힙을 만든다. 여기에는 문제의 컵라면 수가 들어간다. 이후, 데드라인이 큰 문제 순서대로 최대힙에 그 문제의 컵라면 수를 넣어준다. 데드라인이 같은 문제들의 컵라면 수들을 다 넣어줬으면 이제 그들 중 가장 컵라면을 많이 주는 문제를 뽑기 위해 최대힙에서 하나 빼서 해결한다. 이후, 1만큼 줄인 데드라인에 해당하는 문제가 있으면 또 넣고 없으면 또 내려간다. 이런 식으로 해서 구하면 된다. 이렇게 하면 되는 이유는 만약 데드라인 1부터 N까지 전부 하나씩 있으면 그냥 모든 문제를 다 풀면 된다. 이때 데드라인 N인 문제부터 넣고 해결하고 넣고 해결하면 1까지 가고 넣고 해결한다. 결국 이 풀이는 각 데드라인별 기회를 몇 번 주느냐로 이해했다. 데드라인이 N인 문제는 N번 뽑힐 기회가 있고, 데드라인이 1인 문제는 처음에 딱 1번 뽑힐 기회가 있으므로, 데드라인이 가장 큰 것부터 넣어주면서 확인해 나가는 것이다.

 

멀티탭 스케쥴링

구멍이 N개인 멀티탭이 주어지고 전자제품의 사용 순서가 주어질 때 가장 교체 횟수를 적게 사용해서 순서대로 사용하는 경우를 찾으면 된다. 처음에 문제에 접근할 때는 교체가 필요할 때, 현재 멀티탭에 꽂혀 있는 전자제품 중, 앞으로 사용되어야 할 횟수가 가장 적은 전자제품과 교체하는 방식으로 코드를 짰다. 이 경우 문제가 발생하는데, 많이 사용되어야 하지만 나중에 사용되어야 할 경우, 현재는 계속 코드에 남아서 필요 없이 공간을 낭비하고 있는 문제다. 그래서 틀렸고 답은 교체해야 할 때 멀티탭에 꽂혀 있는 전자제품 중 가장 늦게 사용될 전자제품과 교체하는 것이다. 이렇게 그리디를 생각하고 코드로 옮기면 답이 된다. 구현할 때 list.index(value) 메서드를 사용하는데, 해당 value를 찾지 못한 경우 ValueError가 발생해서 이걸 잡아주기 위해 try-except 구문을 사용한다.

 

최장 공통부분 문자열

suffix array와 lcp를 사용해서 풀 수 있다는데 둘 다 공부를 아직 안 해서 보류