[Algorithm Study] 알고리즘 스터디 커리큘럼

최근 코어멤버 남수연님의 'C++로 알고리즘 시작하기'라는 알고리즘 세션을 진행하면서 피드백을 받아보았는데요, 많은 분들이 궁금해하시는 부분 중 하나가 어떻게 알고리즘 학습을 시작했는지, 어떤 방식으로 알고리즘 스터디를 진행했는지 등 이었습니다.

알고리즘 스터디를 시작하시는 모든 분들께 조금이나마 도움이 되었으면 하는 바람에서, 저희 2020-2021 DSC Sookmyung 내부에서 진행한 알고리즘 스터디의 커리큘럼을 공유하고자 합니다. 어떤 자료로 학습하고 어떤 백준 문제를 풀었는지에 대한 글을 작성합니다. 알고리즘 공부를 처음 시작한 사람부터 약간 공부해본 사람들을 대상으로 진행했으므로 처음 공부하시는 분들에게 도움이 될 것 같습니다. 

총 0주차부터 8주차까지, 각 주차마다 정해진 주제로 문제를 풀기 전 참고, 학습할 자료를 공유하고 관련한 문제를 풀며 진행했습니다.
연습, 필수문제와 도전문제로 나눠져있지만 도전문제가 많이 어렵지 않은 경우가 많으므로 모든 문제를 풀어보는 것을 권장드립니다.

참고) Google DSC Sookmyung 깃허브와 블로그에서 관련한 글들을 참고해보실 수 있습니다.

 

---

0주차 시간복잡도와 Big-O 표기법

[참고자료]
-https://www.youtube.com/watch?v=QBZnX_P_dj4
-https://www.youtube.com/watch?v=6Iq5iMCVsXA

[필수문제]
- 일곱 난쟁이https://www.acmicpc.net/problem/2309
- 한수https://www.acmicpc.net/problem/1065
- 덩치https://www.acmicpc.net/problem/7568

[도전문제]
- 컴포트https://www.acmicpc.net/problem/3258
- 복면산https://www.acmicpc.net/problem/15811

---

1주차 브루트 포스와 백트래킹

[참고자료]
- 브루트 포스:http://blog.naver.com/kks227/220769870195
- 브루트 포스 추가자료 : https://www.slideshare.net/JaeyeolLee4/hiarc-ps-102-brute-force
- 백트래킹:https://www.youtube.com/watch?v=Enz2csssTCs&t=37s
- 백트래킹 추가자료 : https://www.slideshare.net/JaeyeolLee4/backtracking-icpc-sinchon

[필수문제]
- 일곱난쟁이 www.acmicpc.net/problem/2309
- 한수 www.acmicpc.net/problem/1065
- 덩치 www.acmicpc.net/problem/7568

[도전문제]
- 컴포트 www.acmicpc.net/problem/3258
- 큰 수 구성하기 www.acmicpc.net/problem/18511
- 맞춰봐 www.acmicpc.net/problem/1248

---

2주차 정렬

[참고자료]
-https://www.youtube.com/watch?v=YJ-OUnZu7nQ&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=9
-https://www.youtube.com/watch?v=ZG68SXDtODM&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=10

[필수문제]
- 수 정렬하기 2 https://www.acmicpc.net/problem/2751 
- 국영수 https://www.acmicpc.net/problem/10825
-  치킨 TOP N https://www.acmicpc.net/problem/11582 

 

[도전문제]
- 좌표 압축 www.acmicpc.net/problem/18870
- 버블 소트 www.acmicpc.net/problem/1517
- 큰 수 만들기 www.acmicpc.net/problem/16496

---

3주차 스택

[참고자료]
- 스택 자료구조 5분만에 이해하기 https://www.youtube.com/watch?v=DsZHDmth6Pc&t=2s
-https://www.youtube.com/watch?v=WB_BoAgWLNU&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=14
-https://www.acmicpc.net/group/practice/9273/4

