스택으로 히스토그램 최대 직사각형 찾기
April 03, 2026백준 3050 집들이 문제는 2D 격자에서 벽이 없는 가장 큰 직사각형 방을 찾는 문제입니다. 핵심은 이 문제를 "히스토그램에서 가장 큰 직사각형 찾기" 로 변환한 뒤, 스택을 이용해 O(N…
Algorithm
19개의 글
세그먼트 트리 (Segment Tree)
January 29, 2026세그먼트 트리(Segment Tree)는 특정 구간(Segment…
CCW(Counter Clock Wise)
July 26, 2025CCW(Counter Clock Wise)는 2차원 평면 위의 세 점 A, B, C…
트라이 (Trie)
April 25, 2025검색창에 'ap'를 입력하는 순간 'apple', 'application', 'apply' 같은 단어가 뜨는 자동완성 기능. 이 기능의 핵심에 트라이(Trie…
외판원 순회 (TSP, Traveling Salesman Problem)
April 25, 2025외판원 순회 문제(Traveling Salesman Problem, TSP…
프림 알고리즘 (Prim's Algorithm)
April 10, 2025이전 포스트에서 크루스칼 알고리즘으로 최소 신장 트리(MST)를 구하는 방법을 정리했습니다. 이번에는 같은 MST 문제를 다른 방식으로 접근하는 프림 알고리즘(Prim's Algorithm) 을 정리합니다. 최소 신장 트리(MST…
최소 스패닝 트리(MST)와 크루스칼 알고리즘
March 16, 2025스패닝 트리 (Spanning Tree…
분할정복(Divide and Conquer)
February 25, 2025분할정복(Divide and Conquer)은 복잡한 문제를 더 작은 하위 문제로 나눠 해결하는 알고리즘 설계 패러다임입니다. 기본 단계 분할정복은 세 단계로 이루어집니다. 분할(Divide…
트리 순회 — 전위, 중위, 후위, 레벨 순회
February 15, 2025순회(Traversal) 란 트리의 모든 노드를 방문하면서 값을 확인하는 작업입니다. 어떤 노드를 먼저 방문하느냐에 따라 순회 방법이 달라지며, 이진 트리에서는 크게 네 가지로 나뉩니다. 전위, 중위, 후위 순회는 재귀로, 레벨 순회는 큐(BFS…
트리에서의 동적 계획법 (Tree DP)
February 10, 2025트리 DP는 일반 DP와 다르게 계층 구조의 트리 위에서 상태를 전이합니다. 핵심은 DFS…
위상 정렬 (Topological Sort)
January 30, 2025수강신청을 할 때 선수과목을 먼저 들어야 하는 것처럼, 작업들 사이에 선후 관계가 있을 때 올바른 실행 순서를 결정하는 알고리즘이 위상 정렬(Topological Sort) 입니다. 1. 위상 정렬이란? 위상 정렬은 방향 비순환 그래프(DAG…
유니온 파인드(Union-Find) 알고리즘
November 08, 2024유니온 파인드(Union-Find)는 두 노드가 같은 집합에 속하는지 판별하는 그래프 알고리즘입니다. 합집합 찾기 알고리즘이라고도 부르며, 서로 연결되지 않은 노드들의 집합을 다루기 때문에 서로소 집합(Disjoint Set…
플로이드 워셜(Floyd-Warshall) 알고리즘
October 25, 2024플로이드 워셜(Floyd-Warshall) 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 한 번에 구하는 알고리즘입니다. 다익스트라가 단일 출발점의 최단 경로를 구하는 것과 달리, 플로이드 워셜은 모든 쌍(Pair…
비트 연산과 아스키코드 변환
September 25, 2024비트 연산과 아스키코드 변환은 코딩테스트에서 단골로 등장하는 테크닉입니다. 특히 비트마스킹은 집합을 정수 하나로 표현해 상태 압축 DP…
우선순위 큐와 힙 (Priority Queue & heapq)
September 05, 2024일반 큐(Queue)는 먼저 들어온 것이 먼저 나가는 FIFO…
벨만-포드(Bellman-Ford) 알고리즘
July 06, 2024벨만-포드(Bellman-Ford) 알고리즘은 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘입니다. 다익스트라와 달리 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있으며, 음수 순환(Negative Cycle…
다익스트라(Dijkstra) 알고리즘
May 05, 2024다익스트라(Dijkstra…
이진 탐색 (Binary Search)
March 17, 2024업다운 게임을 떠올려보면 이진 탐색의 원리가 바로 보입니다. 1~100 사이 숫자를 맞출 때 50부터 시작해서 "UP / DOWN…
다이나믹 프로그래밍 (Dynamic Programming)
January 04, 2024다이나믹 프로그래밍(Dynamic Programming, DP…