입사 코딩테스트 필수 알고리즘 10가지: 완벽 정복 가이드

코딩테스트 준비할 때 모든 알고리즘을 다 공부할 순 없다는 거 아시죠? 시간도 제한되어 있고, 효율적으로 준비해야 하니까요. 저도 처음엔 뭘 공부해야 할지 몰라서 헤맸는데, 지금은 어떤 알고리즘들이 코딩테스트에서 자주 나오는지 알게 됐습니다. 이번 글에서는 제가 배운 경험을 바탕으로 입사를 위한 코딩테스트에서 꼭 알아야 할 10가지 알고리즘을 정리해서 여러분과 공유하려고 합니다. 저도 공부하면서 느꼈던 어려움을 반영해서 최대한 쉽게 설명할 거니까, 함께 차근차근 배워봅시다.

정렬(Sorting) - 모든 알고리즘의 기초

정렬은 코딩테스트에서 가장 기본이 되는 알고리즘입니다. 저는 이걸 "알고리즘의 기초"라고 부르는데, 왜냐하면 정렬을 얼마나 잘 이해하는지에 따라 다른 알고리즘을 배우는 속도가 달라지기 때문입니다.

 

코딩테스트에서 자주 나오는 정렬 알고리즘은 여러 개가 있습니다. 먼저 퀵 정렬(Quick Sort)은 평균적으로 O(nlogn)의 시간복잡도를 가지며, 실무에서도 많이 사용됩니다. 피벗을 기준으로 데이터를 분할해서 정렬하는 방식인데, 처음 배울 때는 좀 복잡해 보일 수 있어요. 하지만 한 번 이해하면 정말 강력한 알고리즘입니다.

 

병합 정렬(Merge Sort)은 항상 O(nlogn)을 보장한다는 장점이 있습니다. 퀵 정렬은 최악의 경우 O(n²)가 될 수 있지만, 병합 정렬은 상황에 상관없이 일정한 성능을 유지합니다. 안정적인 정렬이 필요한 문제에서 유용하죠.

실전 팁으로는, 대부분의 코딩테스트에선 언어에서 제공하는 기본 정렬 함수를 쓰는 게 가장 효율적입니다. Python의 sorted()나 Java의 Arrays.sort()같이요. 하지만 정렬 알고리즘의 원리를 알고 있어야 최적화할 때 도움이 됩니다.

DFS/BFS - 그래프 탐색의 양대 산맥

그래프 탐색은 코딩테스트에서 정말 중요한데, 이 둘의 차이를 정확하게 이해하는 게 핵심입니다.

 

DFS(깊이 우선 탐색)는 한 경로를 끝까지 탐색한 후 다시 돌아와서 다른 경로를 탐색하는 방식입니다. 스택이나 재귀를 사용해서 구현하는데, 재귀로 구현하면 코드가 간단해집니다. DFS는 특히 미로 찾기 문제나 백트래킹이 필요한 문제에서 자주 사용됩니다.

 

BFS(너비 우선 탐색)는 시작점 근처의 모든 노드를 먼저 탐색하고, 점점 멀어지는 방식입니다. 큐를 사용해서 구현합니다. BFS의 가장 큰 특징은 최단 경로를 보장한다는 거예요. 무가중치 그래프에서 두 지점 사이의 최단 경로를 찾아야 할 때 BFS가 정답입니다.

 

내가 처음 배웠을 때 헷갈렸던 부분이 "둘 다 모든 노드를 방문하는데 뭐가 다르냐?"는 거였어요. 하지만 차이는 경로의 특성과 사용 목적에 있습니다. 경로의 특징을 저장해야 하거나 특정 조건을 만족하는 경로를 찾을 때는 DFS, 최단 거리를 구해야 할 때는 BFS를 선택하면 됩니다.

이진 탐색(Binary Search) - O(log n)의 마법

이진 탐색은 정렬된 배열에서 매우 빠르게 원하는 값을 찾는 알고리즘입니다. 시간복잡도가 O(log n)인데, 이게 얼마나 빠른지 아실까요? 100만 개의 데이터에서 약 20번 정도만 비교하면 찾을 수 있다는 뜻입니다.

 

구조는 간단합니다. 배열의 중간 값을 기준으로 찾는 값이 중간값보다 작으면 왼쪽 절반, 크면 오른쪽 절반에서 다시 찾는 식입니다. 이런 식으로 탐색 범위를 계속 반으로 줄여나가는 거죠.

 

코딩테스트에서 이진 탐색이 어려운 이유는 "이진 탐색을 써야 한다"는 걸 인식하지 못하기 때문입니다. 정렬된 배열에서 특정 값을 찾거나, "조건을 만족하는 최소/최대 값을 찾는" 문제라면 이진 탐색을 의심해봐야 합니다.

