이 문제에서는 하나의 양의 정수 문자열이 주어지며, 자릿수를 최대 K번 서로 교환(swap)하여 만들 수 있는 값이 가장 큰 순열을 찾아야 합니다.이 문제는 백트래킹(backtracking) 기법을 활용하여 해결할 수 있습니다. 특정 자릿수를 선택한 뒤, 그 뒤에 위치한 다른 자릿수들과 하나씩 교환해 보면서 더 큰 수를 탐색합니다. 이 과정을 K번 반복하는데, 교환 결과가 기존의 최댓값보다 작거나 같다면 이전 상태로 되돌아가(백트래킹) 다른 경우를 다시 시도하는 방식으로 동작합니다.입력 및 출력입력: 여러 자릿수로 이루어진 정수 입

유한 오토마타(Finite Automata, FA)를 구성하면 텍스트 안에서 특정 패턴을 매우 효율적으로 찾아낼 수 있습니다. 먼저 2차원 배열을 채워 오토마타의 전이 테이블(transition table)을 만들어야 하며, 일단 테이블이 완성되면 실제 검색 과정은 매우 단순해집니다. 오토마톤의 첫 번째 상태에서 출발하여 입력 문자를 하나씩 처리하다가 최종 상태(final state)에 도달하면, 그 지점에서 패턴이 문자열 내에 존재한다는 것을 의미합니다.유한 오토마타를 구성하는 데 드는 시간 복잡도는 O(M×K)입니다. 여기서 M

카사이의 알고리즘(Kasais Algorithm)은 접미사 배열(Suffix Array)을 이용해 최장 공통 접두사(Longest Common Prefix, LCP) 배열을 선형 시간에 계산하는 효율적인 알고리즘입니다. 먼저 문자열의 접미사 배열을 구한 뒤, 카사이의 알고리즘이 이 접미사 배열을 입력받아 LCP 배열을 생성합니다. 일반적인 방식으로 LCP를 계산하면 O(m log n)의 시간이 소요됩니다(여기서 m은 패턴 길이, n은 텍스트 길이). 반면 카사이의 알고리즘은 O(n)의 선형 시간 복잡도로 작동하기 때문에 대용량 텍스

크누스-모리스-프랫(Knuth–Morris–Pratt, KMP) 알고리즘은 텍스트 안에서 특정 패턴을 빠르게 찾아내는 대표적인 문자열 검색 알고리즘입니다. 이 알고리즘은 문자를 항상 왼쪽에서 오른쪽 방향으로 검사하며, 패턴 내부에 반복되는 부분 구조(접두사와 접미사가 일치하는 구간)가 있을 때 그 성질을 활용해 이미 수행한 비교 정보를 재활용합니다. 덕분에 최악의 경우에도 선형 시간 안에 검색을 마칠 수 있습니다. KMP 알고리즘의 시간 복잡도는 O(n)입니다. 단순 무차별 대입(brute-force) 방식의 O(n×m)과 비교하면

마나처(Manacher) 알고리즘이란?문자열에서 가장 긴 팰린드롬(palindrome) 부분 문자열을 찾을 때 마나처(Manacher) 알고리즘을 사용하면 선형 시간 안에 문제를 해결할 수 있습니다. 기본 접근은 각 문자를 중심으로 삼고 왼쪽·오른쪽 포인터를 확장해 가며 팰린드롬 여부를 확인하는 것이지만, 마나처 알고리즘은 이미 계산한 팰린드롬 정보를 별도의 배열(longPal)에 저장해 두었다가 재활용한다는 점이 결정적으로 다릅니다. 이를 통해 불필요한 문자 비교를 건너뛸 수 있으며, 전체 문자열을 한 번 순회한 뒤 배열의 최댓값

나이브 패턴 검색(Naïve Pattern Search)이란?나이브 패턴 검색은 여러 문자열 패턴 검색 알고리즘 중 가장 단순하고 직관적인 방법입니다. 주 문자열(텍스트)의 처음부터 끝까지 한 칸씩 이동하며, 각 위치에서 패턴의 문자들을 하나하나 대조해 일치 여부를 확인합니다.이 알고리즘은 다음과 같은 특징을 가집니다.전처리 과정이 필요 없습니다. KMP, 보이어-무어 같은 알고리즘과 달리 별도의 사전 준비 단계가 없습니다.구현이 매우 간단합니다. 중첩 반복문만으로 손쉽게 작성할 수 있습니다.추가 메모리를 사용하지 않습니다. 탐색

라빈-카프 알고리즘이란? 라빈-카프(Rabin-Karp) 알고리즘은 문자열 안에서 특정 패턴을 효율적으로 찾아내는 패턴 검색 알고리즘입니다. 이 알고리즘 역시 탐색 창(window)을 한 칸씩 이동하며 패턴을 검사하지만, 모든 경우에 전체 문자를 일일이 비교하지 않습니다. 대신 각 창의 해시 값을 미리 계산해 비교하고, 해시 값이 서로 일치할 때에만 실제 문자를 하나씩 대조합니다. 덕분에 불필요한 문자 비교가 크게 줄어들어 검색 효율이 향상됩니다. 시간 복잡도는 평균적으로 O(m+n)이며, 최악의 경우에는 O(mn)입니다. 최악의

