초급-중급 알고리즘 스터디 커리큘럼 추천 (3개월)

 

막학기에 알고리즘 스터디를 하고 싶어서 스터디를 구했..는데 이번에도 내가 팀장을 맡아서 직접 커리큘럼을 짜게 됐다. 스터디를 처음 하시는 분들도 계셔서 초급 수준으로 스터디를 정했고, 후반에는 나도 잘 배울 수 있는 기회가 됐다. 혼자라면 골고루 공부하지 않았을 텐데 스터디를 하니 억지로라도 여러 분야를 고루 공부하고 풀어볼 수 있어서 좋은 기회였다.

이제 새학기라 알고리즘 스터디를 하려는 학생 분들이 많을 텐데 내가 했던 스터디 커리큘럼과 문제들을 한 번 살펴보면 스터디 커리큘럼을 짜는 데 도움이 될 거라고 생각한다. 이런 글 사실 대회 수상자나 백준 루비 이런 사람들이 써야 될 거 같긴 한데, 오히려 신참에서 갓 벗어난 내가 쓰는 게 참신(?)하고 좀 더 현실성 있는 글이 될 수도 있을 것 같다는 생각에 쓴다. 왜냐하면 나는 정말 오랫동안 코테 준비를 위한 문제 풀이를 피해왔고 4학년 마지막 여름방학, 그것도 8월이 되어서야 문풀을 시작했기 때문이다. 이 글은 어떻게 해야 목표 달성을 위한 고통을 최소로 줄이는 깔끔한 학습을 할 수 있을지에 대한 거듭된 생각과 계획의 산물이다. 

특히 이 글을 보는 여러분이 컴퓨터공학 계열이거나 좀 번듯한 테크 회사에 취직하고 싶어하는 3, 4학년이라면 바로 지금이 공부를 시작하고 사람들을 모아 스터디를 준비하기 좋은 시기라고 말씀드리고 싶다.

참고로 우리 알고리즘 스터디는 언어가 파이썬이었다. 이게 딱히 커리큘럼 짜는 데 영향을 미치지는 않을 텐데 혹시 하고 알린다.

시간 없으면 그냥 빨간 글씨 나올 때까지 스크롤해서 거기서 보면 된다.

 

 

0. 우린 왜 알고리즘 문제를 풀어야 할까?

우리가 가고 싶어하는 네카라쿠배당토는 알고리즘 테스트(이하 코테) 전형이 있으며, 이 전형을 거치고 몇 가지 테스트를 더 거쳐야 입사를 하게 된다. 또한 4대 SI 회사들 역시 코테 전형이 있고 이것을 통과해야 한다. 

쉽게 말하면 우리가 챙기고 싶어하는 높은 연봉과 처우 및 가장 중요한 일과 동료의 퀄리티를 높이기 위해서는 코테를 보는 회사를 가는 게 좋다. 그렇기 때문에 코테를 준비해야 한다. 지금으로서는 딱히 다른 대안이 없다. 모 회사 수시 채용 같은 경우에는 과제 전형을 보기도 한다는데 대부분은 코테를 본다. (솔직히 난 과제 전형이 확대되어야 한다는 입장이다)

그래서 코테 준비를 위해 어떤 문제를 얼마나 많이 풀어야 하는가, 하면 누군가 적었듯 최소 백준 실버 3~골드 1 티어 수준의 문제를 200개 이상 풀면 되는 것 같다. 백준 공개 문제집에 삼성 SW 역량 테스트 기출 문제집이 있는데 여길 보면 거의 골드 1 티어 아래에서 문제들이 정리된다. 쉽게 말해 이 정도 풀 수 있으면 코테는 통과할 수 있는 정도라는 뜻이다. (물론 카카오는 좀 다르다. 카카오 난이도는... 절레절레) 혹시 모르는 사람을 위해 말하자면 티어는 solved.ac에 백준 계정 연동하면 볼 수 있으니 참고하시길 바란다.

