분류 전체보기79 최소 비용 최대 유량(MCMF) 알고리즘 (네트워크 플로우의 심화 확장) 앞서 다루었던 에드몬드-카프 알고리즘이 "배관망에서 목적지까지 얼마나 많은 물을 쏟아부을 수 있는가?"라는 '최대 유량'에만 집착했다면, 현실 세계의 네트워크 문제는 한 차원 더 높은 최적화를 요구합니다. 물건을 운송할 때 도로마다 통행료(비용)가 존재하고, 통과할 수 있는 트럭의 대수(용량)도 정해져 있습니다. "도착지까지 물건을 최대한 많이 보내되(Max Flow), 그 과정에서 발생하는 배송 비용을 최소화(Min Cost)하라!" 이 두 마리 토끼를 동시에 완벽하게 잡아내는 끝판왕 알고리즘이 바로 최소 비용 최대 유량(Min-Cost Max-Flow, 이하 MCMF)입니다. 네트워크 플로우와 최단 거리 탐색(Shortest Path)이 결합된 이 우아한 하이브리드 알고리즘의 동작 원리를 낱낱이 파헤.. 2026. 2. 27. 느리게 갱신되는 세그먼트 트리(Lazy Propagation) (구간 업데이트의 마법) 수십만 개의 데이터가 들어있는 배열에서 특정 구간의 합을 구하거나 값을 변경할 때, 매번 O(N)의 시간이 걸리는 것을 O(log N)으로 단축해 주는 구원자가 바로 세그먼트 트리(Segment Tree)입니다. 하지만 일반적인 세그먼트 트리에는 치명적인 약점이 하나 있습니다. 만약 "인덱스 0번부터 10만 번까지의 모든 숫자에 5를 더하시오"라는 구간 업데이트(Range Update) 명령이 내려진다면 어떻게 될까요? 트리의 맨 아래 리프 노드 10만 개를 일일이 찾아가서 값을 바꾸고 트리를 다시 거슬러 올라와야 하므로, 결국 최악의 경우 O(N log N)이라는 재앙적인 시간이 소요됩니다. 이 한계를 완벽하게 박살 내고, 거대한 구간의 업데이트조차 단 O(log N) 만에 처리해 내는 천재적인 기법이.. 2026. 2. 26. 세그먼트 트리(Segment Tree) 비재귀 구현 (메모리와 속도 최적화 팁) 알고리즘 문제를 풀다 보면 구간 쿼리(Range Query)를 효율적으로 처리해야 하는 상황이 자주 발생합니다. 특히 코딩 테스트나 competitive programming에서 세그먼트 트리(Segment Tree)는 필수적인 자료구조로 자리 잡았습니다. 하지만 재귀 방식의 세그먼트 트리는 함수 호출 오버헤드와 스택 메모리 사용으로 인해 성능 저하가 발생할 수 있습니다. 이 글에서는 비재귀(Iterative) 방식으로 세그먼트 트리를 구현하여 메모리와 속도를 동시에 최적화하는 방법을 상세히 다룹니다.1. 세그먼트 트리의 기본 개념과 필요성세그먼트 트리는 배열의 구간에 대한 질의를 O(log N) 시간에 처리할 수 있는 트리 기반 자료구조입니다. 구간 합(Range Sum), 구간 최솟값(Range Mi.. 2026. 2. 25. 동적 계획법(DP) 배낭 문제 (0-1 Knapsack 완벽해결) 알고리즘을 공부하는 수많은 개발자들을 좌절에 빠뜨리는 동적 계획법(Dynamic Programming, DP)의 가장 대표적이고 악명 높은 척도가 바로 '배낭 문제(Knapsack Problem)'입니다. 한밤중에 보석상에 침입한 도둑이 감당할 수 있는 최대 무게가 정해진 배낭을 메고 있을 때, 어떻게 보석들을 담아야 훔친 보석들의 총가치를 가장 높일 수 있을지에 대한 유명한 딜레마입니다. 이 문제는 단순한 탐욕법(Greedy)으로는 절대 풀 수 없는 치명적인 함정을 가지고 있습니다. 오늘은 동적 계획법의 정수라 불리는 '0-1 배낭 문제'의 2차원 배열 설계법과 점화식 도출 과정, 그리고 공간 복잡도를 획기적으로 줄이는 1차원 배열 최적화 기법까지 완벽하게 해부해 보겠습니다.1. 0-1 배낭 문제(0-.. 2026. 2. 23. 최장 증가 부분 수열(LIS) 알고리즘 (O(N^2) vs O(NlogN) 성능 비교) 배열 내부의 데이터 흐름을 분석하는 코딩 테스트 문제 중, '최장 증가 부분 수열(Longest Increasing Subsequence, 이하 LIS)'은 출제 빈도가 매우 높은 알고리즘입니다. "어지럽게 꼬인 전깃줄을 엉키지 않게 최소한으로 잘라내기", "순서대로 배치된 상자들 중 크기가 점점 커지도록 상자를 가장 많이 고르기" 같은 문제들이 겉모습만 다를 뿐 모두 이 LIS 알고리즘의 본질을 묻고 있습니다. LIS를 해결하는 방법은 크게 두 가지로 나뉘는데, 데이터가 적을 때 사용하는 동적 계획법(DP) 기반의 O(N^2) 방식과, 대용량 데이터 환경에서 이진 탐색(Binary Search)을 결합하여 속도를 극대화한 O(N log N) 방식이 있습니다. 이 두 가지 방식의 논리적 전개 과정을 완벽.. 2026. 2. 23. KMP 문자열 매칭 알고리즘 (접두사와 접미사 활용법) 여러분이 작성한 수만 줄의 소스 코드나 수백 페이지 분량의 방대한 텍스트 문서 안에서 "algorithm"이라는 특정 단어를 찾아야 한다고 가정해 보겠습니다. 문서 뷰어의 'Ctrl + F(찾기)' 기능은 어떻게 그 긴 문서 속에서 눈 깜짝할 새에 단어의 위치를 찾아내는 것일까요? 단순히 긴 글(본문)의 첫 글자부터 찾으려는 단어(패턴)를 하나씩 대조해 보는 브루트 포스(Brute Force) 방식은 최악의 경우 엄청난 시간이 소요됩니다. 1977년, 세 명의 천재 컴퓨터 과학자(Knuth, Morris, Pratt)는 "왜 이미 확인해서 일치했던 글자 정보들을 버리고 매번 처음부터 다시 검사해야 하는가?"라는 합리적인 의문을 품었습니다. 이 질문에서 출발하여, 문자열 탐색의 효율성을 혁명적으로 끌어올린.. 2026. 2. 23. 이전 1 ··· 4 5 6 7 8 9 10 ··· 14 다음
