Algorithmic-Problem-Solving-Strategies: A C++ repository from dwax1324

프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 정리

총 93 문제

장	문제	링크	소스코드
1장	록 페스티벌	FESTIVAL
6장	보글 게임	BOGGLE	BOGGLE.cpp / BOGGLE.py
6장	소풍	PICNIC
6장	게임판 덮기	BOARDCOVER
6장	시계 맞추기	CLOCKSYNC
7장	쿼드 트리 뒤집기	QUADTREE
7장	울타리 잘라내기	FENCE
7장	팬 미팅	FANMEETING
8장	외발뛰기	JUMPGAME
8장	와일드카드	WILDCARD
8장	삼각형 위의 최대 경로	TRIANGLEPATH
8장	최대 부분 증가 수열	LIS
8장	합친 LIS	JLIS
8장	원주율 외우기	PI
8장	Quantization	QUANTIZE
8장	타일링 방법의 수 세기	TILING2
8장	삼각형 위의 최대 경로 수 세기	TRIPATHCNT
8장	달팽이	SNAIL
8장	비대칭 타일링	ASYMTILING
8장	폴리오미노	POLY
8장	두니발 박사의 탈옥	NUMB3RS
9장	여행 짐 싸기	PACKING
9장	광학 문자 인식	OCR
9장	모스 부호 사전	MORSE
9장	k번째 최대 증가 부분 수열	KLIS
9장	드래곤 커브	DRAGON
9장	웨브바짐	ZIMBABWE
9장	실험 데이터 복구하기	RESTORE
9장	틱택토	TICTACTOE
9장	숫자 게임	NUMBERGAME
9장	블록 게임	BLOCKGAME
9장	회전초밥	SUSHI
9장	지니어스	GENIUS
10장	출전 순서 정하기	MATCHORDER
10장	도시락 데우기	LUNCHBOX
10장	문자열 합치기	STRJOIN
10장	미나스 아노르	MINASTIRITH
11장	게임판 덮기 2	BOARDCOVER2
11장	알러지가 심한 친구들	ALLERGY
11장	카쿠로	KAKURO2
12장	DARPA Grand Challenge	DARPA
12장	남극 기지	ARCTIC
12장	캐나다 여행	CANADATRIP
12장	수강 철회	WITHDRAWAL
13장	방정식 풀기	ROOTS
13장	전세금 균등상환	LOAN
13장	승률 올리기	RATIO
13장	꽃가루 화석	FOSSIL
14장	비밀번호 486	PASS486
14장	마법의 약	POTION
15장	핀볼 시뮬레이션	PINBALL
15장	보물섬	TREASURE
15장	너드인가, 너드가 아닌가?	NERDS
16장	졸업 학기	GRADUATION
17장	크리스마스 인형	CHRISTMAS
18장	조세푸스 문제	JOSEPHUS
19장	짝이 맞지 않는 괄호	BRACKETS2
19장	외계 신호 분석	ITES
20장	작명하기	NAMING
20장	팰린드롬 만들기	PALINDROMIZE
20장	재하의 금고	JAEHASAFE
20장	말버릇	HABIT
21장	트리 순회 순서 변경	TRAVERSAL
21장	요새	FORTRESS
22장	너드인가, 너드가 아닌가? 2	NERD2
22장	삽입 정렬 뒤집기	INSERTION
23장	변화하는 중간 값	RUNNINGMEDIAN
24장	등산로	MORDOR
24장	족보 탐험	FAMILYTREE
24장	삽입 정렬 시간 재기	MEASURETIME
25장	에디터 전쟁	EDITORWARS
26장	안녕히, 그리고 물고기는 고마웠어요!	SOLONG
26장	보안종결자	NH
28장	고대어 사전	DICTIONARY
28장	단어 제한 끝말잇기	WORDCHAIN
28장	감시 카메라 설치	GALLERY
28장	회의실 배정	MEETINGROOM
29장	Sorting Game	SORTGAME
29장	어린이날	CHILDRENDAY
29장	하노이의 탑	HANOI4B
30장	신호 라우팅	ROUTING
30장	소방차	FIRETRUCKS
30장	철인 N종 경기	NTHLON
30장	시간여행	TIMETRIP
30장	음주 운전 단속	DRUNKEN
30장	선거 공약	PROMISES
31장	근거리 네트워크	LAN
31장	여행 경로 정하기	TPATH
32장	마일리지로 여행하기	준비중입니다
32장	도난당한 조각상	준비중입니다
32장	승부 조작	MATCHFIX
32장	국책 사업	준비중입니다
32장	함정 설치	TRAPCARD

