Published 2020. 4. 27. 23:08

알고리즘 초보자, 어떻게 공부하면 좋을까?

📌 WorkOut

이전에 회사들이 왜 알고리즘 테스트를 시행하는가에 대해 제 생각을 적었습니다.

그렇다면 알고리즘에 대해 잘 모르는데 과연 어떻게 공부를 해야할까요?

제 생각으로 우선 본인이 어떤 상황인지에 따라 방법이 다르다고 생각합니다.

1. 알고리즘에 시간을 쓸 여유가 있는 사람, 초,중,고, 대1,2,3학년 등 공부할 시간적 여유가 있는 사람

2. 알고리즘에 시간을 쓸 여유가 없는 사람, 올해 대기업 공채 등 알고리즘 테스트를 보는 회사에 지원하나 시간이 없는 사람

## 공통적으로 필요한 사항

#### 구현 능력의 필요성

알고리즘에서 가장 중요한 기본기는 바로 "**구현 능력**"입니다. 내가 머릿속에서 생각한걸 코드로 구현을 할 줄 알아야합니다.

머리로는 이런 로직으로 하면 될 것 같은데, 그걸 코드화를 하지 못하면 그 문제는 못 풀기 때문입니다.

대기업이 아니더라도 중견이나 중소기업에서도 구현 능력은 테스트를 합니다. "퀵소팅, 병합정렬을 구현하시오" 라는 고리타분한 문제 같은 것들이 대표적입니다.

퀵소팅이 무엇인가요?

1. 특정 기준 값을 잡아 기준 값보다 작은 값들은 왼쪽, 큰 값들은 오른쪽에 집합시킨다.

2. 기준 값을 중심으로 2개로 집합을 분할합니다.

3. 분할된 집합의 크기가 1이하가 될때까지 반복합니다.

간단하게 설명하면 대충 이런 내용입니다. 그런데 테스트로 구현하라고 시키면 머리로는 이해하지만 막상 코딩을 어떻게 해야할지 모르겠다던가 한다면, 구현 능력을 기르셔야합니다.

알고리즘 테스트 등에서는 "와 이렇게까지 구현을 해야해?"라는 문제가 나올 수 있습니다.

삼*의 경우 제가 취준을 하던 시절에 2문제 중 1문제는 구현 문제이고, 나머지 1문제는 DP 혹은 BFS 혹은 백트래킹 중 나오는게 트랜드였습니다. (취준을 이제 안해서 최신 동향까진 모릅니다.)

신입을 채용하기 위함이지, 알고리즘 경진대회가 아니기 때문에, 굳이 엄청 어려운 알고리즘을 공부하실 필요는 없습니다.

구현 능력, 어떻게 늘릴 수 있나요? 그 답은 백준 사이트에서 알고리즘 분류 중 구현과 시뮬레이션이 해당하는 문제들입니다. 구현 문제와 시뮬레이션의 문제의 가장 큰 특징은, 내가 이 문제를 해결하기 위해서 어떤 알고리즘을 따로 생각 할 필요가 없다는 것입니다.

글을 잘 읽고 이해하여, 글이 하라는대로 조건에 맞춰서 코딩을 하여 결과를 출력하면 되는 문제입니다.

그렇기 때문에 알고리즘을 해보지 않은 분들이라면, 기본적으로 위의 문제들을 풀어보시면서 문제에 따라 그대로 코딩을 하는 연습을 하시는게 알고리즘 공부의 시작 단계입니다.

## 백준에서 문제 고르는 팁

이거는 저의 매우 주관적인 방식이라 안 따르셔도 상관은 없습니다. (그리고 모든 문제에 통용된다는건 아닙니다.)

백준에는 정말 많은 문제가 있습니다. 그리고 난이도가 천차만별이라서 도대체 내 상황에서 어떤 문제를 풀어야 할지 모르는 분들이 있을 수 있습니다.

