https://www.acmicpc.net/problem/11971. 프림# 프림 풀이(다익스트라)import heapqimport sysinput = sys.stdin.readlineN, M = map(int,input().split())arr = [[] for _ in range(N+1)]visited = [ 0 for _ in range(N+1)]for _ in range(M): A,B,C = map(int,input().split()) arr[A].append([C,B]) # 가중치를 기준으로 push, pop을 해줘야하니까 순서를 바꾸기 arr[B].append([C,A])ans = 0cnt = 0q = [[0,1]] # 1에서 출발할거다! 가중치 없이!while q: if..

https://www.acmicpc.net/problem/1240from collections import dequeimport sysinput = sys.stdin.readlineN, M = map(int,input().split())arr = [[] for _ in range(N+1)]for _ in range(N-1): a,b,dist = map(int,input().split()) arr[a].append((b, dist)) arr[b].append((a, dist)) # 무방향이므로 양쪽으로 연결def bfs(start, end): q = deque([(start, 0)]) visited = [0] * (N + 1) visited[start] = 1 whil..

❇️오늘의 학습 키워드 : 노드 사이의 거리(백준 #1240) 문제 N개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.입력첫째 줄에 노드의 개수 N과 거리를 알고 싶은 노드 쌍의 개수 M이 입력되고 다음 N−1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.출력 M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.제한 2≤N≤1000 1≤M≤1000트리 상에 연결된 두 점과 거리는 10000이하인 자연수이다.트리 노드의 번호는 1부터 N까지 자연수이며, 두 노드가 같은 번호를 갖는 경우는 없다.예제 입력 1 4 22 1 24 3 21 4 31 23 2예..

https://www.acmicpc.net/problem/1717import syssys.setrecursionlimit(10**6)input = sys.stdin.readlinedef _union(A, B): # 최대 높이를 확인해서 효율적으로 합쳐주기! A = _find(A) B = _find(B) if A == B: return # rank가 높은 친구한테 낮은 친구를 붙여주는게 더 이득! if rank[A]  Union-Find 알고리즘에서 랭크(rank)가 높은 쪽으로 낮은 쪽을 붙이는 이유: 트리의 깊이가 늘어나지 않게 되어 효율적이기 때문! 예시트리의 높이가 3인 집합과 높이가 1인 집합을 합칠 때, 높이 1인 트리를 높이 3인 트리에 붙이면 트리의 높..

1️⃣ 버블 정렬- 양옆에 위치한 두 값을 비교하면서 크기 순으로 정렬- 뒤에서부터 정렬됨- 별도의 메모리 공간이 필요하지 않지만, 시간복잡도가 O(n²) 2️⃣ 선택 정렬- 배열을 순회하면서 배열의 앞에서부터 차례대로 각 인덱스에 들어갈 값(오름차순이면 최솟값)을 선택해 위치시킴- 구현이 간단하고 별도의 메모리 공간이 필요하지 않지만, 시간복잡도가 O(n²) 3️⃣ 삽입 정렬- 배열을 앞에서부터 순회하면서 정렬된 부분의 적절한 위치에 값을 삽입하는 방식- 시간복잡도는 O(n²)  4️⃣ 합병 정렬- 재귀를 이용하는 분할(배열을 쪼개는 것)정복(분할한 배열을 정렬하면서 하나로 합병하는 것) 알고리즘- 시간 복잡도는 O(nlogn)5️⃣ 퀵 정렬- 합병 정렬과 마찬가지로 분할 정복 알고리즘- 배열에서 피봇..

❇️오늘의 학습 키워드 : DFS 알고리즘 DFS 알고리즘?- 그래프 탐색 알고리즘으로, 노드와 노드를 잇는 간선을 따라가며 모든 노드를 방문하는 방식- 트리나 그래프의 구조를 탐색하거나 경로를 찾는 데 사용며, 재귀나 스택을 활용하여 쉽게 구현할 수 있음!- 미로 탈출, 연결 요소 찾기, 경로 찾기에 많이 활용- but 최단 경로를 보장 xDFS 알고리즘의 동작 원리    (1) 현재 노드에서 갈 수 있는 한 최대로 깊게 탐색    (2) 더 이상 갈 곳이 없으면 직전 노드로 되돌아가 다른 경로를 탐색    (3) 모든 노드를 방문할 때까지 반복DFS 알고리즘의 특징- 후입선출 구조인 스택을 사용해 탐색- 방문 여부를 visited 리스트로 기록- 모든 노드를 한 번씩 방문 -> 시간 복잡도는 O(V ..