그런데 잠깐, 이 말이 "당신의 계정은 무조건 실버 3 이상으로 채우시오. 그 이하는 수치다" 이런 뜻이 아니다. 내 말은 "코테 준비를 위해서는" 저 정도 난이도의 양질의 문제를 충분히 푸는 것이 좋을 것 같다는 이야기다. 나는 브론즈 문제를 되게 많이 풀었다. 코딩테스트를 위한 문제 풀이를 처음 시작한다면 일단 재미를 붙이고 습관을 들여서 포기하지 않는 게 제일 중요하기 때문에 처음에는 아무거나 쉬운 문제를 푸는 걸 추천한다. 나도 저대로 실천하고 있다. 

 

solved.ac 이건 반드시 쓰시기 바란다. 백준 문제 대부분의 난이도를 매겨 놓고 자기 티어도 볼 수 있는 사이트인데, 여기서 자기 티어 올라가는 재미로 문제 푸는 사람(이를테면 나)도 있고, 태그별로 모아놔서 좋은 문제를 골라보기도 쉬운 사이트이다. 초심자들은 어떤 문제가 자기가 풀 수 있는 문제인지 구별하기 어렵기 때문에 꼭!! 연동하시길 바란다.

solved.ac

 

 

1. 스터디 구성방식

우리는 2시간 동안 스터디를 하는 학교 프로그램을 하고 있어서 2시간에 맞춰서 스터디를 구성했다.

처음 1시간 동안은 인당 7분 정도 지난주에 맡은 문제 풀이 방식을 설명하고, 문제 풀이 방식의 공간 시간복잡도를 설명한다. 이 때 본인의 코드보다 더 좋은 코드를 찾았을 경우 개선점과 함께 소개해도 무방하다. (+3분 질의응답 후 5명이 순서대로 설명한 다음 10분 휴식.)

이렇게 남들 앞에서 자기 코드를 설명하는 이유는 동기 부여를 위해서이다. 사람은 남들 앞에서 뭔가를 설명하거나 해야 할 때는 특별히 더 열심히 한다. 위신(?)을 지키기 위해서, 망신당하지 않기 위해 열심히 준비하기 때문에 자기가 푼 문제는 정말 잘 설명할 수 있게 된다. 여기에 바로바로 질문과 답변을 할 수 있다면 금상첨화이다. 그러려면 남들도 똑같은 문제를 풀어와야 해서, 발표를 준비하는 문제는 모두가 다 똑같이 푼 문제로 고르는 것이 좋으나 오로지 화이트보드 코딩처럼 발표를 위한 발표라면 그냥 자기가 개인적으로 푼 문제를 발표해도 괜찮다고 생각한다.

다음 1시간은 새로운 알고리즘과 뼈대 코드 공부를 30~40분 정도 한다. 이 때 발표 자료는 최소 하루 전에 만들어서 팀원들이 보고 예습할 수 있는 환경을 조성하는 것이 좋다. 그리고 진짜 기본만 알면 그냥 풀리는 문제를 하나 풀어보는데, 상황에 따라 알고리즘과 뼈대 코드 설명이 오래 걸리면 이건 과제로 넘길 수 있다.

마지막으로 과제를 할당하고 마무리하는 데 5분 정도 쓰면 그 날 스터디는 끝이다.

 

그런데 막상 진행해 보니 PT하듯이 하는 게 잘 안 됐고 실제로 30분 정도면 5명이 다 돌아가면서 설명할 수 있어서 안 쉬고 바로 코드 공부로 들어가게 됐다. 중급 스터디에서는 그 점이 아쉬워서, 온전히 발표를 하기 위한 문제 2문제를 풀고, 공통문제 3문제를 푼 다음 그 코드와 풀이 방법을 공유하는 코드 리뷰를 매주 진행하고 있다. 

 

다음은 OT 시간에 내가 팀원들에게 공유한 글과 영상 링크이다.

취업을 위한 코딩테스트 공부방법

이 글은 약간 공부를 하고 난 다음에 보면 좋고, 바로 밑에 소개할 plzrun님 글이 제일 먼저 보기에는 좋다.

이 분은 "진짜 모르는 사람은 뭘 모르는지 모른다"라는 단순명쾌한 명제에 기반해 글을 쓴 것 같다..

도움이 많이 된 글이었다. 이 글은 정말정말정말!!!!!!! 강추한다. plzrun님 감사합니다 덕분에 많이 늘었습니다 

알고리즘 문제풀이(PS) 시작하기