알고리즘이라는게 정답이 안 뜨면 정말로 답답하고 화가 나기 때문에 너무 어렵지도, 너무 쉽지도 않게 문제들을 선정해야 합니다.

1. 제출수가 많은 것부터 풀기. 당연히 이미 많은 사람들이 쉬운 문제들은 많이 도전했습니다. 알고리즘 분류에서 이미 맞은사람, 제출수로 정렬이 되어있습니다.

2. 정답률이 50퍼 이상의 경우 초보자가 도전해보기 정 정말 좋은 문제입니다. 입문가한테 가장 좋은 문제들입니다.

3. 정답률 40퍼 ~ 50퍼의 경우, 정답률 50퍼의 문제들이 지루하다면 풀어보기 좋은 문제입니다. 알고리즘 테스트를 준비하는 분들은 이 정도는 풀어야합니다. 가아끔 예외 테스트 케이스 같은게 여러분을 괴롭 힐 수 있습니다.

이 문제들부터는 조금 머리를 쓰고 고민을 해야 정답이 뜹니다.

4. 정답률 30퍼 ~ 40퍼의 경우, 문제를 이해하고 그대로 구현을 했는데 예상치 못한 케이스로 인해 오답이 뜨거나 시간초과 혹 메모리 초과가 일어날 수 있습니다. 이제 효율에 대해서 고민을 하는 시점이 다가왔습니다.

지금의 로직으로는 택이 없으니 메모리적으로 혹은 속도적으로 성능 개선이 필요한 문제들입니다. 이 정도 문제들을 풀 수 있으면 알고리즘 테스트에서도 무난무난한 문제는 시간이 걸려서라도 풀 수 있습니다.

5. 제출 수가 많지만(최소 1500 이상) 정답률 20퍼 ~ 30퍼 이하인 경우, 4번과 비슷하지만 많은 사람들이 제출하고 틀리다가 정답률이 낮아진 케이스입니다. 난이도는 3번 혹은 4번이라고 추측됩니다. 풀어보셔도 좋습니다.

위의 수순에 따라서 문제들을 이것저것 골라 풀어보시며는 어느정도 감이 생겨서 자신의 수준에 맞아보이는 문제를 고르 실 수 있다고 생각합니다.

## 백준 풀어볼 문제 결정하기

저의 가장 추천드리는 알고리즘을 공부를 해본 적이 없다. 라는 분들의 경우 출력하는 법부터 하는 것을 추천드립니다.

본인이 어떤 언어를 할 줄 아는지, 어떤 언어를 쓸건지부터 정하는게 좋기 때문에 아래 링크의 초보용 튜토리얼 급 문제를 풀면서 익숙해 지도록 합니다.

https://www.acmicpc.net/problem/tag/%EC%B6%9C%EB%A0%A5

튜토리얼에 익숙해졌다면 이제 기본적인 구현 문제에 익숙해져야합니다. 구현 문제는 쉬운건 쉽지만 복잡한건 "이걸 이렇게까지 구현해야해?" 싶은 문제도 나올 수 있습니다. 예, 그리고 그렇게까지 구현해야 정답이 뜹니다. 구현 / 시뮬레이션을 먼저 최소 20~30 문제를 풀어봅니다.

구현 문제는 알고리즘을 준비하는 분이라면 뗄 수 없는 관계입니다. 구현은 많이 풀어도 나쁘지 않은 문제들입니다.

https://www.acmicpc.net/problem/tag/%EA%B5%AC%ED%98%84

https://www.acmicpc.net/problem/tag/%EC%8B%9C%EB%AE%AC%EB%A0%88%EC%9D%B4%EC%85%98

구현 문제에 익숙해졌으면 이제 구현 문제는 가끔씩 한 두 문제를 풀어주면서 사이드로 돌리고, 이제 알고리즘을 공부할 시간입니다.

