👀 finalfrontier

👆 Sound of Sorting 정렬 알고리즘의 분류 Stable Sorting : 중복된 원소의 순서가 정렬된 후에도 유지됨이 보장된다. Unstable Sorting : 중복된 원소의 순서가 정렬된 후에 유지됨이 보장되지 않는다. K1, .., K2, .. 순서인 배열에서 정렬 후 K1, K2 임이 보장되면 stable, K2, K1일 수 있으면 unstable in-place: 내부 정렬, 정렬을 위해 외부 배열이 필요하지 않다. not in-place: 외부 정렬, 정렬을 위해 외부 배열이 필요하다. 🔥 핵심은 **교환/선택/삽입** 이다. 대부분의 정렬 알고리즘은 이 세 가지 개념을 응용한다. 1. O(N^2) 알고리즘 1. 교환 정렬 Exchange Sort for i in range(0, ..

BaekJoon 1007: 벡터 매칭 풀이 방법 집합 P는 n개의 점들의 집합이고, P의 벡터 매칭은 P의 모든 점을 한 번씩 사용하여 만든 벡터의 집합이다. 즉, $P = {(x_1, y_1), (x_2, y_2), \dots , (x_n, y_n)}$ $VM = {(x_i - x_j,\space y_i - y-j)\space|\space 1 \le i, j \le n, i \ne j }$ 따라서 벡터 매칭에 속하는 모든 벡터의 합은 다음과 같이 구할 수 있다. $v_1 = (x_2 - x_1, \space y_2 - y_1)$ $v_2 = (x_4 - x_3, \space y_4 - y_3)$ $ \dots $ $v_{n/2} = (x_n - x_{n-1}, \space y_n - y_{n-1})$ ..

BaekJoon 1005: ACM Craft 풀이 방법 위상 정렬 topological sorting 과 DP를 활용하여 문제를 해결한다. 인접 리스트를 사용해 유향 그래프를 만들고, 진입 간선의 수를 체크하기 위해 degree 배열을 만들어 준다. 정점을 모두 담을 큐도 하나 선언해 준다. from collections import deque time = [0] + list(map(int, input().split())) # time to build result = time.copy() degree = [0] * (N + 1) graph = [[] for _ in range(N+1)] queue = deque([i+1 for i in range(N)]) 먼저, 건물을 짓는 순서 X, Y 가 주어질 때마..

위상 정렬 위상 정렬이란? 위상 정렬 Topological Sorting 이란 방향이 있는 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 즉 한 정점에 도달하기 전 먼저 거쳐야 하는 정점들의 순서가 있는 경우 사용하는 알고리즘이다. 만약 특정 수강과목에 선수과목이 있다면 그 선수과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 대 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 방향이 있는 (유향의) 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가..