알고리즘 로드맵

코딩 테스트 단계별로 필요한 준비 by 우영(ilium)

💡 코딩 테스트 준비할 때, 각 단계에서 공부가 필요한 내용들을 정리했습니다. 2023년 코딩 테스트 응시 경험을 바탕으로 작성했기 때문에 주관적일 수 있습니다. [해당 글은 2023년 12월에 작성했습니다.]

코딩 테스트 준비 시작 단계

1. 코딩 테스트 언어 선택
2. 본인의 개발 언어를 중심으로 코딩 테스트 응시 언어를 선택하는 것이 유리합니다. 하지만 제공이 잘 되지 않는 언어이거나, 응시하기 어려운 언어라면 Python3를 가장 추천합니다.
3. 어떤 유형의 시험인지 파악💡 주관적인 코딩 테스트 평가 항목
   • 프로그래밍 활용 능력
     • 요구 사항 분석 및 구현
   • 자료구조 및 알고리즘 활용 능력
     • 문제 해결 및 해결 코드 구현 
4. 제 생각에는 코딩 테스트라는 시험으로 크게 2가지를 평가하려고 합니다. 하지만 프로그래밍이나 알고리즘을 잘 안다고 해서 문제를 잘 해결하는 것은 아닙니다. 어떻게 문제가 나오는 지 어느 정도 파악할 필요가 있습니다.
5. 목표 기업 설정 💡 주관적인 준비 방향
   • 응시자 필터링 용도
     • 1차, 2차 시험이 나누어져 있거나, 많은 응시자가 예상되는 코딩 테스트
     • 기업이 요구하는 최소한의 프로그래밍 능력이 있는지 판단하는 경우
   • 잘하는 사람을 선발
     • 소수 인원이 응시하는 코딩 테스트
     • 수시 채용의 경우, 코딩 테스트 응시 후 코드 면접이 별도로 있는 경우 
6. 어떤 기업은 코딩 테스트를 응시하지 않기도 하고, 응시하기도 합니다. 목표로 하는 기업을 어느 정도 잡고 있다면 준비 방향을 고민할 수 있습니다.

코딩 테스트 입문 단계

1. 문제 해결 & 요구 사항 분석💡 추천 연습 방법
   • 구름 레벨에서 문제를 읽어보고, 문제의 내용을 1~2줄 이내로 정리하는 연습을 하면 좋습니다.
   • ex. 이 문제는 주어지는 정수 중에서, 2번 주어지지 않는 정수를 찾아 더하는 문제이다.
2. 코딩 테스트란 주어진 문제를 코드로 해결하는 것을 기본으로 합니다. 즉, 문제의 요구 사항을 정확히 이해한다면 코드를 작성할 때 명확하게 작성할 수 있습니다. 정리를 할 때 있어서 해결 방법을 같이 작성해도 좋고, 고려할 부분을 작성해도 좋습니다. 하지만, 문제의 내용을 모두 담고 있어야 합니다. 정리 과정에서 누락한 내용이 코드에 반영되지 않으면 문제를 틀리기 때문입니다.
3. 코딩 테스트 언어와 프로그래밍 공부
   1. 다양한 입출력 방법
   2. 입력 데이터와 출력을 하는 방법에 대한 학습이 필요합니다. 요구 사항에 맞춘 결과를 찾는 문제도 있지만, 요구 형식에 맞춰 출력이 필요한 문제도 있습니다.
   3. 기본 자료형 💡 어떤 언어는 자동으로 BigInteger를 제공하지만, 제공하지 않는 언어도 있습니다. 이처럼 언어의 자료형은 언어마다 다양한 특징을 가지고 있습니다. 응시하려는 언어에 맞게 잘 활용할 수 있어야 합니다.
   4. 각각 언어에서 사용되는 다양한 기본 자료형과 특징을 이해하고 있어야 합니다. 더불어 기본 자료형을 다루는 처리 함수와 활용 함수를 함께 공부하면 좋습니다.
   5. 조건문, 반복문💡 대부분 문제 문제는 자원만 무한하다면, 여러 개의 반복문과, 조건문을 통해서 모든 문제를 해결할 수 있습니다. 이때, 자원을 최적화 하는 방법이 바로 알고리즘입니다.
   6. 코드 실행을 제어하는 프로그래밍 문법 체계를 공부해야 합니다. 단순하게 작성하는 것이 아니라, 제어문을 응용하고 개념적으로 이해할 수 있어야 합니다.
   7. 객체 자료형 💡 언어마다 제공하는 객체 자료형이 모두 다릅니다. 어떤 언어는 하나의 자료형으로 스택과 큐를 모두 구현할 수 있는 반면에, 어떤 언어는 큐만 구현할 수 있는 경우도 있습니다. 객체 자료형의 개념을 바탕으로 특정한 자료 구조를 구현하는 방법의 공부 필요합니다.
   8. 배열, Hash, 집합 등 각 언어에서 제공하는 객체 자료형을 처리하고 활용할 수 있어야 합니다. 기본적인 객체 자료형을 제공하지 않는다면 구현하는 방법도 알고 있어야 문제를 해결할 수 있습니다.
