문제 : https://www.acmicpc.net/problem/12865  DP 점화식을 세우는 것이 어려워서 최근에 DP 문제만 풀고 있는데 아직 접근법을 떠올리기 힘든 것 같다. dp[i]는 배낭의 최대 용량이 i일 때 얻을 수 있는 최대 가치를 의미한다. dp[i - w] + v 은 무게 w인 아이템을 추가하여 무게 i가 되었을 때 새로운 최대 가치를 계산하는 부분이다.max(dp[i], dp[i - w] + v)를 계산해, 현재 아이템을 넣었을 때와 넣지 않았을 때 중 최대 가치를 선택해 dp[i]를 갱신한다.  예를 들어 배낭의 최대 용량이 7일 때, 무게와 가치가 각각 (3, 4), (4, 5), (2, 3)인 아이템들이 있다면  1. dp 테이블을 dp = [0] * (K + 1) # [..

문제 : https://www.acmicpc.net/problem/2156  처음에 제출한 코드는 런타임 에러가 발생하였다.n = int(input())lst = [int(input()) for _ in range(n)]dp = [0] * 10000dp[0] = lst[0]dp[1] = lst[0] + lst[1]dp[2] = max(lst[0] + lst[2], lst[1] + lst[2], dp[1])for i in range(3, n): dp[i] = max(dp[i-3] + lst[i-1] + lst[i], dp[i-2] + lst[i], dp[i-1])print(max(dp[-1]))   n이 3보다 작을 때의 예외 처리를 하여 다시 제출했더니 통과하였다. 나의 풀이n = int(input..

문제 : https://www.acmicpc.net/problem/2164 나의 풀이from collections import dequeq = deque()n = int(input())for i in range(1, n+1): q.append(i)while len(q) > 1: q.popleft() qp = q.popleft() q.append(qp)print(q.pop()) 큐를 이용하여 쉽게 풀 수 있는 문제이다. q = deque([i for i in range(1,n+1)]) 위와 같이 선언과 함께 큐에 값을 넣을 수도 있다.

문제 : https://www.acmicpc.net/problem/14940  코드 from collections import dequen, m = map(int, input().split())grid = [list(map(int, input().split())) for _ in range(n)]distance = [[-1] * m for _ in range(n)]dx = [1, -1, 0, 0]dy = [0, 0, 1, -1]def bfs(i, j): q = deque([(i, j)]) distance[i][j] = 0 while q: x, y = q.popleft() for d in range(4): nx, ny = dx[d] + x, dy..

문제 : https://www.acmicpc.net/problem/2293  평소 DP 문제들의 접근에 어려움을 느끼는데 점화식을 세우는 것이 어려운 것 같다. 이번 문제도 점화식 아이디어가 떠오르지 않아서 검색을 통해 공부하고 접근법을 이해하는 데에 노력하였다.단순히 코드를 보는 것만으로 이해가 어려울 때엔 유튜브로 해설 영상을 통해 보다 쉽게 이해할 수 있다.    정답 n, k = map(int, input().split())coins = [int(input()) for _ in range(n)]coins.sort()DP = [0] * (k + 1)DP[0] = 1for c in coins: for i in range(c, k + 1): DP[i] += DP[i - c]print(..

문제 : https://www.acmicpc.net/problem/2579  다이나믹 프로그래밍 (DP) 문제이다.  계단을 오르며 얻을 수 있는 최댓값을 구하면 되는 문제이지만 조건이 있다.1. 한 번에 한 계단 혹은 두 계단씩 오를 수 있다.2. 연속된 세 개의 계단을 밟을 수 없다.3. 마지막 계단은 반드시 밟아야 한다. 이 세 조건을 만족시키며 답을 구하기 위해 다음과 같이 접근하였다.1. 계단의 개수가 각각 1, 2개일 때     계단의 점수를 더한 값을 출력한다. 2. 계단의 개수가 3개 이상일 때  1) dp 테이블을 계단의 개수만큼 0으로 초기화하여 만든다.  2) dp[0] = 첫 번째 계단의 점수 , dp[1] = 첫 번째 계단의 점수 + 두 번째 계단의 점수를 저장한다.  3) dp[..

문제 : https://www.acmicpc.net/problem/1931   처음 문제를 보자마자 알고리즘 강의 때 배운 Interval Schduling의 접근법이 생각났다. Earliest finish time을 기준으로 접근하여 가장 빨리 끝나는 것을 선택하면 최적의 답을 구할 수 있는 것이다.  이를 고려하여 입력 받은 회의 시간들을 끝나는 시간을 기준으로 오름차순 정렬하고 제출하였는데 실패하였다. 그 이유는 끝나는 시간이 동일한 회의들에 대한 처리를 해주지 않았기 때문이었다. 따라서 아래와 같이 1. 회의가 끝나는 시간 2. 회의 시작 시간  이렇게 우선 순위를 두어서  .sort(key = lambda x: x[1])이 아닌  .sort(key = lambda x: (x[1], x[0])) ..

문제 :  https://www.acmicpc.net/problem/14888   코드N = int(input())nums = list(map(int, input().split()))op = list(map(int, input().split()))maxn = -1e9minn = 1e9def dfs(n, i, add, sub, mul, div): global maxn, minn if i == N: maxn = max(maxn, n) minn = min(minn, n) return else: if add: dfs(n + nums[i], i+1, add - 1, sub, mul, div) if sub: ..