코딩테스트 준비하기

블로그를 봐도 각 알고리즘 개념이나 백준 문제들을 설명하는 경우는 많았는데 알고리즘 문제를 어떻게 받아들이고 접근하는지 또는 공부를 하는 게 좋은지에 관한 글은 없어서 글을 작성하게 되었다. 

 

나 또한 근본있게 공부를 한건 아니고 친구에게 기초를 배우고 친구와 같이 kks227 블로그를 참고하며 좁은 시야로 공부를 하였기 때문에 매우 주관적인 경험인걸 감안하고 들어주시면 좋을 것 같다.

 

기본적으로 알고리즘 문제는 2단계를 거쳐 문제를 해결하게 된다고 생각한다.

1.  문제가 요구하는 알고리즘 찾기
2.  알고리즘 구현하기

우선 알고리즘 찾기 과정은 지문 + 제한 조건(시간제한, 입력값의 범위)을 읽고 시간 복잡도를 고려한 알맞은 알고리즘을 생각하는 과정이다. 사실 해당 단계가 알고리즘 문제에서 가장 중요한 부분이고 구현은 별개의 중요도라고 생각한다. 문제를 똑바로 꼼꼼히 읽는 게 가장 중요하고(혼자 없는 조건을 만들거나 곡해하면 안 된다) 요구하는 제한 조건들을 인지한 뒤 가장 먼저 나이브 한 방법을 생각해본다. 일반적으로는 이 문제를 완전 탐색으로 풀면 어떻게 될지를 생각해본다. 그렇게 구하게 될 경우의 시간 복잡도를 생각하고 반복되거나 구간으로 표현되는 부분들을 보고 이미 알고 있는 알고리즘을 적용해서 시간 복잡도를 줄여간다. 이러기 위해선 나이브한 완탐을 짤 때도 구체적인 수도 코드를 적지는 않아도 대강 어떤 흐름으로 되겠다 정도는 정하면서 정리를 해야 한다. 그래서 나는 처음 알고리즘을 배울 때도 그렇고 지금 까지도 항상 종이와 펜을 가지고 그리고 쓰며 알고리즘 설계를 한다. 위의 내용이 사실 글로만 보면 와닿지 않으니 예시를 보자 

우선 문제를 읽어 본다. N 개의 집 좌표가 주어지고 C개의 공유기를 각각의 집에 설치 하는데 공유기 사이의 최소 거리를 최대로 하는 것이 과제인 것으로 보인다. 사실 감은 잘 오지 않으니 예제 입력을 우선 그려 보자

5개의 집이 정렬 되지 않은 상태로 주어 졌는데 필요하다면 정렬을 해도 좋을 것 같다. 예제에서는 3개의 공유기를 설치하라고 했으니 무작위로 설치를 해보자

위와 같이 1, 4, 8에 공유기를 설치할 경우 문제에서 요구하는 공유기간의 최소 거리가 3이 된다는 것을 확인하였다. 

그럼 이제 이문제를 가장 나이브한 방법으로 푼다면 어떻게 될까? 집 좌표의 범위가 1E9이므로 공유 기간  최소 간격은 아마 1E9  정도가 될 거라고 생각할 수 있다. (집이 총 2개고 양 끝에 있을 경우) 그러면 정답의 후보가 될 수 있는 범위는 1~1E9이고 범위에서 값을 하나 뽑아 공유기 최소 거리로 잡고 실제로 설치가 되는지 확인을 해보면 될 것 같다. 

그럼 최소거리를 S로 잡고 설치가 되는지 안되는지는 어떻게 알 수 있을까? S가 1이라 생각하고 다시 위 그림의 경우를 보자 우선 뭔가 첫번째 지점은 무조건 맨 좌측이나 맨 우측에 배치하는 게 좋을 것 같다. 지금 최소거리가 1이면 되니까 2에도 배치를 해도 될 것 같다. 그다음 지점은 4에 해도 거리가 2이니까 문제가 없다는 것을 확인하였다.

S= 1