4. 응시하려는 코딩 테스트 언어에 관한 기초적인 학습이 필요합니다. 개념적인 내용이 많으면, 해당 부분을 실수하면 코드에서 오류가 드러나지 않아서 실수하지 않을 정도로 숙련된 연습이 필요합니다.
5. 기초적인 수학 개념 이해
   1. 진법의 개념과 변환 방법
   2. 소수의 개념과 특징, 소수 판별 알고리즘
   3. 최대 공약수, 최소 공배수
   4. 경우의 수, 정수의 특징, 반올림, 언어에 따른 소수점 이하의 연산 방법
6. 수학 개념 없이 코딩 테스트에 합격할 수 있습니다. 하지만, 최소한의 수학적 테크닉을 활용하기 위해 필요한 간단한 개념을 알고 있으면 큰 도움이 됩니다.

코딩 테스트 초급 단계

초보 단계만 잘 준비해도 합격할 수 있는 코딩 테스트는 많습니다. 초보 단계에서는 알고리즘보다는 자료 구조나 시간 복잡도를 고려하지 않는 풀이를 많이 공부하면 좋습니다.

1. 자료 구조의 이해와 구현 방법더불어 다양하게 활용할 수 있는 방법과 적용하기에 적절한 문제를 찾는 연습도 필요합니다.</aside>
2. <aside> 💡 각 언어가 자료 구조를 선언하는 다양한 방법이 있습니다. 그래서 자료구조를 선언하는 방법에 따라서 언어 별 난이도 차이가 발생합니다. 그래서 Python3를 추천 드린 이유 중 하나가 Python3는 어렵지 않게 위의 모든 자료 구조를 선언할 수 있다는 장점을 가지고 있기 때문입니다.
3. 리스트, 스택, 큐, 데크 등 선형 자료 구조에 대한 학습과 비선형 자료구조인 그래프, 트리, (매트릭스)를 이해하고 구현할 줄 알아야 합니다.
4. 정렬<aside> 💡 이 문제와 같이 다양한 정렬하는 조건이 있을 때 처리하는 방법에 대한 이해가 필요합니다. 또한 정렬을 바탕으로 이진 탐색 등 알고리즘을 적용하기 전에 자료에 대한 전처리 할 때 필요하기도 합니다.
5. </aside>
6. 다양한 정렬 방법이 있지만, 결국 정렬을 하는 코드는 보통은 간단한 편입니다. 하지만 중요한 건 일반적인 정렬이 아닌, 우선 순위가 여러 개이거나, 특별한 조건으로 정렬이 필요한 경우에 작성하는 정렬 우선 순위 함수에 대한 이해가 필요합니다.
7. 완전 탐색완전 탐색을 넘어서, 이분 탐색, Two Pointer 등의 탐색 방법도 함께 알고 있으면 좋습니다.</aside>
8. <aside> 💡 이 문제는 모든 경우의 수 중에서, 최고의 조합을 찾는 문제입니다. 보통 완전 탐색하면 Matrix에서 특정한 값을 찾는 문제로 생각할 수 있지만 경우의 수 중 최고의 조합을 찾는다는 점을 이해해야 합니다.
9. 완전 탐색은 탐색 가능한 모든 경우의 수를 찾아 최적의 해를 찾는 문제입니다. 완전 탐색의 알고리즘은 Brute Force 로 분류가 되고 있지만, 더 넓은 개념에서는 모든 경우의 수 중 최고의 조합을 찾는 문제나, Matrix에서 경로를 찾거나, 문제 상황을 그대로 시뮬레이션을 하면서 탐색을 하는 등 다양한 문제가 출제되고 있습니다.
10. 그래프와 그래프 탐색
    • 그래프에서 이해하면 좋은 개념
      • 그래프의 기본적인 개념
        • 노드와 간선
      • 그래프의 구현 방법
        • 인접 행렬 그래프
        • 인접 리스트 그래프
      • 그래프의 종류
        • 방향 & 무방향 그래프
        • 가중치 & 가중치가 없는 그래프
        • 연결 & 비연결 그래프
        • 사이클 & 비순환 그래프
        • 완전 그래프
        • 트리
    <aside> 💡 그래프 문제의 대부분 해결 방안은 BFS/DFS를 응용하는 문제가 대부분의 문제입니다. 이 문제도 단순하게 그래프의 개념과 탐색 방법만 이해하면 쉽게 해결할 수 있습니다.