-목차-

1부 문제 해결 시작하기

-개관

1장 문제 해결과 프로그래밍 대회

-1.1 도입
-1.2 프로그래밍 대회
-1.3 이 책을 읽는 방법
-1.4 국내에서 참가할 수 있는 프로그래밍 대회들
-1.5 대회 준비를 위한 조언
-1.6 더 읽을 거리

2장 문제 해결 개관

-2.1 도입
-2.2 문제 해결 과정
-2.3 문제 해결 전략
-2.4 더 읽을거리

3장 코딩과 디버깅에 관하여

-3.1 도입: 코딩의 중요성을 간과하지 말라
-3.2 좋은 코드를 짜기 위한 원칙
-3.3 자주 하는 실수
-3.4 디버깅과 테스팅
-3.5 변수 범위의 이해
-3.6 실수 자료형의 이해(optional)
-3.7 더 읽을 거리

2부 알고리즘 분석

개관

4장 알고리즘의 시간 복잡도 분석

-4.1 도입
-4.2 선형 시간 알고리즘
-4.3 선형 이하 시간 알고리즘
-4.4 지수 시간 알고리즘
-4.5 시간 복잡도
-4.6 수행 시간 어림짐작하기
-4.7 계산 복잡도 클래스: P, NP, NP-완비
-4.8 더 읽을 거리

5장 알고리즘의 정당성 증명

-5.1 도입
-5.2 수학적 귀납법과 반복문 불변식
-5.3 귀류법
-5.4 다른 기술들
-5.5 더 읽을 거리

3부 알고리즘 설계 패러다임

-개관

6장 무식하게 풀기

-6.1 도입
-6.2 재귀 호출과 완전 탐색
-6.3 문제: 소풍 (난이도: 하, 문제 ID: PICNIC)
-6.4 풀이: 소풍
-6.5 문제: 게임판 덮기 (난이도: 하, 문제 ID: BOARDCOVER)
-6.6 풀이: 게임판 덮기
-6.7 최적화 문제
-6.8 문제: 시계 맞추기 (난이도: 중, 문제 ID: CLOCKSYNC)
-6.9 풀이: 시계 맞추기
-6.10 많이 등장하는 완전 탐색 유형

7장 분할 정복

-7.1 도입
-7.2 문제: 쿼드 트리 뒤집기 (문제 ID: QUADTREE, 난이도: 하)
-7.3 풀이: 쿼드 트리 뒤집기
-7.4 문제: 울타리 잘라내기 (문제 ID: FENCE, 난이도: 중)
-7.5 풀이: 울타리 잘라내기
-7.6 문제: 팬 미팅 (문제 ID: FANMEETING, 난이도: 상)
-7.7 풀이: 팬 미팅

8장 동적 계획법

-8.1 도입
-8.2 문제: 와일드카드 (문제 ID: WILDCARD, 난이도: 중)
-8.3 풀이: 와일드카드
-8.4 전통적 최적화 문제들
-8.5 문제: 합친 LIS (문제 ID: JLIS, 난이도: 하)
-8.6 풀이: 합친 LIS
-8.7 문제: 원주율 외우기 (문제 ID: PI, 난이도: 하)
-8.8 풀이: 원주율 외우기
-8.9 문제: Quantization (문제 ID: QUANTIZE, 난이도: 중)
-8.10 풀이: Quantization
-8.11 경우의 수와 확률
-8.12 문제: 비대칭 타일링 (문제 ID: ASYMTILING, 난이도: 하)
-8.13 풀이: 비대칭 타일링
-8.14 문제: 폴리오미노 (문제 ID: POLY, 난이도: 중)
-8.15 풀이: 폴리오미노
-8.16 문제: 두니발 박사의 탈옥 (문제 ID: NUMB3RS, 난이도: 중)
-8.17 풀이: 두니발 박사의 탈옥