나동빈 유튜브인데 대회용 알고리즘이 아니라 취직을 위한 알고리즘 공부 순서를 얘기해 준다.

자료구조를 다 까먹었을 때 보기 좋다.

엔지니어대한민국

SK T 아카데미 영상이다. 이것도 1번 보기 좋다. 

 

 

2. 알고리즘 학습 순서 추천 

결론 : 수학 -> 자료구조 -> 재귀 -> DP -> 그래프(DFS/BFS) -> 최단경로 -> 이분탐색 -> 분할정복 -> 그리디 -> 완전탐색, 시뮬레이션, 구현(가능하면 이걸 많이 푸는 게 좋다. 구현력이 늘고 풀 수 있는 문제가 많아진다) -> 문자열 -> 투 포인터, 슬라이딩 윈도우 -> 백트랙킹 1주씩.

이렇게 하면 한 학기 혹은 3개월 동안 얼추 중요한 개념들은 다 돌아볼 수 있다. 물론 스터디가 있는 그 날만 공부하는 게 아니라 과제를 적절히 할당해 거의 매일 문제를 풀 수 있도록 하는 시스템이 제일 중요하다. 스터디 날만 공부하면 절대 안 는다.

 

전제 : 각자 연습하려는 언어의 문법을 알아야 한다. 특히 문자열과 1차원, 2차원 리스트의 삽입, 삭제, 대체, 슬라이싱 등 다루는 기법, 문자와 정수형 변수 사이 형변환 방법 등을 잘 알아야 한다.

 

먼저 처음에 정말 아무것도 할 줄 모를 때는 브론즈 문제 아무거나 풀면서 문제를 푸는 습관을 들이는 게 제일 좋다. 그런 의미로 코드업 100제를 푸는 것을 추천한다.

CodeUp

여기서 100제를 풀고 나면 그래도 어느 정도 문제를 풀 수 있는 능력이 생긴다. 처음에는 이게 문제여? 싶은 문제가 나오지만 풀다보면 난이도가 아주 약간 있는 문제가 있으므로 꼭 풀어보길 권장한다.

그리고, 백준으로 넘어올 때 꼭!!!! 꼭 입출력 문제들을 풀어야 한다. 이건 필수다. 여러 입력들이 들어오는데 이 입력들은 다 정형화되어 있어서 한 번 입출력하는 방법을 잘 외워두면 계속 써먹는다.

위의 plzrun 블로그의 입출력 문제들을 꼭 풀어보고 다음으로 넘어가야 한다. 진지해서 궁서체로 쓴다

 

100제를 풀고 입출력 문제를 풀고 나면 이제 여러 가지를 배우면서 문제를 풀 수 있게 된다.

우리는 다음과 같은 순서로 학습하고 문제를 풀었다.

참고로 문제집 사용을 안 하고 문제를 고를 때는, 난이도는 알아서 하면 된다. 그런데 초급이면 브론즈 1~실버 1 수준에서 문제를 고르는 걸 권장하고 싶다. 브론즈 2티어 아래로는 너무 쉽고, 골드 티어로 넘어가면 자력으로 풀 수 있는 문제가 거의 없는 상태일 테니 말이다. 솔직히 초심자 입장에서는 실버 3티어 위로만 올라가도 힘들다.

 

 

1. 수학 (합공식, 피보나치수, 약수, 최대공약수, 최소공배수, 소수, 조합과 순열)

• 수학 문제를 제일 먼저 추천하는 이유는 이것이 특별한 알고리즘을 학습하거나 할 필요가 크게 없기 때문이다. 물론 최대공약수 같은 건 유클리드 호제법을 배워야 하고, 소수는 에라토스테네스의 체를 사용해야 하긴 하는데 그래도 다른 문제들에 비해서는 비교적 적은 학습으로 많은 문제를 풀 수 있다.
• 소수 문제는 꽤 나오는 편이므로 꼭 학습을 권한다.
• 여기서 1부터 N까지의 합 공식, N부터 M까지의 합 공식, 피보나치 수 구하는 방법(DP, 재귀), 어떤 수의 약수 구하는 방법, 최대공약수와 최소공배수 공식, 소수 구하는 방법(에라토스테네스의 체) 등을 배우고 문제를 풀어보면 된다.
• 물론 수학을 잘 알면 유리하긴 한데 수학을 못 해도 딱히 상관없다. 외워서 하면 되기 때문에...
• 아 추가로 조합, 순열을 구하는 것도 알아두면 좋다. 파이썬에서는 itertools에서 combinations, permutations라는 이름으로 제공하고 있다. 이건 수학뿐 아니라 여러 가지 경우의 수를 고려해야 하는 완탐 문제 등에서 쓸 일이 가~끔 생기기도 한다. 
• 추천 문제는 다음과 같다.

