전체 글55 그리디(Greedy)의 정당성 증명 (매트로이드 개념 맛보기) 코딩 테스트에서 탐욕법(Greedy Algorithm) 문제를 풀고 채점을 돌릴 때, "이게 과연 항상 정답을 보장할까?"라며 등골이 서늘해진 경험이 있으신가요? 그리디 알고리즘은 "미래는 생각하지 않고, 오직 현재 눈앞에 있는 최적의 이익만을 좇는다"는 직관적이고 맹목적인 전략입니다. 어떤 문제에서는 이 무식한 전략이 마법처럼 100% 최적해(Optimal Solution)를 찾아내지만, 배낭 문제(Knapsack)처럼 교묘한 함정이 있는 문제에서는 완전히 엉터리 답을 뱉어냅니다. 그렇다면 대체 언제 그리디를 써도 안전하고, 언제 쓰면 안 되는 것일까요? 내 직감이 맞았음을 수학적으로 완벽하게 증명하기 위해 등장한 개념이 바로 '매트로이드(Matroid)' 이론입니다. 오늘은 그리디가 성립하는 두 가지.. 2026. 2. 26. 스위핑(Sweeping) 알고리즘 기초 (선분 겹침 문제 해결) 2차원 평면 위에 수백만 개의 선분이 무작위로 흩뿌려져 있다고 상상해 보십시오. "이 선분들이 겹치는 구간의 총길이는 얼마인가?" 혹은 "가장 많은 선분이 동시에 겹치는 지점은 어디인가?"라는 질문을 받았을 때, 모든 선분을 서로 일일이 대조하는 O(N^2)의 브루트 포스(Brute Force) 방식을 사용한다면 컴퓨터는 영원히 답을 내놓지 못할 것입니다. 이러한 기하학적 문제나 겹치는 구간(Interval) 최적화 문제를 마법처럼 O(N log N)의 선형 로그 시간으로 해결해 내는 기법이 바로 '스위핑(Sweeping)' 알고리즘입니다. 마치 바닥을 빗자루로 쓸고(Sweep) 지나가듯, 가상의 세로선을 왼쪽에서 오른쪽으로 쭉 이동시키며 만나는 이벤트들을 순차적으로 처리하는 이 우아하고 직관적인 알고리.. 2026. 2. 25. 분할 정복(Divide and Conquer) 거듭제곱 최적화 (O(logN) 성능) 프로그래밍 대회를 준비하다 보면 "A를 B번 거듭제곱한 결과를 C로 나눈 나머지를 구하시오 (A^B % C)"와 같은 수학 정수론 문제를 심심치 않게 마주치게 됩니다. A가 2, B가 10 정도라면 단순한 for 반복문으로 10번 곱해서 쉽게 구할 수 있습니다. 하지만 만약 B가 1,000억(100,000,000,000)이라면 어떻게 될까요? 1,000억 번의 루프를 도는 것은 최신 CPU로도 수십 초가 걸려 무조건 시간 초과(TLE) 판정을 받게 됩니다. 게다가 숫자가 기하급수적으로 커지면서 변수의 메모리 한도(Long 타입의 오버플로우)를 순식간에 박살 내버립니다. 이 끔찍한 선형 연산의 굴레를 끊고, 1,000억 번의 연산을 단 30번 대의 연산(O(log N))으로 극단적으로 압축해 내는 컴퓨터 .. 2026. 2. 24. K번째 최단 경로 찾기 (다익스트라 알고리즘 변형 기법) 내비게이션 앱에서 목적지를 검색할 때, 단순히 '가장 빠른 길(1위)' 딱 하나만 보여주지 않고, '무료 도로 우선(2위)', '경치가 좋은 길(3위)' 등 여러 개의 대안 경로를 함께 제시해 줍니다. 컴퓨터 공학의 그래프 이론에서도 이와 마찬가지로 첫 번째 최단 경로뿐만 아니라 'K번째로 짧은 경로'를 구해야 하는 고난도 상황이 발생합니다. 일반적인 다익스트라(Dijkstra) 알고리즘은 노드 방문을 한 번으로 제한하여 1등 경로만 확정 짓고 끝나버리기 때문에 이 문제를 해결할 수 없습니다. 다익스트라의 탐욕적(Greedy) 전제를 영리하게 비틀어, 우선순위 큐(Priority Queue)의 배열을 활용해 K번째 경로까지 남김없이 긁어모으는 'K번째 최단 경로(K-th Shortest Path)' 알고.. 2026. 2. 24. 최소 공통 조상(LCA) 심화 (희소 배열을 이용한 O(logN) 탐색) 방대한 가계도에서 두 사람의 가장 가까운 공통 조상을 찾거나, 거대한 컴퓨터 네트워크 트리 라우팅에서 두 노드 간의 최단 통신 경로를 계산할 때 필수적으로 사용되는 알고리즘이 있습니다. 바로 최소 공통 조상(Lowest Common Ancestor, 이하 LCA)입니다. 기본적으로 트리의 부모를 한 칸씩 거슬러 올라가는 탐색 방식은 구현이 쉽지만, 트리가 한쪽으로 편향되어 있을 경우 탐색 한 번에 O(N)이라는 막대한 시간이 소요됩니다. 만약 질의(Query)가 10만 번 쏟아진다면 가차 없이 시간 초과(TLE)가 발생하게 됩니다. 이 끔찍한 병목 현상을 해결하기 위해 동적 계획법(DP)의 일종인 '희소 배열(Sparse Table)'을 도입하여, 부모 노드를 2의 거듭제곱 단위로 비약적으로 점프(Bin.. 2026. 2. 24. 비트마스킹(Bitmasking) 외판원 순회 문제(TSP) 완벽해결 전 세계를 돌아다니며 물건을 파는 외판원(Traveling Salesman)이 있습니다. 이 외판원이 "자신의 집(시작 도시)에서 출발하여, 지도에 있는 모든 도시를 단 한 번씩만 빠짐없이 방문한 뒤, 다시 출발했던 원래 집으로 돌아오는 가장 짧고 저렴한 경로는 무엇일까?"라는 고전적인 수학적 딜레마. 이것이 바로 컴퓨터 과학에서 가장 유명한 NP-Hard 난제인 외판원 순회 문제(TSP, Traveling Salesman Problem)입니다. 도시가 10개만 넘어가도 모든 경로를 탐색하는 순열(Permutation) 방식은 O(N!)의 기하급수적인 시간이 걸려 슈퍼컴퓨터로도 풀기 힘들어집니다. 이 극악의 시간 복잡도를 O(N^2 * 2^N) 수준으로 끌어내려 코딩 테스트 통과가 가능하게 만들어 주는 .. 2026. 2. 23. 이전 1 2 3 4 5 ··· 10 다음
