# Greedy

2026년 6월 17일 알고리즘
테이프 스토리지 — 접근 시간을 최소로 만드는 greedy 배치
크기와 사용 빈도가 다른 데이터들을 하나의 테이프에 어떤 순서로 배치해야 평균 접근 시간이 최소가 될까? 빈도 대비 길이의 비율 F/L이 큰 데이터부터 앞에 놓는 greedy 전략을 세우고, 이웃한 두 데이터를 맞바꾸는 교환 논증으로 그 최적성을 증명한다.
2026년 6월 11일 알고리즘
구간 스케줄링 — 겹치지 않게 가장 많은 일 고르기
시작 시간과 종료 시간이 정해진 여러 일이 있고, 한 번에 하나만 할 수 있다. 이익이 모두 같을 때, 겹치지 않게 고를 수 있는 일의 개수를 최대로 만드는 문제를 다룬다. 종료 시간이 빠른 일부터 고르는 greedy 전략을 세우고, 교환 논증으로 그 최적성을 증명한다.
2026년 6월 8일 알고리즘
데드라인 스케줄링 — 이익을 최대로 만드는 그리디 배치
마감 기한과 이익이 있는 일들 중에서, 이익의 합을 최대로 만드는 일정을 짜는 문제를 다룬다. 이익이 큰 일부터 마감 기한에 가까운 자리에 넣는 그리디 전략을 세우고, 교환 논증으로 그 최적성을 증명한 뒤, 균형 트리로 O(N log N)까지 줄이는 방법을 살펴본다.
2026년 6월 1일 알고리즘
다익스트라 알고리즘 2 — 최단 경로 복원, 시간 복잡도, 그리고 Prim과의 비교
다익스트라 알고리즘에서 부모 배열로 최단 경로를 복원하고, 우선순위 큐로 O(m log n)을 달성한 뒤 Prim 알고리즘과 차이를 비교한다.
2026년 5월 29일 알고리즘
다익스트라 알고리즘 1 — 각 정점까지의 최단 거리만 구하기
다익스트라 알고리즘으로 한 시작점에서 모든 정점까지 최단 거리를 구한다. 확정 집합을 키우며 가장 가까운 정점을 추가하는 그리디 전략을 보고, 왜 최소 d_min이 정답인지·왜 추가한 정점의 간선만 갱신하면 되는지를 증명한다.
2026년 5월 27일 알고리즘
Prim·Kruskal은 모든 MST를 찾을 수 있는가
같은 그래프에 여러 MST가 나올 수 있다. 동률 간선이 같은 자리를 두고 맞설 때 갈림이 생기는 조건을 짚고, 목표 MST를 정해 그것을 출력하게 하는 선택 규칙을 Prim과 Kruskal 각각에 대해 구성해 두 알고리즘이 모든 MST에 도달함을 보인다. 가중치가 모두 다르면 MST가 유일함도 증명한다.
2026년 5월 26일 알고리즘
Kruskal 알고리즘 — 그리디로 MST를 만든다
Kruskal 알고리즘으로 최소 신장 트리(MST)를 구성한다. 가장 작은 간선부터 그리디하게 고르는 전략이 왜 최적인지 컷 기반 교환 논법으로 증명하고, Union-Find로 사이클 검사를 거의 상수 시간에 처리해 O(m log m)으로 마무리한다.
2026년 5월 23일 알고리즘
프림 알고리즘 (Prim) — MST를 찾는 그리디 전략
프림 알고리즘은 하나의 정점에서 시작해 현재 트리 안과 밖을 가르는 간선 중 가장 가벼운 것을 반복적으로 추가하여 MST를 만든다. 알고리즘의 동작을 단계별로 살펴보고, 매 단계 선택이 항상 어떤 MST의 부분집합에 포함된다는 사실을 귀납법과 사이클 논증으로 증명한다.
2026년 5월 23일 알고리즘
최소 신장 트리 (MST) — 정의와 성질
최소 신장 트리(MST)는 가중 연결 그래프에서 모든 정점을 잇는 간선 가중치 합이 최소인 부분 그래프다. MST가 왜 트리여야 하는지, 정확히 n−1개 간선을 갖는 이유를 증명하고, MST가 유일하지 않을 수 있는 경우를 정리한다.
2026년 5월 18일 알고리즘
그리디 알고리즘 — 매 순간 가장 좋아 보이는 선택
그리디 알고리즘은 매 단계에서 가장 좋아 보이는 선택을 하고 그 선택을 번복하지 않는다. selection sort와 최단 경로 문제를 통해 그리디의 작동 원리를 살펴보고, 눈앞의 최적이 전체 최적이 아닐 수 있는 한계를 확인한다.