Algorithm
알고리즘 학습 기록
-
1. 삽입 정렬은 이미 정렬된 구간을 믿는다
삽입 정렬에서 왜 앞부분을 끝까지 다시 보지 않아도 되는지, 당시의 의문과 작은 배열 추적을 통해 선택 정렬과 비교한다.
수정 2026.09.09 · 기초 개념과 예제를 보강하고 시리즈 흐름을 연결
조회수 —
-
2. 힙은 한 경로만 고쳐도 된다
OJ 60점과 DownHeap 의심 메모에서 출발해 힙 삽입과 삭제가 한 경로만 복구하는 이유를 확인한다.
수정 2026.09.09 · 기초 개념과 예제를 보강하고 시리즈 흐름을 연결
조회수 —
-
3. 모든 노드가 끝까지 내려가지는 않는다
DownHeap을 모든 부모에 호출해도 상향식 힙 생성이 O(n)인 이유를 높이별 노드 수로 따라간다.
수정 2026.09.09 · 기초 개념과 예제를 보강하고 시리즈 흐름을 연결
조회수 —
-
4. k번째 값만 필요하면 전부 정렬하지 않는다
최소 힙을 한 번 만든 뒤 k-1번만 꺼내는 과제 코드에서 O(n+k log n)을 이해한다.
수정 2026.09.09 · 기초 개념과 예제를 보강하고 시리즈 흐름을 연결
조회수 —
-
5. 정렬된 자리는 힙에서 빼낸다
최댓값을 배열 끝으로 보낸 뒤 힙 크기를 줄이는 과정을 추적하며 힙 정렬의 경계와 불변식을 이해한다.
수정 2026.09.09 · 기초 개념과 예제를 보강하고 시리즈 흐름을 연결
조회수 —
-
6. 새 노드 없이 합쳐도 호출 스택은 남는다
연결 리스트를 끊고 기존 노드를 다시 잇는 과정을 따라 더미 노드, 안정성, 재귀 공간을 구분한다.
수정 2026.09.09 · 기초 개념과 예제를 보강하고 시리즈 흐름을 연결
조회수 —
-
7. 퀵 정렬의 경계는 한 칸도 그냥 넘길 수 없다
Lomuto와 Hoare의 서로 다른 반환 경계를 구분하고 3-way partition의 세 구간을 직접 추적한다.
수정 2026.09.09 · 기초 개념과 예제를 보강하고 시리즈 흐름을 연결
조회수 —
-
8. 이진 탐색은 못 찾았을 때의 답도 정한다
같은 이진 탐색 구조가 exact search, predecessor, lower bound에서 다른 실패값을 내는 이유를 계약으로 정리한다.
수정 2026.09.09 · 기초 개념과 예제를 보강하고 시리즈 흐름을 연결
조회수 —
-
9. 그래프의 저장 방식이 탐색 비용을 바꾼다
간선만 남길 수 있는지 묻던 기록에서 출발해, 인접리스트의 포인터가 가리키는 대상과 저장 방식별 탐색 비용을 확인한다.
수정 2026.09.09 · 기초 개념과 예제를 보강하고 시리즈 흐름을 연결
조회수 —
-
10. DFS는 바로 들어가고 BFS는 차례를 기다린다
바로 재귀로 처리하는 DFS와 큐 뒤에 넣어 두는 BFS라는 노트의 깨달음을, 같은 그래프의 방문 순서와 거리 배열로 따라간다.
수정 2026.09.09 · 기초 개념과 예제를 보강하고 시리즈 흐름을 연결
조회수 —
-
11. 방향이 생기면 방문 표시만으로는 부족하다
미완성으로 남아 있던 방향그래프 노트를 다시 읽고, 도달 가능성·순환·강연결·위상 순서가 서로 다른 질문임을 작은 예제로 구분한다.
수정 2026.09.09 · 기초 개념과 예제를 보강하고 시리즈 흐름을 연결
조회수 —
-
12. 가장 싼 선택을 믿을 수 있는 조건
동전 반례와 최소신장트리의 분할 속성을 연결해, Prim과 Kruskal이 현재 가장 싼 간선을 선택해도 되는 조건을 따라간다.
수정 2026.09.09 · 기초 개념과 예제를 보강하고 시리즈 흐름을 연결
조회수 —
-
13. 최단 경로는 음수 간선에서 갈라진다
최단 경로가 없다는 노트의 문장에 출발점과 도착점 조건을 붙이고, Dijkstra의 확정과 Bellman-Ford의 반복 완화를 비교한다.
수정 2026.09.09 · 기초 개념과 예제를 보강하고 시리즈 흐름을 연결
조회수 —
-
14. 같은 부분문제를 다시 풀지 않는다
에어텔 과제에 보관된 재귀와 반복문 코드를 같은 점화식으로 읽고, 중복 호출·숙박비의 위치·경로 복원을 직접 확인한다.
수정 2026.09.09 · 기초 개념과 예제를 보강하고 시리즈 흐름을 연결
조회수 —