Kruskal Algorithm 이란?가중치가 작은 간선부터 선택하면서, 사이클이 생기지 않도록 추가하는 방식알고리즘 과정모든 간선을 가중치 기준으로 오름차순 정렬한다.가중치가 가장 작은 간선부터 하나씩 선택한다. 유니온-파인드를 사용해 사이클이 생기는지 확인한다.만약 사이클이 생기지 않는다면, 해당 간선을 선택한다.만약 사이클이 생긴다면, 해당 간선을 버린다. N-1개의 간선이 선택될 때까지 반복한다. (MST의 성질)import sysinput = sys.stdin.readline# 유니온 파인드 (경로 압축 적용)def find(parent, x): if parent[x] != x: parent[x] = find(parent, parent[x]) return parent[x]..

분할 정복분할 정복은 직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 쪼갠 다음, 그 하위의 결과들을 조합하여 원래 문제의 결과로 만들어 낸다.분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다.정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.분할 정복의 대표적인 알고리즘은 머지 소트(병합 정렬)이 있으며, 유클리드 호제법(최대공약수 알고리즘)도 이에 해당된다. 병합 정렬배열을 절반으로 나누어 각각 정렬한 후 병합하는 방식def merge_sort(arr): if len(arr) 정복def merge(left, right): result = [] i = j = 0 while i 유클리..

0 - 1 배낭 문제다이나믹 프로그래밍의 대표적인 문제 중 하나로, 한정된 용량의 배낭에 최대 가치를 담을 수 있도록 최적의 선택을 찾는 문제이다.배낭 문제는 짐을 쪼갤 수 있는지 여부로 그리디로 풀 수 있는지, DP(Dynamic Programming)으로 풀 수 있는지 나뉜다. 0-1 배낭 문제는 짐을 쪼갤 수 없는 경우에 해당하며, 다이나믹 프로그래밍으로 풀이 가능하다. Bottom-upclass Solution: def zero_one_knapsack(self,cargo:list): capacity = 15 # 최대 용량 pack = [] # 가치 저장 for i in range(len(cargo)+1): # len(cargo) = 5 ..

부울 연산자AND, OR, NOT은 기본 부울 연산자로, 연산들을 서로 결합하거나 조합해 다른 보조 연산을 만들어 낼 수 있다. XOR이 보조 연산에 해당하며, 기본 연산의 조합으로 다음과 같이 XOR을 구성할 수 있다.x = y = True(x and not y) or (not x and y)# False 1. XOR    - 다르면 1, 같으면 0      0 ^ 0 = 0         0 ^ 1 = 1         1 ^ 0 = 1         1 ^ 1 = 0  2. AND    - 논리곱: 곱하기처럼 생각하면 쉽다.        0 & 0 = 0        0 & 1 = 0        1 & 0 = 0        1 & 1 = 1 3. OR    - 논리합: 더하기처럼 생각하면 쉽다...