시간복잡도5 알고리즘 - 이분 탐색, 매개변수 탐색 이분 탐색 (이진 탐색, 매개변수 탐색, 경계 조건)정렬된 데이터에서 원하는 값을 찾을 때, 처음부터 끝까지 훑는 선형 탐색은 100만 개 자료에서 최악 100만 번을 비교한다. 같은 상황에서 이분 탐색(Binary Search)은 단 20번이면 끝난다. 탐색 범위를 절반씩 잘라 내며 후보를 지수적으로 줄이는 이 단순한 발상이 데이터베이스 인덱스, 표준 라이브러리의 bisect, git의 bisect 명령, 그리고 코딩 테스트 단골 기법인 매개변수 탐색까지 떠받친다. 본 글은 이분 탐색의 정확한 구현과 가장 자주 틀리는 경계 조건, 그리고 최적화 문제를 탐색 문제로 바꾸는 매개변수 탐색을 세심하게 정리한다(출처: 위키백과 — Binary search algorithm). 제가 학교 알고리즘 과제에서 이분.. 2026. 5. 23. 알고리즘 - 분할 정복과 시간 복잡도 분할 정복 (재귀, 시간복잡도, 점화식)알고리즘 시리즈의 첫 글은 분할 정복(Divide and Conquer)이다. 이름이 거창해 보이지만 발상은 단순하다. 큰 문제를 같은 형태의 작은 문제 두세 개로 쪼개고, 작은 문제들의 답을 합쳐 원래 문제의 답을 만드는 전략이다. 이 단순한 아이디어 위에 병합 정렬·퀵 정렬·이진 탐색·고속 푸리에 변환·행렬 곱셈 같은 거의 모든 고급 알고리즘이 서 있으며, 같은 사고 틀이 그래픽스의 KD-Tree·DB의 B-Tree·MapReduce의 분산 처리까지 확장된다. 본 글은 분할 정복의 정의·시간복잡도 분석·마스터 정리·실전 예시를 세심하게 정리한다(출처: CLRS — Introduction to Algorithms). 제가 학교 알고리즘 수업에서 처음 같은 정렬 문.. 2026. 5. 19. 자료구조 - 정렬 알고리즘 정렬 알고리즘 (퀵, 병합, 안정)정렬은 컴퓨터 과학에서 가장 오래 연구된 문제이자 실무에서 가장 자주 마주치는 작업이다. 데이터를 보여주기 위해, 검색을 빠르게 하기 위해, 중복을 제거하기 위해, 통계를 계산하기 위해 — 어느 방향으로 가도 결국 정렬이 한 번 끼어든다. 본 글은 입문자가 반드시 익혀야 할 여덟 가지 핵심 정렬 알고리즘을 시간복잡도·안정성·실전 채택 기준으로 비교하면서 세심하게 정리한다(출처: CLRS — Introduction to Algorithms). 제가 학교 알고리즘 수업에서 같은 100만 개 데이터를 버블 정렬과 퀵 정렬로 비교 측정해 본 후 시간 차이가 1000배가 넘는 모습을 직접 본 후로는 "정렬 알고리즘 선택 한 줄이 시스템의 응답 시간을 결정한다"는 사실을 손끝으로 .. 2026. 5. 17. 자료구조 - BST와 균형트리 BST 균형트리 (AVL, RB, 자료구조)이진 트리 위에 "왼쪽은 작은 값, 오른쪽은 큰 값"이라는 단 한 줄의 정렬 규칙을 얹으면 곧바로 이진 탐색 트리(BST)가 된다. 이 한 규칙 덕분에 평균 O(log n) 시간에 탐색·삽입·삭제가 가능해지며, 자료구조 학습에서 처음 만나는 진짜 "실용적인" 트리이기도 하다. 다만 BST에는 결정적인 약점이 있는데, 데이터가 정렬된 순서로 들어오면 한쪽으로 편향되어 O(n)으로 떨어진다는 점이다. 이 약점을 해결하기 위해 등장한 것이 균형 트리(Balanced Tree)이며, 대표적으로 AVL 트리와 Red-Black(RB) 트리가 있다. 본 글은 BST의 정의·연산·시간복잡도부터 두 균형 트리의 차이까지 세심하게 정리한다(출처: 위키백과 — Binary Sea.. 2026. 5. 15. 자료구조 - 배열과 연결리스트 자료구조 (배열, 연결리스트, 시간복잡도)컴퓨터 과학에서 가장 먼저 배우는 두 자료구조가 배열과 연결리스트다. 두 구조는 데이터를 메모리에 어떻게 늘어놓을 것인가에 대한 가장 본질적인 두 답이며, 이후 등장하는 모든 고급 자료구조(스택·큐·트리·해시·그래프)가 이 둘의 변형이거나 조합이라고 해도 과언이 아니다. 본 글은 정보처리기사 시험 출제 범위와 학교 자료구조 수업 입문 영역을 모두 닿도록 배열과 연결리스트의 메모리 구조, 시간복잡도, 실전 선택 기준을 정리한다(출처: Python 공식 자료구조 문서). 제가 학교 자료구조 수업에서 처음 두 구조의 시간복잡도 표를 봤을 때 솔직히 "그래서 무엇을 언제 쓰라는 거지?" 한 줄로 정리되지 않아 한참 헤맸는데, 직접 두 구조로 같은 알고리즘을 짜고 실행 시.. 2026. 5. 14. 이전 1 다음