IT관련 대기업, 금융권 및 유니콘 기업에 취업하기 위한 코딩테스트 준비는 선택이 아닌 필수가 되었다.
대부분의 기업의 채용 프로세스는 서류 - 코딩테스트 - 면접 순으로 이루어지기 때문에 코딩테스트에 통과하지 못한다면 면접을 볼 수 있는 기회조차 없는 것이 일반적이다.
이 글에서 코딩테스트 준비를 시작하는 학생들에게 가늘고 길게 공부할 수 있는 방법을 제시할 것이다.
그리고 이 방법은 내가 작년부터 코딩테스트를 위해 경험한 내용을 기반으로 한다. 나름 긴 시간동안 꾸준히 문제해결과 알고리즘 공부를 해왔고, 채용 단계에서 PS유형의 코딩테스트에서는 한 곳 빼고 모두 합격했었다.
글을 읽는 사람들에게 나름의 신뢰도를 제시해야 하기에 부끄럽지만 나의 백준 프로필을 근거로 올린다.
https://www.acmicpc.net/user/tjdahr25
tjdahr25 정보
맞았지만 만점을 받지 못한 문제
www.acmicpc.net
저보다 백준 티어가 높거나 PS 실력이 더 높을 것이라고 판단되면 이 글을 읽을 필요가 없다. 이미 고수십니다.
그러므로 이후의 글은 나보다 PS 경험이 부족한 사람들을 대상으로 작성하겠다.
코딩테스트와 알고리즘 대회의 차이
최근 코딩테스트가 각광받기 시작하며 동시에 알고리즘 대회들도 많은 관심을 받고 있다.
ICPC, 정보 올림피아드, SCPC, NYPC 등 다양한 기관 또는 기업에서 알고리즘 대회를 개최하고 수상자에게 꽤 좋은 혜택들을 제공한다.
그러나 일반적인 기업의 채용 프로세스에서 실시하는 코딩테스트는 위 알고리즘 대회와 성격이 조금 다르다.
알고리즘 대회는 고난이도 알고리즘, 기하 및 수학 등 기본적으로 문제의 난이도가 살벌하며 특정 알고리즘을 모를 경우 절대 풀 수 없는 문제들이 있다. 나또한 알고리즘 대회 출전이 아닌 코딩테스트 통과를 목적으로 공부했기 때문에 고난도 알고리즘들은 전혀 알지 못한다. 혹시나 위 알고리즘 대회를 준비하기 위해 이 글을 읽는다면 별로 좋은 정보를 얻지 못할 것이다.
코딩테스트와 알고리즘 대회의 가장 큰 차이점은 위에서 말했듯이 난이도와 알고리즘의 범위이다.
후술하겠지만, 코딩테스트에 출제되는 알고리즘의 범위는 그렇게 넓지 않다. 난이도 또한 후술하겠지만, Solved.ac 기준으로 골드1의 난이도만 나와도 그 문제는 가장 어려운 문제일 것이다.
이제 알고리즘 대회는 뒤로 하고 코딩테스트에만 집중하여 서술하겠다.
코딩테스트에 관하여
어떤 문제를 논리를 통해 특정 Input에 대해 정해진 Output을 출력하게끔 코드를 작성하는 것이 일반적인 문제해결의 유형이다.
그리고 이런 유형을 앞으로 PS유형이라고 하겠다.
코딩테스트또한 대부분 PS유형의 문제들로 구성된다. 간혹 API를 부르는 문제나 다른 유형의 문제 등이 등장하기도 하지만, 본 글에서는 일반적인 PS에 대해서만 다룰 것이다.
주관적인 생각으로 문제는 크게 두 가지 분류로 나눌 수 있다.
특정 알고리즘을 몰라도 풀 수 있는 문제와 알아야만 풀 수 있는 문제로 말이다.
- 특정 알고리즘을 몰라도 풀 수 있는 문제
보통 이런 류의 문제를 구현문제로 분류한다. 또는 풀 수 있는 해법이 다양하다면 애드혹으로 분류될 수 도 있다.
이런 문제는 보통 적절한 자료구조를 이용해 정확한 해답을 요구하는 시뮬레이션 문제나 모든 과정을 탐색하는 브루트포스가 많다. 물론 브루트포스를 위해 백트래킹과 같은 알고리즘 적인 요소가 요구될 수 있다.
개인적인 견해인데, 요즘은 이렇게 특정 알고리즘을 몰라도 풀 수 있는 문제들이 유행인 것 같다.
- 특정 알고리즘을 알아야 풀 수 있는 문제
보통 코딩테스트 수준의 알고리즘 문제는 풀이법이 정해져 있는 경우가 많다. 예를 들어 최단거리를 구하기 위해 다익스트라, 벨만포드 및 플로이드등을 사용하듯이 문제에서 풀이를 위해 요구하는 알고리즘을 생각해내고 이를 이용해 해결해야 한다. 따라서 자신이 사용할 알고리즘에 대해 시간복잡도를 식으로 표현해보고, Input의 크기를 대입해 제한시간 내에 들어오는지에 대한 판단을 하는 것이 가장 중요하다.
시간복잡도에 대한 내용은 알고리즘 수업을 들으신 분들이라면 알고 있을 것이고, 모르신다면 별도의 검색을 통해 이해하고 오시길 강력히 추천드립니다.
C++ 기준, 보통 1억번의 연산에 대해 1초라고 생각하면 편하다. 예를 들어 N의 크기가 1000이고 설계한 알고리즘의 시간복잡도가 O(N^2)이라면 대충 1000*1000으로 계산하고, 이는 1억보다 현저히 작기에 제한시간이 1초인 문제에서 충분히 사용한 알고리즘이다. 그러나 N의 크기가 10000이라면 사용할 수 없는 알고리즘이다.
보통 시뮬레이션이나 브루트포스문제에선 시간복잡도를 걱정하지 않아도 된다.
다만, 어떤 문제든 코드를 작성하기 전에 자신이 설계한 로직의 대략적인 시간복잡도를 측정해보는 습관은 매우 중요하다.
언어 선택
나는 C++ 이외에 다른 언어로 PS를 하지 않기 때문에 언어의 선택에 대해서 추천해주기 힘들다.
다만, PS에 유용한 라이브러리, 코드의 양 및 난이도를 모두 고려해 보았을 때, C++와 Python을 선택하는 것이 유리할 것이다. 그리고 대부분의 사람들이 이 두 언어를 사용한다.
또한, 코딩테스트의 경우 각 문제에 대해 언어별 제한시간을 다르게 주는 것이 일반적이기 때문에 언어에 따른 처리속도는 걱정하지 않아도 된다. 같은 로직임에도 불구하고 언어의 차이때문에 시간초과가 결정된다면 로직이 잘못된 경우가 대부분 일것이다.
+추가
대부분 기업의 코딩테스트에서 C/C++, Java, Python은 웬만하면 지원하기 때문에 셋 중 하나를 선택하면 된다.
플랫폼 선택
백준을 강력히 추천한다. 문제 수가 타 플랫폼들에 비해 넘사고, Solved.ac라는 서비스와 연동이 되어 문제에 대한 난이도를 제공해주는데, 사용자가 많다보니 나름 정확한 난이도로 측정이 되어있다.
Baekjoon Online Judge
Baekjoon Online Judge 프로그래밍 문제를 풀고 온라인으로 채점받을 수 있는 곳입니다.
www.acmicpc.net
solved.ac
알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 문제들의 난이도 및 티어 정보를 제공하는 사이트입니다.
solved.ac
Solved.ac는 shiftpsh라는 분께서 만드신 백준과 연동할 수 있는 서비스이다.
브론즈 ~ 루비까지 티어를 나누어놓고 사용자와 문제의 티어를 측정한다. 문제의 난이도는 해당 문제를 해결한 유저들이 자유롭게 의견을 제시하는 방식이고, 백준은 국내 온라인저지 플랫폼 중 사용자가 가장 많아서 가장 신뢰도가 높다.
거의 모든 코딩테스트에서는 Solved.ac기준으로 실버5 ~ 골드2 까지의 난이도 안에서 문제가 출제되므로 타겟팅할 문제를 잡기도 수월하다.
또한, 프로그래머스라는 플랫폼이 있다. 일단 대부분의 기업들이 프로그래머스를 통해 코딩테스트를 실시하기 때문에 IDE 환경을 미리 익혀볼 수 있다는 점이 장점이지만, 문제 수가 많이 없다. 다만, 매년 카카오 기출문제와 SQL 문제 등 다양한 분야의 문제들을 가지고 있기 때문에 백준과 같이 병행해서 사용하는 것이 가장 바람직하다.
프로그래머스 기준으로 Level 2 ~ Level 3 사이의 문제들을 막힘없이 해결할 수 있다면 코딩테스트는 걱정하지 않아도 된다.
https://school.programmers.co.kr/learn/challenges?order=recent&page=1
코딩테스트 연습 | 프로그래머스 스쿨
개발자 취업의 필수 관문 코딩테스트를 철저하게 연습하고 대비할 수 있는 문제를 총망라! 프로그래머스에서 선발한 문제로 유형을 파악하고 실력을 업그레이드해 보세요!
school.programmers.co.kr
다시 백준으로 돌아와서 난이도에 대한 이야기를 이어나아가겠다.앞서 말했듯이 거의 모든 코딩테스트에서는 아무리 어려워봤자 플래티넘이상의 문제는 등장하지 않는다. 따라서 백준에서 Solved.ac 연동 기능을 이용해 골드5 ~ 골드2까지 난이도를 적용해놓고 무작위 문제를 풀며 연습하면 된다. 이를 골랜디(골드랜덤디펜스)라고 한다. 스타 유즈맵 해보신 분들이라면 익숙하실듯
Solved.ac를 백준과 연동하게 되면 위와 같은 옵션을 통해 문제를 선택할 수 있다.
나는 주로 위 옵션 조합을 이용하는데, 이를 이용해 골랜디를 진행할 수 있다.
그러나 골랜디는 후술 할 알고리즘 목록에 있는 알고리즘들을 모두 공부한 뒤에 진행해야 한다. 골랜디를 통해 연습하는 가장 큰 이유는 코딩테스트에서 어떤 문제를 보았을 때 문제에서 요구하는 알고리즘을 찾아내는 것이 핵심이기 때문이다. 그러나 여러 알고리즘들에 대한 이해도도 갖추지 않은 상태에서 무작정 실랜디, 골랜디부터 한다면 모르는 알고리즘 문제가 나왔을 때 많은 시간을 허비할 수 있으므로 바람직하지 않다. (물론 이 방식을 통해 사고력을 키울 수 있다) 하지만, 우리는 코딩테스트 통과를 위해 최대한 효율적으로 공부해야 하기 때문에 위 방식을 지양해야한다. 학교수업, 프로젝트 및 취업준비등 할 것이 너무 많기에..
내가 생각하기에 코딩테스트를 준비하기 위한 효율적인 프로세스는 다음과 같다.
각 알고리즘들에 대한 개념공부 및 예제 풀이 → 실랜디 → 골랜디
실랜디에서 전혀 막힘이 없는 수준이 된다면 골랜디로 넘어가면 된다.
공부해야 할 알고리즘
코딩테스트 전형에서 탈락에 대한 걱정을 하지 않기 위해선 코딩테스트에 주로 등장하는 알고리즘들은 정확히 이해하고 구현할 수 있어야 한다. 그동안 여러 코딩테스트들을 경험해보며 필수로 알아야 한다고 생각하는 알고리즘들은 다음과 같다.
앞으로 각 알고리즘들에 대해 포스팅을 작성해서 링크를 달아놓도록 하겠다. (추가 중)
또한, 너무 기본적인 내용(브루트포스, 정렬, 트리, 이진트리, 해쉬, 맵, 힙, 스택, 큐 등)은 따로 공부를 하고 PS를 시작해야 한다.
Dynamic Programming(DP)
DP의 기본 개념을 확실하게 알고 있어야 한다. 일반 난이도의 수준에선 중복된 작업을 방지하기 위해 메모를 이용한다고 이해해도 좋다. DP를 응용하여 생긴 LCS, 배낭문제 등의 알고리즘도 필수로 알고 있어야 한다.
그리디
쉬우면 한없이 쉽고 어려우면 한없이 어려운게 그리디라고 생각한다. 그리디는 증명이 필요한데, 코딩테스트 도중에 이를 귀납적 추론과 같은 방법을 이용해 증명하고 있는 사람은 없을 것이다. 직관적인 감을 이용해도 좋고 특정 유형을 암기해도 좋다. 우리의 목적은 그저 테스트에서 AC(정답)을 띄우면 되는거니까.
수학
소수판별(에라토스테네스의 체), GCD 등 기본적인 수학 내용은 알고있어야 한다.
백트래킹
보통 브루트포싱을 하기 위한 테크닉으로 사용된다. 요즘 코딩테스트에서는 완전탐색문제는 무조건 등장하기 때문에 백트래킹 테크닉은 필수로 장착해야한다.
백트래킹을 연습하려면 백준의 N과 M 시리즈를 모두 풀면 된다.
BFS, DFS
알고리즘 중 가장 중요하다고 생각한다. 각 코딩테스트에서 거의 매번 빠지지 않고 등장하는 유형이다. BFS와 DFS의 기본적인 이해가 정말 중요하고, 응용할 수 있는 능력이 필요하다. 0-1 BFS까지 장착했다면 두려울 것이 없다.
BFS(Breadth-First Search)
설명 탐색을 위해 사용되는 알고리즘이다. 이름에서 알 수 있듯이, 너비를 우선으로 탐색하기 때문에 단계적인 탐색을 위해 사용된다. 여기서 탐색이란, 대표적으로 그래프에서 정점 방문을 예
seongmok.com
DFS(Depth-First Search)
DFS BFS와 같이 탐색에 이용되는 대표적인 알고리즘이다. BFS(Breadth-First Search) 설명 탐색을 위해 사용되는 알고리즘이다. 이름에서 알 수 있듯이, 너비를 우선으로 탐색하기 때문에 단계적인 탐색
seongmok.com
시뮬레이션
카카오와 삼성이 좋아하는 유형의 문제다. 보통 시간복잡도에 대해 크게 걱정하지 않아도 되지만, 문제 요구사항에 맞는 정확한 구현력을 요구한다. 나는 개인적으로 시뮬레이션을 어려워해서 백준에서 측정된 난이도보다 체감난이도가 훨씬 더 높은 것 같다. 또한 BFS나 DFS와 같이 탐색을 하기 위한 알고리즘이 요구되는 경우가 자주 있다.
이분 탐색
코딩테스트에 나오는 알고리즘 유형중 가장 생각하기 쉽고, 정해를 찾아내기 쉽다. 아이디어 또한 매우 간단하기 때문에 구현상의 오류를 범하지 않는다면 쉽게 해결할 수 있다. (코딩테스트 한정)
다만, 대부분의 이분탐색 문제들은 다루는 수의 범위가 매우 크기 때문에 C++를 사용한다면 자료형에 유의해야한다.
투 포인터
개인적인 의견으로 투 포인터는 특정 알고리즘이라고 칭하기엔 너무 광범위하고, 일종의 테크닉이라고 생각한다.
두 개의 포인터를 사용해 불필요한 연산을 줄이며 답을 찾아 나아가는 과정인데, 이분탐색도 일종의 투 포인터 개념으로 생각할 수 있다.
꽤 자주 등장하며 투 포인터를 사용해 특정 연산을 건너 뛴다면 이에 맞는 증명을 확실히 해야 한다.
최단 거리(다익스트라, 벨만-포드, 플로이드-워셜)
최단거리를 찾기위한 알고리즘으로는 크게 세가지를 뽑을 수 있다.
다익스트라, 벨만포드, 플로이드인데, 각 알고리즘이 가지고 있는 특성을 정확히 이해하고 특정 상황에 적용할 수 있는 능력을 가지고 있어야 한다. 즉, 세 가지 알고리즘 모두 알고 있어야 한다.
위 알고리즘은 어떤 단계에서의 최소 비용이나 그래프에서의 최단 거리를 찾을 때 주로 사용되고, 대부분의 문제도 이 두 유형안에서 나온다.
유니온 파인드
이번 하반기에 여러 코딩테스트를 응시해보며 세 번정도 쓴 것 같다.
내용도 크게 어렵지 않으므로 자신만의 find, merge function을 외우고 다니는 것도 좋은 방법이 될 수 있다.
유니온 파인드(Union Find)
설명 유니온 파인드는 집합의 표현을 빠르게 구현하는 알고리즘이다. 예를 들어보자. 사람 P1, P2, P3, P4가 있다. 각 사람은 자신의 소속집단 C1, C2, C3, C4에 가입되어 있다고 가정하자. 1. C3에 속한 P
seongmok.com
MST(Minimum Spanning Tree) - 크루스칼
MST를 구하기 위한 알고리즘은 대표적으로 크루스칼과 프림 알고리즘이 있다. 프림은 구현하기가 힘들어서 사용하지 않고, 실제로 몰라도 코딩테스트에서 문제될 것이 없다.
다만, 크루스칼 알고리즘은 알고 있어야 한다. 크루스칼 알고리즘을 구현하기 위해선 유니온파인드를 알고 있어야 한다.
크루스칼(Kruskal) 알고리즘
설명 크루스칼 알고리즘은 프림 알고리즘과 함께 그래프에서 MST(Minimum Spanning Tree)를 찾을 때 사용 되는 알고리즘이다. 알고리즘을 전개하는 과정에서 소속집단의 검색과 합병기능이 필요한데,
seongmok.com
이외에도 알아놓으면 좋은 알고리즘들
- LCA, Trie구조, KMP, 위상정렬, 임계경로, SCC, 세그먼트 트리(자료구조), 팬윅 트리(자료구조), SCC
정말 드문 케이스로 위 알고리즘이 코딩테스트에 나왔다면 운이 안좋았다고 생각하는게 편하다. 어차피 대부분의 사람들이 풀지 못했을 것. 또한, 위 알고리즘보다 더 높은 난이도로 측정되어 있는 알고리즘들은 코딩테스트에 절대 안나온다.
나는 쫄보라 만약의 상황에 대비해 위 알고리즘들을 학습해놓았지만, 코딩테스트에서 사용해본적은 단 한번도 없다.
위 알고리즘들을 모두 공부했다면
실랜디또는 골랜디를 하면 된다. 나는 최대한 하루에 한 문제씩 꾸준히 풀려고 노력했었고, 꽤 많은 문제들을 해결할 수 있었다.
보통 골드3정도의 문제를 문제없이 해결할 수 있다면 코딩테스트 탈락은 걱정하지 않아도 될 수준이라고 생각한다.
또한, 개인적인 생각으로 요즘 코딩테스트의 난이도가 점점 내려가고 있다고 생각하기 때문에 너무 걱정하지 않아도 된다.
골랜디를 마음껏 할 수 있는 수준이 된다면 자연스럽게 PS에 흥미를 가졌을 것이고 코딩테스트 전형은 곧 나의 무기가 될 수 있음을 알아야 한다. 실제로, 나는 코딩테스트 이후 꽤 어려번의 면접을 첫날 첫타임으로 봤었다. 면접 순서의 의미는 인사팀 이외에 아무도 알 수 없지만, 지극히 개인적인 일반화를 통해 분명 코딩테스트의 결과가 어떤 작용을 했을 것이라고 생각한다. 또한, 채용 프로세스가 허들식(앞 전형의 점수를 가지고 나아가는 식)이라면 코딩테스트에서 높은 점수를 받아 놓는 것이 큰 도움이 될 것이다.
종합
위 글을 읽었다면 느꼈을테지만 공부방식이 상당히 가늘고 길다. 나는 하루에 3문제씩 푸는 삶은 살고싶지 않았기에 최대한 하루에 한문제씩, 아무리 못해도 1주일에 5문제는 풀어야겠다고 다짐했었다.
그렇게 1년 반이 넘는 시간동안 백준에서만 600문제 정도를 해결했고, 나에게 코딩테스트 전형은 큰 무기가 될 수 있었다. 나는 말하는 감자이고, 심지어 3학년 2학기라는 다소 늦은 시기에 시작을 했음에도 불구하고 위 방법을 통해 나름 성장할 수 있었다.
이 글을 읽고 코딩테스트 준비를 시작하는 사람들이 있다면 가늘고 길게 공부하는 것을 추천한다. 그렇지 않으면 빠르게 지칠 수 있음에 주의하자.
아 그리고 위에서는 Solved.ac 의 문제 난이도에서만 티어를 언급했지만, 자신의 티어도 볼 수 있다. 롤 티어와 단계가 매우 흡사해서 쉽게 이해할 수 있다. 단순히 티어를 올리기 위해 공개된 해법을 복붙해서 제출하는 행위는 엄격히 금지되어 있고, 자신에게도 도움이 될 수 없다. 내가 생각할 때 티어값을 한다는 의미는 자신 티어보다 한단계 낮은 문제를 문제없이 풀 수 있어야 한다는 것이다. 예를 들어 나의 티어가 플래티넘3이라면 골드3정도 수준의 문제는 막힘없이 풀 수 있어야 한다.
이 글이 도움이 되었으면 좋겠다.