ayeongjin 님의 블로그

https://www.acmicpc.net/problem/2240 이문제를 풀면서 가장 어려웠던 점은 dp 테이블을 어떻게 설계해야하는지에 대한 고민이었다.처음에는 dp 테이블에 저장할 값을1. T 시간만큼 순회하는 동안 현재 시간까지의 이동 수2. 현재 위치3. 그 이동 수와 현재 위치에 따라 얻을 수 있는 최대 자두의 수이렇게 저장하려고 생각했다.하지만 이동 수에 따라서 현재 나무 위치와 자두 최댓값을 어떻게 점화식을 세울지 너무 헷갈렸다.그래서 처음부터 다시 생각했다. 먼저1. 처음 위치는 똑같이 1번 나무에서 시작2. 만약에 3번 이동했다면, 1 -> 2 -> 1 -> 2 로 2번 나무2-2. 따라서 현재 나무 위치를 dp 테이블에 저장할 필요는 없음 (이동 횟수에 따라서 알 수 있으므로)3. 그..

https://www.acmicpc.net/problem/22115 dp 다 까먹어서 요즘 dp 문제를 풀었다.이 문제는 9465번 스티커처럼 커피를 마실때, 안마실 때 구분해서 dp 배열에 저장해서 풀면 되는 줄 알고 엄청 헤맸다.14782 벼락치기처럼 dp 배열을 바꿨더니 풀렸다. 1. dp K+1 크기의 1차원 리스트로 생성2. 커피 하나씩 순회하면서 그 커피를 마실 때 가능한 카페인 합 거꾸로 순회하면서 커피의 최솟값 갱신 N, K = map(int, input().split())coffees = list(map(int, input().split()))dp = [float('inf')] * (K + 1)dp[0] = 0for c in coffees: # 전체 카페인을 하나씩 거꾸로 순회하면서..

https://www.acmicpc.net/problem/11057 첨엔 문제가 이해 안됐다.수의 길이 N은 N자리수 수 중에 오르막 수를 구하라는 뜻이었다. 그래서 dp 배열을 10 * (N+1) 칸으로 만들었다.그리고 dp[i][j] = i 자리 수 중에 첫번째 숫자가 j인 수의 오르막 수로 지정해서 풀었다. 1. 한자리 수 중에 첫자리가 0인 수의 오르막 수 = 0개한자리 수 중에 첫자리가 1인 수의 오르막 수 = 1개한자리 수 중에 첫자리가 2인 수의 오르막 수 = 1개...한자리 수 중에 첫자리가 9인 수의 오르막 수 = 1개이므로 dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] 로 초기화했다. 2. 두자리 수 중에 첫자리가 1인 수의 오르막 수 = 한자리 수 중에 첫자리가..

https://www.acmicpc.net/problem/11909  처음에 문제만 보고 그냥 다익스트라로 푸는 문제인줄알았는데 계속 시간초과났다. 1. (0, 0)부터 시작 -> 이미 더 빠르게 지나온 기록이 있으면 continue2. 현재 칸이 다음 칸보다 작으면 버튼 올려서 칸 맞춰주기3. 최솟값 갱신 # 실패 코드# 다익스트라 - 시간초과from heapq import heappop, heappush# 1. A[a][b] > A[c][d]# 2. 1 visited[r][c]: continue for di, dj in [(1, 0), (0, 1)]: nr, nc = r + di, c + dj if not (0 arr[nr][nc]: ..

큰 문제를 작은 문제로 나누어 풀고, 작은 문제의 해답을 저장하여 재활용함으로써 중복 계산을 줄이고 효율성을 높이는 알고리즘 설계 기법 1. 탑다운 (Top-Down):재귀와 메모이제이션을 사용하여 문제를 풀어나감큰 문제를 먼저 풀기 시작하고, 하위 문제를 재귀적으로 호출하여 해결이미 계산된 하위 문제의 결과를 메모이제이션(dp)으로 저장하고 재사용2. 바텀업 (Bottom-Up):반복문을 사용하여 작은 문제부터 시작해서 큰 문제를 해결기본값부터 차례로 계산하며, 작은 문제의 결과를 기반으로 큰 문제를 해결

https://www.acmicpc.net/problem/15989   처음엔 점화식 풀어서 해야하는 줄 알고 엄청 고민했는데 결국 풀리지 않았다.그래서 다른 블로그 도움 받았는데 이해하는데 꽤 오래 걸렸다.for문 한 개 안에서 해결하려는 고정관념 때문에 생각도 못한 코드가 정답이었다.  다른 블로그에서는 dp 배열을 처음부터 1로 초기화 하고 시작했다. 문제 조건이 n은 양수이지만 그래도 dp[0] = 1 이 되는건 좀 찝찝했다.1, 2, 3을 사용해서 0을 만들 수 있는 경우의 수는 0인데... 이해하는데 어려움이 있어서 최적화 없이 풀어봤다. 1. dp 테이블 0으로 초기화2. 1만 사용해서 정수의 합 나타내는 경우의 수 : 모든 정수 다 한가지3. 2추가 : 1로만 이루어진 정수에서 1+1 빼고..

https://www.acmicpc.net/problem/15988   1, 2, 3 더하기 4가 스터디 문제로 나와서 3도 풀어봤다. 순서 없는 1, 2, 3 배열 수 구하는 문제라 점화식을 간단하게dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 으로 세웠는데 메모리 초과에 시간초과까지 완전 난리났다.  실패 코드원인 1. 매 테스트케이스마다 dp 새로 계산 (시간초과)원인 2. dp 테이블 저장할 때 1000000009로 나눈 나머지 저장 안 함 (메모리초과) -> 분배법칙 적용해서 해결..for tc in range(int(input())): n = int(input()) dp = [0] * (n + 1) dp[1] = 1 dp[2] = 2 dp[3] = ..