동적 프로그래밍(Dynamic Programming) - 중복 계산 피하기

동적 프로그래밍은 처음 배울 때 정말 어렵게 느껴집니다. 저도 그랬고요. 하지만 핵심은 간단합니다: 작은 문제의 답을 저장해서 큰 문제를 푼다.

 

피보나치 수열을 예로 들면, 재귀로 구현하면 fib(5)를 계산할 때 fib(3)을 여러 번 계산하게 됩니다. 이게 비효율적이죠. 하지만 DP에서는 한 번 계산한 결과를 배열에 저장해두고 다시 필요하면 그걸 꺼내 쓰는 겁니다.

 

DP를 풀 때는 세 가지를 항상 생각해야 합니다. 첫째, 상태 정의: 문제의 상태를 어떻게 표현할 것인가. 둘째, 점화식: 현재 상태와 이전 상태의 관계식. 셋째, 초기값: 가장 작은 경우의 답.

 

코딩테스트에서 DP 문제는 "정보 처리에서 최적값을 구하는 문제"가 많습니다. 배낭 문제, 최장 증가 부분수열, 최대 경로 합 이런 식으로요. 처음엔 어렵지만, 많은 문제를 풀다 보면 패턴이 보입니다.

그리디 알고리즘(Greedy Algorithm) - 현재의 최선이 전체 최선일 때

그리디 알고리즘은 매 순간 지금 상황에서 가장 좋아 보이는 선택을 하는 알고리즘입니다. 이게 항상 정답이 되는 건 아니지만, 올바르게 적용하면 정말 간단하고 빠르게 최적해를 구할 수 있습니다.

 

예를 들어 거스름돈 문제를 봅시다. 10,000원을 거슬러 줘야 할 때, 큰 동전부터 먼저 사용하면 최소 개수의 동전으로 거슬러 줄 수 있습니다. 5,000원 짜리 동전 2개를 선택하는 게 매 순간의 최선이고, 동시에 전체 최선이죠.

 

그리디의 핵심은 "정말 이 선택이 전체 최적해로 이어지는가?"를 증명할 수 있는가입니다. 논리적으로 증명이 안 되면 그리디로 풀 수 없고, DP나 다른 방법을 써야 합니다. 코딩테스트에서 그리디 문제가 나오면, 먼저 그리디 접근이 가능한지 검증하는 시간을 가져야 합니다.

백트래킹(Backtracking) - 불가능한 길을 빨리 포기하기

백트래킹은 DFS의 한 형태인데, "가능성이 없는 경로는 빨리 포기하자"는 아이디어입니다. 가지를 쳐낸다고 해서 "가지치기"라고도 부르죠.

 

예를 들어 N-Queen 문제를 봅시다. N개의 퀸을 N×N 체스판에 배치하는데, 서로 공격할 수 없도록 놓는 거예요. 각 행에 퀸을 하나씩 배치하면서, 이미 배치된 퀸들과 충돌하는 위치는 시도도 하지 않습니다. 이게 백트래킹입니다.

 

백트래킹은 조합, 순열, 부분집합 문제에서 자주 나옵니다. 코딩테스트에서 "모든 경우의 수를 확인해야 하지만, 일부 경우는 불가능하다"는 상황이 백트래킹의 신호입니다.

해시(Hash) - 빠른 탐색과 저장

해시는 정말 실용적인 알고리즘입니다. HashMap이나 HashSet을 쓸 때 내부적으로 작동하는 원리죠.

 

해시의 기본 아이디어는 간단합니다: 데이터와 그 데이터의 위치를 연결하는 함수(해시 함수)를 만드는 거예요. 그러면 데이터를 찾을 때 O(1) 시간에 찾을 수 있습니다.

 

코딩테스트에서 해시가 유용한 경우는 "중복 확인", "빈도 계산", "특정 조건을 만족하는 원소 찾기" 같은 상황입니다. 예를 들어 배열에서 중복된 원소를 찾는 문제라면, HashMap에 각 원소의 빈도를 저장하고, 빈도가 2 이상인 것을 찾으면 됩니다.

 

해시의 단점은 충돌(두 다른 데이터가 같은 해시값을 가지는 경우)이 발생할 수 있다는 것인데, 좋은 해시 함수를 쓰면 충돌을 최소화할 수 있습니다.

분할 정복(Divide and Conquer) - 문제를 쪼개서 정복하기

분할 정복은 큰 문제를 작은 문제로 나눈 후, 각 작은 문제를 해결하고, 그 결과를 합쳐서 원래 문제를 푸는 방식입니다.

 

