분류 전체보기37 퀵 정렬(Quick Sort) 최악의 시나리오 (피벗 선택 전략과 최적화) 컴퓨터 공학과 알고리즘 세계에서 퀵 정렬(Quick Sort)은 이름부터 '빠르다'는 맹렬한 자신감이 넘치는, 현대 소프트웨어 산업에서 가장 널리 쓰이는 정렬 방식입니다. 평균 시간 복잡도 O(N log N)에, 뛰어난 캐시 지역성(Cache Locality)을 바탕으로 메모리 스왑이 적어 병합 정렬이나 힙 정렬보다 압도적으로 빠른 실측 속도를 보여줍니다. 하지만 IT 대기업의 백엔드 개발자 기술 면접에서 면접관들이 단골로 던지는 아주 날카로운 함정 질문이 있습니다. "퀵 정렬이 무조건 빠를까요? 퀵 정렬이 최악의 속도를 내는 시나리오는 구체적으로 무엇이며, 라이브러리 개발자들은 이를 어떻게 최적화하여 해결했나요?" 이 질문에 명확하게 답하지 못한다면 퀵 정렬을 반쪽만 알고 있는 것입니다. 퀵 정렬의 숨.. 2026. 2. 21. 세그먼트 트리(Segment Tree) 기초 (특정 구간 합 빠르게 구하기) 배열이나 리스트 내부의 '특정 구간에 대한 합(Sum)'을 구하거나, '특정 인덱스의 값을 빈번하게 변경'해야 하는 상황은 코딩 테스트의 고난도 문제나 실무 대규모 시스템 성능 최적화에서 매우 흔하게 발생합니다. 만약 100만 개의 데이터가 있는 배열에서 "10만 번째부터 90만 번째까지의 합을 구하라"는 쿼리가 10만 번 들어온다면 어떻게 될까요? 단순 반복문(for문)을 쓰면 매번 O(N)의 시간이 걸려 전체 시스템이 다운될 것입니다. 그렇다고 누적 합(Prefix Sum) 배열을 미리 만들어 쓰자니, 배열 안의 데이터가 단 하나라도 변경될 때마다 전체 누적 합 배열을 100만 번 다시 계산해야 하는 치명적인 단점이 존재합니다. 이처럼 '빈번한 데이터의 수정'과 '거대한 구간에 대한 쿼리(합, 최댓값.. 2026. 2. 21. 플로이드-워셜(Floyd-Warshall) (모든 정점 간의 최단 경로) 앞서 우리는 다익스트라(Dijkstra) 알고리즘을 통해 '어느 한 출발 도시'에서 '나머지 모든 도시'로 가는 최단 경로를 구하는 방법을 배웠습니다. 하지만 현실의 비즈니스 요구사항은 훨씬 가혹합니다. 만약 서울에서 부산을 가는 최단 거리뿐만 아니라, "지도상에 존재하는 대전, 대구, 광주 등 모든 도시에서 출발하여 또 다른 모든 도시로 도착하는 최단 거리를 하나의 표(Matrix)로 싹 다 뽑아주세요"라는 요청이 들어오면 어떻게 해야 할까요? 다익스트라 알고리즘을 N번 반복해서 돌릴 수도 있겠지만, 코드가 몹시 지저분해지고 로직이 복잡해집니다. 이럴 때 불과 세 줄의 반복문만으로 마법처럼 모든 정점 간의 최단 경로를 한 번에 계산해 내는 우아한 알고리즘이 바로 '플로이드-워셜(Floyd-Warshal.. 2026. 2. 20. 이진 탐색(Binary Search): 정렬된 데이터에서 원하는 값을 찾는 효율적인 비결 도서관에서 책을 찾거나 사전에서 단어를 찾을 때, 우리는 본능적으로 처음부터 한 장씩 넘기지 않습니다. 대충 중간쯤을 펼쳐보고, 찾는 단어가 그보다 뒤에 있으면 뒷부분의 중간을, 앞에 있으면 앞부분의 중간을 다시 펼쳐봅니다. 이처럼 범위를 절반씩 뚝뚝 잘라내며 순식간에 데이터를 찾아내는 직관적인 방법, 바로 이진 탐색(Binary Search)입니다. 데이터가 40억 개라도 단 32번 만에 원하는 값을 찾아내는 이 놀라운 알고리즘의 원리와 구현 방법을 깊이 있게 파헤쳐 보겠습니다.1. 이진 탐색이란? (Divide and Conquer)이진 탐색은 정렬된 데이터 내에서 특정한 값을 찾을 때, 탐색 범위를 매 단계마다 절반($1/2$)으로 줄여가며 찾는 알고리즘입니다. '분할 정복(Divide and Co.. 2026. 2. 20. 완전 탐색(Brute Force): 무식해 보여도 가장 확실한 해결 전략 알고리즘 문제를 접하다 보면 '최적화'나 '효율성'이라는 단어에 강박을 갖기 쉽습니다. 하지만 컴퓨터 과학의 역사에서 가장 오래되고, 가장 확실하며, 때로는 가장 강력한 문제 해결 방법은 바로 "무식하게 다 해보기"입니다. 이를 전문 용어로 완전 탐색, 영어로는 브루트 포스(Brute Force)라고 부릅니다. '짐승(Brute)'과 '힘(Force)'의 합성어인 이 알고리즘은 지능적인 전략보다는 컴퓨터의 압도적인 연산 속도를 믿고 밀어붙이는 방식입니다. 보안 시스템을 뚫으려는 해커부터 복잡한 퍼즐을 푸는 인공지능까지, 모든 알고리즘의 기초가 되는 완전 탐색의 세계를 탐구해 보겠습니다.1. 완전 탐색(Brute Force)이란?브루트 포스는 문제 해결을 위해 가능한 모든 경우의 수를 빠짐없이 탐색하여 정.. 2026. 2. 19. 그래프(Graph)와 탐색: 내비게이션은 어떻게 길을 찾을까? 우리가 지금까지 배운 트리(Tree)는 부모와 자식이라는 계층이 있는 깔끔한 구조였습니다. 하지만 현실은 그렇게 깔끔하지 않습니다. 지하철 노선도는 얽히고설켜 순환선이 되기도 하고, 페이스북 친구 관계는 촌수 따위 없이 거미줄처럼 연결됩니다. 이렇게 복잡한 네트워크 연결 망을 표현하기 위해 탄생한 자료구조가 바로 그래프(Graph)입니다. 그리고 이 미로 같은 그래프 속에서 길을 찾는 방법이 바로 코딩 테스트의 단골 손님인 DFS와 BFS입니다.1. 그래프(Graph)란? (트리와의 차이점)그래프는 점(Vertex/Node)과 그 점들을 잇는 선(Edge)으로 이루어진 자료구조입니다. 트리와 가장 큰 차이점은 '순환(Cycle)'입니다. 트리는 밑으로 내려갔다가 다시 위로 돌아올 수 없지만, 그래프는 빙.. 2026. 2. 18. 이전 1 2 3 4 ··· 7 다음