어떤 알고리즘들을 공부해야 할까요?라고 물어본다면 저는 이렇게 대답을 할 것입니다.

1. 다이나믹 프로그래밍

2. BFS

3. DFS

4. 백트래킹

5. 그리디

6. 분할 정복

위의 알고리즘들의 특징이라고 한다면, **해당 알고리즘을 정확히 알고 있지는 못하더라도, 내가 열심히 생각하고 코딩을 하면 정답은 띄울 수 있다.** 라는 점입니다.

세그먼트 트리나, 네트워크 유량 등의 고급 알고리즘은 그 알고리즘 자체로도 구현하는데 시간이 많이 들고 그 구현한 알고리즘을 가지고 문제를 풀어야 해서 일반적으로 알고리즘 테스트에 적합하지 않다고 생각합니다. 그래서 잘 나오지도 않구요.

위의 여섯 알고리즘만 열심히 풀어도 알고리즘 테스트나 알고리즘 대회에서 문제를 그래도 몇 문제는 풀어볼 수 있는 수준이 될 수 있습니다. 좀 더 욕심이 있으시다면

6. 세그먼트 트리

7. 네트워크 유량

8. 이분 매칭

까지 공부를 해보시고 그 이후에는 스스로 방향성을 잡을 수 있다고 생각합니다.(사실 저도 저기서 뭘 더 공부해야 할지 모르겠습니다.)

***

## 알고리즘에 시간을 쓸 여유가 있는 경우 공부 방법

0. CS도 그렇고 어떤 공부던 원리를 공부하고 실전 예제에 적용하는 것이 가장 정석입니다. 그래서 시간적으로 여유가 있는 부분은 생각하는 습관과 그 생각을 구현하는 연습이 가장 중요합니다.

1. 공부하고자 하는 알고리즘을 선택합니다. 알고리즘에 대해서 검색하고 해당 알고리즘을 공부하고 알고리즘이 어떤 용도 및 목적으로 사용되는지 이해를 합니다.(해당 문제에 대한 답을 보라는게 아닙니다.)

2. 알고리즘에 대해서 이 알고리즘이 어떤 원리인지를 충분히 이해했다고 한다면 이제 문제를 풀 시간입니다. 문제를 읽고 본인만의 생각 혹은 해당 문제에 해당하는 알고리즘을 토대로 답을 구현합니다. 이 때 문제에 대해 해결 방법을 생각이 날때까지 생각해봅니다.

이 때, 시간이 얼마나 걸려도 상관 없습니다. 저의 경우 어렵다 생각한 문제는 하루에 몇시간씩 생각해보며 1주일동안 고민을 해본 적도 있습니다. 중요한 것은 해당 카테고리의 알고리즘 기반으로도 좋고 나만의 방법으로도 좋고, 아무 방법으로 문제에 대한 해결 로직을 만들었는가입니다. 이 습관이 필수적입니다.

3. 해결 로직(알고리즘)을 만들고 구현을 하고 제출을 합니다.

4.1 정답이 뜨는 경우, 다른 사람들의 코드를 확인하며 나랑 어떤게 다른지, 어떤 방식으로 풀었는지 코드를 살펴봅니다. 혹은 해당 문제를 구글에 검색해서 잘 정리한 글들을 봐도 좋습니다.

이 과정을 통해서 이렇게도 생각 할 수 있구나를 통해 다른 관점에서 문제를 보는 법을 기를 수 있습니다.

4.2 오답 뜬다면 예외 케이스에 대한 처리를 하지 않거나 생각한 알고리즘이 틀렸다는 것입니다. 예외처리를 해보고 그래도 오답이 뜨는 경우, 해당 알고리즘을 고려하지 않고 내 생각대로 구현을 해서 문제가 된 부분이 있을 수 있습니다.

해당 알고리즘으로 문제를 풀어보려고 다시 생각을 하고 구현을 합니다.

정말 안 풀리는 경우

