DP 문제https://www.acmicpc.net/problem/9084 9084번: 동전우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는www.acmicpc.net 💡 풀이 코드import syst = int(sys.stdin.readline())for _ in range(t): n = int(sys.stdin.readline()) c = list(map(int, sys.stdin.readline().split())) price = int(sys.stdin.readline()) dp = [[0] * (price +..

DP 문제https://www.acmicpc.net/problem/2294 2294번: 동전 2첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어www.acmicpc.net 💡 풀이 코드import sysn, k = map(int, sys.stdin.readline().split())coin = []for _ in range(n): value = int(sys.stdin.readline()) coin.append(value)dp = [10001] * (k + 1)dp[0] = 0def coin2(n, coin, k):..

정렬 + 스위핑 문제https://www.acmicpc.net/problem/2170 2170번: 선 긋기첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x www.acmicpc.net 💡 풀이 코드 import sysn = int(sys.stdin.readline())line = []for _ in range(n): start, end = map(int, sys.stdin.readline().split()) line.append((start, end))line.sort()last = -sys.maxsizeanswer = 0for start, end in line: ..

BFS + 백트래킹 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크www.acmicpc.net 0 - 빈 칸1 - 벽2 - 바이러스 처음에 생각한 방식 이것도 처음에 패턴 찾아서 쌩자 구현하려 했는데, 불가능이다. 그 이유는 바이러스(2)가 벽(1)을 만날때까지 상하좌우로 이동하며 벽(0)을 바이러스(2)로 감염시키기 때문이다. 즉, 패턴을 찾을 수 없다. 접근 방식바이러스들(2)의 위치에서 동시에 퍼져야 하므로 BFS벽을 무조건 3개 세워야 하는데, 바이러스가 최대한 퍼지지 않는..

BFS 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로www.acmicpc.net (1) 처음에 생각한 방식 - V1 (실패)# 벽 부수고 이동하기 (골드 3) / BFSimport sysfrom collections import dequen, m = map(int, sys.stdin.readline().split())graph = [[] for _ in range(n)]visited = [[False] * m for _ in range(n)]..

BFS 문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가www.acmicpc.net 문제 조건처음에 아기 상어의 크기는 2, 아기 상어는 상하좌우로 인접한 한 칸씩 이동아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지날 수 없고, 나머지 칸은 모두 지나갈 수 있다.아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.더 이상 먹을 수 있는 물고기가 공간에 없다면 아기..