본문 바로가기

분류 전체보기55

동적 계획법(DP) 최장 공통 부분 수열(LCS) 과정 역추적하기 두 개의 긴 문자열 데이터가 주어졌을 때, 두 문자열이 얼마나 비슷한지(유사도) 판별하는 것은 현대 컴퓨터 과학에서 대단히 중요한 기술입니다. 염기서열(DNA)이 얼마나 일치하는지 분석하는 바이오 인포매틱스(Bioinformatics), 두 소스 코드 파일의 변경 사항을 비교하여 보여주는 깃(Git)의 diff 기능, 맞춤법 검사기와 검색어 자동교정 시스템 등 수많은 첨단 기술의 핵심 엔진으로 자리 잡고 있는 것이 바로 '최장 공통 부분 수열(Longest Common Subsequence, 이하 LCS)' 알고리즘입니다. 코딩 테스트에서는 단순히 "LCS의 길이가 얼마인가?"를 묻는 것을 넘어, "길이를 구했다면, 그 실제 문자열이 무엇인지 과정까지 역추적하여 출력하라"는 극악의 난이도를 자랑하는 심화.. 2026. 2. 23.
힙 정렬(Heap Sort) 제자리 정렬(In-place) 구현 완벽정리 데이터를 정렬하는 수많은 알고리즘 중, 힙 정렬(Heap Sort)은 O(N log N)이라는 아주 빠르고 훌륭한 시간 복잡도를 100% 확정적으로 보장하면서도, 병합 정렬(Merge Sort)처럼 배열을 복사하기 위한 추가적인 메모리 공간을 전혀 요구하지 않는 극강의 효율을 자랑합니다. 원본 배열 그 자체만을 도마 위에 올려두고 요리하듯 뚝딱 정렬을 마쳐버리는 이러한 특성을 '제자리 정렬(In-place Sort)'이라고 부릅니다. 퀵 정렬(Quick Sort)이 최악의 경우 O(N^2)으로 느려질 위험을 안고 있는 반면, 힙 정렬은 어떠한 악의적인 데이터가 들어와도 흔들림 없이 안정적인 성능을 뽑아냅니다. 오늘은 1차원 배열을 가상의 완전 이진 트리로 매핑하는 수학적 마법과, 가장 큰 값을 맨 뒤로 .. 2026. 2. 23.
오일러 경로(Eulerian Path)와 회로 (한붓그리기 알고리즘 원리) 어릴 적 스케치북에 별 모양이나 집 모양을 그리며, "펜을 한 번도 떼지 않고, 왔던 선을 다시 지나지 않으면서 전체 그림을 완성할 수 있을까?"라는 내기를 해본 적이 있으실 것입니다. 이 단순해 보이는 놀이는 18세기 천재 수학자 레온하르트 오일러(Leonhard Euler)가 '쾨니히스베르크의 7개 다리 문제'를 해결하기 위해 창시한 그래프 이론의 시초이자, 현대 컴퓨터 과학에서 네트워크 패킷 라우팅이나 DNA 시퀀싱 등에 폭넓게 응용되는 '오일러 경로(Eulerian Path)' 알고리즘의 뼈대입니다. 그래프 내의 모든 간선(Edge)을 단 한 번씩만 통과하여 완벽한 경로를 찾아내는 수학적 조건과, 이를 컴퓨터 코드로 우아하게 구현해 내는 하이어홀저(Hierholzer) 알고리즘의 동작 원리를 깊이.. 2026. 2. 22.
이분 매칭(Bipartite Matching) 기초 (네트워크 플로우 응용하기) 현실 세계의 수많은 비즈니스 문제는 결국 '자원의 효율적인 배분'으로 귀결됩니다. "5명의 직원이 있고 5개의 서로 다른 업무가 있을 때, 각 직원의 희망 업무를 반영하여 최대한 많은 사람에게 업무를 배정하려면 어떻게 해야 할까?", "비행기 좌석을 고객들의 선호도에 맞춰 가장 많이 팔려면 어떻게 매칭해야 할까?" 이러한 일대일 대응의 배정(Assignment) 문제를 수학적이고 체계적으로 풀어내는 알고리즘이 바로 '이분 매칭(Bipartite Matching)'입니다. 유체 역학에서 파생된 복잡한 네트워크 플로우(Network Flow) 이론의 특수한 형태이지만, 코딩 테스트에서는 아주 간결한 DFS(깊이 우선 탐색) 로직만으로 O(V*E)의 빠른 속도에 뚝딱 해결해 낼 수 있는 마법 같은 알고리즘의 .. 2026. 2. 22.
강한 연결 요소(SCC) 판별법 (코사라주 vs 타잔 알고리즘) 복잡하게 얽혀 있는 도로망이나 웹페이지의 하이퍼링크 네트워크, 혹은 사용자 간의 팔로우 관계를 나타내는 방향 그래프(Directed Graph)를 분석할 때, 네트워크 학자들이 가장 중요하게 살펴보는 개념이 있습니다. 바로 그래프 내부에서 "어떤 노드에서 출발하더라도 나머지 모든 노드로 찾아갈 수 있고, 또다시 자기 자신으로 돌아올 수 있는 가장 거대한 폐쇄적 무리"를 찾는 것입니다. 이러한 노드들의 끈끈한 집합을 컴퓨터 공학에서는 강한 연결 요소(Strongly Connected Component, 이하 SCC)라고 부릅니다. 거대한 그래프를 여러 개의 유의미한 그룹(클러스터)으로 분해하여 전체 시스템의 뼈대를 파악하는 핵심 기술입니다. 이 SCC를 O(V+E)의 압도적인 선형 시간에 추출해 내는 두 .. 2026. 2. 22.
펜윅 트리(Binary Indexed Tree) 구현 (구간 합을 더 가볍게) 앞서 다루었던 '세그먼트 트리(Segment Tree)'는 구간 합, 최댓값, 최솟값 등 다양한 구간 쿼리를 O(log N)의 속도로 처리할 수 있는 만능 자료구조입니다. 하지만 구현을 위해 원본 배열 크기의 4배에 달하는 거대한 메모리 공간이 필요하며, 코드가 다소 길고 복잡하다는 단점이 있습니다. 만약 우리가 풀어야 할 문제가 '단순한 구간 합(Range Sum)'과 '단일 인덱스의 값 업데이트(Point Update)' 단 두 가지만을 요구한다면 굳이 무거운 세그먼트 트리를 쓸 필요가 없습니다. 메모리는 원본 배열과 똑같은 1배(N)만 차지하면서도 코드는 단 몇 줄에 불과하고, 속도마저 비트 연산을 활용해 극단적으로 빠른 천재적인 자료구조가 있습니다. 바로 1994년 피터 펜윅(Peter Fenwi.. 2026. 2. 21.

티스토리툴바