본문 바로가기

전체 글55

라빈-카프(Rabin-Karp) 문자열 검색 (해싱을 이용한 패턴 매칭) 수만 글자로 이루어진 거대한 웹 문서 속에서 사용자가 입력한 특정 단어를 찾아내는 '문자열 검색(String Matching)' 알고리즘. 우리는 이전 글에서 접두사와 접미사의 반복을 이용해 불일치 시 빠르게 건너뛰는 천재적인 KMP 알고리즘을 살펴보았습니다. 하지만 KMP는 코드가 매우 복잡하고 LPS 테이블이라는 전처리 과정을 거쳐야 하는 까다로움이 있습니다. 만약 "문자열의 텍스트 자체를 한 글자씩 비교하지 않고, 각 문자열을 암호화된 '숫자(Hash)'로 바꿔서 한 번에 퉁치고 비교한다면 어떨까?"라는 신선한 발상에서 탄생한 알고리즘이 있습니다. 바로 암호학과 해시(Hash) 함수의 마법을 문자열 탐색에 우아하게 접목시킨 '라빈-카프(Rabin-Karp)' 알고리즘입니다. 여러 개의 패턴을 동시에.. 2026. 2. 21.
희소 행렬(Sparse Matrix) 데이터 압축 (메모리 낭비 줄이는 법) 우리가 머신러닝, 딥러닝, 혹은 거대한 추천 시스템(예: 넷플릭스 영화 추천)을 구축할 때 마주하는 데이터는 흔히 거대한 2차원 표(행렬, Matrix) 형태로 다뤄집니다. 1,000만 명의 사용자가 10만 개의 영화에 남긴 평점 데이터를 행렬로 만든다고 상상해 보십시오. 무려 1조 개의 칸이 생깁니다. 그런데 여기서 치명적인 문제가 발생합니다. 대부분의 사용자는 기껏해야 수십 편의 영화만 보았을 뿐이므로, 1조 개의 칸 중 99.9%는 평점이 없는 '빈칸(0)'으로 채워집니다. 이처럼 대부분의 원소 값이 0인 행렬을 컴퓨터 공학에서는 '희소 행렬(Sparse Matrix)'이라고 부릅니다. 이 엄청난 양의 0을 2차원 배열에 그대로 저장하는 것은 메모리 공간의 끔찍한 낭비일 뿐만 아니라, 행렬 곱셈 등.. 2026. 2. 21.
레드-블랙 트리(Red-Black Tree) 회전 원리 (AVL 트리와 완벽 비교) 이진 탐색 트리(Binary Search Tree, BST)는 검색 속도를 획기적으로 줄여주는 훌륭한 자료구조지만, 데이터가 오름차순이나 내림차순으로 연속해서 들어올 경우 한쪽으로만 끝없이 길어지는 '편향 트리(Skewed Tree)'가 되어버린다는 치명적인 약점이 있습니다. 이 경우 검색 속도는 O(N)으로 전락해 버립니다. 이러한 최악의 시나리오를 막기 위해 스스로 트리의 균형을 맞추는 '자가 균형 이진 탐색 트리(Self-Balancing BST)'가 고안되었으며, 그중에서도 현대 소프트웨어(Java의 HashMap, C++의 std::map, 리눅스 커널 등)에서 압도적인 표준으로 사용되는 것이 바로 '레드-블랙 트리(Red-Black Tree)'입니다. 오늘은 레드-블랙 트리가 균형을 맞추는 오.. 2026. 2. 20.
재귀 함수(Recursion): 자기 자신을 호출하는 구조와 종료 조건의 중요성 프로그래밍을 처음 배울 때 반복문(for, while)까지는 수월하게 이해하다가, 처음으로 벽을 느끼는 구간이 바로 재귀 함수(Recursion)입니다. "함수가 자기 자신을 호출한다니, 이게 무슨 말장난인가?"라는 생각이 들기 십상입니다. 하지만 재귀는 복잡한 문제를 매우 간결하고 우아하게 해결할 수 있는 강력한 도구입니다. 특히 DFS(깊이 우선 탐색), 트리 순회, 동적 계획법 등 고급 알고리즘의 기초가 되므로 반드시 정복해야 합니다. 오늘은 재귀 함수의 동작 원리를 그림을 그리듯 쉽게 설명해 드립니다.1. 재귀의 정의: 마트료시카 인형[Image of Recursion call stack diagram]재귀 함수는 함수 내부에서 다시 자기 자신을 부르는 함수입니다. 가장 좋은 비유는 러시아 인형 .. 2026. 2. 17.
버블 정렬 vs 선택 정렬: 가장 기초적인 정렬 알고리즘 원리 정복하기 개발자가 다루는 데이터의 90% 이상은 정렬(Sorting)이 필요합니다. 쇼핑몰의 '낮은 가격순', 게시판의 '최신순', 엑셀의 '가나다순' 등 정렬은 우리 생활 깊숙이 들어와 있습니다. 수많은 정렬 알고리즘이 존재하지만, 그중에서도 가장 기본이 되며 알고리즘적 사고의 기초를 다져주는 두 가지 방법이 있습니다. 바로 버블 정렬(Bubble Sort)과 선택 정렬(Selection Sort)입니다. 비록 $O(N^2)$이라는 느린 속도 때문에 실무에서 대량의 데이터를 처리할 때는 잘 쓰이지 않지만, 이들이 데이터를 비교하고 교환하는 원리를 이해하는 것은 더 복잡한 알고리즘을 배우기 위한 필수 코스입니다.1. 버블 정렬(Bubble Sort): 인접한 놈과 싸운다버블 정렬은 이름처럼 데이터가 물방울(Bub.. 2026. 2. 16.
버블정렬 알고리즘 프로그래밍 입문자나 컴퓨터 공학 전공생이 알고리즘을 학습할 때 가장 먼저 접하게 되는 것이 바로 정렬(Sorting)입니다. 데이터를 순서대로 나열하는 것은 데이터 처리의 효율성을 높이는 가장 기초적인 작업이기 때문입니다. 그중에서도 버블 정렬(Bubble Sort)은 구현이 매우 간단하고 직관적이어서 알고리즘적 사고를 기르는 데 최적의 예제입니다. 비록 현업의 대용량 데이터 처리에는 효율성 문제로 잘 사용되지 않지만, 버블 정렬의 동작 방식과 시간 복잡도를 이해하는 것은 향후 퀵 정렬, 병합 정렬 등 고급 알고리즘을 이해하는 필수 기반이 됩니다. 이번 글에서는 버블 정렬의 핵심 원리부터 파이썬(Python) 코드 구현, 그리고 성능 최적화 방법까지 심도 있게 다뤄보겠습니다.1. 버블 정렬(Bubble .. 2026. 2. 5.

티스토리툴바