어려운 알고리즘 문제

1/4: 다이나믹 프로그래밍

어려운 다이나믹을 배워봅니다.

• 격자판 채우기: https://www.acmicpc.net/problem/1648
• 연습 시즌: https://www.acmicpc.net/problem/9023
• 트리의 독립집합: https://www.acmicpc.net/problem/2213
• 팰린드롬 경로: https://www.acmicpc.net/problem/2172
• Sequence: https://www.acmicpc.net/problem/2291
• 택배: https://www.acmicpc.net/problem/1866
• 가로등 끄기: https://www.acmicpc.net/problem/2315
• 사수아탕: https://www.acmicpc.net/problem/2419
• 팰린드롬: https://www.acmicpc.net/problem/1243

1/5: RMQ, LCA (구간의 최소값, 가장 가까운 공통 조상)

RMQ: 구간의 최소값, 구간의 합

• Segment Tree
• Binary Indexed Tree (Fenwick Tree)
• 2D-BIT
• Segment Tree Lazy Propagation
• 구간 합 구하기: https://www.acmicpc.net/problem/2042
• 구간 합 구하기 2: https://www.acmicpc.net/problem/10999
• 구간 합 구하기 3: https://www.acmicpc.net/problem/11658
• 사탕상자: https://www.acmicpc.net/problem/2243
• 공장: https://www.acmicpc.net/problem/7578
• 순열: https://www.acmicpc.net/problem/1849
• 굉장한 학생: https://www.acmicpc.net/problem/2336
• 영화 수집: https://www.acmicpc.net/problem/3653

LCA: 가장 가까운 공통 조상

• 정점들의 거리: https://www.acmicpc.net/problem/1761
• LCA 2: https://www.acmicpc.net/problem/11438
• 도로 네트워크: https://www.acmicpc.net/problem/3176

1/6 강한 연결 요소(SCC), 단절점(Articulation Point), 단절선(Bridge), 2-SAT

강한 연결 요소(SCC), 단절점(Articulation Point), 단절선(Bridge)

• Strongly Connected Component: https://www.acmicpc.net/problem/2150
• 단절점: https://www.acmicpc.net/problem/11266
• 단절선: https://www.acmicpc.net/problem/11400
• 동치 증명: https://www.acmicpc.net/problem/3682
• Urban planning: https://www.acmicpc.net/problem/11097
• ATM: https://www.acmicpc.net/problem/4013
• 교통 체계: https://www.acmicpc.net/problem/1734

2-SAT

• 가위바위보: https://www.acmicpc.net/problem/2207
• Perfect Election: https://www.acmicpc.net/problem/3747
• TORNJEVI: https://www.acmicpc.net/problem/3153

1/11, 1/12: 네트워크 플로우, 이분 매칭

네트워크 플로우

• Total Flow: https://www.acmicpc.net/problem/6086
• Crucial Links: https://www.acmicpc.net/problem/5651
• 돼지 잡기: https://www.acmicpc.net/problem/1658
• Avoiding the Apocalypse: https://www.acmicpc.net/problem/10319
• Chess competition: https://www.acmicpc.net/problem/5424
• 도시 왕복하기: https://www.acmicpc.net/problem/2316
• 숫자판 만들기: https://www.acmicpc.net/problem/2365

이분 매칭

• 열혈강호: https://www.acmicpc.net/problem/11375
• 열혈강호 2: https://www.acmicpc.net/problem/11376
• 열혈강호 3: https://www.acmicpc.net/problem/11377
• 열혈강호 4: https://www.acmicpc.net/problem/11378
• 축사 배정: https://www.acmicpc.net/problem/2188
• 노트북의 주인을 찾아서: https://www.acmicpc.net/problem/1298
• 소수 쌍: https://www.acmicpc.net/problem/1017
• 상어의 저녁식사 https://www.acmicpc.net/problem/1671
• 흔한 수열 문제: https://www.acmicpc.net/proble/2787
• 스타 대결: https://www.acmicpc.net/problem/1031

Minimum Cut

• 떡국: https://www.acmicpc.net/problem/1127
• 학교 가지마!: https://www.acmicpc.net/problem/1420
• No Smoking, Please: https://www.acmicpc.net/problem/5406

이분 탐색 + 이분 매칭

• 주차장: https://www.acmicpc.net/problem/1348

Minimum Vertex Cover

• 돌멩이 제거: https://www.acmicpc.net/problem/1867
• 게시판 구멍 막기: https://www.acmicpc.net/problem/2414
• N-Rook: https://www.acmicpc.net/problem/1760
• 비숍 2: https://www.acmicpc.net/problem/2570

Maximum Independent Set

• 컨닝 2: https://www.acmicpc.net/problem/11014

1/13: MCMF