9장 동적 계획법 테크닉

-9.1 최적화 문제의 실제 답 계산하기
-9.2 문제: 여행 짐 싸기 (문제 ID: PACKING, 난이도: 중)
-9.3 풀이: 여행 짐 싸기
-9.4 문제: 광학 문자 인식 (문제 ID: OCR, 난이도: 상)
-9.5 풀이: 광학 문자 인식
-9.6 k번째 답 계산하기
-9.7 문제: k번째 최대 증가 부분 수열 (문제 ID: KLIS, 난이도: 상)
-9.8 풀이: k번째 최대 증가 부분 수열
-9.9 문제: 드래곤 커브 (문제 ID: DRAGON, 난이도: 중)
-9.10 풀이: 드래곤 커브
-9.11 정수 이외의 입력에 대한 메모이제이션
-9.12 문제: 웨브바짐 (문제 ID: ZIMBABWE, 난이도: 상)
-9.13 풀이: 웨브바짐
-9.14 문제: 실험 데이터 복구하기 (문제 ID: RESTORE, 난이도: 중)
-9.15 풀이: 실험 데이터 복구하기
-9.16 조합 게임
-9.17 문제: 숫자 게임 (문제 ID: NUMBERGAME, 난이도: 하)
-9.18 풀이: 숫자 게임
-9.19 문제: 블록 게임 (문제 ID: BLOCKGAME, 난이도: 중)
-9.20 풀이: 블록 게임
-9.21 반복적 동적 계획법
-9.22 문제: 회전초밥 (문제 ID: SUSHI, 난이도: 중)
-9.23 풀이: 회전초밥
-9.24 문제: 지니어스 (문제 ID: GENIUS, 난이도: 중)
-9.25 풀이: 지니어스
-9.26 더 읽을 거리

10장 탐욕법

-10.1 도입
-10.2 문제: 도시락 데우기 (문제 ID: LUNCHBOX, 난이도: 하)
-10.3 풀이: 도시락 데우기
-10.4 문제: 문자열 합치기 (문제 ID: STRJOIN, 난이도: 중)
-10.5 풀이: 문자열 합치기
-10.6 문제: 미나스 아노르 (문제 ID: MINASTIRITH, 난이도: 상)
-10.7 풀이: 미나스 아노르

11장 조합 탐색

-11.1 도입
-11.2 조합 탐색 기법들
-11.3 문제: 게임판 덮기 2 (문제 ID: BOARDCOVER2, 난이도: 하)
-11.4 풀이: 게임판 덮기 2
-11.5 문제: 알러지가 심한 친구들 (문제 ID: ALLERGY, 난이도: 중)
-11.6 풀이: 알러지가 심한 친구들
-11.7 문제: 카쿠로 (문제 ID: KAKURO2, 난이도: 중)
-11.8 풀이: 카쿠로
-11.9 더 읽을거리

12장 최적화 문제 결정 문제로 바꿔 풀기

-12.1 도입
-12.2 문제: 남극 기지 (문제 ID: ARCTIC, 난이도: 하)
-12.3 풀이: 남극 기지
-12.4 문제: 캐나다 여행 (문제 ID: CANADATRIP, 난이도: 중)
-12.5 풀이: 캐나다 여행
-12.6 문제: 수강 철회 (문제 ID: WITHDRAWAL, 난이도: 상)
-12.7 풀이: 수강 철회

4부 유명한 알고리즘들

-개관

13장 수치 해석

-13.1 도입
-13.2 이분법
-13.3 문제: 승률 올리기 (문제 ID: RATIO, 난이도: 하)
-13.4 풀이: 승률 올리기
-13.5 삼분 검색
-13.6 문제: 꽃가루 화석 (문제 ID: FOSSIL, 난이도: 상)
-13.7 풀이: 꽃가루 화석
-13.8 다른 주제들

14장 정수론

-14.1 도입
-14.2 소수
-14.3 문제: 비밀번호 486 (문제 ID: PASS486, 난이도: 중)
-14.4 풀이: 비밀번호 486
-14.5 유클리드 알고리즘
-14.6 문제: 마법의 약 (문제 ID: POTION, 난이도: 중)
-14.7 풀이: 마법의 약
-14.8 모듈라 연산
-14.9 더 읽을거리(optional)

