코딩 테스트를 위한 주요 알고리즘
코딩 테스트를 준비할 때는 문제를 많이 푸는 것도 중요하지만, 자주 쓰이는 자료구조와 알고리즘이 어떤 상황에서 필요한지 먼저 정리해두는 편이 좋다. 문제를 읽고 “이건 정렬로 풀 수 있겠다”, “여기서는 BFS가 자연스럽겠다”처럼 접근 방향을 빠르게 잡을 수 있기 때문이다.
이 카테고리에서는 코딩 테스트에서 반복해서 등장하는 주제를 하나씩 정리한다. 기본 문법이나 풀이 팁처럼 실전에서 바로 도움이 되는 내용부터, 정렬, 배열, 탐색, 스택과 큐 같은 핵심 자료구조까지 다룬다.
먼저 정렬은 데이터를 일정한 기준으로 재배치하는 가장 기본적인 도구다. 단순히 오름차순으로 정리하는 데서 끝나지 않고, 그리디나 이분 탐색의 전처리로도 자주 사용된다. 배열은 가장 기본적인 저장 구조이지만, 인덱스 접근과 삽입·삭제 비용을 이해해야 효율적인 풀이를 만들 수 있다.
DFS와 BFS는 그래프와 트리 문제의 핵심이다. DFS는 한 방향으로 깊게 들어가며 탐색하기 때문에 백트래킹이나 모든 경우의 수 탐색에 잘 어울린다. BFS는 가까운 노드부터 차례대로 탐색하므로 최단 거리나 단계별 확산 문제에서 자주 사용된다.
스택, 큐, 우선순위 큐도 문제의 흐름을 제어하는 데 많이 쓰인다. 스택은 최근 상태를 먼저 처리해야 할 때, 큐는 들어온 순서대로 처리해야 할 때, 우선순위 큐는 매번 가장 작은 값이나 가장 큰 값을 빠르게 꺼내야 할 때 유용하다.
연결 리스트와 LinkedHashMap처럼 언어별 라이브러리에서 제공하는 자료구조도 함께 살펴볼 필요가 있다. 직접 구현하는 문제도 있지만, 대부분의 실전 문제에서는 제공되는 자료구조를 정확히 고르고 안전하게 사용하는 능력이 더 중요하다.
결국 목표는 개념을 외우는 것이 아니라 문제 상황에 맞는 도구를 고르는 것이다. 각 글에서는 정의보다 “언제 쓰는지”, “왜 이 방식이 효율적인지”, “실수하기 쉬운 부분은 무엇인지”를 중심으로 정리한다.