주어진 문자열에서 만들 수 있는 모든 접미사(suffix)를 구한 뒤, 이를 사전순(lexicographical order)으로 정렬하면 접미사 배열(Suffix Array)을 얻을 수 있습니다. 접미사 배열은 접미사 트리(suffix tree)를 통해서도 만들 수 있는데, 접미사 트리를 DFS(깊이 우선 탐색)로 순회하면 접미사 배열과 동일한 결과를 얻게 됩니다.접미사 배열을 활용하면 문자열 내에서 특정 패턴을 O(m log n) 시간 복잡도로 효율적으로 검색할 수 있습니다. 여기서 m은 패턴의 길이, n은 원본 문자열의 길이입니

주어진 텍스트에서 만들 수 있는 모든 접미사(suffix)를 생성해 하나의 트리 구조로 구성할 수 있습니다. 여기서 핵심은, 텍스트 안에 등장하는 모든 패턴은 반드시 텍스트의 어떤 접미사의 접두사(prefix)가 된다는 성질입니다. 따라서 모든 접미사로 트라이(Trie)를 미리 만들어 두면, 임의의 부분 문자열을 선형 시간에 찾아낼 수 있습니다. 각 접미사는 문자열 종료 기호로 끝납니다. 탐색은 루트 노드에서 시작하여, 자식으로 이어지는 경로가 있으면 계속 앞으로 진행하고, 더 이상 경로가 없으면 해당 패턴이 존재하지 않는다고 판단

Z 알고리즘이란?이 알고리즘은 계산 과정에서 Z 배열을 생성해야 하기 때문에 Z 알고리즘이라는 이름이 붙었습니다. Z 배열의 크기는 탐색 대상 텍스트의 길이와 동일하며, 각 위치의 문자에서 시작하여 만들 수 있는 가장 긴 부분 문자열의 길이, 즉 접두사와 일치하는 최대 길이를 저장하는 용도로 사용됩니다.먼저 패턴과 주 텍스트를, 양쪽 어디에도 등장하지 않는 특수 기호 하나로 이어 붙입니다. 패턴을 P, 주 텍스트를 T라고 할 때 연결 결과는 P$T 형태가 됩니다(단, $는 P와 T에 포함되어 있지 않다고 가정합니다).이 알고리즘의

무방향 그래프에서 해밀턴 경로(Hamiltonian Path)는 각 정점을 정확히 한 번씩만 방문하는 경로를 의미합니다. 그리고 해밀턴 사이클(Hamiltonian Cycle)은 해밀턴 경로 중 마지막 정점에서 첫 번째 정점으로 돌아가는 간선이 존재하여 경로가 하나의 순환을 이루는 경우를 말합니다.이번 글에서는 주어진 그래프에 해밀턴 사이클이 존재하는지 판별하고, 만약 해밀턴 사이클이 있다면 그 경로까지 출력하는 방법을 다룹니다.입력과 출력입력: 그래프 G(V, E)의 인접 행렬(adjacency matrix) 출력: 알고리즘은

모든 간선에 가중치(비용)가 부여된 연결 그래프 G(V, E)가 주어졌을 때, 크루스칼(Kruskal) 알고리즘은 이 그래프에서 최소 신장 트리(Minimum Spanning Tree, MST)를 찾아냅니다.이 알고리즘은 병합 트리(merge-tree) 방식에 기반합니다. 처음에는 각 정점이 독립적인 트리로 존재하며, 알고리즘은 비용이 가장 작은 간선부터 선택해 이 트리들을 점차 하나의 트리로 병합해 나갑니다.동작 원리크루스칼 알고리즘은 다음 순서로 진행됩니다.그래프의 모든 간선을 비용 기준으로 오름차순 정렬합니다.정렬된 목록에서

서로 다른 동전 목록 C(c₁, c₂, …, Cₙ)와 만들어야 할 금액 V가 주어졌을 때, 최소 개수의 동전만 사용하여 V를 만드는 것이 바로 최소 동전 교환(Minimum Coin Change) 문제입니다.참고: 모든 종류의 동전은 무한개 있다고 가정합니다.이 문제에서는 동전 집합 C{1, 2, 5, 10}이 주어지며, 각 동전은 무한히 많이 사용할 수 있습니다. 요청된 금액을 만들기 위해 가능한 한 적은 수의 동전을 선택하는 것이 목표입니다.예를 들어 금액이 22라면 {10, 10, 2}처럼 3개의 동전으로 만드는 것이 최소입니

