보이어-무어(Boyer-Moore) 알고리즘에는 또 다른 접근 방식이 있으며, 이를 좋은 접미사 휴리스틱(Good Suffix Heuristic) 방법이라고도 부릅니다. 이 방식에서는 전처리 단계에서 접미사 테이블(suffix table) 형태의 전처리 테이블을 생성합니다.이 절차에서는 패턴의 마지막 문자부터 부분 문자열 또는 패턴을 검색합니다. 메인 문자열의 부분 문자열이 패턴의 부분 문자열과 일치하면, 일치한 부분의 다른 출현 위치를 찾기 위해 이동합니다. 또한 패턴의 접두사가 메인 문자열의 접미사와 일치하는 경우에도 해당 위치

퀵 정렬(Quicksort)은 리스트를 두 부분으로 나누는 분할 정복(Divide and Conquer) 방식의 대표적인 정렬 알고리즘입니다. 먼저 분할(Partition) 과정을 통해 피벗(pivot) 요소를 하나 선택하고, 피벗을 기준으로 왼쪽에는 피벗보다 작은 값들을, 오른쪽에는 피벗보다 큰 값들을 배치합니다. 분할이 완료되면 각각 나뉜 부분 리스트에 대해 동일한 절차를 재귀적으로 반복하여 전체 배열을 정렬합니다.퀵 정렬의 시간 및 공간 복잡도시간 복잡도: 최선의 경우와 평균의 경우 O(n log n), 최악의 경우 O(n²)

기수 정렬(Radix Sort)은 비교 연산을 사용하지 않는 정렬 알고리즘입니다. 이 알고리즘은 정수 키를 대상으로, 같은 자릿수 위치에 같은 값을 가진 숫자들을 그룹으로 묶는 방식으로 동작합니다. 여기서 말하는 기수(radix)란 수 체계의 밑(base)을 뜻하며, 우리가 일상적으로 사용하는 10진법에서 기수는 10입니다. 따라서 10진수를 정렬할 때에는 숫자를 임시로 보관할 10개의 버킷(포켓)이 필요합니다. 기수 정렬의 복잡도 시간 복잡도: O(nk) — n은 데이터 개수, k는 최대 자릿수 공간 복잡도: O(n+k)

선택 정렬(Selection Sort)은 리스트를 두 부분으로 나누어 정렬하는 기법입니다. 한쪽 부분에는 정렬된 요소들이, 다른 쪽 부분에는 아직 정렬되지 않은 요소들이 위치합니다. 처음에는 배열에서 최댓값 또는 최솟값을 찾습니다. 예를 들어 최솟값을 찾았다면, 그 값을 리스트의 맨 앞에 있는 데이터와 교환하여 리스트의 시작 부분에 배치합니다. 이 과정이 반복될수록 정렬해야 할 배열의 크기는 점점 작아지며, 이러한 방식으로 전체 정렬이 완성됩니다.선택 정렬의 시간 복잡도시간 복잡도(Time Complexity): O(n²)공간 복잡