5. 한 문제를 붙들고 있을 때 물리적인 시간으로 최소 12시간은 투자해도 좋다고 저는 생각합니다. 심지어 저는 어떤 문제들을 1주일 ~ 2주일 고민 한 적도 있고요. 개인 성향에 따라 시간을 줄여도 괜찮습니다, 내가 고민을 많이 할 수록, 정 안되어 다른 사람의 답을 보더라도 확 와닿는게 있고, 코딩 센스라던가 알고리즘 센스라던가 받아들이는 부분이 더 많아집니다.

***

## 알고리즘에 시간을 쓸 여유가 그리 없는 경우 공부 방법으로

상황에 따라 사람은 유도리가 필요합니다.

저는 고등학생 때 영어를 정말로 못 했습니다. 모의고사를 보면 언제나 4-5등급이 었구요. 제가 재수해서 수능을 볼 때 EBS 연계로 EBS 책에서 70퍼센튼가 문제를 낸 적이 있습니다. 지금도 그런지는 모르겠네요

그래서 저는 이 때 EBS 영어 문제집들을 사서 문제를 한 문제도 풀지 않고, 해설만 보는 방법을 선택했습니다. 한국어로 보는 것은 영어보단 훨씬 쉬우니까요. 반복적으로 봐서 첫 문장만 나와도 해당 해설이 생각날 정도로만 반복해서 보는 전략으로 수능을 치뤘습니다.

그 결과 3등급까지 올랐던 경험이 있네요.

위의 여유가 있는 분들과 다르게 우리는 단 시간안에 알고리즘을 빠르게 체득해야합니다. 그래서 위의 방식은 정말 느긋하지만, 우리는 속성 강의가 필요합니다.

1. 구현 문제들은 어쩔 수 없습니다. 계속 풀어주면서 구현 실력을 올려야합니다.

2. 구현 실력을 올리면서 동시에 제가 위에 나열한 필수 알고리즘 6가지의 분류 탭에서 문제들을 선정합니다. 문제를 보고 어떤 식으로 풀어야 할지, 1시간 정도는 고민을 해봅니다.

3. 고민을 해보고 어떤 식으로 풀지 떠올랐다면, 코딩을 하고 정답을 제출합니다.

4. 오답이 뜨는 경우, 수정을 해가며 20번 정도는 제출을 합니다.(제출하는 것에도 익숙해져야합니다.)

5. 3번에서 생각이 안 떠오르는 경우, 4번에서 결국 끝내 오답이 뜨는 경우, 구글에서 해당 문제를 검색하고 다른 사람들의 해결법을 봅니다.

6.1 나와 같은 알고리즘을 썻다면 구현의 어떤 점이 다른지 확인을 합니다. 예외처리 부분은 어떻게 처리했는지 코드를 살펴봅니다.

6.2 나와 다른 알고리즘을 썻다면 이 사람이 어떻게 생각하고 이런식으로 했는지를 확인합니다. 그리고 코드를 보고 어떻게 문제를 풀었는지 확인을 합니다.

7. 다른 사람의 코드를 일일히 따라 칩니다. 그러면서 이 사람이 이 줄에서 어떤 의도로 이 코드를 넣었는지 분석 및 파악합니다. 이것이 안되면 정답을 띄워도 의미가 없습니다.

8. 위의 방법을 6가지 알고리즘에서 각각 최소 20문제씩은 풀어봅니다. 테스트를 볼 때는 해답을 알려줄 사람이 없습니다. 내가 문제들을 최대한 많이 풀어보면서 다른 사람들의 센스를 빨리 배우고 따라 할 수준이 되어야합니다.

세상에 정답은 없습니다. 학생 때도 누군가에겐 학원이, 누군가에겐 과외가, 누군가에겐 온라인 강의가 더 잘 맞습니다. 자신에게 맞는 방법 잘 찾아서 잘 공부하시길 바랍니다.