병합 정렬과 퀵 정렬이 대표적입니다. 배열을 반으로 쪼개서 각각 정렬한 후 합치는 거죠. 분할 정복의 시간복잡도는 재귀 관계식으로 표현되는데, 마스터 정리를 사용하면 계산할 수 있습니다.

 

분할 정복이 효율적이려면 부분 문제들이 독립적이어야 합니다. 만약 부분 문제들이 겹친다면 동적 프로그래밍을 고려해야 합니다.

코딩테스트에서 분할 정복은 "큰 데이터를 작은 단위로 나눠서 처리"해야 할 때 유용합니다. 예를 들어 구간 합 구하기, 행렬 곱셈 같은 문제들이 있습니다.

투 포인터(Two Pointer) - 두 개의 포인터로 선형 시간 구하기

투 포인터는 정말 간단하지만 강력한 기법입니다. 시작점과 끝점에 포인터를 두고, 조건에 따라 포인터를 이동시키면서 문제를 푸는 거예요.

 

예를 들어 정렬된 배열 [1, 2, 3, 4, 5]에서 합이 6인 두 수를 찾는다고 합시다. 시작 포인터는 0(값 1), 끝 포인터는 4(값 5)에 놓습니다. 1+5=6이면 답이고, 7이면 끝 포인터를 왼쪽으로, 3이면 시작 포인터를 오른쪽으로 이동합니다. 이렇게 하면 O(n²)을 O(n)으로 줄일 수 있습니다.

 

투 포인터가 작동하는 핵심 조건은 데이터가 정렬되어 있거나, 순서대로 처리 가능해야 한다는 것입니다. 정렬된 배열에서 두 수의 합 구하기, 연속 부분배열 찾기, 중복 제거 같은 문제에서 자주 나옵니다.

1최단 경로 알고리즘(다익스트라, 플로이드-워샬) - 최적의 경로 찾기

마지막이 최단 경로 알고리즘입니다. 이건 실무에서도 정말 많이 쓰이는 알고리즘이에요.

 

다익스트라 알고리즘은 한 지점에서 다른 모든 지점까지의 최단 거리를 구합니다. 네비게이션이나 라우팅 같은 곳에서 사용됩니다. 우선순위 큐를 사용해서 구현하면 O(E log V) 시간복잡도를 가집니다.

 

플로이드-워샬 알고리즘은 모든 지점 쌍 사이의 최단 거리를 구합니다. 구현은 간단하지만(3중 반복문), 시간복잡도는 O(n³)입니다. 따라서 노드가 적을 때만 사용 가능합니다.

 

코딩테스트에서 "최단 경로"라는 표현이 나오면 일단 다익스트라를 생각해보세요. 음수 간선이 있으면 벨만-포드를 써야 하고, 특정 조건(같은 비용의 여러 경로 등)이 있으면 상황에 맞게 변형해야 합니다.

학습 팁과 실전 조언

몇 가지 조언을 드리자면, 먼저 한 알고리즘을 완벽하게 이해하는 게 많은 알고리즘을 맛보는 것보다 낫습니다. 정렬부터 시작해서 하나씩 깊이 있게 배워나가세요.

 

둘째, 문제를 풀 때 어떤 알고리즘을 써야 할지 판단하는 능력을 기르세요. 이건 많은 문제를 풀면서 패턴을 익혀야 합니다. 처음엔 어렵지만, 50개, 100개 풀다 보면 자동으로 판단됩니다.

 

셋째, 구현보다는 논리를 먼저 생각하세요. 코드를 작성하기 전에 종이에 그려보고, 로직을 명확히 한 후 코딩하면 버그가 훨씬 적습니다.

 

마지막으로, 한 번 배운 알고리즘을 계속 복습하세요. 코딩테스트 준비 기간이 길지 않으니 효율적으로 준비해야 합니다. 백준, 프로그래머스, LeetCode 같은 플랫폼에서 꾸준히 문제를 풀면서 실력을 다져나가시길 바랍니다.

 

입사 준비 과정은 정말 길고 힘들 수 있습니다. 저도 처음 코딩테스트를 봤을 때 정말 떨렸으니까요. 하지만 이 10가지 알고리즘을 정확히 이해하고 많은 문제를 풀다 보면, 어떤 문제가 나와도 대처할 능력이 생깁니다.

 

여러분도 저와 함께 차근차근 준비하면 반드시 좋은 결과를 얻을 수 있을 겁니다. 어려운 부분이 있으면 같은 주제의 문제를 여러 번 풀어보세요. 반복이 실력을 만듭니다. 화이팅!

 

코딩테스트 합격을 위해 반드시 알아야 할 자료구조 핵심 개념 완벽 정리 가이드