Basic 1/2 (40X, Dynamic Programming)

2023.12.14, Basic 1/2 400 Start.

2023.12.21, Basic 1/2 400 DONE. (8th day)
2023.12.22, Basic 1/2 401 DONE. (9th day)
2023.12.25, Baisc 1/2 402 DONE. (12th day)

2023.12.25 - Baekjoon 17404: RGB 거리2 나는 끝과 시작을 저장하는 DP로 도전했음. 3일 동안 고민해도 왜 틀렸는지 몰랐는데, 질문을 통해서 확인하니 마지막에 print 출력을 빼먹었었음 =|. Colab 에서는 return 만해도 결과값이 자동으로 나와서 전혀 몰랐던 상황. 익명의 코더분의 도움을 통해서, 내 알고리즘 구성은 틀린 것이 없음을 확인할 수 있었고, 사소한 실수가 정말 고치는데 오랜 시간이 걸린다는 것을 느낌! 그래도 크리스마스 선물 받은 느낌. 감사함.

인터넷 풀이는 보통 RGB 거리 1의 알고리즘을 그대로 이용하되, [R, G, B] 의 초기값을 설정하여 강제로 R, G, B 중 한가지 색으로 시작하는 방식을 채택. 꽤 스마트한 방식으로 생각되었음. =)

2023.12.25 - Basic Algorithms 1/2 DONE =)

2023.12.22 - Baekjoon 11054: 가장 긴 바이토닉 부분 수열, 기준을 나누어 증가/감소에 관한 함수를 각각 구성했더니 시간초과.

(1) 각각 A[:i]. A[i+1,:] inc/dec 를 찾는다. O(n^2) (2) 찾고나서 max()를 진행한다. O(n^3)

(3) 합친다.

2023.12.22 - Baekjoon 11054: 가장 긴 바이토닉 부분 수열, 기준을 나누어 증가/감소에 관해 찾는 것은 동일.

(1) 각각 A[:] 전체에 대해서 inc/dec를 찾는다. O(n^2)

(2) 합친다.

처음 알고리즘은, A를 나누어서 각각에 inc/dec 부분수열은 찾고 max를 취하는 번거로움에 의해서 알고리즘 복잡도 상승. 두번째 알고리즘은 A를 나누지 않고 진행.

2023.12.22 - Baekjoon 13398 연속합 2

수열을 제거하는 경우도 포함
A의 최솟값이 -1000 이므로, -1001로 initialization하여 비교.
원소하나를 지웠을 때의 연속 최대합은 Baekjoon 11054 바이토닉 부분 수열처럼, A[:] 전체에 대해 역방향 연속 최대합을 찾아서, 원소 A[i]를 빼고 합하여 비교.
DP 2개를 나누어서 원소를 제거한적 없는 연속합/ 원소를 제거한적 있는 연속합 두가지 경우가 연결된 점화식을 만드는 인터넷 풀이도 인상적.

import sys

input = sys.stdin.readline

N = int(input())

A = list(map(int, input().split()))

dp = [[x for x in A] for _ in range(2)]

for i in range(1, N):

dp[0][i] = max(dp[0][i - 1] + A[i], dp[0][i])

dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + A[i])

print(max(max(dp[0]), max(dp[1])))

2023.12.21 - Baekjoon 14002: 가장 긴 증가하는 부분 수열 4

Baekjoon 11053: 가장 긴 증가하는 부분 수열의 감소하는 수열에서 수열 자체도 출력하는 문제. 동일한 알고리즘.

2023.12.21 - Baekjoon 1912: 연속합, 수열이 연속이라는 조건이 있기 때문에 비교적 쉬운 DP

Basic 1/2 400 DONE

2023.12.21 - Baekjoon 11055: 가장 "큰" 증가하는 부분 수열

Baekjoon 11053: 가장 "긴" 증가하는 부분 수열의 최대합으로 확장하는 문제. 굉장히 유사한 알고리즘.