15장 계산 기하

-15.1 도입
-15.2 계산 기하의 도구들
-15.3 교차와 거리, 면적
-15.4 문제: 핀볼 시뮬레이션 (문제 ID: PINBALL, 난이도: 상)
-15.5 풀이: 핀볼 시뮬레이션
-15.6 다각형
-15.7 문제: 보물섬 (문제 ID: TREASURE, 난이도: 상)
-15.8 풀이: 보물섬
-15.9 문제: 너드인가, 너드가 아닌가? (문제 ID: NERDS, 난이도: 중)
-15.10 풀이: 너드인가, 너드가 아닌가?
-15.11 계산 기하 알고리즘 디자인 패턴
-15.12 자주 하는 실수와 유의점들
-15.13 더 읽을거리

5부 기초 자료 구조

-개관

19장 큐와 스택, 데크

-19.1 도입
-19.2 큐와 스택, 데크의 구현
-19.3 스택과 큐의 활용
-19.4 문제: 짝이 맞지 않는 괄호 (문제 ID: BRACKETS2, 난이도: 하)
-19.5 풀이: 짝이 맞지 않는 괄호
-19.6 문제: 외계 신호 분석 (문제 ID: ITES, 난이도: 중)
-19.7 풀이: 외계 신호 분석

20장 문자열

-20.1 도입
-20.2 문자열 검색
-20.3 문제: 재하의 금고 (문제 ID: JAEHASAFE, 난이도: 중)
-20.4 풀이: 재하의 금고
-20.5 접미사 배열
-20.6 문제: 말버릇 (문제 ID: HABIT, 난이도: 중)
-20.7 풀이: 말버릇
-20.8 더 읽을거리

6부 트리

-개관

21장 트리의 구현과 순회

-21.1 도입
-21.2 트리의 순회
-21.3 문제: 트리 순회 순서 변경 (문제 ID: TRAVERSAL, 난이도: 하)
-21.4 풀이: 트리 순회 순서 변경
-21.5 문제: 요새 (문제 ID: FORTRESS, 난이도: 중)
-21.6 풀이: 요새

22장 이진 검색 트리

-22.1 도입
-22.2 이진 검색 트리의 정의와 조작
-22.3 시간 복잡도 분석과 균형 잡힌 이진 검색 트리
-22.4 문제: 너드인가, 너드가 아닌가? 2 (문제 ID: NERD2, 난이도: 중)
-22.5 풀이: 너드인가, 너드가 아닌가? 2
-22.6 균형 잡힌 이진 검색 트리 직접 구현하기: 트립
-22.7 문제: 삽입 정렬 뒤집기 (문제 ID: INSERTION, 난이도: 중)
-22.8 풀이: 삽입 정렬 뒤집기

23장 우선순위 큐와 힙

-23.1 도입
-23.2 힙의 정의와 구현
-23.3 문제: 변화하는 중간 값 (문제 ID: RUNNINGMEDIAN, 난이도: 하)
-23.4 풀이: 변화하는 중간 값

24장 구간 트리

-24.1 구간 트리: 구간에 대한 질문 대답하기
-24.2 문제: 등산로 (문제 ID: MORDOR, 난이도: 중)
-24.3 풀이: 등산로
-24.4 문제: 족보 탐험 (문제 ID: FAMILYTREE, 난이도: 상)
-24.5 풀이: 족보 탐험
-24.6 펜윅 트리: 빠르고 간단한 구간 합
-24.7 문제: 삽입 정렬 시간 재기 (문제 ID: MEASURETIME, 난이도: 중)
-24.8 풀이: 삽입 정렬 시간 재기

25장 상호 배타적 집합

-25.1 도입
-25.2 문제: 에디터 전쟁 (문제 ID: EDITORWARS, 난이도: 중)
-25.3 풀이: 에디터 전쟁

26장 트라이

