코생코사

배낭 문제라고도 불리는 냅색 알고리즘은 DP 문제 중 일부이다.주어진 물건들 중 일부를 선택하여 제한된 용량의 가방(또는 배낭)에 최대한의 가치를 담는 문제를 해결하는 알고리즘 물건을 넣을 것인가, 안넣을 것인가를 정하는 것이 문제의 핵심이다. 평범한 배낭 문제를 이용하여 원리를 알아보겠다https://www.acmicpc.net/problem/12865 일단 예제 1을 보면4 7 # 물품 수 n 과 최대 무게 k # 각 물품의 무게와 가치6 13 4 83 65 12  물품 수 n+1 (아무 물품도 넣지 않았을 때)를 행으로무게 k+1 (무게가 0일 때)를 열로 한2차원 표를 만든다2차원 표 안에는 가치가 들어간다.각 행의 물건을 넣었을 때, 넣지 않았을 때의 가치를 비교해서 더 큰 값을 넣어준다 안넣는..

https://www.acmicpc.net/problem/1309 DP를 사용 맨 위의 두 칸을 세 가지 경우로 나눈다- 공백: 두 칸에 아무도 없음- 좌: 왼쪽 칸에 사자 있음- 우: 오른쪽 칸에 사자 있음 만약 n이 1이라면위처럼 세 가지 경우가 있습니다  n이 2인 경우를 보겠습니다 그런데 아래 칸(파란색)의 경우의 수는n=1일 때의 경우의 수와 같습니다  즉 맨 위의 두 칸이 공백이면 n-1의 모든 경우의 수가 올 수 있고,왼쪽만 있으면 n-1의 경우의 수 중 공백과 오른쪽이 채워져 있는 경우가 올 수 있고,오른쪽만 있으면 n-1의 경우의 수 중 공백과 왼쪽이 채워져 있는 경우가 올 수 있습니다. dp 점화식으로 풀게 된다면# 0번 째는 공백(사자 없음), 1번 째는 왼쪽에 사자, 2번 째는 오른..

https://www.acmicpc.net/problem/1504 방법은노드 1 -> 노드 v1 -> 노드 v2 -> 노드 n노드 1 -> 노드 v2 -> 노드 v1 -> 노드 n두 가지 중 최소 경로를 구하고, 만약 INF 보다 크거나 같다면 -1을 출력하면 되는 문제였습니다.  일단 이 문제를 플로이드 워셜로 푸려고 했습니다(이유는.. 800 ** 3을 1억번보다 더 적게 나온다고 잘못 계산해서..)import sysinput = sys.stdin.readlineINF = int(1e9)n, e = map(int, input().split())graph = [[INF]*(n+1) for _ in range(n+1)]for i in range(1, n+1): graph[i][i] = 0 fo..

https://www.acmicpc.net/problem/1956 저는 노드가 400개이기 때문에400 ^ 3이 1억번보다 적어 플로이드 워셜 알고리즘을 사용해야겠다고 생각했습니다 import sysinput = sys.stdin.readlineINF = int(1e9)v, e = map(int, input().split())graph = [[INF]*(v+1) for _ in range(v+1)]for i in range(1, v+1): graph[i][i] = 0 for _ in range(e): a, b, c = map(int, input().split()) graph[a][b] = c # 단방향 for k in range(1, v+1): for i in range(..

https://www.acmicpc.net/problem/9205저는 dfs를 사용하였습니다.DFS를 사용하는 이유: 거리가 되는 모든 방향을 탐색해야 하기 때문https://www.acmicpc.net/board/view/86660 x와 y의 값이 1000(20X50) 이하이면 갈 수 있다1000보다 크면 갈 수 없다  입력 받기from sys import stdint = int(stdin.readline())result = []for _ in range(t): n = int(stdin.readline()) # 편의점 개수 home_x, home_y = map(int, stdin.readline().split()) store = [] for _ in range(n): ..

+https://www.acmicpc.net/problem/1351 먼저 저는 다이나믹 프로그래밍을 사용해야겠다고 생각했습니다예를 들어 n=7, p=2, q=3이 나왔을 때 다이나믹 프로그래밍- 재귀 함수 + 메모제이션을 이용(탑다운 방식)- 반복문을 이용(보텀업 방식) 먼저 반복문을 이용하여 코드를 구현했습니다.from sys import stdinn, p, q = map(int, stdin.readline().split())dp = [0] * (n+1)dp[0] = 1for i in range(1, n+1): dp[i] = dp[i//p] + dp[i//q] print(dp[n])하지만 n이 최대 10의 12승이기 때문에 메모리 초과가 났습니다. 그래서 저는 메모리를 줄이기 위해 n//p와..

https://www.acmicpc.net/problem/11399  그리디를 이용하여 제일 적게 걸리는 사람부터 처리한다 # 빨리 끝나는 사람 먼저n = int(input())t_list = list(map(int, input().split()))sum_time, wait = 0, 0# 제일 적게 나오는 사람for t in sorted(t_list): # 합 sum_time += wait + t # 뒷 사람이 기다려야 하는 wait += t print(sum_time)

https://www.acmicpc.net/problem/11047  그리디(탐욕법)을 이용한다 n, k = map(int, input().split())money = []for _ in range(n): money.append(int(input()))cnt = 0for m in money[::-1]: if k//m == 0: continue else: cnt += k//m k = k % mprint(cnt)