개념 큰 문제를 작은 부분 문제로 나누어 풀고, 결과를 저장하여 재사용하는 알고리즘 설계 기법이다. 핵심 특징 최적 부분 구조: 큰 문제의 최적해가 부분 문제의 최적해로 구성됨 중복 부분 문제: 같은 부분 문제가 여러 번 반복 등장 메모이제이션/타뷸레이션: 한 번 계산한 결과를 저장하여 재계산 방지 DP vs 분할 정복 vs 그리...

개념 메모리 풀(Memory Pool)은 미리 할당한 메모리 블록을 관리하여 동적 할당의 오버헤드를 줄이는 기법이다. 동적 할당 vs 메모리 풀 항목 동적 할당 (new/malloc) 메모리 풀 할당 속도 느림 (OS 호출) 빠름 (배열 ...

문제 f(a) = a의 약수의 합 g(x) = f(1) + f(2) + … + f(x) 자연수 N이 주어질때 g(N) 구하기 접근법 처음에는 입력 받고 각 케이스마다 f(), g() 함수 돌려서 답을 구하게 할려고 했었다. 그런데 f 함수에서 소인수 분해를 해야 하나…? 이런 생각을 하게 되면서 시간초과가 발생할것을 알았다. 그 뒤로 내 머리로 생...

개념 네트워크 플로우는 소스(S)에서 싱크(T)로 흘려보낼 수 있는 최대 유량을 구하는 문제이다. 핵심 특징 용량 제한: 각 간선에 흘릴 수 있는 최대 유량이 정해져 있음 유량 보존: 중간 정점에서 들어오는 유량 = 나가는 유량 최대 유량 = 최소 컷: max-flow min-cut 정리 동작 원리 그래프 (용량): S --...

개념 그래프는 정점(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개 간선, 사이클 없음, 모든 정점 연결 최소 가중치: 가능한 신장 트리 중 가중치 합이 최소 두 가지 대표 알고리즘: 크루스칼 (간선 중심), 프림 (정점 중...