정보처리기사43 알고리즘 - 투포인터, 슬라이딩 윈도우 투 포인터 (슬라이딩 윈도우, 부분합, 시간복잡도)"연속한 부분 배열 중 합이 가장 큰 것", "합이 정확히 K인 구간의 개수", "중복 없는 가장 긴 부분 문자열" — 이런 문제를 만나면 초보자는 본능적으로 이중 반복문을 떠올린다. 모든 시작점과 끝점을 다 시도하면 O(N²)이다. 그러나 배열을 한 번만 훑으면서 두 개의 포인터를 적절히 움직이면 같은 문제를 O(N)에 풀 수 있다. 이것이 투 포인터(Two Pointer)와 그 특수형인 슬라이딩 윈도우(Sliding Window)다. 본 글은 두 기법의 동작 원리, 고정 크기와 가변 크기 윈도우의 차이, 그리고 단조성이라는 적용 조건을 세심하게 정리한다(출처: 위키백과 — Maximum subarray problem). 제가 코딩 테스트를 처음 준비할.. 2026. 5. 24. 알고리즘 - KMP 문자열 매칭 문자열 매칭 (KMP, 실패 함수, 라빈-카프)긴 문서 안에서 특정 단어를 찾는 일은 검색 엔진, 코드 에디터의 Ctrl+F, 유전자 서열 분석, 침입 탐지 시스템의 패턴 매칭까지 컴퓨터가 가장 자주 하는 작업 중 하나다. 가장 단순한 방법은 텍스트의 모든 위치에서 패턴을 한 글자씩 맞춰 보는 브루트포스이지만, 최악의 경우 O(N×M)으로 느려진다. 1977년 발표된 KMP(Knuth-Morris-Pratt) 알고리즘은 이 비교를 O(N+M)의 선형 시간으로 끌어내린 최초의 알고리즘이며, 그 비결은 "이미 비교해서 알아낸 정보를 버리지 않는다"는 한 문장에 있다. 본 글은 브루트포스의 비효율, KMP의 실패 함수, 그리고 해시 기반 라빈-카프와의 비교를 세심하게 정리한다(출처: 위키백과 — Knuth–M.. 2026. 5. 23. 알고리즘 - 이분 탐색, 매개변수 탐색 이분 탐색 (이진 탐색, 매개변수 탐색, 경계 조건)정렬된 데이터에서 원하는 값을 찾을 때, 처음부터 끝까지 훑는 선형 탐색은 100만 개 자료에서 최악 100만 번을 비교한다. 같은 상황에서 이분 탐색(Binary Search)은 단 20번이면 끝난다. 탐색 범위를 절반씩 잘라 내며 후보를 지수적으로 줄이는 이 단순한 발상이 데이터베이스 인덱스, 표준 라이브러리의 bisect, git의 bisect 명령, 그리고 코딩 테스트 단골 기법인 매개변수 탐색까지 떠받친다. 본 글은 이분 탐색의 정확한 구현과 가장 자주 틀리는 경계 조건, 그리고 최적화 문제를 탐색 문제로 바꾸는 매개변수 탐색을 세심하게 정리한다(출처: 위키백과 — Binary search algorithm). 제가 학교 알고리즘 과제에서 이분.. 2026. 5. 23. 알고리즘 - MST 위상정렬 MST와 위상정렬 (그래프 알고리즘)그래프 알고리즘의 두 번째 영역은 연결성 구조를 다루는 알고리즘들이다. 모든 정점을 가장 싸게 연결하는 최소 신장 트리(MST)와, 선후 관계가 있는 작업을 올바른 순서로 늘어놓는 위상 정렬(Topological Sort)은 통신망 설계·강의 수강 순서·빌드 시스템·의존성 해결처럼 일상적 시스템의 핵심에 깔려 있다. 본 글은 Kruskal·Prim 두 MST 알고리즘과 Union-Find 자료구조, 그리고 Kahn·DFS 두 위상 정렬 알고리즘을 세심하게 정리한다(출처: CLRS — Introduction to Algorithms, 23·22장). 제가 학교 알고리즘 과제에서 Kruskal을 단순 배열 검사로 짰다가 노드 1만짜리 그래프에서 30초 걸리던 코드가 Uni.. 2026. 5. 19. 알고리즘 - 최단경로, 그래프 알고리즘 최단경로 (다익스트라, 벨만포드, BFS)그래프에서 한 점에서 다른 점으로 가는 가장 빠른 길을 찾는 문제가 최단 경로(Shortest Path)이다. 네비게이션의 길찾기, 라우터의 패킷 전달, 비행기 노선 설계, SNS의 친구 추천, 게임 캐릭터의 이동 AI까지 — 그래프 위에서 동작하는 거의 모든 응용의 토대가 최단 경로 알고리즘이다. 가중치의 유무·음수 가중치 허용 여부·시작점이 하나인지 모두인지에 따라 적합한 알고리즘이 갈리며, 그 선택의 정확성이 시스템의 응답 시간을 직접 결정한다. 본 글은 BFS·다익스트라·벨만-포드·플로이드-워셜 네 가지 핵심 최단 경로 알고리즘의 차이와 사용 조건을 세심하게 정리한다(출처: CLRS — Introduction to Algorithms, 22~25장). 제가.. 2026. 5. 19. 알고리즘 - 백트래킹, N-Queens 백트래킹 (N-Queens, 가지치기, DFS)분할 정복·DP·그리디가 모두 효율적인 알고리즘 패러다임이었다면, 백트래킹(Backtracking)은 본질적으로 모든 가능한 답을 시도해 보는 완전 탐색의 정교한 변형이다. "일단 한 길로 가 보고, 막히면 되돌아 와 다른 길을 시도하는" 사고방식이며, N-Queens·미로 찾기·스도쿠·조합 생성처럼 답의 후보가 트리 구조로 자라는 문제에 강력하다. 핵심 기교는 가지치기(Pruning) — 명백히 답이 될 수 없는 경로를 미리 잘라 내는 일이며, 가지치기 없는 백트래킹은 단순 완전 탐색일 뿐이다. 본 글은 백트래킹의 정의·DFS와의 관계·N-Queens 고전 풀이·가지치기 전략을 세심하게 정리한다(출처: CLRS — Introduction to Algorit.. 2026. 5. 19. 이전 1 2 3 4 5 ··· 8 다음