세그먼트 트리(Segment Tree)
세그먼트 트리(Segment Tree)는 구간에 대한 정보를 빠르게 구해낼 수 있으며 완전 이진트리 형식의 구조를 가지는 자료구조입니다. 구간 최소값을 구하는 세그먼트 트리 예시 구간의 최솟값을 구하는 세그먼트 트리는 먼저 구하고자…
2024-05-234분
글
51개최소 신장 트리(Minimum Spanning Tree)
최소 신장 트리(Minimum Spanning Tree)는 가중치가 있는 무방향 그래프의 모든 노드를 포함하면서 사이클이 없고 가중치의 합이 최소가 되는 트리입니다. 연결그래프가 주어질 때, MST를 구하는 알고리즘은 대표적으로…
2024-05-214분
Dynamic Programming (동적 계획법)
흔히 DP라 불리는 동적 계획법이란, 복잡한 문제를 여러 개의 작은 부분 문제(sub-problem)로 나누어 해결하는 문제 해결 기법입니다. 동적 계획법의 특징 중 하나는 이미 계산된 부분 문제가 다시 발생하면 새롭게 계산하지…
2024-05-1920분
위상 정렬 (Topological Sort)
위상 정렬이란 유향 그래프에서 정해진 순서를 위배하지 않도록 나열하는 것입니다. 예를 들면 전략 게임에서의 빌드 오더나 선수강과목을 예로 들 수 있습니다. 전략 게임의 빌드 오더에서 A를 짓지 않으면 B를 지을 수 없고, B를 짓지…
2024-05-173분
퀵 정렬 (Quick Sort)
퀵 정렬(Quick Sort)은 배열에 있는 수 중 사용자가 지정한 규칙대로 임의의 pivot을 잡고, 해당 pivot을 기준으로 작거나 같은 수를 왼쪽 파티션, 큰 수를 오른쪽 파티션으로 보내고 다시 왼쪽 파티션 구간에 한하여…
2024-05-163분