최소 공통 조상란?최소 공통 조상(LCA) 문제는 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제 ex) 8번 노드와 15번 노드의 최소 공통 조상은 2번 노드이다.ex) 3번 노드와 15번 노드의 최소 공통 조상은 1번 노드이다. 최소 공통 조상(LCA) 알고리즘 [기본]모든 노드에 대한 깊이(depth) 계산두 노드의 깊이(depth)가 동일하도록 거슬러 올라감이후 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라감기본적인 최소 공통 조상(LCA) 알고리즘 구현 : Python https://www.acmicpc.net/problem/11437# 기본적인 LCA 알고리즘import syssys.setrecursionlimit(int(1e5)) #런타임 오류 피하기n=..

간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로하나의 시작 정점에서 끝 정점까지의 최단 경로1) 다익스트라(dijkstra) 알고리즘: 음의 가중치 X# Priority queue그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘시작 정점에서 각 정점까지의 최단 거리를 저장할 리스트 생성 (각 거리는 무한대로 초기화, 시작 정점 거리는 0)시작 정점과 거리를 우선순위 큐에 삽입우선순위 큐에서 가장 짧은 거리를 가진 정점 추출 → 인접한 정점 모두 확인 → 기존 거리보다 멀면 무시인접한 정점까지의 새로운 거리가 기존 저장된 거리보다 짧으면 → 거리 갱신 → 해당 정점과 갱신된 거리를 우선순위 큐에 삽입우선선위 큐가 모두 빌 때까지 반복구분다익..

신장 트리 (Spanning Tree)n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리최소 신장 트리 (Minimum Spanning Tree)무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리그래프에서 최소 비용 문제KRUSKAL 알고리즘# Union-Find 알고리즘가중치가 작은 간선을 차례대로 선택하여 MST를 구성하는 알고리즘그래프의 모든 간선을 가중치 기준으로 오름차순 정렬가중치가 가장 낮은 간선부터 하나씩 확인해당 간선이 연결하는 두 정점의 대표자가 다르다면 → 사이클이 생기지 않으므로 MST 집합에 추가두 정점의 대표자가 같다면 → 사이클이 생기므로 간선을 무시모든 정점이 연결될 때까지 위 과정을 반복PRIM 알고리즘#..

https://youtu.be/eJC2oetXaNk?si=n6ZFPnv56clCkA8f코드없는 프로그래밍님의 영상이 가장 이해하기 좋았다. - Problem이 Sub Problem으로 쪼개질 때- Sub Problem의 solution으로 Problem의 solution을 구할 수 있을 때- 이런 Sub Problem들이 겹칠 때 fib_array=[0,1]def fib_td(n): #Top-down if n하지만 Top-Down 방식은 recursion depth exceeded 에러가 발생할 수도 있음. def fib_dp(n): #Bottom-up fib_array=[0,1] for i in range(2,n+1): num=fib_array[i-1]+fib_array[i..