개발자로 취업하기 - 코딩테스트 (심화편)

안녕하세요. 이전 포스팅에서는 코딩테스트 기초에 대해서 알아봤었습니다. 이번 포스팅에서는 코딩테스트 꿀팁과 더 추가로 공부하면 좋은 심화 알고리즘들에 대해 소개하겠습니다. 기초편을 안보신 분들은 아래 링크에서 확인해보시길 바랍니다.

 

https://nakco.tistory.com/entry/%EA%B0%9C%EB%B0%9C%EC%9E%90%EB%A1%9C-%EC%B7%A8%EC%97%85%ED%95%98%EA%B8%B0-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EA%B8%B0%EC%B4%88%ED%8E%B8

개발자로 취업하기 - 코딩테스트 (기초편)

 

프로그래머스 고득점 Kit을 전부 완료하였다면 이젠 실전 연습을 해야할 때입니다. 기업의 코딩테스트는 보틍 2~4시간 정도 주고, 4~7문제 정도를 풀어야합니다. 이때 중요한 점은, 부분점수는 아무 의미가 없다는 것입니다. 한 문제당 100점 or 0점이라고 생각하셔도 무방합니다. 보통 50%이상 맞추면 합격권이기 때문에, 선택과 집중을 잘하여 풀수 있는 문제를 완벽하게 푸는 것이 핵심입니다.

 

코딩테스트 전략

코딩테스트는 제한 시간이 있고, 빠르게 최대한 많은 문제를 풀어야 합니다. 하지만 그렇다고 조바심 내서 이문제 저문제 풀다보면 결국 풀 수 있는 문제도 못풀고 시간만 낭비하게 될 것입니다. 그렇다면 어떻게 전략을 짜야 할까요? 네, 바로 풀 수 있을 문제에 선택과 집중을 해야합니다. 어려운 문제에 더 높은 점수를 주는 기업도 있지만, 보통은 쉽든 어렵든 푼 문제 수로 갈리기 때문에, 내가 풀 수 있는 문제가 무엇인지 파악하는 것이 중요합니다.

 

1. 문제 파악하기

 문제를 읽으면서 어떤 알고리즘을 써야할지 먼저 알아내야합니다. 저희는 고득점 Kit를 푼 상태이기 때문에 해당 유형의 문제가 나오면 무조건 파악할 수 있습니다. 여러 코딩테스트를 봐보았을때 문제가 다 거기서 거기고, 그냥 내용만 살짝 바뀌는 정도였습니다. 따라서 내가 아는 유형인지 먼저 파악하고, 파악이 안될 시 우선 과감히 버리는 것을 추천드립니다. 그렇게 먼저 내가 아는 유형부터 문제를 풀도록 합니다. 

 

2. 문제 손으로 먼저 풀기

 알고리즘 문제를 풀 때 절대 문제를 읽으면서 바로 코딩해서는 안됩니다. 우선 문제를 모두 읽으면서 이해하고, 손으로 직접 풀어본 후, 그것을 코딩으로 옮기는 것이 순서입니다. 무작정 시작한다면 중간에 꼬여서 코드를 수정하고, 또 다시 문제를 읽고 예외를 발견하여 또 수정하고, 이러다 보면 코드도 더러워지고 나중엔 마구마구 꼬여버릴 수 있습니다. 제 경험상 다 이해하고 손으로 풀고, 코드로 옮기는 것이 훨씬 빨랐습니다.

 

3. 30분 내로 못풀면 넘어가기

 문제를 풀다보면, 분명 잘 푼거 같은데 정답이 아닌 경우가 있습니다. 이런 경우는 보통 3가지 이유로 나뉩니다.

 

(1). 내가 생각 못한 예외 상황이 있다.

(2). 아예 잘못된 알고리즘을 선택했다. (시간 복잡도를 고려 못했을 경우)

(3). 코드상 문법이 잘못된 부분이 있다. (Segmentation Fault, Runtime Error 등..)

 

어떤 이유든지 이러한 경우에는 우선 넘어가도록 합시다. 거의 다 풀었다고 생각하지만, 해당 문제만 붙잡고 있을 순 없는 노릇입니다. 넘어가서 다른 문제를 풀다보면 해결방안이 생각 날 수도 있고, 그때 돌아와서 풀는게 낫습니다. (2)번 같은 경우에는 코드를 싹 다 갈아 엎어야하는 문제가 있고, 또한 모르는 알고리즘이여서 원래부터 못푸는 문제였을 확률이 매우 높습니다. (3)번 또한 컴파일러를 보통 사용할 수 없기 때문에, 디버깅하는데 너무 많은 시간을 허비해야하기 때문에, 우선 풀 수 있는 다른 문제들로 넘어가고, 시간이 남거나 해결방안이 떠올랐을 때 돌아가도록 합시다. 시간 배분하는 것이 매우 중요합니다.

 

 

 

추가로 알아두면 좋은 알고리즘

  코딩테스트를 볼때 보통 맨 밑에 보면 조건이 있습니다. 데이터의 사이즈와, 시간 제한이 있는데, 저희가 사용하려는 알고리즘이 해당 제한 내에서 돌아갈 수 있는지 판단하는 것이 중요합니다. 계산해보고 안되는데 더 줄일 방법이 없는 경우에는 저희가 모르는 알고리즘이 있다는 뜻이겠죠!? 따라서 시간복잡도를 줄이는데 주로 사용되는 알고리즘들에 대해서 소개하겠습니다.

 

1. 이분 탐색

https://nakco.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89

알고리즘 - 이진 탐색(이분 탐색)

 

2. Union & Find

https://nakco.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Union-Find

알고리즘 - Union & Find

 

3. 누적합 (Prefix Sum)

https://nakco.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%88%84%EC%A0%81%ED%95%A9Prefix-Sum

알고리즘 - 누적합(Prefix Sum)

 

4. 크루스칼 알고리즘 (Kruskal)

https://nakco.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BCKruskal

알고리즘 - 크루스칼(Kruskal)

 

5. 다익스트라 (dijkstra)

https://nakco.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCdijkstra

알고리즘 - 다익스트라(dijkstra)

 

6. 인덱스 트리 (Index Tree)

https://nakco.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B8%EB%8D%B1%EC%8A%A4-%ED%8A%B8%EB%A6%ACIndex-Tree

알고리즘 - 인덱스 트리(Index Tree)

 

마무리

 저는 이러한 공부 방법으로 라인을 제외하고는 모든 기업의 코딩테스트에서 합격했습니다. 라인은 시간 분배를 못하고, 앞에 문제에서 끙끙대다가 풀 수 있는 문제도 못풀고, 시간분배를 못해 떨어졌다고 생각합니다. 여러분은 꼭 시간 분배를 잘 하시길 바랍니다! 제가 코딩테스트를 본 기업은 네이버, 카카오, 신한은행, 삼성전자, 네이버 클라우드 등이 있는데 나중에 시간이 된다면 각 기업의 코딩테스트에 대해 리뷰해보도록 하겠습니다. 오늘도 읽어주셔서 감사합니다. 개발자, 취준생 여러분 항상 응원하겠습니다.