분류 전체보기55 아호-코라식(Aho-Corasick) 다중 문자열 동시 검색 (트라이 + KMP) 여러분이 카카오톡이나 게임 서버의 채팅 금칙어 필터링 시스템을 개발한다고 상상해 보십시오. 채팅방에 올라오는 긴 문장 속에, 데이터베이스에 등록된 10만 개의 욕설 중 단 하나라도 포함되어 있는지 실시간으로 검사해야 합니다. 앞서 배운 고속 문자열 탐색 알고리즘인 KMP를 사용한다 하더라도, 패턴이 10만 개라면 KMP 알고리즘을 10만 번 반복해서 돌려야 하므로 서버는 순식간에 터져버릴 것입니다. "찾아야 할 단어가 수만 개라도, 본문 텍스트를 딱 한 번만 쭉 훑으면서 모든 단어의 포함 여부를 동시에 알아낼 수는 없을까?" 1975년, 알프레드 아호와 마거릿 코라식이 이 미친 발상을 현실로 만들어 낸 궁극의 오토마타가 바로 '아호-코라식(Aho-Corasick)' 알고리즘입니다. 트라이(Trie)의 확.. 2026. 3. 4. 에드몬드-카프(Edmonds-Karp) 알고리즘 (최대 유량 네트워크 완벽정리) 상하수도 배관망을 설계하여 도시 전체에 물을 공급하거나, 꽉 막힌 도로망에서 차량의 흐름을 최적화하여 가장 많은 차를 통과시켜야 하는 상황을 상상해 보십시오. 각 파이프나 도로마다 한 번에 통과할 수 있는 '최대 용량(Capacity)'이 정해져 있을 때, "출발지(Source)에서 도착지(Sink)까지 초당 보낼 수 있는 가장 많은 물의 양(최대 유량, Maximum Flow)은 얼마인가?"라는 질문에 완벽한 해답을 제시하는 것이 바로 네트워크 플로우(Network Flow) 알고리즘입니다. 이 분야의 기초인 포드-풀커슨(Ford-Fulkerson) 방법론의 치명적인 약점을 완벽하게 보완하고, 어떤 악의적인 데이터가 들어와도 O(V * E^2)의 확정적인 속도를 보장하는 '에드몬드-카프(Edmonds-.. 2026. 3. 3. 평형 이진 탐색 트리(Balanced BST) 자바/파이썬 내부 구현체 분석 데이터를 빠르게 검색하고, 순서대로 정렬된 상태를 유지해야 하는 시스템을 구축할 때 이진 탐색 트리(Binary Search Tree, BST)는 매우 강력한 도구입니다. 하지만 데이터가 오름차순으로 계속 들어올 경우 한쪽으로 쏠리는 편향 트리(Skewed Tree) 현상을 막기 위해, 현대 프로그래밍 언어의 창시자들은 스스로 균형을 잡는 평형 이진 탐색 트리(Balanced BST, 주로 레드-블랙 트리)를 언어의 표준 라이브러리 깊숙한 곳에 내장해 두었습니다. 하지만 흥미롭게도 전 세계에서 가장 많이 쓰이는 언어인 Java(자바)와 Python(파이썬)은 이 트리를 대하는 철학과 내부 구현 방식이 극명하게 갈립니다. 코딩 테스트 언어를 선택할 때 이 내부 구현의 차이를 모르면 치명적인 성능 저하를 겪.. 2026. 3. 2. 트라이(Trie)를 활용한 배열 내 최대 XOR 값 구하기 비트 연산의 대표 주자인 XOR(배타적 논리합)은 두 비트가 서로 다를 때 1을, 같을 때 0을 반환하는 연산입니다. 만약 10만 개의 숫자가 들어있는 거대한 배열에서, "임의의 두 숫자를 뽑아 XOR 연산을 했을 때 나올 수 있는 가장 큰(Maximum) 결과값을 구하시오"라는 문제를 만났다면 어떻게 풀어야 할까요? 10만 개 중 2개를 뽑는 조합이므로 이중 for 반복문을 사용하여 모든 경우의 수를 검사하는 O(N^2) 방식을 쓰면 100억 번의 연산이 발생해 무조건 시간 초과(TLE)가 납니다. 이 어마어마한 연산량을 O(N)으로 획기적으로 줄여주는 천재적인 해법이 있습니다. 바로 문자열 검색에 쓰이던 트라이(Trie) 자료구조를 이진수 비트(Bit)에 접목시키는 방법입니다. 비트와 트리의 기막힌 .. 2026. 3. 1. 투 포인터(Two Pointers) 응용 (연속된 부분합 문제 완벽해결) 크기가 10만 개가 넘는 거대한 수열(배열)이 주어지고, "이 배열 안에서 연속된 숫자들을 더했을 때, 그 합이 정확히 M이 되는 구간은 총 몇 개나 있을까?" 혹은 "합이 M 이상이 되는 연속 구간 중 길이가 가장 짧은 구간은 얼마인가?"라는 질문을 던졌을 때, 이중 반복문을 겹쳐 쓰는 O(N^2)의 낡은 무기를 꺼내 든다면 즉시 시간 초과(TLE)의 철퇴를 맞게 됩니다. 우리는 배열 전체를 단 한 번만 처음부터 끝까지 스캔하면서(O(N)), 마치 자벌레가 기어가듯 탐색 구간을 고무줄처럼 늘렸다 줄였다 하며 정답을 낚아채는 고급 기법을 사용해야만 합니다. 바로 '투 포인터(Two Pointers)' 알고리즘입니다. 오늘 이 글에서는 투 포인터를 이용해 연속 부분합 문제를 격파하는 핵심 논리와, "배열에.. 2026. 2. 28. 파라메트릭 서치(Parametric Search) 결정 문제로 최적해 찾기 알고리즘 코딩 테스트에서 "조건을 만족하는 가장 큰 값을 구하시오" 혹은 "조건을 만족하는 가장 작은 값을 구하시오"라는 최적화(Optimization) 문제를 자주 마주하게 됩니다. 이때 답이 될 수 있는 값의 범위가 1부터 10억까지라면, 모든 경우의 수를 하나씩 대입해보는 브루트 포스(Brute Force) 방식은 가차 없이 시간 초과(TLE)를 발생시킵니다. 이럴 때 문제의 관점을 완전히 뒤집어, 거대한 최적화 문제를 "이 값이 정답이 될 수 있는가? (Yes or No)"라는 단순한 스무고개 질문(결정 문제, Decision Problem)으로 변환하여 O(log N)의 압도적인 속도로 정답을 핀포인트로 찾아내는 마법 같은 기법이 있습니다. 바로 파라메트릭 서치(Parametric Search).. 2026. 2. 27. 이전 1 2 3 4 ··· 10 다음