문제집: Week 1 : 수학 (postcookie)

 

2. 자료구조 (해시, 스택, 큐, 덱, 힙)

• 그 다음은 자료구조를 이용하면 바로 풀 수 있는 문제를 푸는 게 좋다. 다른 문제를 풀 때도 쓰이는 기본적인 자료구조들이기 때문에 초반에 한 번 보고 가면 좋다.
• 파이썬의 경우 해시는 일반 딕셔너리 혹은 defaultdict, 스택은 그냥 쓰고, 큐와 덱은 deque으로 구현하는 경우가 많다. 나는 큐와 덱을 따로 구분하지 않고 큐가 필요하면 그냥 deque 쓴다. 힙은 heapq 써서 구현한다.
• 추천 문제는 다음과 같다. 추가로 힙 연습을 위해 프로그래머스에서 '더 맵게' 문제를 풀면 좋다. 아래 문제집을 풀다 보면 쉬운 실버 문제는 딱 문제만 보고도 무슨 자료구조를 이용해서 풀어야할지 감이 오기도 한다. 일례로 괄호 문제는 거의 스택 쓴다. 
• 프로그래머스 42577 문제가 해시 테이블을 써서 푸는 문제인데 꽤 까다로우므로 시도해보고 잘 안 풀리면 나중에 시도하기 바란다. 이 문제는 백준에도 비슷한 문제가 있다.

문제집: Week 2 : 자료구조 (postcookie)

 

3. 재귀, 정렬

• 사실 기본적인 재귀 문제는 하노이 탑, 팩토리얼, 피보나치 수 구하기 정도 풀면 풀 게 없어서 대충 재귀함수를 어떻게 썼는지 그 기억을 되살리는 용도로 풀게 된다.
• 정렬도 딱히 할 건 없다. 무슨 정렬을 구현하라는 문제는 딱히 없어서... 단, 파이썬의 경우 sort의 key에 람다 함수를 커스텀으로 만들어서 요소의 n번째 요소를 기준으로 정렬하기, 내림차순 정렬하기, 길이 순으로 정렬하기 등을 할 수 있다. 이렇게 key에 람다 함수 만드는 연습을 하기 위해 정렬 문제를 몇 개 풀어보면 좋다.
• 전체적으로 이 주는 이 2개만 하면 굉장히 부실해질 것이기 때문에 전주와 전전주에 한 수학, 자료구조 문제를 보충하는 게 스터디 퀄리티를 높이는 데 도움이 될 것이다.
• 추천 문제는 다음과 같다.

문제집: Week 3 : 재귀함수와 정렬 (postcookie)

 

4. 다이나믹 프로그래밍 (DP)

• 그 다음 DP 문제를 푼다. DP 문제를 풀 수 있게 되면 새로운 지평이 열린다. 피보나치에서 재귀 쓰다 시간초과났다면 DP로 풀면 빠르게 풀 수 있다는 것을 알 수 있다.
• 이건 말마따나 "캐시질"을 하는 문제이기 때문에 보통 입력만큼의 빈 테이블을 만들어 둔다.
• 추천 문제는 다음과 같다.

문제집: Week 4 : 다이나믹 프로그래밍 (postcookie)

 

5. 그래프 문제, 기초 DFS와 BFS

• 그래프야말로 코테의 꽃이라고 생각한다. 구현에서도 그래프 쓰는 문제가 되게 많아서 잘 알아둬야 한다.
• 이론을 이해하는 것도 중요하지만 코드로 구현해서 익숙해지는 게 더 좋다. 여기서 트리도 같이 하면 된다.
• 추천 문제는 다음과 같다.