쉘 정렬(Shell Sort)은 삽입 정렬(Insertion Sort)을 기반으로 한 정렬 기법입니다. 일반적인 삽입 정렬에서는 요소를 올바른 위치에 삽입하기 위해 대량의 데이터를 한꺼번에 이동(shift)해야 하는 비효율이 발생할 수 있습니다. 쉘 정렬은 이러한 문제를 해결하기 위해 고안되었으며, 특정 간격(gap)을 두고 떨어져 있는 요소들을 먼저 비교·교환함으로써 불필요한 이동 횟수를 크게 줄입니다.쉘 정렬의 핵심 아이디어는 다음과 같습니다. 처음에는 배열 길이의 절반에 해당하는 넓은 간격으로 정렬을 시작하고, 매 패스(pas

시작 시간과 종료 시간이 주어진 n개의 서로 다른 활동이 있을 때, 한 사람이 수행할 수 있는 최대 개수의 활동을 선택하는 것이 활동 선택 문제(Activity Selection Problem)입니다. 이 문제는 그리디(Greedy) 접근법으로 효율적으로 해결할 수 있습니다.핵심 아이디어는 간단합니다. 남은 활동 중 종료 시간이 가장 빠른 활동을 우선 선택하고, 그다음에는 마지막으로 선택한 활동의 종료 시간보다 늦게 시작하거나 같은 시간에 시작하는 활동만을 차례로 고르는 것입니다. 종료가 빠른 활동을 먼저 배정할수록 이후에 선택할

인접 리스트(adjacency list)로 표현된 그래프 G(V, E)와 시작 정점(source vertex)이 주어졌을 때, 다익스트라(Dijkstra) 알고리즘은 시작 정점에서 그래프의 다른 모든 정점까지 도달하는 최소 비용의 최단 경로를 찾아냅니다. 해결 접근 방법 이 문제를 해결하기 위해 두 개의 리스트를 활용합니다. 하나는 최단 경로 트리(shortest path tree)에 이미 확정된 정점들을 보관하는 리스트이며, 다른 하나는 아직 확정되지 않은 정점들을 담는 리스트입니다. 알고리즘의 매 단계마다 아직 처리되지 않은

다익스트라 알고리즘이란?다익스트라 알고리즘은 가중치 그래프에서 시작 정점(source)으로부터 다른 모든 정점까지의 최단 거리를 구하는 대표적인 탐욕(greedy) 기반 알고리즘입니다. 이번 글에서 다룰 문제는 앞선 예제와 본질적으로 동일하지만, 한 가지 중요한 차이점이 있습니다. 바로 그래프를 인접 행렬(adjacency matrix) 형태로 표현한다는 점입니다.최단 경로 계산의 관점에서 보면 비용 행렬(cost matrix)과 인접 행렬은 사실상 같은 역할을 하므로, 두 용어를 혼용해도 무방합니다. 인접 행렬을 사용하는 이 구현

허프만 코딩(Huffman Coding)이란?허프만 코딩은 대표적인 비손실(lossless) 데이터 압축 알고리즘입니다. 이 알고리즘은 입력되는 각 문자에 서로 다른 길이의 가변 길이 코드(variable-length code)를 부여하며, 코드의 길이는 해당 문자가 사용되는 빈도에 따라 결정됩니다.핵심 원리는 간단합니다. 자주 등장하는 문자에는 짧은 코드를, 드물게 등장하는 문자에는 긴 코드를 할당함으로써 전체 데이터의 크기를 줄이는 것입니다.허프만 코딩은 크게 두 단계로 나눌 수 있습니다.1단계: 허프만 트리(Huffman Tr

이전에 다룬 허프만 코드(Huffman Code) 문제에서는 문자의 빈도(frequency)가 정렬되어 있지 않은 상태였습니다. 하지만 만약 빈도 목록이 이미 정렬된 상태로 주어진다면, 각 문자에 코드를 할당하는 작업을 훨씬 더 효율적으로 수행할 수 있습니다.이 문제에서는 두 개의 빈 큐(queue)를 활용합니다. 먼저 고유한 문자마다 하나의 리프 노드(leaf node)를 생성하고, 이를 빈도가 오름차순이 되도록 첫 번째 큐에 순서대로 삽입합니다.이러한 접근 방식을 사용하면 알고리즘의 시간 복잡도를 O(n)까지 낮출 수 있으며,

문제 개요 기한이 있는 작업 순서(Job Sequencing with Deadlines) 문제는 그리디 알고리즘의 대표적인 응용 사례입니다. 작업 목록이 주어지며, 각 작업에는 고유 ID, 마감 기한(deadline), 그리고 완료 시 얻을 수 있는 이익(profit)이 함께 제공됩니다. 모든 작업은 하나의 시간 단위를 소요하므로 작업의 최소 마감 기한은 1입니다. 한 번에 하나의 작업만 스케줄링할 수 있을 때, 어떤 순서로 작업을 배치해야 총 이익을 최대화할 수 있을까요? 접근 방법 가장 단순한 방법은 작업 집합의 모든 부분집합

버킷 정렬(Bucket Sort)은 데이터 항목들을 여러 개의 버킷(bucket)으로 분산시키는 정렬 기법입니다. 각 버킷에는 성격이 비슷한 데이터가 담기며, 분산이 완료되면 각 버킷을 다른 정렬 알고리즘(예: 삽입 정렬, 표준 라이브러리의 sort 함수 등)으로 개별적으로 정렬합니다. 마지막으로 모든 버킷의 요소를 순서대로 모아 원래 리스트에 합치면 정렬된 결과를 얻을 수 있습니다.버킷 정렬은 특히 입력 데이터가 균등하게 분포되어 있을 때 뛰어난 성능을 보이며, 0과 1 사이의 실수처럼 값의 범위가 명확한 부동소수점 데이터를 정렬

빗 정렬(Comb Sort)의 기본 아이디어는 거품 정렬(Bubble Sort)과 같습니다. 다시 말해, 빗 정렬은 거품 정렬을 개선한 알고리즘입니다. 거품 정렬에서는 각 단계마다 인접한 항목끼리 비교를 수행하지만, 빗 정렬에서는 일정한 간격(gap)을 두고 떨어져 있는 항목들을 비교하며 정렬합니다.한 단계(phase)가 끝날 때마다 간격은 점차 줄어들며, 이때 사용되는 감소 계수(shrink factor)는 1.3입니다. 즉, 매 단계가 완료될 때마다 현재 간격을 1.3으로 나눈 값으로 갱신합니다. 이러한 방식 덕분에 빗 정렬은

카운팅 정렬(Counting Sort)은 안정 정렬(stable sort) 기법의 하나로, 데이터를 서로 비교하지 않고 각 키 값이 나타난 횟수를 세어 정렬하는 방식입니다. 주로 키가 작은 정수일 때 사용되며, 키 값들 사이의 범위 차이가 크지 않을 때 특히 효과적입니다. 다만 최댓값과 최솟값의 차이가 큰 데이터에 적용하면 그만큼 큰 카운트 배열이 필요해져 공간 복잡도가 증가할 수 있으므로 주의해야 합니다. 카운팅 정렬의 복잡도 시간 복잡도: O(n+r) — n은 데이터 개수, r은 키 값의 범위 공간 복잡도: O(n+r) 카

순환 정렬(Cycle Sort)이란?순환 정렬(Cycle Sort)은 제자리(in-place) 정렬 알고리즘의 하나로, 각 원소를 자신이 위치해야 할 곳으로 직접 옮기는 사이클 단위로 배열을 정렬하는 방식입니다. 비교 기반(comparison-based) 정렬에 속하며, 가장 큰 특징은 정렬 과정에서 발생하는 메모리 쓰기(write) 연산 횟수를 이론상 최소한으로 줄인다는 점입니다.이러한 특성 때문에 순환 정렬은 쓰기 작업 비용이 큰 환경에서 특히 유용합니다. 대표적으로 EEPROM이나 플래시 메모리처럼 쓰기 횟수가 수명에 직결되는

힙 정렬은 힙(heap) 데이터 구조를 기반으로 수행되는 정렬 알고리즘입니다. 힙은 완전 이진 트리(complete binary tree)의 일종으로, 크게 두 가지 유형으로 나뉩니다.최소 힙(Min-Heap): 루트 노드가 항상 최솟값을 가집니다.최대 힙(Max-Heap): 루트 노드가 항상 최댓값을 가집니다.힙 정렬의 핵심 원리는 다음과 같습니다. 먼저 배열을 힙 구조로 만든 후, 루트에 있는 요소를 삭제하고 마지막 요소를 루트로 이동시킵니다. 이러한 교환(swap) 과정이 끝나면 배열 전체를 다시 힙 구조로 재구성(re-hea

삽입 정렬은 카드 게임에서 손에 쥔 카드를 정렬할 때 사용하는 방식과 매우 유사한 정렬 기법입니다. 실제로 우리가 카드를 정렬할 때도 삽입 정렬의 원리를 자연스럽게 활용하고 있습니다. 이 기법은 데이터 집합에서 하나의 요소를 선택한 뒤, 해당 요소가 들어갈 적절한 자리를 만들기 위해 앞쪽 요소들을 한 칸씩 밀어내고, 선택한 요소를 올바른 위치에 다시 삽입하는 방식으로 동작합니다. 삽입 정렬의 동작 원리 삽입 정렬은 두 번째 요소부터 시작하여 각 요소를 이미 정렬된 앞부분과 비교하며 적절한 위치에 배치합니다. 구체적인 과정은 다음과

병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 기법에 기반한 대표적인 정렬 알고리즘입니다. 전체 데이터 집합을 더 작은 단위로 나눈 뒤, 각 부분을 정렬된 순서로 다시 합쳐(merge) 하나의 정렬된 배열을 만듭니다. 특히 최악의 경우에도 O(n log n)의 낮은 시간 복잡도를 유지하기 때문에 성능이 중요한 상황에서 매우 효과적입니다.병합 정렬의 시간·공간 복잡도시간 복잡도: 모든 경우(최선·평균·최악)에서 O(n log n)공간 복잡도: O(n) — 병합 과정에서 임시 배열이 필요합니다.입력 및

비둘기집 정렬(Pigeonhole Sort)은 비교 연산 없이 데이터를 정렬하는 기법의 대표적인 예입니다. 정렬할 항목의 개수와 키 값의 범위가 대략 비슷할 때 특히 효율적으로 동작합니다. 이름은 비둘기집 원리(Pigeonhole Principle)에서 유래했으며, 각 값을 고유한 공간에 분류해 넣는 방식으로 정렬을 수행합니다. 이 정렬을 수행하려면 먼저 구멍(hole)이라 불리는 공간들을 만들어야 합니다. 필요한 구멍의 개수는 데이터 값의 범위에 따라 결정되며, 각 요소는 자신에게 맞는 구멍에 삽입됩니다. 마지막으로 구멍을 순서대

Git으로 프로젝트를 진행하다 보면, 커밋하기엔 아직 이르지만 지금까지 작업한 내용을 잠시 저장해 두고 싶은 순간이 찾아옵니다. 이럴 때 유용하게 쓸 수 있는 것이 바로 git stash 명령어입니다. 스태시(stash)를 활용하면 현재 작업 브랜치의 코드를 나중을 위해 안전하게 저장해 둘 수 있습니다. 이 글에서는 예제와 함께 Git 스태시의 기본 개념과 git stash 명령어의 다양한 사용법을 살펴보겠습니다. Git 스태시(Stash)란 무엇인가? 스태시는 작업 디렉터리와 인덱스에 있는 변경 사항을 나중을 위해 저장하는 기