S가 2일 경우도 한번 해보자 다시 맨 좌측에서 시작을 한다. 다음 지점을 찾는데 일단 2를 선택하면 거리가 1이 되어서 S보다 작아지게 된다. 그렇기 때문에 4에 하나를 설치해주고 다음 집인 8에도 설치를 하니 3개를 설치가 되긴 하였다.

S=2, 3

된 거 같기는 한데 최소 거리가 2가 아니라 3이긴 하다 물론 1에 있는 공유기를 2로 옮기면 최소 거리가 2가 되기는 하지만 굳이 1이 있는데 2에 설치를 할 필요는 없어 보인다. 방금 과정으로 S가 3 이어도 설치가 가능하다는 게 증명이 되었고 4일 때도 해보자 

S가 4이면 1에 하나를 설치하면 2나 4에 설치를 할 수 없고 8에 설치를 해야 한다. 8에 설치를 한다면 9에 설치를 할 수 없게 되고 결국 3개의 공유기를 설치 할 수 없게 된다는 사실을 알게 되었다. 당연히 2나 4에는 설치를 할 수 없는게 위에서 1번 점을 설치한 순간 2와 4에는 설치를 할수 없다는 것을 확인했었다 즉 공유기 설치는 탐욕 법과 마찬 가지로 설치된 집을 하나씩 보다가 이전 공유기와 간격이 S이상이 되면 체크를 하면서 본인의 우측 지점만 고려한다는 것을 알게 되었고 시간 복잡도는 집의 개수인 N이라는 것을 알게 되었다. 

S = 4

ㄴ지금 좌측부터 시작을 하였는데 우측인 9부터도 봐야 할까? 증명을 한다면 안 해도 되고 하지 못했다면 코드로 2번을 봐주면 된다. 그렇게 하더라도 시간 복잡도는 2*N일 것이다. 

 

그럼 이제 S를 1~1E9까지 가면서 N의 시간 동안 판별을 한 다변 1E9*N의 시간 복잡도를 가지게 된다. 어떻게 하면 시간 복잡도를 줄일 수 있을까? N을 줄이기는 힘들어 보이니 1E9을 줄일 방법을 고민을 해보자 

아까 예제를 그려 보면서 S가 1부터 3까지는 가능했고 4는 불가능하다는 것을 알았고 같은 이유로 4 이상인 값은 모두 불가능하다는 것을 알게 되었었다.

날카로운 2분탐색 각

위와 같이 정수인 index로 값이 OOOOOOXXXXXXXX나 XXXXXXXXOOOOOOOOOOO로 구성되는 경우에는 이분 탐색을 활용하면 된다는 것을 알 수 있다. 혹시 모른다면 한번 블로그 링크를 보자! 이분 탐색을 쓴다면 1E9의 시간 복잡도를 log 1E9으로 줄일 수 있고 약 30 정도가 된다는 것을 알 수 있다. 그렇다면 최종 시간 복잡도는 (log 1E9 )* N 이 되고 시간 복잡도 문제는 해결되었다고 볼 수 있다. 위와 같은 과정을 거치면서  어느 부분에 어떤 알고리즘이나 개념을 쓸지는 자연스럽게 정해 졌으니 구현하기를 하면 된다.  

 

개인적으로는 문제를 읽고 위와 같은 사고의 흐름을 거쳐서 어떤 알고리즘을 찾는 것이 알고리즘 문제의 가장 핵심이라고 생각하고 위와 같은 능력을 키우기 위해선 각 알고리즘을 정확히 이해를 해야 한다고 생각한다. 누군가 해당 알고리즘을 물어보더라도 설명을 할 수 있을 정도가 되어야 한다고 생각하고 그 알고리즘을 공부하는 방법은 여러 가지가 있긴 하다 책으로는 종 만북, 하얀 책, 초록 책 이 유명하고 어떤 책을 사도 사실은 대회용이기 때문에 책의 앞부분만 보면 충분하다 사실 너무 좋은 블로그들이 많아 개인적으로는 책을 구매하지 않아도 된다고 생각한다. 추천 블로그는 라이 블로그, 안즈 블로그를 추천한다. 두 블로그 모두 다양한 알고리즘을 포함하고 있고 추천 문제와 설명까지 포함되어 있어서 좋다.

 

