정의 동적 계획법(Dynamic Programming, 이하 DP)이란, 최적화 이론을 기반으로 특정 범위까지의 값을 구하기 위해 이전에 구한 값을 이용하여 효율적으로 계산하는 알고리즘 설계 기법이다. 실질적으로, DP는 DFS나 BFS처럼 특정 방식으로 구현한다기보다는, 문제를 해결하는 하나의 방식과 유사하다. DP는 기본적으로 분할 정복 알고리즘과...

문제 링크 2667번 해결책 import sys N = int(sys.stdin.readline().rstrip()) maps = [] is_visited = [[False for i in range(N)] for j in range(N)] for i in range(N): maps.append(list(sys.stdin.readlin...

문제 링크 18405번 해결책 import sys N, K = map(int, sys.stdin.readline().rstrip().split()) test_tube = [[]] # 열, 행, 바이러스 번호 순서 virus_loc = [[] for i in range(K+1)] for x in range(1,N+1): temp_list...

문제 링크 1388번 해결책 import sys N, M = map(int, sys.stdin.readline().rstrip().split()) floor = [] for i in range(N): temp_str = list(sys.stdin.readline().rstrip()) floor.append(temp_str) is_...

문제 링크 3055번 해결책 import sys R, C = map(int, sys.stdin.readline().rstrip().split()) path = [] water = [] stone = [] dochi = [] dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] for i in range(R): tempst...

문제 링크 2617번 해결책 import sys N, M = map(int, sys.stdin.readline().rstrip().split()) """ 아이디어 정리 A번 구슬보다 무겁거나 가벼운 것이 N//2+1 개 이상이면...! 만약 5개의 구슬이 있다면, A 구슬보다 무겁거나 가벼운 것이 3개 이상인 경우 A 구슬은 절대 중앙이 될 수 ...

문제 링크 2294번 해결책 import sys n, k = map(int, sys.stdin.readline().rstrip().split()) coins = [] for i in range(n): coin=int(sys.stdin.readline().rstrip()) if coin not in coins and coin <...

문제 링크 1948번 해결책 import sys n = int(sys.stdin.readline().rstrip()) m = int(sys.stdin.readline().rstrip()) to_city = [[] for i in range(n + 1)] back_city = [[] for i in range(n + 1)] indegree = [...

문제 링크 1432번 해결책 import sys N = int(sys.stdin.readline().rstrip()) path = [[] for i in range(N + 1)] indegree = [0 for i in range(N + 1)] for i in range(1,N+1): str_in = sys.stdin.readline()...

문제 링크 2637번 해결책 import sys N = int(sys.stdin.readline().rstrip()) M = int(sys.stdin.readline().rstrip()) indegree = [0 for _ in range(N + 1)] path = [[] for _ in range(N + 1)] for _ in range(M...