문제집: Week 5 : DFS/BFS 스터디 1 (postcookie)

 

6. DFS와 BFS 응용, 최단 경로 구하기

• 기초 DFS/BFS 문제를 풀고 나면 다익스트라, 플로이드-와샬을 배워서 한 점에서 다른 모든 정점으로의 최단 거리, 모든 점에서 모든 정점으로의 최단 거리 등을 구하는 문제를 풀어보는 게 좋다. 사실 최단 경로 문제는 나도 많이 안 풀어봤지만 가끔 나온다고 하니 대비해두는 게 좋을 것 같다.
• 이쯤에서 슬슬 골드 문제를 풀게 된다. 다익스트라, 플로이드-와샬 등 최단 경로를 구하는 문제들은 거의 골드 5티어부터 시작한다. 둑흔둑흔한 마음을 안고 풀면 된다. 대신 쉬운 문제(진짜 다익스트라 코드 그대로 써야 풀리는 문제)부터 풀어야 좌절이 없다. 기초는 탄탄히 응용은 천천히!
• 추천 문제는 백준 7576, 2178, 10026, 5014, 1916, 4485 이다.

 

7. 이분 탐색과 분할정복

• 이 둘은 솔직히 재귀랑 분할정복을 같이 묶고 이분 탐색은 투포인터랑 같이 묶거나 단독으로 해도 된다는 생각이 든다. 그런데 10주 과정이랑 다 다뤄야해서 그냥 같이 했다.
• 솔직히 이분 탐색과 파라메트릭 서치는 그렇게 엄청 어렵지는 않은데(개인적으로는), 분할정복은 좀 까다롭다. 나는 아직도 분할정복 문제가 나오면 좀 쩔쩔맨다. 재귀 사고를 익히는 데 좋기는 하다. 하지만 사람에 따라 고통스러운 한 주가 될 수 있다는 경고는 한다... 
• 추천 문제는 분할정복 백준 2630, 2448, 1780, 1992, 이분 탐색 2512, 2110, 2470이다. 

 

8. 그리디 알고리즘

• 그리디 알고리즘도 코딩테스트 문제 빈출 유형이라고 한다. 솔직히 나는 그리디 아직도 어떻게 푸는지 잘 모르겠다. 보통 정렬해서 풀긴 하는데 정형화된 풀이 방법은 딱히 없는 듯.
• 추천 문제는 백준 1783, 11501, 1946, 11497, 프로그래머스 42883, 42862다.

 

9. 완전탐색과 시뮬레이션

• 이 부분은 초급, 중급, 진짜 실전 난이도의 문제 정도로 한 3주 정도는 넉넉히 다뤄서 어떻게 푸는지 감을 확실하게 잡는 게 중요하다고 생각한다.
• 여기가 이제 초급 스터디는 끝나고 중급으로 넘어가는 기점이 된다. 통상 8주 정도 알고리즘을 매일매일 꾸준히 풀었다면 이미 문제 푸는 습관은 잡혔을 것이고 모를 때 어떻게 해야 하는지 대응법도 생겼을 것이기 때문에 좀 담대한 마음으로 문제를 대할 수 있다. 이 때 구현이랑 완탐 푸는 게 효과 제일 좋은 것 같다.
• 추천 문제는 백준 2961, 1713, 15683, 17143, 3190, 프로그래머스 42839이다.

 

여기까지가 우리 팀이 한 학기 동안 학습한 내용이고, 이 뒤로는 한 학기에 한 주도 안 쉬고 알고리즘 공부를 한다고 했을 때 제안하는 추가 내용이다.

 

10. 구현

