전체 글48 해시(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. 퀵 정렬(Quick Sort) 최악의 시나리오 (피벗 선택 전략과 최적화) 컴퓨터 공학과 알고리즘 세계에서 퀵 정렬(Quick Sort)은 이름부터 '빠르다'는 맹렬한 자신감이 넘치는, 현대 소프트웨어 산업에서 가장 널리 쓰이는 정렬 방식입니다. 평균 시간 복잡도 O(N log N)에, 뛰어난 캐시 지역성(Cache Locality)을 바탕으로 메모리 스왑이 적어 병합 정렬이나 힙 정렬보다 압도적으로 빠른 실측 속도를 보여줍니다. 하지만 IT 대기업의 백엔드 개발자 기술 면접에서 면접관들이 단골로 던지는 아주 날카로운 함정 질문이 있습니다. "퀵 정렬이 무조건 빠를까요? 퀵 정렬이 최악의 속도를 내는 시나리오는 구체적으로 무엇이며, 라이브러리 개발자들은 이를 어떻게 최적화하여 해결했나요?" 이 질문에 명확하게 답하지 못한다면 퀵 정렬을 반쪽만 알고 있는 것입니다. 퀵 정렬의 숨.. 2026. 2. 21. 이전 1 2 3 4 5 ··· 8 다음
