알고리즘 공부순서

 

 

어떤 분야이든지 간에 공부를 잘하는 방법은 '공부하는 법에 대한 정보를 먼저 수집하는 것'으로부터 시작하여야 한다.

 

<plzrun님의 시행착오>

- 친구가 여름방학 때 BOJ에서 코딩 하는 것을 보면서 Problem Solving 분야에 대한 흥미가 생김.

- 그래서 BOJ를 풀어보려 했는데 스스로 풀 수 있는 문제가 거의 없었음.

- 그 후 친구가 종만북(알고리즘 문제해결전략)을 추천해줌.

- 어려워서 하루에 3~4페이지를 볼까말까한 상황이라 진도가 나가지 않음.

- 이렇게 26살이 다 지나가버렸다. 취업준비든 대학원준비든 해야했지만 아무것도 하지 않았다.

- 그러다 다시 공부를 시도했고 27살이 되던해 2월부터 백준 오프라인 기초 강의를 듣기 시작했다. (1주일, 3시간*4회 강의 33만원)

- 거기서 이런말을 듣게된다. "ACM-ICPC(ACM 대학생 프로그래밍 경시대회) 를 준비하는 사람들은 밥만먹고 하루 10문제 이상씩 푼다."

- 자신의 수준이 형편없음을 다시 깨닫게 되었다. 

- 그래서 결심했다. 강의를 듣는 2주 시간동안 그 안에서 가장 문제를 많이 풀어본 사람이 되자고.

- 당시 약 60문제 정도를 풀었으며, 그 때 1등이었던 사람은 250문제 정도를 풀었다.

- 이 이후부터는 눈만 뜨면 하루종일 문제를 풀었고, 한달 내내 이런 생활을 했다.

- BOJ랭킹을 수시로 확인했는데, 강의를 듣는 사람들 중에 누군가가 어떤 문제를 제출했으면 자려다가도 꼭 한문제를 더 풀었다.

- 쉬운문제가 참 많았지만 하루에 5~10문제 정도씩 풀었던 것 같다.

- 이렇게 400문제가 넘어가면서 강의를 듣는 그룹내에서 제일 많은 문제를 푼 사람이 되었다.

- 잠은 하루에 4시간 정도 잤던거 같다.

- 이 때 쯤에 강의를 듣는 사람들 중 같이 스터디할 사람들을 모았다.

- 강의가 마무리된 뒤, BOJ 슬랙 안에서 private channel을 파고 여기서 스터디하는 사람들과 같이 계속해서 문제를 풀었다.

- 그리고 27살의 여름이 찾아왔고, 친구랑 종만북 2권을 다 보는 것을 목표로 공부하기 시작했다.

- 최종목표는 ACM-ICPC 본선에서 괜찮은 place를 받는 것이었음. 이렇게 2권을 보는데 2달 반이 걸렸다.

- 백준 기초 강의를 안들었다면 절대 종만북을 다 못봤을 것이다.

- 이후에 ACM 예선을 봤는데 보기좋게 예선탈락.

- 이 때 심정은 말로 표현할 수 없었다. 취업준비도 안되어있고, 대학원 준비도 안되어있는 상태였기 때문이다.

- 그런데, 한달이 지난뒤 취업을 하게 되었다. 

- 비록 지금까지 공부한 알고리즘이 대회에서는 빛을 발하지 못하였지만, 취업준비가 되어있던 것이다.

- 이 후 인생 참 살만하다고 느낀다.

 

<plzrun님의 추천 공부법, 2가지 중 택일>

* 최소 준비기간 6개월 필요.

* 백준님은 모르는 문제가 있으면 2시간을 넘기지 말라고 했는데, 이런 기초적인 문제들은 1시간을 넘길 필요가 없다.

- PS를 처음 접하는 사람들이 하는 가장 큰 실수가 모르는 문제를 하루종일 붙들고 있는 경우인데, 이는 미련한 짓이다.

- 이건 마치 덧셈, 곱셈 정도만 아는 상태에서 미적 문제를 푸려는 시도와 같을지도 모른다.

- 그러니 1시간이 넘으면 답을 바로 바로 찾아봐라. 특히, 이 문제들은 정말 기초 문제들이라 구글이나 네이버에 검색시 자세한 설명과 코드가 넘쳐난다.

- 반드시 1시간이 넘어가면 풀던 행위를 멈추고, AC받은 코드를 찾아봐라(설명이 달려있는 코드를 읽자)

- 한 문제 가지고 며칠씩 씨름하고 풀어봐야, 끝까지 풀지 못 할 수도 있을 뿐더러 아주 비효율적인 방법으로 푸는 경우도 있을 거다.

- 이럴 바에야 문제의 답을 빨리 확인하고 이와 유사한 문제들을 여러개 풀어재끼는 것이 아주 아주 현명한 방법이다.

 

