🧑‍💻 개발자로 취업하기 위한 알고리즘 공부법 1강 코딩테스트

1강보다 2강 3강이 중요하기 때문에 적어도 2강까지 꼭 봐주세요 !!

 

본 강의는 알고리즘 자체를 가르쳐 주는 것이 아니라 혼자 공부를 어떻게 하셔야 하는지 모르는 분들을 위해 공부 하는 법을 가르쳐 주는 강의 입니다.

​

내가 개발자로 취업을 해야지 라고 생각을 하시면 이브이 마냥 선택 할 수 있는 길은 엄청 많고 (FE, BE, And, IOS, DE, ML/AI 등등) 회사들 또한 매우 많습니다. (대기업 + 네카라쿠배당토 + 많은 스타텁) 하지만 어떤 직무와 회사를 고르셔도 만나게 되는 관문이 서류의 연장선인 코딩 테스트 이고 비 전공자 분들이 겪으시는 장 큰 벽도 바로 여기 입니다!

일반적인 IT기업 취업 과정

코딩테스트 : 취업을 할 때 일반적으로 서류 다음에 있는 시험, 코테라고 많이 부름

알고리즘 : 코딩테스트를 풀기 위한 개념

---

기업들은 왜 코테 볼까요?

현업에 가면 알고리즘은 쓸모가 없다! 공부하는게 시간 아깝다!

많은 취준생 현업에서 일하시는 분들

저도 어느 정도 부분적으로는 동의 하지만 코테를 위한 알고리즘 공부에 분명한 장점은 존재 합니다.

​

장점

- 반복적인 실패의 경험 : 디버깅(오류가 발생했을 떄 추적하는 과정)을 연습, 멘탈이 수련됨

- 복합적인 경험 : 글을 읽고 이해하근 과정, 문제를 읽고 코드로 옮기기 전 설계하는 경험, 본인 언어에 능숙해 지는 과정 , 여러 알고리즘을 공부하고 학습하는 경험

​

그리고 동의를 하시지 않을 수도 있겠지만 코딩 테스트의 허들을 넘는것은 생각보다 어렵지 않습니다. 짧으면 2~3달 길어도 1년이면 충분합니다. 그렇다면 많은 분들이 왜 그렇게 고생을 하고 스트레스를 받으실까요?

​

1. 취업 시즌에 서류를 내고 너무 급하게 공부를 하려고 한다.

2. 길게 공부를 했지만 공부 방법이 잘못 되었다. (개인적인 생각)

1번은 시간 문제상 어쩔 수 없지만 2번은 생각보다 많이 발생하고 가장 안타까운 상황입니다. 본인이 노력을 하지 않은 것도 아닌데 어떻게 공부를 해야하는지를 몰라서 시간을 효율적으로 쓰지 않은 것이니까요.

​

잘못된 공부법

아래 내용 들 중 하나라도 공감이 되시면 잘못된 공부법을 하셨다고 생각하고 이후에 진행될 글을 보시면 도움이 되실거라고 생각합니다!

​

1. 100문제 이상을 풀었느데 코테가 아직 어렵다.

2. 코드를 제출 하였을 때 틀렸습니다, 시간초과 가 많이 나온다.

3. 문제를 풀기는 하는데 어떤 알고리즘을 써서 푼지 잘 모르겠다.

4. 혼자 공부할 때(백준, 프로그래머스)는 문제가 잘 풀리는데 실전(코테)만 가면 죽을 쑨다.

5. 문제를 읽어도 도대체 어떻게 풀어야 하는지를 모르겠다. (코테가 끝나고 다른 사람 풀이를 보면 아! 풀수 있었던건데 한다)

​

알고리즘 문제를 풀때 겪는 과정들을 통해서 위의 문제들이 왜 발생 하는지를 알아보도록 하겠습니다.

​

지문과 제한 조건(시간제한, 입력값의 범위)를 읽고 어떤 알고리즘을 써야 할지 방향을 잡고 설계를 종이와 펜으로 한 후 코드를 치게 됩니다.

