개념 최소 신장 트리(Minimum Spanning Tree)는 그래프의 모든 정점을 연결하면서 간선의 가중치 합이 최소인 트리이다. 핵심 특징 신장 트리: V개 정점, V-1개 간선, 사이클 없음, 모든 정점 연결 최소 가중치: 가능한 신장 트리 중 가중치 합이 최소 두 가지 대표 알고리즘: 크루스칼 (간선 중심), 프림 (정점 중...

개념 해시 테이블(Hash Table)은 키(key)를 해시 함수로 변환하여 배열 인덱스로 사용하는 자료구조이다. Chaining은 충돌을 연결 리스트로 처리하는 방식이다. 구성 요소 요소 설명 해시 함수 키를 배열 인덱스로 변환 ...

문제 미로에 지훈이랑 불이랑 같이 있고, 같은 시간에 한칸씩 이동할 수 있다. 밖으로 통과할수 있는지 없는지, 있다면 탈출시간을 알아보자 접근법 사람, 불 모두 같이 큐에 넣고 BFS 돌리는 방법으로 했다. 그냥 했을때는 틀렸고 몇가지 주의해야할 점이 있었는데. 불의 좌표를 먼저 큐에 다 넣고 마지막에 지훈의 좌표를 넣어야 함. (불이 먼...

개념 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘이다. 음수 가중치도 허용하며, 3중 for문으로 구현이 간단하다. 핵심 특징 모든 쌍 최단 경로: 모든 (i, j) 쌍의 최단 거리를 한 번에 구함 DP 기반: 경유 정점을 하나씩 추가하며 갱신 음수 가중치 허용: 음수 사이클 탐지도 가능 동작 원리 핵심 아이디어: di...

개념 최소 공통 조상(Lowest Common Ancestor, LCA)은 트리에서 두 노드의 공통 조상 중 가장 깊은(가장 가까운) 노드를 찾는 문제이다. LCA 예시 1 /|\ 2 3 4 /| | 5 6 7 / 8 LCA(5, 6) = 2 LCA(5, 7) = 1 LCA(...

개념 하나의 시작 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다. 다익스트라와 달리 음수 가중치 간선이 있어도 동작하며, 음수 사이클을 탐지할 수 있다. 핵심 특징 음수 가중치 허용: 다익스트라가 못 하는 것을 할 수 있음 음수 사이클 탐지: 무한히 짧아지는 경로가 있는지 판별 모든 간선을 V-1번 반복: 매 반복마다...

개념 펜윅 트리(Fenwick Tree), 또는 이진 인덱스 트리(Binary Indexed Tree, BIT)는 구간 합을 효율적으로 계산하는 자료구조이다. 세그먼트 트리와 비교 항목 펜윅 트리 세그먼트 트리 메모리 O(N) O(4N) ...

개념 하나의 시작 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다. 음수 가중치가 없는 그래프에서 동작한다. 핵심 특징 단일 출발점 최단 경로: 하나의 시작점에서 모든 정점까지의 최단 거리 탐욕적 접근: 현재까지 가장 가까운 정점을 선택하여 확장 음수 간선 불가: 음수 가중치가 있으면 올바른 결과를 보장하지 않음 동...

개념 세그먼트 트리(Segment Tree)는 구간에 대한 질의와 업데이트를 효율적으로 처리하는 이진 트리 자료구조이다. 특징 특징 설명 구간 질의 구간 합, 최솟값, 최댓값 등을 O(log N)에 계산 점 업데이트 특정...

개념 방향 그래프(DAG: Directed Acyclic Graph)에서 정점들을 간선의 방향을 거스르지 않도록 나열하는 알고리즘이다. 핵심 특징 선행 조건 처리: A → B이면 A가 반드시 B보다 먼저 나옴 DAG에서만 가능: 사이클이 있으면 위상 정렬 불가능 결과가 유일하지 않음: 여러 유효한 순서가 존재할 수 있음 동작 원리...