[필수문제]
- 막대기: https://www.acmicpc.net/problem/17608
- 스택: https://www.acmicpc.net/problem/10828
- 스택의 값: https://www.acmicpc.net/problem/2504
- 제로: https://www.acmicpc.net/problem/10773

[도전문제]
- 외계인의 기타 연주: https://www.acmicpc.net/problem/2841
- 쇠막대기: https://www.acmicpc.net/problem/10799
- 이상한 하노이 탑: https://www.acmicpc.net/problem/15500
원판을 옮긴 횟수가 12345보다 작기만 하면 모두 정답입니다. 풀이는 여러 가지가 있을 텐데, 그 중에는 스택으로 푸는 방법도 있습니다.

---

4주차 큐와 덱

[참고자료]
- 큐 자료구조 5분만에 이해하기 https://www.youtube.com/watch?v=BdsyG5yP1cQ
- 큐 https://www.youtube.com/watch?v=D_fwSy5tRAY
- 덱 https://www.youtube.com/watch?v=0mEzJ4S1d8o
큐 응용
- 슬라이딩 윈도우 https://www.youtube.com/watch?v=uH9VJRIpIDY
- 투 포인터 https://www.youtube.com/watch?v=rI8NRQsAS_s

[연습문제]
- 기초문제: https://www.acmicpc.net/group/practice/9273/5
- 큐:https://www.acmicpc.net/problem/10845
- 덱: https://www.acmicpc.net/problem/10866

[필수문제]
- 요세푸스 문제 0: https://www.acmicpc.net/problem/11866
- AC: https://www.acmicpc.net/problem/5430
- 게으른 백곰(슬라이딩 윈도우): https://www.acmicpc.net/problem/10025
- 귀여운 라이언(투 포인터): https://www.acmicpc.net/problem/15565
- 풍선 터뜨리기: https://www.acmicpc.net/problem/2346

[도전문제]
- 부분합: https://www.acmicpc.net/problem/1806

---

5주차 다이나믹 프로그래밍(DP, 동적 계획법)

[참고자료]
- (이론) https://www.youtube.com/watch?v=FmXZG7D8nS4
- (문제풀이 포함 - 1부) https://www.youtube.com/watch?v=lu7sQHs2O7I&t=543s
- (문제풀이 포함 - 2부) https://www.youtube.com/watch?v=hjlkqAgzZ50&t=535s

[연습문제]
- https://www.acmicpc.net/group/practice/9273/6

[필수문제]
- 2xn 타일링: https://www.acmicpc.net/problem/11726
- 피보나치 수 2: https://www.acmicpc.net/problem/2748
n이 커지면 C/C++에서 표현할 수 있는 정수 범위를 넘어가는 문제가 있어 피보나치 수 4 문제를 피보나치 수 2로 대체했습니다.
- 가장 긴 증가하는 부분 수열: [https://www.acmicpc.net/problem/11053]
- 행렬 곱셈 순서: https://www.acmicpc.net/problem/11049

[도전문제]
- 트리의 독립집합: https://www.acmicpc.net/problem/2213
- RGB거리: https://www.acmicpc.net/problem/1149
- 크리스마스 트리: https://www.acmicpc.net/problem/1234

---

6주차 이분탐색과 파라메트릭 탐색

파라메트릭 탐색에 대한 개념은 여기(https://sarah950716.tistory.com/16)에 잘 설명되어 있습니다.
이번 강의자료들은 모두 Python을 사용합니다. 강의에서 사용하는 bisect_left와 bisect_right는 C++ algorithm 헤더의 lower_bound와 upper_bound로 대체 가능합니다.

[참고자료]
- lower_bound & upper_bound 함수 사용법: https://chanhuiseok.github.io/posts/algo-55/
- 이진 탐색과 파라메트릭 탐색: https://youtu.be/94RC-DsGMLo

[연습문제]
- https://www.acmicpc.net/group/practice/9273/7

[필수문제]
- [10816] 숫자 카드 2: https://www.acmicpc.net/problem/10816
(C++)lower_bound/upper_bound 또는 (Python)bisect_left/bisect_right 사용하시면 됩니다.
- [1654] 랜선 자르기: https://www.acmicpc.net/problem/1654
- [2343] 기타 레슨: https://www.acmicpc.net/problem/2343
- [18113] 그르다 김가놈: https://www.acmicpc.net/problem/18113

[도전문제]
- [2110] 공유기 설치: https://www.acmicpc.net/problem/2110
무엇을 이분 탐색할지 잘 생각해 봐야 합니다.
- [1790] 수 이어 쓰기 2: https://www.acmicpc.net/problem/1790
- [1561] 놀이 공원: https://www.acmicpc.net/problem/1561

<이분탐색 꿀팁>
1) ~~인 값 중 최소
mid=(lo+hi)/2 (내림)
- 오른쪽 가야함 -> lo=mid+1
- 왼쪽 가야함 -> hi=mid
(lo 고정, hi 근소하게 왼쪽)

2) ~~인 값 중 최대
mid=(lo+hi+1)/2 (올림)
- 오른쪽 가야함 -> lo=mid
(hi 고정, lo가 근소하게 오른쪽)
- 왼쪽 가야함 -> hi=mid-1