제한 조건(시간제한, 입력값의 범위)를 읽고 어떤 알고리즘을 찾아야 하는지를 학습을 하지 않았다면 1,3,4,5의 문제들을 경험 하고 설계를 하지 않으신다면 1,2,3의 문제를 겪으시게 됩니다.

---

문제가 요구하는 알고리즘 찾기

​

지문을 읽고 설계를 하는게 중요하다는것을 알게 되었는데 이러한 과정이 어떻게 일어나는지 감이 안오시는 분들이 많을 겁니다. 지문을 보고 어떤 알고리즘을 써야 하는지 찾아 가는 과정을 먼저 살펴 보겠습니다.

아직 모르시는 단어나 내용이 나올 수 있는데 전체적인 흐름을 따라가본다고 생각하시면 됩니다.

​

예시 문제 :  https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

​

​

문제를 천천히 읽어봅니다. N개의 좌표가 있고 C개의 공유기를 각각의 집에 설치하는데 공유기 사이의 최소 거리를 최대로 하는것이 목표입니다. 한글을 읽었는데 이해가 안되고 감도 안온다면 예제 입력을 그려봐야 합니다.

예제

5개의 집 입력이 정렬되지 않은 상태로 주어 지는데 필요하다면 정렬을 하는것이 좋아 보입니다.

예제에서는 3개의 공유기를 설치하라고 했는데 무작위로 설치를 해봅니다.

위와 같이 1, 4, 8에 공유기를 설치할 경우 문제에서 요구하는 공유기간의 거리가 3, 4 로 2개가 나오게 되고 최소 거리가 3이 된다는 것을 확인할 수 있습니다.

​

이 문제를 가장 나이브한 방법으로 푼다면 어떻게 될까요?

집 좌표의 범위가 1E9이므로 공유 기간 최대 간격은 아마 1E9 정도가 될 거라고 생각할 수 있습니다. (집이 총 2개고 양 끝에 있을 경우)

그러면 정답의 후보가 될 수 있는 범위는 1~1E9이고 범위에서 값을 하나 뽑아 공유기 최소 거리로 잡고 실제로 설치가 되는지 확인을 해보면 될 것 같다. (이해가 잘 안가신다면 끝까지 읽어보시고 다시 읽어보세요!)

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

S= 1

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

S = 3

된 거 같기는 한데 S(최소 거리)가 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

이제 우리는 S를 고정 했을 때 원하는 수의 공유기를 설치 할 수 있게 되었습니다. 그럼 이제 S를 1~1E9까지 가면서 N의 시간 동안 판별을 하면 1E9 * N의 시간 복잡도를 가지게 된다. 어떻게 하면 시간 복잡도를 줄일 수 있을까요? N을 줄이기는 힘들어 보이니 1E9을 줄일 방법을 고민을 해봐야 합니다. 아까 예제를 그려 보면서 S가 1부터 3까지는 가능했고 4는 불가능하다는 것을 알았고 같은 이유로 4 이상인 값은 모두 불가능하다는 것을 알게 되었습니다.

위와 같이 정수인 index로 값이 OOOOOOXXXXXXXX나 XXXXXXXXOOOOOOOOOOO로 구성되는 경우에는 이분 탐색을 활용하면 된다는 것을 알 수 있습니다.(지금 몰라도 됩니다!) 이분 탐색을 쓴다면 1E9의 시간 복잡도를 log 1E9으로 줄일 수 있고 약 30 정도가 된다는 것을 알 수 있습니다. 그렇다면 최종 시간 복잡도는 (log 1E9 )* N 이 되고 시간 복잡도 문제는 해결되었다고 볼 수 있습니다.

위와 같은 과정을 거치면서 어느 부분에 어떤 알고리즘이나 개념을 쓸지는 자연스럽게 정해 졌으니 구현하기를 하면됩니다.

---

문제를 읽고 위와 같은 사고의 흐름을 거쳐서 어떤 알고리즘을 사용해야 하는지를 찾는것이 코뎅테스트의 가장 핵심이라고 생각하고 위와 같은 능력을 키우기 위해서는 알고리즘을 정확하게 이해 해야 합니다.

​이전에 작성 했던 글을 더 자세하게 다룬다고 보시면 됩니다 .