11. </aside>
12. 그래프의 개념과 구현 방법을 이해하고 BFS/DFS 탐색을 구현하는 방법에 대한 공부가 필요합니다. 복잡한 그래프 문제가 아닌, 기본적으로 동작하는 방법과 알고리즘을 구현하는 방법만 이해하면 됩니다.

코딩 테스트 중급 단계

본격적으로 심화된 완전 탐색과 그래프 탐색을 이해하고 탐욕 알고리즘과 동적계획법 등 알고리즘 중심의 공부를 하게 됩니다. 중급 단계까지 잘 준비하면 대부분의 코딩 테스트를 합격선으로 만들 수 있습니다.

1. 시간/공간 복잡도의 개념<aside> 🤙 입출력 예시를 통해서 어느 정도 시간 복잡도를 예측해보는 연습이 필요합니다. 시험 환경은 보통 1초에 대략 1억 ~ 10억 번의 연산을 수행할 수 있습니다. 시험에 따라서 제한 시간을 준다면 이는 분명 효율적인 방법론에 대한 고민이 필요한 시험입니다.
2. 초급 단계와 다르게 최적화에 대한 개념이 필요합니다. 즉, 단순하게 반복문이나 조건문을 사용하여 문제를 해결하지 않고 문제 해결을 위한 효율적인 방법을 찾아야 합니다.
3. 완전 탐색 심화<aside> 🤙 완전 탐색은 기본적으로 $O(N^2)$ 의 시간 복잡도 이상을 고려합니다. 하지만, 다양한 탐색 알고리즘을 통해서 시간 복잡도를 최소화 하는 것을 목표로 하는 알고리즘들이 대부분입니다.
4. 완전 탐색이 단순하게 모든 경우의 수에서 원하는 결과를 찾는 방법이라면, 심화 단계에서는 모든 경우의 수를 빠르게 찾는 방법을 고민하고 적용합니다. 백트래킹, 조합, 비트 마스킹 기법들을 공부하면 좋습니다.
5. 그래프 응용<aside> 🤙 이 문제는 난이도는 어렵지만, 사실 단순한 최단 비용 경로를 찾는 문제입니다. 이처럼 개념이 어려워서 높은 난이도로 잡지만, 풀이는 간단한 경우가 있습니다.
6. 그래프 응용은 그래프의 구현 방법에 대한 이해와 간선과 노드 사이의 관계에 대한 새로운 정의를 합니다. 비용이나, 가중치 등이 그래프에 추가됩니다. 이를 해결하기 위해서 유니온 파인드, 최소 신장 트리, 최단 경로를 찾는 그래프 알고리즘이 필요합니다.
7. 탐욕 알고리즘<aside> 🤙 배낭 문제, 동전 거스름돈 문제, 회의실 문제, 최소 신장 트리 정도의 개념만 있다면 코딩 테스트에서 이 이상의 알고리즘을 질의하는 경우는 드뭅니다.<aside> 🤙 이 문제는 회의실 문제를 바탕으로 해결하는 문제입니다. 탐욕 알고리즘은 특수한 상황에 올바른 알고리즘을 선택하면 어렵지 않게 풀어낼 수 있습니다.
8. </aside>
9. </aside>
10. 현재 단계에서 최적이라고 판단되는 선택을 통해서, 전체의 최적화된 결과를 도출하는 알고리즘입니다. 대표적인 유형이 있기 때문에, 유형에 대한 학습만 진행하면 크게 어려움이 없습니다.
11. 동적 계획법<aside> 🤙 동전 거스름돈과 배낭 문제는 탐욕 알고리즘으로 풀리지 않는 경우가 있습니다. 탐욕 알고리즘은 특수한 상황에서 적용되기 때문입니다. 이 경우, 우리는 다른 방법을 선택해야 합니다.<aside> 🤙 이 문제는 동적 계획법을 활용한 문제입니다. 꼭 단순하게 수학적 계산이 아닌, 다양한 자료구조를 활용해서 이전의 계산에 대한 기록이 필요할 수 있습니다.
12. </aside>
13. </aside>
14. 탐욕 알고리즘과 다르게, 현재 단계에서 최적의 상태가 아닌 전체의 상태에서 최적의 선택을 통해서 결과를 도출하는 방법론입니다. 수학적인 식을 도출하는 문제와, 과거의 기록을 바탕으로 다음의 기록을 선택하는 문제도 있습니다.
15. 트리의 이해와 활용<aside> 🤙 이 문제는 트리의 일반적인 개념을 익히기에 적합한 문제입니다. 트리에서 노드가 생성되는 과정을 구현할 수 있습니다.
16. </aside>
17. 트리의 개념과 용어, 종류를 이해하고 구현할 수 있으면 좋습니다. 트리를 순회하는 방법을 바탕으로 트리 위에서 발생하는 기본적인 탐색 방법을 트리에 적용할 수 있으면 대부분 코딩 테스트에서 나오는 트리 문제는 이 수준에서 이상을 요구하지 않습니다.