선택1. 오프라인 혹은 온라인 강의활용

- 뭘 알고 뭘 모르는지 알려면 먼저 알고리즘의 숲을 봐야한다. 알고리즘 전체에 대한 목록이 어떤게 있는지 크게 살펴봐야 한다. 여기까지가 기초다.

- 이를 위해 코드플러스의 백준 기초, 중급1, 중급2 부분을 추천한다. 여기까지 2달정도 소요된다.

- 여기까지 하면 종만북도 더욱 쉽게 읽혀지고, 스스로 공부하는데 무리가 없게 된다.

- 알고스팟

- 노란책

 

선택2. 강의가 싫은 경우 아래의 것들을 순서대로 풀자.

* BOJ에서 입출력 ~ 분할정복 소요기간 2주

* BOJ에서 그리디 ~ 완전탐색 소요기간 2주

  (입출력~ 완전탐색을 통틀어 1달안에 끝내는 것을 목표로 해라. PS는 단기간에 해야 얻는게 많기 때문)

* 마지막으로 종만북 소요기간 2달 반

  (1권의 뒷부분인 수치해석부터 읽는 것을 추천한다. 이렇게 2권을 본 뒤 1권을 볼것을 추천. 기하부분은 skip할것. 어차피 문제 출제가 잘 안되기 때문)

* 알고스팟 문데들 다 풀어봐야 한다.

* 노란책을 봐라. 전체적으로 책이 매우 얇으면서도 있을건 다있다.(종만북에는 없는것도 있고, 설명이 부족한 것도 있다. 그 부족한 부분을 채워준다는 느낌이다.) https://book.naver.com/bookdb/book_detail.nhn?bid=6750543

* 종만북의 기하랑 DP최적화 부분을 보지 못한 상태이고, 노란책의 반 정도 밖에 안본 상태이다. 이 상태에서 삼성전자를 합격.

 

@ 입출력

- 입출력 문제들을 풀 때 10분이상 이 문제를 붙들고 있는 경우, 이건 입출력에서 뭔가 모르는 부분이 있다는 뜻이다.
- 그러므로 이전 질문들을 무조건 찾아보고 다른 사람이 푼 코드를 반드시 봐야한다. 

- 코드 길이를 줄이려고 이상하게 짧은 코드들로 된 것들도 많은데, 그런건 보지말고 랭킹 100위권 안에 드는 사람들 중 인덴트 멀쩡한 코드를 보면 된다. 

2557, 1000, 2558, 10950, 10951, 10952, 10953, 11021, 11022, 11718, 11719, 11720, 11721, 2741, 2742, 2739, 1924, 8393, 10818, 2438, 2439, 2440, 2441, 2442, 2445, 2522, 2446, 10991, 10992

@ DP

1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

@ 그다음

2751, 11650, 11651, 10814, 10825, 10989, 11652, 11004, 10828, 9012, 10799, 10845, 10866, 10808, 10809, 10820, 2743, 11655, 10824, 11656, 1406, 1158, 1168, 10430, 2609, 1934, 1850, 9613, 11005, 2745, 1373, 1212, 2089, 11576, 1978, 1929, 6588, 11653, 10872, 1676, 2004

 

@ 그래프(BFS, DFS)

1260, 11724, 1707, 10451, 2331, 9466, 2667, 4963, 7576, 2178, 2146, 1991, 11725, 1167, 1967

 

@ 이분탐색/삼분탐색 

1654, 2805, 2110, 10815, 10816, 11662

 

@ 분할정복

- DP랑 거의 똑같은데, 부분문제의 답을 DP 테이블에 저장할 필요가 없는 부분이 DP랑 다른 점이다.

11728, 1780, 11729, 1992, 2447, 2448, 1517, 2261

 

@ 그리디

11047, 2875, 10610, 1783, 1931, 11399, 2873, 1744

 

@ 완전탐색

1476, 1107, 1451, 9095, 10819, 10971, 1697, 1963, 9019, 1525, 2251, 2186, 3108, 5014, 1759, 2580, 1987, 6603, 1182, 2003, 1806, 1644, 1261, 1208, 7453, 2632, 2143

 

 

<출처>

https://plzrun.tistory.com/entry/PS%EA%B3%B5%EB%B6%80%EB%A5%BC-%ED%95%98%EB%A9%B4%EC%84%9C-%EC%A2%8C%EC%A0%88%EA%B0%90%EC%9D%84-%EB%8A%90%EB%82%80-%EB%B6%84%EB%93%A4%EC%9D%B4-%EC%9D%BD%EC%96%B4%EB%B4%A4%EC%9C%BC%EB%A9%B4-%ED%95%98%EB%8A%94-%EB%82%98%EC%9D%98-2016%EB%85%84

 

https://plzrun.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4PS-%EC%8B%9C%EC%9E%91%ED%95%98%EA%B8%B0