코테 대비용으로 알아야 한다고 생각하는 알고리즘 공부 순서는 시간 복잡도 -> 완전 탐색 -> 그리디 -> 분할 정복 -> BFS, DFS (기초) -> DP(초급) -> BFS, DFS, 여러 그래프 자료구조 -> 최단 경로 -> 이분 탐색(조금 더 앞에 해도 됨) -> 슬라이딩 윈도, 투 포인터 -> 유니온 파인드, 최소 스패닝 트리(MST) -> 위상 정렬(잘 안 나오긴 하는데 알면 좋음) 여기까지가 기본직은 코테 대비용 알고리즘들이고 다른 IT기업보다 어려운 카카오의 경우 비트 마스킹 DP, 최소 공통 조상(LCA)까지 알면 좋을 것 같다.

 

나의 경우 개념의 흐름 자체가 완전 탐색에서 시간 복잡도를 줄이는 방법을 찾아서 나아가기 때문에 가장 중요한 것은 완전 탐색을 정확하게 짜고 그때의 시간 복잡도를 정확하게 계산해야 한다. 따라서 가장 먼저 시간 복잡도를 공부하고 완전 탐색을 공부해야 한다고 생각한다. 완전탐색 문제를 풀 때부터 코딩전 설계한 완탐의 시간 복잡도를 계산하면서 문제를 풀어보는 것이 좋다.  알고리즘 문제라는 게 정확하게 하나의 알고리즘을 묻는 게 아니라 dp+bfs , 그리디 + 이분 탐색과 같이 여러 알고리즘을 같이 사용하고 이자주 사용되는 개념인 그리디와 분할 정복을 먼저 익힌 뒤 기본 중의 기본인 BFS와 DFS를 익힌다. DFS와 BFS는 결국 탐색 방법 이기 때문에 이후에 나오는 개념들에도 많이 연관이 있어 정확하게 이해를 하고 넘어가는 게 좋다. 최단 경로의 경우 다익스트라, 벨만 포드, 플로이드 워셜 3가지가 있는데 본인이 시간이 없다면 다익스트라만 알고 있어도 좋지만 간혹 나머지 2개를 묻는 경우도 있으니 공부를 하고 3가지의 차이점을 유의 깊게 보는 것이 중요하다! 이후에 있는 것들은 죽 따라가면서 풀면 될 것 같다. 

 

또한 세그먼트 트리라는 알고리즘이 있는데 구간을 묻는 문제를 치트키 수준으로 쉽게 풀어 줘서 백준 기준 난이도가 골 1 ~ 플레 하위권 정도이지만 한번 고생해서 배워 두면 두고두고 도움이 된다. 실제로 이번 카카오 인턴 코테도 5문제 중에 2.7 솔이 컷이었고 이건 대부분의 사람들이 3번을 못 풀었다는 건데 해당 문제를 정해는 아니지만 세그먼트 트리를 쓰면 통과를 받을 수 있었다고 알고 있다. 

 

이론을 익혔다면 문제를 풀면서 구현 능력을 키울 단계이다. 나는 관련 문제를 보통 10문제씩 풀 기는 했지만 그냥 절대적으로 수를 정하고 푸는 것이 아니라 문제를 읽으면 해당 알고리즘이라는 감이 바로 올 때까지 풀었다. 위에도 말했지만 코테는 결국 문제를 읽고 어떤 알고리즘을 써야 하는지를 알아차리는 것이 핵심이기 때문에 단순히 문제를 읽고 알고리즘의 구현 실력을 기른다가 전부가 아니라 문제를 읽을 때 왜 이 문제가 해당 알고리즘을 요구하는 건 지를 생각하면서 읽으면 (연습과정이니 해당 문제가 어떤 알고리즘을 요구하는지 알고 있으니까) 실전에서 더 쉽게 알맞은 알고리즘을 찾을 수 있게 된다. 예를 들면 이분탐색의 경우 값의 범위가 10000000000000000정도가 되거나 최소를 최대로 한다 와 같은 조건이 있으면 이분탐색일 확률이 매우 높아 진다. 

 

