# 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 원소가 속한 집합을 합치기 def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] = b # 노드의 개수와 간선(Union 연산)의 개수 입력 받기 v, e = map(int, input().split()) parent = [0] * (v +..

서로소 집합 # find 함수 : 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 관행적 함수 이름 # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: # 자기 자신이 아니라면 return find_parent(parent, parent[x]) return x # 두 원소가 속한 집합을 합치기(합집합) def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: # 숫자가 더 큰 쪽이 작은 쪽을 부모 함수로 삼는다 parent[b] = a else: parent[a] = b # 노드의 개수와 간선(Union 연..

자기 자신에서 자기 자신으로 가는 경우는 갱신되지 않는다. INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수 및 간선의 개수를 입력받기 n = int(input()) m = int(input()) # 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화 graph = [[INF] * (n + 1) for _ in range(n + 1)] # 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화 for a in range(1, n + 1): for b in range(1, n + 1): if a == b: graph[a][b] = 0 # 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화 for _ in range(m): # A에서 B로 가는 비용은 C라고..

다익스트라 최단 경로 알고리즘 최단 경로 알고리즘은 다이나믹 프로그래밍의 원리가 적용된 문제다. 다양한 다익스트라 알고리즘이 많지만 대표적으로 최단 경로 문제를 설명한다. 방문하지 않은 노드 중에서 가장 최단거리 비용이 작은 것을 선택해야 하는데 2번과 5번이 비용이 같다. 어느 것을 선택해도 상관없지만 보통 숫자가 작은 것을 선택한다. 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 테이블의 모든 원소를 확인 탐색(순차 탐색)한다. import sys input = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수, 간선의 개수를 입력받기 n, m = map(int, input().s..

효율적인 화폐 구성 N X M 만큼의 시간 복잡도가 소요된다. # 정수 N, M을 입력 받기 n, m = map(int, input().split()) # N개의 화폐 단위 정보를 입력 받기 array = [] for i in range(n): array.append(int(input())) # 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [10001] * (m + 1) # 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업) d[0] = 0 for i in range(n): for j in range(array[i], m + 1): if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우 d[j] = min(d[j], d[..

다이나믹 프로그래밍(동적 계획법) 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운(하향식)과 보텀업(상향식))으로 구성된다. 시간복잡도를 획기적으로 줄일 수 있다! 프로그래밍 분야에서 동적이란 어떤 의미일까? 자료 구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다. 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어다. 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용한다. 1. 최적 부분..