DevFit
무료 시작

알고리즘 CS 지식백과

알고리즘 관련 핵심 개념을 개발자 기술 면접에서 설명할 수 있도록 문서 16편으로 정리했습니다. 각 문서는 개념, 동작 원리, 시간 복잡도와 실무 선택 기준을 함께 다룹니다.

최종 업데이트 2026.09.17

  1. 이분 탐색 (Binary Search)

    정렬된 배열에서 탐색 범위를 절반씩 줄여 O(log n)에 값을 찾는 이분 탐색의 원리와 동작 과정을 그림으로 정리했다. lower bound와 upper bound, 코딩테스트 단골인 파라메트릭 서치와 회전 정렬 배열, 구현 코드와 자주 하는 실수까지 다룬다.

  2. 비트마스크 (Bitmask)

    정수의 각 비트로 집합의 포함 여부를 표현하는 비트마스크 기법을 다룬다. 기본 비트 연산 정리, 부분집합 열거, 외판원 순회 동적 계획법 구현과 주의점을 정리한다.

  3. DFS와 BFS (Depth First Search, Breadth First Search)

    그래프의 모든 정점을 방문하는 DFS와 BFS의 원리와 방문 순서 차이를 스택과 큐로 설명하고, O(V + E) 복잡도, 구현 코드, 문제 유형별 선택 기준을 정리한다.

  4. 다익스트라 알고리즘 (Dijkstra's Algorithm)

    음수 간선이 없는 그래프에서 한 정점으로부터의 최단 거리를 구하는 다익스트라 알고리즘의 그리디 원리, 우선순위 큐 구현, 복잡도 비교와 한계를 정리한다.

  5. 동적 계획법 (Dynamic Programming)

    겹치는 부분 문제와 최적 부분 구조를 전제로 부분 문제의 답을 저장해 재사용하는 동적 계획법을 다룬다. 하향식과 상향식 비교, 문제 풀이 단계, 배낭 문제 구현을 정리한다.

  6. 최대공약수와 최소공배수 (GCD, LCM)

    유클리드 호제법으로 최대공약수를 O(log n)에 구하는 원리를 도형과 나머지 연산으로 풀어 설명한다. 최소공배수 공식과 오버플로 방지, 기약분수와 주기 문제 같은 활용 사례를 정리한다.

  7. 해시 테이블 구현 (Hash Table Implementation)

    키를 해시 함수로 인덱스에 대응시켜 평균 O(1) 연산을 제공하는 해시 테이블을 직접 구현한다. 체이닝과 개방 주소법, 적재율과 재해싱, 파이썬 구현 코드를 정리한다.

  8. 힙 정렬 (Heap Sort)

    배열을 최대 힙으로 만들고 루트를 끝으로 보내며 정렬하는 힙 정렬을 다룬다. 배열 기반 힙 표현, 힙 구성이 O(n)인 이유, 최악에도 O(n log n)인 근거와 구현을 정리한다.

  9. 최소 공통 조상 (LCA, Lowest Common Ancestor)

    트리에서 두 노드의 가장 깊은 공통 조상을 찾는 LCA 알고리즘을 다룬다. 단순 상승 방법부터 희소 테이블 기반 이진 리프팅까지 원리, 질의 과정, 구현 코드를 정리한다.

  10. 최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)

    수열에서 가장 긴 증가 부분 수열을 찾는 LIS 문제를 다룬다. O(n^2) 동적 계획법과 이분 탐색을 결합한 O(n log n) 풀이, tails 배열의 의미와 수열 복원 방법을 정리한다.

  11. 병합 정렬 (Merge Sort)

    배열을 절반씩 나눠 정렬한 뒤 합치는 분할 정복 정렬인 병합 정렬을 다룬다. 항상 O(n log n)을 보장하는 이유, 안정성이 결정되는 지점, 구현 코드와 활용을 정리한다.

  12. 순열과 조합 구현 (Permutation and Combination)

    순서를 고려하는 순열과 무시하는 조합의 차이를 백트래킹 구현으로 설명한다. 시작 인덱스로 중복 셈을 막는 원리, 경우의 수와 복잡도, 중복 처리 요령을 정리한다.

  13. 퀵 정렬 (Quick Sort)

    피벗을 기준으로 배열을 분할해 재귀적으로 정렬하는 퀵 정렬을 다룬다. 평균 O(n log n)과 최악 O(n^2)의 조건, 피벗 전략, 로무토 분할 구현과 퀵 셀렉트를 정리한다.

  14. 코딩테스트 최적화 기법 (Optimization Techniques)

    시간 초과를 피하는 실전 요령을 모았다. 입력 크기로 목표 복잡도를 역산하는 기준표, 빠른 입출력, 누적 합, 투 포인터와 슬라이딩 윈도우, 가지치기를 정리한다.

  15. 계수 정렬 (Counting Sort)

    원소를 비교하지 않고 값별 등장 횟수로 정렬 위치를 계산하는 계수 정렬을 다룬다. O(n + k) 복잡도, 안정성을 위한 역방향 배치, 적합한 데이터 조건과 구현을 정리한다.

  16. 기수 정렬 (Radix Sort)

    낮은 자릿수부터 안정 정렬을 반복해 전체를 정렬하는 기수 정렬을 다룬다. 안정성이 필수인 이유, O(d(n + k)) 복잡도와 진법 트레이드오프, 구현 코드를 정리한다.

알고리즘를 특히 많이 묻는 직군

같은 개념이라도 직군에 따라 파고드는 각도가 다릅니다. 직군별 가이드에서 어떤 질문으로 이어지는지 확인해 보세요.

다른 CS 토픽도 이어서 보기

한 주제의 원리를 익혔다면 인접한 자료구조와 운영체제, 네트워크 개념을 함께 읽어 전체 동작을 연결해 보세요.

CS 지식백과 전체 보기