• 책 구매하기: https://www.acmicpc.net/problem/11405
• 책 구매하기 2: https://www.acmicpc.net/problem/11406
• 책 구매하기 3: https://www.acmicpc.net/problem/11407
• 열혈강호 5: https://www.acmicpc.net/problem/11408
• 열혈강호 6: https://www.acmicpc.net/problem/11409
• 선발 명단: https://www.acmicpc.net/problem/3980
• 왕복 여행: https://www.acmicpc.net/problem/2311
• 제독: https://www.acmicpc.net/problem/3640
• 최고의 팀 만들기: https://www.acmicpc.net/problem/1633
• 풍선: https://www.acmicpc.net/problem/4716
• 경찰: https://www.acmicpc.net/problem/1585
• Concert Hall Scheduling: https://www.acmicpc.net/problem/3938
• Crazy Bits: https://www.acmicpc.net/problem/6267
• 두부장수 장홍준 2: https://www.acmicpc.net/problem/11111
• 제주도: https://www.acmicpc.net/problem/9413
• 칙칙폭폭: https://www.acmicpc.net/problem/11410
• Train Tickets: https://www.acmicpc.net/problem/11122
• 스타 대결: https://www.acmicpc.net/problem/1031
• Catering: https://www.acmicpc.net/problem/10786

1/25: 문자열 알고리즘

KMP

• KMP는 왜 KMP일까? https://www.acmicpc.net/problem/2902
• 찾기: https://www.acmicpc.net/problem/1786
• 광고: https://www.acmicpc.net/problem/1305
• Cubeditor: https://www.acmicpc.net/problem/1701

Trie

• Boggle: https://www.acmicpc.net/problem/9202
• 전화번호 목록: https://www.acmicpc.net/problem/5052
• 아름다운 이름: https://www.acmicpc.net/problem/3080

Aho-corasick

• 문자열 집합 판별: https://www.acmicpc.net/problem/9250
• 돌연변이: https://www.acmicpc.net/problem/10256
• Word Puzzles: https://www.acmicpc.net/problem/6300

Suffix Array

• 서로 다른 부분 문자열의 개수: https://www.acmicpc.net/problem/11478
• 서로 다른 부분 문자열의 개수 2: https://www.acmicpc.net/problem/11479
• 공통 부분 문자열: https://www.acmicpc.net/problem/5582
• Period: https://www.acmicpc.net/problem/3779
• Cubeditor: https://www.acmicpc.net/problem/1701

1/26: 알고리즘 게임

• 돌 게임: https://www.acmicpc.net/problem/9655
• 돌 게임 2: https://www.acmicpc.net/problem/9656
• 돌 게임 3: https://www.acmicpc.net/problem/9657
• 돌 게임 4: https://www.acmicpc.net/problem/9658
• 돌 게임 5: https://www.acmicpc.net/problem/9659
• 돌 게임 6: https://www.acmicpc.net/problem/9660
• 돌 게임 7: https://www.acmicpc.net/problem/9661
• 돌 게임 8: https://www.acmicpc.net/problem/9662
• 님 게임: https://www.acmicpc.net/problem/11694
• 표 게임: https://www.acmicpc.net/problem/11695
• 작은 직사각형: https://www.acmicpc.net/problem/1603
• John: https://www.acmicpc.net/problem/3754
• 금화 게임: https://www.acmicpc.net/problem/5386
• A Coin Game: https://www.acmicpc.net/problem/6000
• Nim: https://www.acmicpc.net/problem/9157
• Number Game: https://www.acmicpc.net/problem/10563
• 수학 게임: https://www.acmicpc.net/problem/2862

1/27: 기하 알고리즘

CCW

• 교차점: https://www.acmicpc.net/problem/10255

Convex Hull (볼록 껍질)

• 볼록 껍질: https://www.acmicpc.net/problem/1708
• 감옥 건설: https://www.acmicpc.net/problem/2254
• 벽과 못: https://www.acmicpc.net/problem/2964
• 점 분리: https://www.acmicpc.net/problem/3878
• 안전 구역: https://www.acmicpc.net/problem/3970
• Convex Hull: https://www.acmicpc.net/problem/4181
• Gunslinger: https://www.acmicpc.net/problem/5377
• Find the Treasure: https://www.acmicpc.net/problem/5383
• 땅 따먹기: https://www.acmicpc.net/problem/6171
• Wall: https://www.acmicpc.net/problem/7420
• 로버트 후드: https://www.acmicpc.net/problem/9240
• 고속도로: https://www.acmicpc.net/problem/10254
• Citadel Construction: https://www.acmicpc.net/problem/10321

Sweeping Algorithm:

• 가장 가까운 두 점: https://www.acmicpc.net/problem/2261
• City Park: https://www.acmicpc.net/problem/10534
• DOSTAVA: https://www.acmicpc.net/problem/10862
• 허후민: https://www.acmicpc.net/problem/1617
• 과수원: https://www.acmicpc.net/problem/1831
• 선 긋기: https://www.acmicpc.net/problem/2170
• 직사각형의 합집합: https://www.acmicpc.net/problem/2185
• 시장 선거 포스터: https://www.acmicpc.net/problem/2370
• 보이는 정사각형: https://www.acmicpc.net/problem/2397
• 아스키 거리: https://www.acmicpc.net/problem/2809
• 수상 택시: https://www.acmicpc.net/problem/2836
• 고속도로 구매: https://www.acmicpc.net/problem/3083
• 울타리: https://www.acmicpc.net/problem/3119
• November Rain: https://www.acmicpc.net/problem/3455
• Mummy Madness: https://www.acmicpc.net/problem/4223
• Skyscrapers: https://www.acmicpc.net/problem/7882
• 핀볼: https://www.acmicpc.net/problem/9244
• 위성 사진: https://www.acmicpc.net/problem/9318
• 원 영역: https://www.acmicpc.net/problem/10000