컴공생 누르지 마세요! 컴공생 울어요.

서로소 집합 서로소 집합이란 공통 원소가 없는 두 집합 의미 ex) {1, 2}와 {3, 4}는 공통 원소가 없으므로 서로소 관계 ex) {1, 2}와 {2, 3}은 공통 원소가 있으므로 서로소 관계가 아님 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 union과 find 두 가지 연산으로 조작 union (합집합) 연산 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 find (찾기) 연산 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 트리 자료구조를 이용하여 집합 표현 트리를 이용한 서로소 집합 계산 알고리즘 union 합집합 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다 A와 B의 루트 노드 A'과 B'을 각각 찾는다 둘..

이코테 p.262 실전 문제 - 전보 입력 예시 3 2 1 1 2 4 1 3 2 출력 예시 2 4 내 소스코드 다익스트라 알고리즘 사용 메시지를 보내고자 하는 도시 c를 시작 노드로 설정 c로부터의 최단 시간 정보가 존재하는 도시를 카운트하여 메시지를 받는 도시 개수를 구함 c로부터의 최단 시간 정보들 중에서 최댓값을 구하여 메시지 전송에 걸리는 총 시간을 구함 import heapq import sys input = sys.stdin.readline INF = int(1e9) # 도시 개수 n, 간선 개수 m, 메시지를 보내고자 하는 도시 c 입력 받기 n, m, c = map(int, input().split()) # 그래프 입력 받기 graph = [[] for _ in range(n + 1)] f..

이코테 p.259 실전 문제 - 미래 도시 입력 예시 1 5 7 1 2 1 3 1 4 2 4 3 4 3 5 4 5 4 5 출력 예시 1 3 입력 예시 2 4 2 1 3 2 4 3 4 출력 예시 2 -1 내 소스코드 ver. 다익스트라 1번 노드에 대해 다익스트라 알고리즘을 적용한 후, 1번 노드부터 k번 노드까지의 거리 구하기 k번 노드에 대해 다익스트라 알고리즘을 적용한 후, k번 노드부터 x번 노드까지의 거리 구하기 연결된 2개의 회사는 양방향으로 이동할 수 있다고 하였으니 특정 간선 정보에 대해 D[a][b]와 D[b][a] 둘 다 설정해줘야 함 import heapq import sys input = sys.stdin.readline INF = int(1e9) # 입력받기 n, m = map(in..

플로이드 워셜 알고리즘 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 구해야 하는 경우 사용 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘 수행 다익스트라와 달리, 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없음 시간 복잡도는 O(N^3) 노드의 개수가 N개일 때, 알고리즘 상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐가는' 모든 경로를 고려함 최단 거리 정보를 저장하기 위해 2차원 리스트 사용 다익스트라는 시작 노드에서 다른 모든 노드까지의 최단 거리를 저장하기 위해 1차원 리스트 사용 플로이드 워셜은 모든 노드에서 다른 모든 노드로 가는 최단 거리 정보를 저장하기 위해 2차원 리스트 사용 다이나믹 프로그래밍 방식 노드의 개수..

다익스트라 최단 경로 알고리즘 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 '음의 간선' 즉, 0보다 작은 값을 가지는 간선이 없을 때 정상적으로 동작 기본적으로 그리디 알고리즘 매번 가장 비용이 적은 노드를 선택 알고리즘 동작 원리 출발 노드를 설정한다 최단 거리 테이블을 초기화한다 방문하지 않은 노드들 중에서 최단 거리가 가장 짧은 노드를 선택한다 해당 노드를 거쳐 다른 노드로 가는 비용을 계산한 후, 기존 비용과 비교하여 더 작은 값으로 최단 거리 테이블을 갱신한다 3번과 4번 과정을 반복한다 항상 '각 노드에 대한 현재까지의 최단 거리' 정보를 1차원 리스트인 최단 거리 테이블에 저장하며 리스트를 계속 갱신함 2가지 구현 방법 존재 ..

최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘 '길찾기' 문제 다양한 유형의 문제 존재 ex) 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우, 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우 등 실제 코테에서는 주로 전자를 요구하는 문제가 많이 출제됨 그래프를 이용하여 표현함 각 지점은 그래프의 노드 지점 간 연결된 도로는 그래프의 간선 주요 최단 경로 알고리즘 다익스트라 최단 경로 알고리즘 플로이드 워셜 벨만 포드 알고리즘 1, 2가 코테에서 주로 출제 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 적용됨

이코테 p.226 실전 문제 - 효율적인 화폐 구성 입력 예시 3 7 2 3 5 출력 예시 2 내 소스코드 점화식 a(i) = min(a(i - money[0]), a(i - money[1]), a(i - money[2]), ...) + 1 최솟값을 구하기 위해 DP 리스트를 INF로 초기화 # 입력 받기 n, m = map(int, input().split()) money_list = list(map(int, input().split())) INF = 10001 dp = [INF] * (m + 1) # 자기 자신에 대해서는 최소 화폐 개수 1개 for money in money_list: dp[money] = 1 for i in range(min(money_list), m + 1): min_money ..

이코테 p.223 실전 문제 - 바닥 공사 입력 예시 3 출력 예시 5 교재 소스코드 다이나믹 프로그래밍 기초 예제 중 하나인 타일링 문제 유형 N = 3 일 경우 바닥을 덮개로 채울 수 있는 모든 경우의 수는 다음과 같음 왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하면 다음과 같은 점화식을 세울 수 있음 왼쪽부터 (i - 1)까지의 길이가 덮개로 이미 채워져 있으면 2 x 1 덮개를 채우는 하나의 경우만 존재 왼쪽부터 (i - 2)까지의 길이가 덮개로 이미 채워져 있으면 2 x 2 덮개를 채우는 경우와 1 x 2 덮개를 채우는 경우 총 2가지 존재 따라서 점화식은 a(i) = a(i - 1) + a(i - 2) x 2 이를 DP 구현하면 다음과 같음 # 점수 N 입력받기 n = int(input())..