문제 개요열차의 도착 시간과 출발 시간 목록이 주어졌을 때, 어떤 열차도 역 안에서 대기하지 않고 바로 승강장에 진입할 수 있도록 하려면 철도역에 최소 몇 개의 플랫폼이 필요한지 구하는 문제입니다.모든 시간 정보를 오름차순으로 정렬한 뒤 차례대로 살펴보면, 어떤 열차가 아직 역을 떠나지 않은 상태에서 새로운 열차가 도착했다는 순간을 손쉽게 추적할 수 있어 문제를 간단하게 해결할 수 있습니다.이 알고리즘의 시간 복잡도는 O(n log n)으로, 정렬에 드는 비용이 전체 성능을 좌우합니다.입력 및 출력입력:도착 시간 목록과 출발 시간

프림 알고리즘이란? 모든 간선에 가중치(비용)가 부여된 연결 그래프 G(V, E)가 주어졌을 때, 프림(Prim) 알고리즘은 이 그래프에서 최소 신장 트리(Minimum Spanning Tree, MST)를 찾는 대표적인 탐욕(Greedy) 기반 알고리즘입니다. 프림 알고리즘은 성장하는 트리(Growing Tree) 방식으로 동작합니다. 시작을 위해 하나의 시드(seed) 정점이 필요하며, 이 시드 정점에서 출발해 간선을 하나씩 추가하면서 전체 트리를 점진적으로 확장해 나갑니다. 동작 원리 프림 알고리즘은 두 개의 집합(set)을

여기서 소개하는 알고리즘은 앞서 살펴본 인접 행렬 기반 프림(Prim) 알고리즘과 원리는 동일합니다. 유일한 차이점은 그래프 G(V, E)를 인접 리스트(adjacency list) 형태로 표현한다는 점입니다. 인접 리스트 표현을 사용할 때의 시간 복잡도는 O(E log V)입니다. 따라서 간선 수가 정점 수에 비해 적은 희소 그래프(sparse graph)에서 특히 효율적으로 동작합니다. 입력과 출력 입력: 비용 행렬(cost matrix): 출력: Edge: A--B And Cost: 1 Edge: B--E And Cost:

부분 배낭 문제란?각각 고유한 가치(value)와 무게(weight)를 지닌 물건들의 목록이 주어지고, 최대 허용 무게가 W인 배낭에 이 물건들을 담는 상황을 생각해 봅시다. 부분 배낭 문제(Fractional Knapsack Problem)의 목표는 배낭에 담긴 물건들의 총 무게가 W를 초과하지 않는 조건에서 가치의 합을 최대한 크게 만드는 것입니다.배낭 문제는 크게 두 가지 유형으로 나뉩니다.0-1 배낭 문제(0-1 Knapsack) — 물건을 자를 수 없으므로 각 물건을 통째로 담거나 아예 담지 않아야 합니다.부분 배낭 문제(

아호-코라식(Aho-Corasick) 알고리즘은 주어진 키워드 집합 전체에 대한 모든 출현 위치를 텍스트에서 한 번의 탐색으로 찾아내는 데 유용한 알고리즘입니다. 일종의 사전 매칭(Dictionary-matching) 알고리즘으로, 모든 키워드를 트라이(Trie) 트리 구조로 구성한 뒤 이를 오토마타(상태 기계)로 변환하여 선형 시간 내에 검색을 수행할 수 있도록 설계되었습니다. 알고리즘의 세 가지 단계 아호-코라식 알고리즘은 Go-to(전이), Failure(실패), Output(출력)이라는 세 단계로 구성됩니다. Go-to

아나그램(Anagram)은 주어진 문자열이나 패턴의 문자들을 재배열하여 만들 수 있는 모든 순열을 뜻합니다. 일반적인 패턴 검색 알고리즘이 텍스트에서 정확히 일치하는 패턴만 찾는 것과 달리, 아나그램 패턴 검색은 패턴 자체뿐 아니라 그 패턴으로 만들 수 있는 모든 가능한 배열까지 함께 찾아냅니다. 예를 들어 패턴이 AABC라면, 텍스트 안에서 AABC, AACB, ABAC, ABCA처럼 문자의 종류와 개수가 동일한 부분 문자열을 모두 탐색하게 됩니다. 접근 방식 이 문제는 슬라이딩 윈도우(Sliding Window) 기법으로 해결할

나쁜 문자 휴리스틱(Bad Character Heuristic)은 보이어-무어(Boyer-Moore) 알고리즘을 구성하는 두 가지 접근 방식 중 하나입니다. 다른 하나는 좋은 접미사 휴리스틱(Good Suffix Heuristic)입니다. 이 방법에서는 메인 문자열에서 패턴과 일치하지 않는 문자, 즉 나쁜 문자(bad character)를 찾습니다. 불일치가 발생하면 해당 위치가 일치하게 될 때까지 패턴 전체를 이동시키고, 그럴 수 없다면 패턴을 나쁜 문자를 지나쳐 이동시킵니다.시간 복잡도이 알고리즘의 시간 복잡도는 최선의 경우 O