개념 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조이다. 표현 방식에 따라 시간/공간 복잡도가 달라진다. 그래프 종류 종류 설명 무방향 그래프 간선에 방향이 없음 방향 그래프 간선에 방향이 있음 ...

개념 단절점(Articulation Point): 이 정점을 제거하면 그래프가 2개 이상의 연결 요소로 분리되는 정점. 단절선(Bridge): 이 간선을 제거하면 그래프가 2개 이상의 연결 요소로 분리되는 간선. 핵심 특징 무향 그래프에서 정의 (방향 그래프는 별도 처리) DFS 트리 기반: DFS 방문 순서와 역방향 간선(back ed...

개념 트라이(Trie)는 문자열을 효율적으로 저장하고 검색하는 트리 자료구조이다. 접두사 트리(Prefix Tree)라고도 한다. 구조 (root) / | \ a b c /| | p n a / | | p t r / l (ap...

개념 방향 그래프에서 강한 연결 요소(Strongly Connected Component)란 임의의 두 정점 u, v 사이에 u→v, v→u 경로가 모두 존재하는 최대 부분 그래프이다. 핵심 특징 방향 그래프 전용: 무향 그래프에서는 연결 요소(CC)와 동일 SCC 내부: 어떤 정점에서 다른 어떤 정점으로든 도달 가능 SCC 축약 (...

개념 개방 주소법(Open Addressing)은 충돌 시 다른 빈 슬롯을 찾아 저장하는 방식이다. 모든 데이터가 해시 테이블 배열 내에 저장된다. Chaining vs Open Addressing 항목 Chaining Open Addressing 충돌 해결 ...

개념 최소 신장 트리(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(...