---

7주차 DFS 와 BFS

[참고자료]
- (선택)DFS, BFS에 대한 이해: https://youtu.be/-wsYtm0x3nw
- DFS: https://youtu.be/l0Rsu7dziws
- BFS: https://youtu.be/66ZKz-FktXo

[연습문제]
- https://www.acmicpc.net/group/practice/9273/8

[필수문제]
- [1260] DFS와 BFS: https://www.acmicpc.net/problem/1260
- [2606] 바이러스: https://www.acmicpc.net/problem/2606
- [1012] 유기농 배추: https://www.acmicpc.net/problem/1012
- [14502] 연구소: https://www.acmicpc.net/problem/14502
14502번 문제는 삼성 SW 역량 테스트 기출문제입니다.

[도전문제]
- [1707] 이분 그래프: https://www.acmicpc.net/problem/1707
- [19641] 중첩 집합 모델: https://www.acmicpc.net/problem/19641
- [14267] 내리 칭찬: https://www.acmicpc.net/problem/14267

---

8주차 Set, Map과 Dictionary

C++에서는 map을 사용하고, Python에서는 Dictionary합니다. Set은 모두 아시다시피 집합이고, Map과 Dictionary는 해시 테이블입니다. 원하는 정보에 빠르게 접근할 수 있다는 장점이 있습니다.

[참고자료]
- (선택)set, map의 시간복잡도: https://codingdog.tistory.com/entry/c-set%EC%9D%B4%EB%82%98-map%EC%9D%84-%EC%A0%84%EC%B2%B4-%EC%88%9C%ED%9A%8C%ED%95%98%EB%8A%94-%EB%8D%B0-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84%EB%8A%94-%EC%96%BC%EB%A7%88%EC%9D%BC%EA%B9%8C%EC%9A%94
- (C++)set, map 사용 방법: https://sarah950716.tistory.com/6
- (C++)set 정렬 방법: https://chanhuiseok.github.io/posts/algo-46/
- (Python)dictionary 사용 방법: https://www.daleseo.com/python-ditonary/

[연습문제]
- https://www.acmicpc.net/group/practice/9273/9

[필수문제]
- [1620] 포켓몬 마스터 이다솜: https://www.acmicpc.net/problem/1620
- [19583] 싸이버개강총회: https://www.acmicpc.net/problem/19583
- [1764] 듣보잡: https://www.acmicpc.net/problem/1764
- [4358] 생태학: https://www.acmicpc.net/problem/4358

[도전문제]
- [14425] 문자열 집합: https://www.acmicpc.net/problem/14425
- [16165] 걸그룹 마스터 준석이: https://www.acmicpc.net/problem/16165