분류 전체보기49 희소 배열(Sparse Table) 완벽정리 (빠른 구간 쿼리 처리 기법) 앞서 우리는 배열의 특정 구간에 대한 쿼리(합, 최댓값, 최솟값)를 빠르게 처리하기 위해 '세그먼트 트리(Segment Tree)'라는 훌륭한 자료구조를 배웠습니다. 세그먼트 트리는 데이터가 수시로 변경(Update)되는 상황에서도 O(log N)의 속도를 보장하는 전천후 무기입니다. 하지만 실무 시스템이나 코딩 테스트 문제 중에는 "배열의 데이터는 처음 주어진 상태에서 단 한 번도 변하지 않는데(Static), 특정 구간의 최솟값을 묻는 쿼리만 수백만 번 쏟아지는 상황"이 존재합니다. 이때 세그먼트 트리보다 구현이 훨씬 간결하면서도, 쿼리 처리 속도를 O(log N)에서 경이로운 O(1) 상수 시간으로 단축시켜 버리는 궁극의 최적화 기법이 있습니다. 바로 동적 계획법(DP)의 원리를 배열 구간 쿼리에 .. 2026. 2. 23. 해시(Hash) 충돌 해결법 심화 (체이닝 vs 개방 주소법 성능 분석) 해시 테이블(Hash Table)은 '키(Key)' 문자열만 알면 그 즉시 해당되는 '값(Value)'을 뽑아낼 수 있는 O(1)의 기적 같은 성능을 보여주는 현대 컴퓨터 과학의 결정체입니다. 하지만 비둘기집 원리에 의해 유한한 한정된 메모리 공간에서 해시 함수가 내뱉는 숫자가 우연히 겹쳐버리는 '해시 충돌(Hash Collision)'은 피할 수 없는 절대적인 숙명과도 같습니다. 백엔드 기술 면접관이 "해시 충돌을 어떻게 해결합니까?"라고 물었을 때, 단순히 "체이닝과 개방 주소법이 있습니다"라고 교과서적으로 나열하는 것에 그친다면 좋은 점수를 받기 어렵습니다. 두 기법이 컴퓨터의 하드웨어(CPU 캐시 메모리) 자원을 어떻게 효율적으로 사용하고 최적화하는지, 그리고 Java 같은 모던 언어들은 이 한계.. 2026. 2. 23. 이분 탐색(Binary Search)의 함정 (Lower Bound와 Upper Bound 구현) 수백만 개의 정렬된 데이터 속에서 원하는 값을 찾아낼 때 O(log N)의 압도적인 속도를 보여주는 이분 탐색(Binary Search). 하지만 실무 시스템 구축이나 코딩 테스트에서 이분 탐색을 맹목적으로 적용하다 보면 전혀 예상치 못한 치명적인 함정에 빠지게 됩니다. 바로 "찾고자 하는 타겟 데이터가 배열 내에 여러 개 중복되어 존재할 때"입니다. 기본 이분 탐색 코드는 중복된 값들 중 어느 위치에 있는 값을 반환할지 전혀 보장하지 않으며, 그저 운 좋게 걸린 '아무거나' 하나를 찾아내고 쿨하게 탐색을 종료해 버립니다. 만약 "80점을 받은 학생들이 배열에 총 몇 명인가?" 또는 "새로운 80점짜리 데이터를 끼워 넣을 수 있는 가장 앞쪽 위치는 어디인가?"를 구해야 한다면 기본 이분 탐색은 완벽한 무.. 2026. 2. 22. 비트마스크(Bitmask)를 활용한 집합 처리 (메모리와 속도 최적화) 컴퓨터는 본질적으로 0과 1이라는 두 가지 상태(Bit)만을 이해하는 기계입니다. 우리가 일상적인 프로그래밍에서 수백 개의 불리언(Boolean, 참/거짓) 데이터를 다루기 위해 배열(Array)을 선언할 때, 이를 하나하나 메모리에 올리면 적지 않은 공간과 시간이 낭비됩니다. 만약 "전구 10개가 켜져 있는지 꺼져 있는지"의 복잡한 상태를 불리언 배열 대신 단 하나의 정수(Integer) 숫자로 압축해서 표현하고 제어할 수 있다면 어떨까요? C++이나 Java에서 정수 하나는 보통 32비트(4바이트)이므로, 정수 변수 딱 하나만 선언해도 무려 32개의 켜짐/꺼짐 상태를 동시에 저장하고 조작할 수 있습니다. 이렇게 컴퓨터의 가장 낮은 레벨인 비트 연산을 활용하여 집합(Set) 데이터를 경이로운 속도와 최.. 2026. 2. 22. 백트래킹(Backtracking) 상태 공간 트리 탐색 (N-Queen 문제 분석) 미로에 갇혔을 때 탈출구를 찾는 가장 확실한 방법은 깊이 우선 탐색(DFS)을 이용해 모든 길을 다 가보는 것입니다. 하지만 현실에서 무작정 모든 길을 다 가보는 것은 체력과 시간의 엄청난 낭비입니다. 만약 어떤 길로 접어들었는데 저 멀리 낭떠러지가 보인다면, 굳이 그 낭떠러지 끝까지 걸어갔다가 돌아올 바보가 있을까요? 낭떠러지가 보이는 그 즉시 발길을 돌려 다른 길을 찾는 것이 현명할 것입니다. 컴퓨터 알고리즘에서도 이처럼 "모든 경우의 수를 탐색하되, 가망이 없는 길은 조기에 포기하고 돌아온다"는 매우 효율적인 지능형 탐색 기법이 존재하는데, 이를 백트래킹(Backtracking, 퇴각 검색)이라고 부릅니다. 가지치기(Pruning)의 미학이자, 코딩 테스트 완전 탐색 파트의 끝판왕인 백트래킹의 원리.. 2026. 2. 22. 선형 탐색 vs 이진 탐색: 업다운 게임으로 이해하는 탐색 효율의 차이 프로그래밍의 본질은 결국 '데이터를 저장'하고 '데이터를 검색'하는 것입니다. 그중에서도 검색(Search) 알고리즘은 사용자가 느끼는 서비스의 속도와 직결되는 매우 중요한 요소입니다. "그냥 for문 돌려서 찾으면 되는 거 아니야?"라고 생각할 수 있지만, 데이터가 100만 개, 1,000만 개로 늘어나면 알고리즘의 선택에 따라 1시간이 걸릴 수도, 0.1초가 걸릴 수도 있습니다. 오늘은 검색의 기초인 선형 탐색(Linear Search)과 이진 탐색(Binary Search)을 술자리 게임인 '업다운(Up-Down) 게임'에 비유하여 그 결정적인 효율 차이를 비교해 보겠습니다.1. 선형 탐색: "1번이야? 2번이야? 3번이야?"선형 탐색은 말 그대로 데이터를 선(Line)처럼 처음부터 끝까지 순서대로.. 2026. 2. 21. 이전 1 2 3 4 5 ··· 9 다음
