Category
Preparing references and filters for this topic. 이 주제의 레퍼런스와 필터를 준비하고 있습니다.
Category Reference
복잡도, 자료구조, 정렬, 탐색, 그래프, 코테 패턴까지 알고리즘의 핵심 이론을 카드형 레퍼런스로 정리합니다.
Search titles, summaries, tags, and subcategories.
Showing 40 cards.
Subcategory
4 cards
Big-O를 입력 크기에 따른 성장률로 읽고, 코딩 테스트에서 시간 제한과 메모리 제한을 기준으로 알고리즘을 고르는 방법을 정리합니다.
3n + 10 -> O(n)
2n^2 + 50n -> O(n^2)
n log n + n -> O(n log n)재귀를 자기 자신을 호출하는 함수가 아니라 상태를 더 작은 문제로 넘기는 방식으로 읽고, 기저 조건과 콜 스택 한계를 정리합니다.
int Factorial(int n)
{
if (n <= 1) return 1; // 기저 조건
return n * Factorial(n - 1); // 더 작은 문제
}입력 크기, 값 범위, 정렬 여부, 그래프 구조, 엣지케이스를 읽고 코딩 테스트 문제의 알고리즘 후보를 좁히는 순서를 정리합니다.
1. 입력 크기와 시간 제한을 본다
2. 값 범위와 자료형을 정한다
3. 정렬 여부, 중복 여부, 그래프 조건을 표시한다
4. 가능한 복잡도 후보를 좁힌다
5. 엣지케이스를 먼저 적고 구현한다
6. 예제보다 작은 직접 케이스로 검산한다AND, OR, XOR, SHIFT를 비트 단위 조건과 상태 집합으로 읽고, 코딩 테스트에서 자주 쓰는 마스크 패턴을 정리합니다.
int mask = 0;
mask |= 1 << 2; // 2번 비트 켜기
bool has = (mask & (1 << 2)) != 0; // 2번 비트 확인
mask &= ~(1 << 2); // 2번 비트 끄기
mask ^= 1 << 2; // 2번 비트 토글
bool isOdd = (x & 1) == 1;
int doubled = x << 1;
int halved = x >> 1;10 cards
배열의 O(1) 인덱스 접근과 동적 배열의 확장 비용을 구분하고, 코딩 테스트에서 배열과 List<T>를 고르는 기준을 정리합니다.
int[] fixedArray = new int[1000];
var dynamicArray = new List<int>();
fixedArray[3] = 10; // O(1)
dynamicArray.Add(10); // 평균 O(1)연결 리스트를 노드와 포인터 연결 구조로 이해하고, 배열보다 삽입·삭제가 유리한 조건과 코테에서 덜 쓰이는 이유를 정리합니다.
var list = new LinkedList<int>();
var node = list.AddLast(10);
list.AddAfter(node, 20);
list.Remove(node);스택의 LIFO와 큐의 FIFO를 구분하고, 괄호 검사, DFS, BFS처럼 코딩 테스트에서 자주 쓰이는 패턴을 정리합니다.
var stack = new Stack<int>();
stack.Push(1);
int top = stack.Pop();
var queue = new Queue<int>();
queue.Enqueue(1);
int front = queue.Dequeue();해시 테이블을 키를 배열 위치로 바꾸는 구조로 이해하고, Dictionary와 HashSet의 평균 O(1)이 성립하는 조건을 정리합니다.
var count = new Dictionary<string, int>();
foreach (string word in words)
{
count[word] = count.GetValueOrDefault(word) + 1;
}이진 트리를 왼쪽·오른쪽 자식을 가진 계층 구조로 이해하고, 전위·중위·후위·레벨 순회의 방문 순서를 정리합니다.
class Node
{
public int Value;
public Node? Left;
public Node? Right;
}BST의 왼쪽은 작고 오른쪽은 큰 규칙을 이해하고, 높이에 따라 탐색·삽입·삭제 성능이 달라지는 이유를 정리합니다.
왼쪽 서브트리 값 < 현재 값 < 오른쪽 서브트리 값힙을 최솟값이나 최댓값을 빠르게 꺼내는 완전 이진 트리로 이해하고, 우선순위 큐의 삽입·삭제 비용을 정리합니다.
var pq = new PriorityQueue<string, int>();
pq.Enqueue("B", 20);
pq.Enqueue("A", 10);
string first = pq.Dequeue(); // "A"그래프를 정점과 간선으로 읽고, 인접 리스트와 인접 행렬의 시간·공간 비용을 기준으로 표현 방식을 고르는 방법을 정리합니다.
var graph = new List<int>[n];
for (int i = 0; i < n; i++) graph[i] = new List<int>();
graph[a].Add(b);
graph[b].Add(a); // 무방향 그래프문자열을 문자 단위 경로로 저장해 prefix 검색, 자동완성, 사전형 탐색을 빠르게 처리하는 Trie 구조를 정리합니다.
sealed class TrieNode
{
public Dictionary<char, TrieNode> Next { get; } = new();
public bool IsWord { get; set; }
}배열 구간 정보를 트리로 나누어 저장하고, 구간 질의와 단일 원소 갱신을 O(log n)에 처리하는 segment tree 기본을 정리합니다.
int Query(int node, int start, int end, int left, int right)
{
if (right < start || end < left) return 0;
if (left <= start && end <= right) return tree[node];
int mid = (start + end) / 2;
return Query(node * 2, start, mid, left, right)
+ Query(node * 2 + 1, mid + 1, end, left, right);
}5 cards
O(n²) 정렬 세 가지의 동작 차이를 비교하고, 코딩 테스트에서 직접 구현하거나 개념 확인용으로 쓰는 기준을 정리합니다.
for (int i = 0; i < arr.Length; i++)
{
for (int j = 0; j + 1 < arr.Length - i; j++)
{
if (arr[j] > arr[j + 1])
{
(arr[j], arr[j + 1]) = (arr[j + 1], arr[j]);
}
}
}병합 정렬을 반으로 나누고 정렬된 두 구간을 합치는 분할 정복으로 이해하고, O(n log n) 보장과 추가 공간 비용을 정리합니다.
1. 배열을 반으로 나눈다
2. 왼쪽과 오른쪽을 각각 정렬한다
3. 정렬된 두 배열을 하나로 병합한다퀵 정렬을 피벗 기준으로 작은 값과 큰 값을 나누는 분할 정복으로 이해하고, 평균 O(n log n)과 최악 O(n²)의 조건을 정리합니다.
pivot을 고른다
pivot보다 작은 값과 큰 값을 나눈다
왼쪽과 오른쪽을 다시 정렬한다비교하지 않는 정렬인 계수 정렬과 기수 정렬을 값 범위 조건으로 이해하고, O(n+k)가 가능한 상황과 메모리 비용을 정리합니다.
int[] count = new int[maxValue + 1];
foreach (int x in arr)
{
count[x]++;
}
int index = 0;
for (int value = 0; value < count.Length; value++)
{
while (count[value] > 0)
{
arr[index++] = value;
count[value]--;
}
}Array.Sort, List.Sort, LINQ OrderBy의 차이와 comparer 작성법을 정리하고, 코딩 테스트에서 정렬 기준을 안전하게 표현하는 방법을 설명합니다.
Array.Sort(arr);
Array.Sort(arr, (a, b) => a.CompareTo(b));
list.Sort();
list.Sort((a, b) => b.Score.CompareTo(a.Score)); // 내림차순
var sorted = items
.OrderBy(x => x.Group)
.ThenByDescending(x => x.Score)
.ToList();11 cards
이진 탐색을 정렬된 범위나 단조 조건에서 후보를 절반씩 줄이는 방법으로 이해하고, off-by-one과 lower bound 기준을 정리합니다.
int left = 0;
int right = arr.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;BFS를 가까운 거리부터 차례대로 확장하는 탐색으로 이해하고, Queue 기반 구현과 최단 거리 보장 조건을 정리합니다.
var q = new Queue<int>();
int[] dist = Enumerable.Repeat(-1, n).ToArray();
q.Enqueue(start);
dist[start] = 0;
while (q.Count > 0)
{
int current = q.Dequeue();
foreach (int next in graph[current])
{
if (dist[next] != -1) continue;
dist[next] = dist[current] + 1;
q.Enqueue(next);
}
}DFS를 한 경로를 끝까지 내려갔다가 되돌아오는 탐색으로 이해하고, 재귀와 스택 구현, 백트래킹과의 연결을 정리합니다.
void Dfs(int current)
{
visited[current] = true;
foreach (int next in graph[current])
{
if (visited[next]) continue;
Dfs(next);
}
}다익스트라를 음수 간선이 없는 가중치 그래프에서 가장 가까운 후보부터 확정하는 최단 경로 알고리즘으로 정리합니다.
var pq = new PriorityQueue<int, long>();
long[] dist = Enumerable.Repeat(long.MaxValue, n).ToArray();
dist[start] = 0;
pq.Enqueue(start, 0);유니온-파인드를 서로소 집합을 합치고 대표를 찾는 구조로 이해하고, 경로 압축과 랭크 최적화의 의미를 정리합니다.
int Find(int x)
{
if (parent[x] == x) return x;
return parent[x] = Find(parent[x]);
}
bool Union(int a, int b)
{
int ra = Find(a);
int rb = Find(b);
if (ra == rb) return false;
parent[rb] = ra;
return true;
}위상 정렬을 선후 관계가 있는 DAG에서 가능한 처리 순서를 만드는 방법으로 이해하고, 진입 차수 기반 Kahn 알고리즘을 정리합니다.
A -> C
B -> C
C -> D
가능한 순서: A, B, C, D 또는 B, A, C, DBellman-Ford를 음수 간선이 있는 그래프의 단일 시작점 최단 경로와 음수 사이클 감지 기준으로 정리합니다.
for (int i = 0; i < n - 1; i++)
{
bool changed = false;
foreach ((int from, int to, long cost) in edges)
{
if (dist[from] == INF) continue;
if (dist[to] <= dist[from] + cost) continue;
dist[to] = dist[from] + cost;
changed = true;
}
if (!changed) break;
}Floyd-Warshall을 모든 정점 쌍의 최단 거리를 구하는 O(V³) DP로 이해하고, 음수 간선과 경유지 순서 기준을 정리합니다.
for (int k = 0; k < n; k++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (dist[i, k] == INF || dist[k, j] == INF) continue;
dist[i, j] = Math.Min(dist[i, j], dist[i, k] + dist[k, j]);
}
}
}최소 신장 트리를 모든 정점을 최소 비용으로 연결하는 문제로 이해하고, Kruskal과 Prim을 고르는 기준을 정리합니다.
edges.Sort((a, b) => a.cost.CompareTo(b.cost));
long total = 0;
int used = 0;
foreach ((int a, int b, int cost) in edges)
{
if (!Union(a, b)) continue;
total += cost;
used++;
if (used == n - 1) break;
}A* 탐색을 실제 이동 비용 g와 목표까지의 추정 비용 h를 더해 후보를 고르는 최단 경로 탐색으로 정리합니다.
var open = new PriorityQueue<Point, int>();
dist[start] = 0;
open.Enqueue(start, Heuristic(start, goal));LCA를 트리에서 두 정점의 가장 가까운 공통 조상을 찾는 문제로 정리하고, 깊이 맞추기와 binary lifting 흐름을 구분합니다.
int LOG = 18;
int[,] up = new int[LOG, n];
int[] depth = new int[n];10 cards
투 포인터를 두 위치를 움직이며 후보를 줄이는 패턴으로 이해하고, 정렬 배열과 양끝 수렴, 같은 방향 이동의 차이를 정리합니다.
int left = 0;
int right = arr.Length - 1;
while (left < right)
{
int sum = arr[left] + arr[right];
if (sum == target) return true;
if (sum < target) left++;
else right--;
}슬라이딩 윈도우를 연속 구간의 상태를 유지하며 한 칸씩 이동하는 패턴으로 이해하고, 고정 길이와 가변 길이 구간을 정리합니다.
int sum = 0;
for (int i = 0; i < k; i++)
{
sum += arr[i];
}
int best = sum;
for (int right = k; right < arr.Length; right++)
{
sum += arr[right];
sum -= arr[right - k];
best = Math.Max(best, sum);
}DP를 중복되는 하위 문제의 답을 저장해 다시 쓰는 방식으로 이해하고, 메모이제이션과 타뷸레이션, 상태 정의 방법을 정리합니다.
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++)
{
dp[i] = dp[i - 1] + dp[i - 2];
}그리디를 매 순간의 선택으로 전체 최적해를 만드는 전략으로 이해하고, 언제 성립하고 언제 DP가 필요한지 구분 기준을 정리합니다.
정렬한다
현재 기준에서 가장 좋아 보이는 선택을 한다
선택 후 조건을 갱신한다
끝까지 반복한다백트래킹을 상태 공간을 DFS로 탐색하되 불가능한 가지를 빨리 버리는 방식으로 이해하고, 순열·조합·부분집합 패턴을 정리합니다.
선택한다
다음 상태로 내려간다
돌아오면서 선택을 취소한다
불가능한 가지는 더 내려가지 않는다구간 합을 빠르게 묻는 누적합과, 여러 구간 갱신을 한 번에 모아 처리하는 차분 배열의 차이를 정리합니다.
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++)
{
prefix[i + 1] = prefix[i] + arr[i];
}
int sum = prefix[right + 1] - prefix[left];다음 큰 값, 다음 작은 값, 막대 그래프 최대 직사각형처럼 가까운 더 큰/작은 원소를 찾는 단조 스택 패턴을 정리합니다.
int[] answer = new int[n];
Array.Fill(answer, -1);
var stack = new Stack<int>(); // index
for (int i = 0; i < n; i++)
{
while (stack.Count > 0 && arr[stack.Peek()] < arr[i])
{
int index = stack.Pop();
answer[index] = arr[i];
}
stack.Push(i);
}0/1 Knapsack을 각 물건을 한 번만 고르는 용량 제한 DP로 정리하고, 2차원 DP와 1차원 압축의 반복 방향을 구분합니다.
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++)
{
int weight = weights[i];
int value = values[i];
for (int w = capacity; w >= weight; w--)
{
dp[w] = Math.Max(dp[w], dp[w - weight] + value);
}
}KMP를 실패 함수로 이미 비교한 접두사 정보를 재사용해 문자열 패턴을 O(N+M)에 찾는 알고리즘으로 정리합니다.
int[] pi = BuildPi(pattern);
int matched = 0;LIS를 순서를 유지하며 고른 값들이 엄격히 증가하는 가장 긴 부분 수열 문제로 정리하고, O(N²) DP와 O(N log N) tails 방식을 구분합니다.
var tails = new List<int>();
foreach (int value in arr)
{
int index = LowerBound(tails, value);
if (index == tails.Count) tails.Add(value);
else tails[index] = value;
}