2023.12.21 - Baekjoon 11722: 가장 긴 "감소"하는 부분 수열

Baekjoon 11053: 가장 긴 "증가"하는 부분 수열의 감소하는 수열로 확장하는 문제. 굉장히 유사한 알고리즘.

2023.12.19 - Baekjoon 2133: 타일채우기. 각 3*N마다 1행이나 3행을 모두 1x2 블럭으로 채우는 고유의 모양이 2개씩 존재한다.

2023.12.20 - Baekjoon 11053: 가장 긴 증가하는 부분 수열의 경우, 아이디어를 떠올리기 힘들어서 인터넷 참조.

2023.12.19 - Baekjoon 2156; 포도주 시식 끝에 와인잔이 연속으로 0개, 1개, 2개 있는지에 따라 경우를 나누어 DP 적용.

인터넷은 보통 d[x]:= x번째 와인잔까지 마신 경우, d[x]= max(d[x-1], d[x-2]+cup[x], d[x-3]+cup[x]+cup[x-1]) 로 풀이. 각각 n=3인 경우, (OOX, OXO, XOO) 에 해당.

2023.12.18 - Baekjoon9465: 스티커, 마지막 열의 스티커를 1) 모두 사용하지 않는다, 2) 첫번째 행의 스티커만 사용한다., 3)세번째 행의 스티커만 사용한다. 로 나누어서 DP로 풀이

2023.12.18 - Baekjoon 1149 RGB 거리, 간단한 DP 문제. 끝이 R,G,B로 끝나는 경우로 나누어서 DP 적용.

< Baekjoon 401, 402, 403, Dynamic Programming(DP) 중간 후기>

점화식을 찾는 과정이 꽤 중요하다.
현재 부분 수열 문제, 연속합 문제의 종류에서 헤매고 있다.
인터넷과 다르게 나는 DP 대신 중복조합 or 단일배열보다 더 직관적인 이중배열에 DP를 사용하여 푼 경우가 종종 있었다.

2023.12.17 - Baekjoon 11057 오르막수 갯수: 간단한 DP, 끝이 0,...9 로 끝나는 각각에 대하여 DP로 구현.

2023.12.17 - Baekjoon 1932: 정수 삼각형: 간단한 DP

2023.12.17 - Baekjoon 15988: 1,2,3, 더하기 3, 시간초과 해결을 위해 모든 결과값에 나머지 연산 적용

2023.12.17 - Baekjoon 1309 동물원: 인터넷은 d[i] = 2*d[i-1]+d[i-2] 라는 점화식으로 해결. 나는 케이스 3개를 나누어서 메모리 초과가 있었으나, 배열을 재사용함으로써 메모리 초과도 해결.

2023.12.17 - < Baekjoon 15990: 1,2,3, 더하기 5 > 시작을 1,2,3 으로 하는 수열로 경우를 나누어서 이중배열에 DP를 적용. MOD 연산을 통해서 시간초과 해결

2023.12.17 - Baekjoon 2225: 합분해,

나는 중복조합 공식으로 해결.
DP로 해결하려면,

d[n][k] = d[n-1][k] + d[n][k-1] 점화식 활용. (N-1을 만들기 위해 K개의 수를 사용한 것의 제일 앞에 '1'씩 더하거나 (제일 앞이 0이 아닌수열) + N을 만들기 위해 K-1개의 수를 사용한 것의 제일 앞에 '0' 을 추가하거나 (제일 앞이 0인 수열)

인터넷의 2차원 DP로 점화식 구하는 과정은 대부분 근거가 불충분함을 확인함. 중복조합의 이해가 없어서 그렇다고 생각됨. 골드 이상의 문제에서는 생각보다 백준을 이해없이 풀고 솔루션을 올려두는 사람들이 많아보인다. 인터넷은 때때로 생각보다 퀄리티가 낮은 정보처일 수도 있다는 생각도 들었다.