본문 바로가기

전체 글54

느리게 갱신되는 세그먼트 트리(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.
위상 정렬(Topological Sort) 완벽해부 (DAG와 진입 차수) 대학교 수강신청 기간을 떠올려 보십시오. '자료구조' 과목을 수강하려면 반드시 'C언어 기초'를 먼저 이수해야만 하고, '운영체제'를 들으려면 '컴퓨터 구조'를 먼저 들어야 합니다. 이처럼 우리의 현실 세계와 프로젝트 관리(PM)에서는 "어떤 작업을 수행하기 전에 반드시 선행되어야만 하는 작업의 순서"가 명확하게 존재하는 경우가 무수히 많습니다. 소프트웨어 빌드 시스템(Make, Gradle)에서 소스 코드의 의존성을 파악하여 빌드 순서를 결정하는 과정 역시 마찬가지입니다. 이렇게 복잡하게 얽힌 선후 관계의 규칙을 절대 위배하지 않고, 모든 작업을 차례대로 나열하여 올바른 실행 순서를 찾아주는 마법의 알고리즘이 바로 '위상 정렬(Topological Sort)'입니다. 그래프 이론 중에서도 실생활 응용력.. 2026. 2. 22.

티스토리툴바