• 사실 구현, 완탐, 시뮬레이션 사이 차이점이 많지는 않다. 비슷비슷하게 생겼다. 이건 백준에 구현 문제집 치면 좋은 문제집이 많다. 정말 무식한 완탐은 어떤 알고리즘이 필요하지 않고 방향 벡터 갖고 순회하면서 보는 게 전부인 문제도 있다.
• 개인적으로 10주차쯤 되면 어느 정도 원숙(?)해졌을 거고 문제를 풀 수 있는 끈기를 갖춘 상태일 테니 타이머를 갖고 슬슬 실전처럼 푸는 연습을 하면 좋을 것 같다.
• 삼성 SW 역량 테스트 기출 문제집에 구현 문제 되게 많으니까 연습하고 싶을 때 이 문제집 풀면 좋다.
• 이외에도 문제 좋은 거 풀고 싶으면 어떻게 하나? 싶을 때가 있는데 그럴 때는 (1) 다른 플랫폼으로 옮긴다 (프로그래머스, 리트코드, 코딜리티 등) (2) solved.ac에서 태그 구현, 완탐, 시뮬레이션으로 걸고 푼 사람 수로 정렬해서 사람들이 많이 푼 문제를 풀면 된다. 이 때 수준이 너무 낮으면 도움이 안 되고, 최소 실버 3 티어 이상 골드 1 이하 정도 문제를 풀면 좋은 것 같다. 어디 기출 문제면 더 좋은데 삼성이랑 카카오 말고는 문제가 공개된 데가 많이 없으니 공개된 기출 문제집을 적극 활용하자. 실제로 우리도 이런 기준으로 문제를 고르고 있다. 

문제집: 삼성 SW 역량 테스트 기출 문제 (baekjoon)

 

11. 문자열

• 문자열 고급 문제를 풀면 좋다. 여기서 기상천외한.. 본 적도 없는 메소드를 활용해야 할 수도 있다. 뭐 그러면서 배우는 거라고 생각한다.
• 여기서 트라이를 공부할 수도 있긴 한데 우리는 패스했다. 카카오에는 트라이 문제가 가끔 나온다고 하니 카카오를 준비한다면 트라이를 하는 것도 좋은 선택일 거다.

 

12. 투 포인터, 슬라이딩 윈도우

• 투 포인터와 슬라이딩 윈도우 문제도 가끔 가다 나온다. 이건 모르면 삽질하는데 알고 나면 이걸 써서 풀 수 있는 문제에 딱 적용할 수 있게 돼서 좋다. 그렇게 어렵(?)지 않으니 한 번 짚고 넘어가면 좋을 것 같다.

 

13. 백트랙킹

• 사실 백트랙킹을 따로 하기보다는 완전탐색이나 그런 거할 때 같이 하면 좋긴 한데 따로 빼서 하면 좋긴 하다. 특히 재귀를 잘 이해하지 못하거나 DFS를 써야 하는 문제에 쩔쩔맨다면 한 번 짚고 넘어가면 좋다. 왜 백트랙킹이란 게 따로 빠져 있냐면, 단순히 DFS를 해서는 시간초과로 풀 수 없는 문제가 있기 때문이다.

 

이 이후로는 그냥 부족한 문제 풀면 된다. 위상 정렬, 트라이 같은 거해도 된다. 나는 지금 중급 스터디를 하고 있는데, 스터디에서 할당받은 문제 외에는 프로그래머스 아직 안 푼 렙2 문제, 구현 문제 같은 거 푼다. 

내가 커리큘럼을 짤 때 도움이 됐던 repo 2개 공유한다.

GitHub - tony9402/baekjoon: 코딩테스트 대비 문제집(Baekjoon Online Judge)

GitHub - CodeTest-StudyGroup/Code-Test-Study: 코딩 테스트 관련 기출문항을 풀어보고 소스코드 및 설명을

 

그리고 우리 초급 알고리즘 스터디 팀이 공부했던 repo도 공유한다.

먼 훗날 여기서 공부한 스터디팀 전원 네카라쿠배당토에 취직해.. 이런 후기를 쓸 수 있게 되었으면.. ㅋㅋㅋㅋㅋㅋㅋㅋ

GitHub - dev-dain/Dukgorithm: 덕새는 알고리즘을 찢어! 알고리즘, 제대로 공부하자

 

마지막으로, 정말 좋은 글이라 한 번 더 공유한다. 아까 위에 그 블로그이다.

제발 읽어보면 좋겠다. 앞뒤광고 절대 아니고 진짜 도움이 많이 돼서 올리는 글이다.

알고리즘 문제풀이(PS) 시작하기

 

끝!!

코테 준비에 도움이 되길~

 

이 글이 도움이 되셨다면 광고 한 번 클릭 부탁드립니다. ㅎㅎ