[Study 010] 알고리즘 문제해결전략 (종만북)

목차

스터디 주제

• 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (aka 종만북)

 

 

참가자

• https://github.com/nahwasa (boj : nahwasa)
• https://github.com/kwanik-kor (boj : rhksdlr134)
• https://github.com/JustBestRyuna (boj : specidiee)
• https://github.com/r4pidstart (boj : r4pidstart)
• https://github.com/kevinlys00 (boj : kevinlys00)

 

진행 방법

• github 참고

 

 

일정 (완료)

• ~2023-03-13 : 인원 모집
  • 2023-03-13 게더타운 : 킥오프
• 1주차 2023-03-14 ~ 2023-03-20 : 6섹션 - 무식하게 풀기 (brute force)
• 2주차 2023-03-21~2023-03-27 : 7섹션 - 분할 정복 (divide and conquer)
• 3주차 2023-03-28~2023-04-03 : 8섹션 - 동적 계획법 (DP) 1차
• 4주차 2023-04-04~2023-04-10 : 8섹션 - 동적 계획법 (DP) 2차
• 5주차 2023-04-11~2023-04-17 : 10섹션 - 탐욕법 (Greedy)
• 6주차 ~2023-05-01 : 11섹션 - 조합 탐색 (combinatorial search)
  • (2023-04-18~2023-04-24 : 시험기간 이므로 패스)
• 7주차 ~2023-05-08 : 12섹션 - 최적화 문제 결정 문제로 바꿔 풀기
• 8주차 ~2023-05-15 : 16.비트마스크, 17.부분 합, 18.선형 자료 구조
• 9주차 ~2023-05-22 : 19. 큐와 스택, 데크, 20. 문자열(~20.4까지)
• 10주차 ~2023-05-29 : 20. 문자열(20.5~), 21. 트리의 구현과 순회
• 11주차 ~2023-06-05 : 22. 이진 검색 트리, 23. 우선순위 큐와 힙
• 12주차 ~2023-06-12 : 24. 구간 트리
• 13주차 ~2023-06-19 : 25. 상호 배타적 집합
• 14주차 ~2023-06-26 : 26. 트라이
• 15주차 ~2023-07-10 : 27. 그래프의 표현과 정의, 28. 그래프의 깊이 우선 탐색
• 16주차 ~2023-07-17 : 29. 그래프의 너비 우선 탐색
• 17주차 ~2023-07-24 : 30. 최단 경로 알고리즘 (+29장 설명 못한 부분)
• 18주차 ~2023-08-07 : 31. 최소 스패닝 트리, 32. 네트워크 유량

 

 

문제

※ 종만북에 이미 풀이가 있는데 제 풀이를 올리는 이유는 제가 책의 풀이를 보지 않고 문제를 푼 후 제 풀이를 올리고 나서 책의 풀이를 보는 방식으로 풀어보고 싶기 때문입니다.

 

※ 추천 문제는 스터디 팀원분들이 서로에게 추천해주고 싶은 문제를 올린 것들입니다. (깃허브 이슈에 올려져 있음)

 

1주차 - 무식하게 풀기 (brute force)

BOGGLE / PICNIC / BOARDCOVER / CLOCKSYNC

 

1주차 추천 문제

• BOJ_14927 / BOJ_1214 / BOJ_3040

 

 

2주차 - 분할 정복 (divide and conquer)

QUADTREE(cpp) /  FENCE / FANMEETING

 

2주차 추천 문제

• BOJ_2261 / BOJ_1187 / BOJ_10090

 

 

3, 4주차 - 동적 계획법 (DP)

JUMPGAME / WILDCARD / TRIANGLEPATH / LIS / JLIS / PI / QUANTIZE / TILING2 / TRIPATHCNT / SNAIL / ASYMTILING / POLY / NUMB3RS

 

3,4주차 추천 문제

• BOJ_1048 / BOJ_14003

 

 

5주차 - 탐욕법 (greedy)

MATCHORDER / LUNCHBOX / STRJOIN / MINASTIRITH

 

5주차 추천 문제

• BOJ_2873 / BOJ_1422 / BOJ_1715 / BOJ_13448

 

 

6주차 - 조합 탐색 (combinatorial search)

BOARDCOVER2 / ALLERGY / KAKURO2

 

 

7주차 - 최적화 문제 결정 문제로 바꿔 풀기

DARPA / ARCTIC / CANADATRIP / WITHDRAWAL

 

 

8주차 - 비트마스크, 부분 합, 선형 자료 구조

GRADUATION / CHRISTMAS / JOSEPHUS

 

 

9주차 - 큐와 스택, 데크, 문자열(~20.4)

BRACKETS2 / ITES / NAMING / PALINDROMIZE / JAEHASAFE

 

 

10주차 - 문자열(20.5~), 트리의 구현과 순회

HABIT / TRAVERSAL / FORTRESS

 

 

11주차 - 이진 검색 트리, 우선순위 큐와 힙

NERD2 / INSERTION / RUNNINGMEDIAN

 

 

12주차 - 구간 트리

MORDOR / FAMILYTREE / MEASURETIME (cpp)

 

 

13주차 - 상호 배타적 집합

EDITORWARS

 

 

14주차 - 트라이

SOLONG / NH

 

 

15주차 - 그래프의 표현과 정의, 그래프의 깊이 우선 탐색

DICTIONARY / WORDCHAIN / GALLERY / MEETINGROOM

종만북 사이트 1주넘게 터져있어서 백준 문제로 대체됨. (스터디 당일(230710) 오전에 복구됨 ㅠ)

BOJ25195 / BOJ10542 / BOJ1199 / BOJ1987 / BOJ2638 / BOJ17472 / BOJ15681 / BOJ13024

 

 

16주차 - 그래프의 너비 우선 탐색

SORTGAME / CHILDRENDAY / HANOI4
추가 추천 : BOJ_17114 / BOJ_16930 / BOJ_22949

 

 

17주차 - 최단 경로 알고리즘

ROUTING / FIRETRUCKS / NTHLON / TIMETRIP / DRUNKEN / PROMISES

 

 

18주차 - 최소 스패닝 트리, 네트워크 유량

LAN / TPATH / MATCHFIX / BISHOPS / TRAPCARD