-26.1 도입
-26.2 문제: 안녕히, 그리고 물고기는 고마웠어요! (문제 ID: SOLONG, 난이도: 중)
-26.3 풀이: 안녕히, 그리고 물고기는 고마웠어요!
-26.4 트라이를 이용한 다중 문자열 검색
-26.5 문제: 보안종결자 (문제 ID: NH, 난이도: 상)
-26.6 풀이: 보안종결자

7부 그래프

-개관

27장 그래프의 표현과 정의

-27.1 도입
-27.2 그래프의 사용 예
-27.3 암시적 그래프 구조들
-27.4 그래프의 표현 방법

28장 그래프의 깊이 우선 탐색

-28.1 도입
-28.2 문제: 고대어 사전 (문제 ID: DICTIONARY, 난이도: 하)
-28.3 풀이: 고대어 사전
-28.4 오일러 서킷
-28.5 문제: 단어 제한 끝말잇기 (문제 ID: WORDCHAIN, 난이도: 하)
-28.6 풀이: 단어 제한 끝말잇기
-28.7 이론적 배경과 응용
-28.8 문제: 감시 카메라 설치 (문제 ID: GALLERY, 난이도: 중)
-28.9 풀이: 감시 카메라 설치
-28.10 문제: 회의실 배정 (문제 ID: MEETINGROOM, 난이도: 상)
-28.11 풀이: 회의실 배정

29장 그래프의 너비 우선 탐색

-29.1 도입
-29.2 문제: Sorting Game (문제 ID: SORTGAME, 난이도: 중)
-29.3 풀이: Sorting Game
-29.4 문제: 어린이날 (문제 ID: CHILDRENDAY, 난이도: 상)
-29.5 풀이: 어린이날
-29.6 최단 경로 전략
-29.7 문제: 하노이의 탑 (문제 ID: HANOI4B, 난이도: 중)
-29.8 풀이: 하노이의 탑

30장 최단 경로 알고리즘

-30.1 도입
-30.2 다익스트라의 최단 경로 알고리즘
-30.3 문제: 신호 라우팅 (문제 ID: ROUTING, 난이도: 하)
-30.4 풀이: 신호 라우팅
-30.5 문제: 소방차 (문제 ID: FIRETRUCKS, 난이도: 중)
-30.6 풀이: 소방차
-30.7 문제: 철인 N종 경기 (문제 ID: NTHLON, 난이도: 상)
-30.8 풀이: 철인 N종 경기
-30.9 벨만-포드의 최단 경로 알고리즘
-30.10 문제: 시간여행 (문제 ID: TIMETRIP, 난이도: 중)
-30.11 풀이: 시간여행
-30.12 플로이드의 모든 쌍 최단 거리 알고리즘
-30.13 문제: 음주 운전 단속 (문제 ID: DRUNKEN, 난이도: 중)
-30.14 풀이: 음주 운전 단속
-30.15 문제: 선거 공약 (문제 ID: PROMISES, 난이도: 중)
-30.16 풀이: 선거 공약

31장 최소 스패닝 트리

-31.1 도입
-31.2 크루스칼의 최소 스패닝 트리 알고리즘
-31.3 프림의 최소 스패닝 트리 알고리즘
-31.4 문제: 근거리 네트워크 (문제 ID: LAN, 난이도: 하)
-31.5 풀이: 근거리 네트워크
-31.6 문제: 여행 경로 정하기 (문제 ID: TPATH, 난이도: 상)
-31.7 풀이: 여행 경로 정하기

32장 네트워크 유량

-32.1 도입
-32.2 포드-풀커슨 알고리즘
-32.3 네트워크 모델링
-32.4 문제: 승부 조작 (문제 ID: MATCHFIX, 난이도: 중)
-32.5 풀이: 승부 조작
-32.6 문제: 국책 사업 (문제 ID: PROJECTS, 난이도: 상)
-32.7 풀이: 국책 사업
-32.8 이분 매칭
-32.9 문제: 비숍 (문제 ID: BISHOPS, 난이도: 중)
-32.10 풀이: 비숍
-32.11 문제: 함정 설치 (문제 ID: TRAPCARD, 난이도: 상)
-32.12 풀이: 함정 설치
-32.13 더 공부할 거리

dwax1324/Algorithmic-Problem-Solving-Strategies