코딩 테스트 고급 단계

코딩 테스트에서 고득점을 목표로 한다면 준비가 필요한 알고리즘입니다. 독학으로 공부하기에는 어려운 알고리즘이 많습니다. 사람들이 어렵다고 느끼는 코딩 테스트에서 해당 영역의 문제까지 출제가 됩니다.

1. 문자열 알고리즘
2. 단순한 문자열을 탐색하는 것이 아닌, 문자열을 효율적으로 탐색하는 알고리즘입니다. 문자열을 정수로 치환하는 해싱, 문자열 매칭과 KMP, 문자열 집합을 관리하는 트라이 등 다양한 문자열을 탐색하는 알고리즘이 있습니다.
3. 동적 계획법 응용
4. 기존의 동적 계획법은 이전의 고정된 계산 결과를 반영하여, 다음의 최적해를 찾았습니다. 하지만, 트리나 그래프에서도 동적 계획법을 활용하여 최적해를 탐색하기도 합니다.
5. 트리의 응용
6. 단순하게 트리에서 특정 값을 탐색하거나 찾는 것이 아니라, 자식 노드와 부모 노드 사이의 관계를 찾는 알고리즘을 공부합니다. 최소 공통 조상이나, 이전의 노드 기록을 바탕으로 최적해를 찾거나, 세그먼트 트리 등을 이용하여 자식 정보를 바탕으로 부모 노드를 구성하기도 합니다.
7. 그래프 심화
8. 이전에 양수의 비용과 가중치에서 비용을 찾는 문제에서, 음수 비용과 가중치가 있을 때 어떤 선택과 탐색을 고민하는 밸만포드와 SPFA 알고리즘이 있습니다. 방향이 있는 그래프에서 정점들을 정렬하는 위상 정렬과 플로이드 알고리즘을 바탕으로 모든 노드 사이의 최단 거리를 구할 수도 있습니다.
9. 수학적 접근<aside> 🤙 이러한 수학 문제의 경우 주어지는 입력 데이터가 매우 큰 경우가 있습니다. 단순하게 $O(N)$값이 10억을 넘어가는 경우에는 수학 문제일 가능성이 높습니다.
10. </aside>
11. 문제를 해결을 위한 수학적 개념입니다. 수학적 접근은 동적 프로그래밍 문제를 해결할 때 점화식을 세울 때 많이 필요하며, 카탈린 수, 오일러 순환, 유클리드 정리 등 문제를 해결할 때 자료구조나 알고리즘 없이 단순하게 수학적 계산으로 해결할 수 있는 문제들입니다.

코딩 테스트 전문가 단계

코딩 테스트에서 보기는 어렵지만, 간혹 개념을 활용한 문제가 출제됩니다. 대부분 경진대회에서 볼 수 있는 수준의 알고리즘으로, 코딩 테스트의 단순한 합격이 목적이면 공부하지 않아도 큰 문제가 없습니다.

1. 고급 트리 구현과 응용
2. 펙윅 트리, 2차원 세그먼트 트리, Lazy 세그먼트 트리 등 기존의 트리를 효율적으로 연산하기 위한 구조입니다.
3. 고급 문자열 알고리즘
4. Suffix Trie나 야호-코라식 등 기존의 문자열 매칭, 탐색을 자료 주고 형태로 변경하여 탐색하는 알고리즘입니다.
5. 최대 유량 알고리즘
6. 대표적인 알고리즘으로 MCMF가 있습니다. 이는 어떤 흐름이 있을 때 그 비용이 최소가 되도록 하는 알고리즘입니다. 반대로 최소 비용으로 운영할 수 있는 유량의 순환을 구성할 때 고려되는 알고리즘입니다.
7. 기하 알고리즘
8. CCW, Convex Hull 등 평면 상에서 점들 사이의 관계를 구성하여 다각형을 찾는 알고리즘입니다.