또 다른 구현 능력을 키우는 핵심 꿀팁은 다른 사람의 코드를 보는 것이다. 보통 백준으로 공부를 할 것 같은데 숏 코딩이나 랭킹이 높은 사람의 코드를 보는 게 아닌 채점 현황을 가서 사용했던 언어들의 최근 언어들의 정답을 2~3개를 읽어보는 게 매우 큰 도움이 된다. 일반적으로 같은 문제 같은 알고리즘을 사용해서 문제를 풀었기 때문에 코드에서 느껴지는 점은 결국 구현 방법이다. 또한 내가 방금 해당 문제를 이해하고 풀었기 때문에 다른 사람의 코드를 훨씬 수월하게 읽을 수 있다. 

 

마지막으로 문제 하나를 언제까지 붙잡고 있어야 할까? 개인적으로 공부를 할 때는 진짜 답지도 안 보고 하루고 이틀이고 고민을 하였었다. 물론 이런 과정을 거치면서 실력 향상이 많이 되었고 엄청난 자기만족이 있었지만 가성비는 엄청나게 좋지 않았다. 그래서 개인적으로 최근 사용하는 방법은 1시간을 고민을 한다. 1시간도 너무 많은 거 아닌가?라고 생각을 할 수도 있지만 고민을 하는 것도 훈련을 해야 한다고 생각한다. 결국 문제를 푸는 이유는 코딩 테스트에서 좋은 성적을 얻기 위해서 인데 실전에서는 5문제를 던져주고 3시간 동안 풀라고 한다. 그럼 많은 사람들은 2번까지 1시간 에서 2시간 동안 풀고 3번 문제나 4번 문제에서 막히게 된다. 여기서 많은 사람들이 고민을 30분에서 1시간이 채 안되게 고민을 하다가 '아 나는 못 풀어 몰라!'라고 생각하고 테스트를 종료해 버리는데 나중에 다른 사람이 알려준 코드를 보고는 '아 왜 이걸 생각을 못했지!'라고 후회를 하게 된다. 물론 이걸 실력이 부족하다고 말할 수도 있지만 나는 고민을 하는 훈련이 되지 않아서라고 생각을 한다. 연습을 할 때 1시간이 넘도록 고민을 해서 문제를 풀어본 적이 없는데 실전에서 1시간 넘게 고민을 하는 걸 성공을 하고 알맞은 알고리즘을 찾으려고 하는 거는 욕심이라고 생각한다. 즉 연습을 할 때부터 고민을 하는 것도 연습을 해야 하고 그 시간은 자신이 코딩 테스트에서 실제로 경험하는 마지막 한 문제를 풀 때 평균적으로 남는 시간으로 하면 된다. 

 

진짜 마지막 내용이다. 위에서 우리가 지금까지 한 방법은 결국 고등학교 때 수학공부를 하면 정석을 펴서 해당 단원의 문제를 골라 푼거다. 하지만 실전에서는 이 문제가 어디 단원 문제인지를 가르쳐 주지 않았다. 따라서 문제가 어떤 알고리즘을 묻는지 모른체로 문제를 푸는 훈련을 해야 한다. 가장 좋은 방법은 열리는 코딩테스트를 일단 다 참가를 하는 것이다. 나도 20년 하반기 부터 21년 상반기 까지 열린 코테는 금융쪽을 제외하고 약속이 있는게 아니면 거의 다 지원을 했던 것 같고 코드포스나 릿코드 같은 온라인 대회도 열린다. (시간이 바쁜 취준생은 힘듦 ㅠ)아니면 또 다른 방법은  백준 그룹에서 연습을 활용하는 것이다.

 

실제 대회와 같이 어떤 유형의 문제인지를 알 수 없고 제한 시간을 두고 문제를 풀기 때문에 실전이나 대회와 유사한 경험을 백준에서 할 수 있다. 

 

국내에서 또한 문제를 풀 수 있는 사이트로는 백준과 프로그래머스 2개가 있는데 본인이 시간이 진짜 너무 없다면 바로 프로그래머스에서 하는걸 추천하고 여유가 있다면 백준에서 먼저 공부를 한 뒤에 프로그래머스에서 한번더 확인을 하는걸 추천한다. 같은 알고리즘이라도 프로그래머스의 경우 스타일이 조금 다르다고 생각한다.