BOJ 길라잡이 (Beta)

Problem Solving

BOJ 길라잡이 (Beta)

Ryute 2019. 2. 12. 02:05

내년 동아리 활동을 대비해서 만들어 놓는 [BOJ를 여행하는 히치하이커를 위한 안내서]입니다.

아직 미완성이라 부족한 부분이 있습니다. 보완해야 할 것 같은 부분은 댓글로 달아주시면 감사하겠습니다.

<정보올림피아드/알고리즘 과외 합니다>

ryute.tistory.com/68

<활용 안내>

한 세트는 총 4개의 소단원으로 구분되어 있습니다. 각 소단원에는 4~5개정도의 문제가 실려 있으며, 난이도 순은 아닙니다. *가 달린 문제는 심화 문제이거나 매우 유사한 문제입니다. 알고리즘 초보 딱지를 떼기 위한 목적으로 다양한 유형의 기초 문제들을 계단식으로 학습할 수 있도록 주제들을 배치하였습니다. C를 문제 해결에 무리 없이 활용할 수 있는 수준에 도달했을 때 시작하는 것을 전제 조건으로 하였습니다.

<목차>

1-1. 탐색과 정렬 (1)

1-2. 기초 자료구조 (1)

1-3. 탐색과 정렬 (2)

1-4. 기초 자료구조 (2)

2-1. 백트래킹 (1)

2-2. 기초 수학 (1)

2-3. 백트래킹 (2)

2-4. 기초 수학 (2)

3-1. DFS와 BFS (1)

3-2. 기초 다이나믹 프로그래밍 (1)

3-3. DFS와 BFS (2)

3-4. 기초 다이나믹 프로그래밍 (2)

4-1. 그리디 알고리즘 (1)

4-2. 파라메트릭 서치 (1)

4-3. 힙

4-4. 그리디 알고리즘 (2)

5-1. 파라메트릭 서치 (2)

5-2. 다이나믹 프로그래밍 (1)

5-3. 분할 정복 (1)

5-4. 유니온-파인드 트리 (1)

6-1. 최단 경로 알고리즘 (1)

6-2. 다이나믹 프로그래밍 (2)

6-3. 최단 경로 알고리즘 (2)

6-4. 최소 스패닝 트리

7-1. 위상 정렬

7-2. 펜윅 트리와 세그먼트 트리 (1)

7-3. DFS와 BFS (3)

7-4. 펜윅 트리와 세그먼트 트리 (2)

8-1. 계산 기하 (1)

8-2. 선형 자료구조의 활용

8-3. 문자열 (1)

8-4. 다이나믹 프로그래밍 (3)

SET 1~4

https://www.acmicpc.net/workbook/view/2418

<SET 1>

1-1. 탐색과 정렬 (1)

A – 1920 수 찾기 https://www.acmicpc.net/problem/1920

B – 2750 수 정렬하기 https://www.acmicpc.net/problem/2750

C – 2751 수 정렬하기 2 https://www.acmicpc.net/problem/2751

D – 10989 수 정렬하기 3 https://www.acmicpc.net/problem/10989

E – 10815 숫자 카드 https://www.acmicpc.net/problem/10815

문제를 풀기 전에 공부하기: 이진 탐색, O(nlgn) 정렬, 카운팅 정렬

학습 유의사항: 이분 탐색과 정렬을 직접 구현해도 좋지만, std::binary_search, std::lower_bound/std::upper_bound, std::sort 등의 STL을 제대로 익히고 가자.

1-2. 기초 자료구조 (1)

A – 10828 스택 https://www.acmicpc.net/problem/10828

B – 10845 큐 https://www.acmicpc.net/problem/10845

C – 10866 덱 https://www.acmicpc.net/problem/10866

D – 1406 에디터 https://www.acmicpc.net/problem/1406

문제를 풀기 전에 공부하기: 스택, 큐, 덱, 연결 리스트

학습 유의사항: 역시 자료구조를 직접 구현하기보다는 std::stack, std::queue, std::deque, std::list를 활용하는 방향으로 학습해 보자.

1-3. 탐색과 정렬 (2)

A – 1026 보물 https://www.acmicpc.net/problem/1026

B – 1181 단어 정렬 https://www.acmicpc.net/problem/1181

C – 11650 좌표 정렬하기 https://www.acmicpc.net/problem/11650

C* - 11651 좌표 정렬하기 2 https://www.acmicpc.net/problem/11651

D – 10867 중복 빼고 정렬하기 https://www.acmicpc.net/problem/10867

E – 10816 숫자 카드 2 https://www.acmicpc.net/problem/10816

문제를 풀기 전에 공부하기: X

학습 유의사항: std::unique와 std::lower_bound와 std::upper_bound를 함께 활용해 개수를 구하는 테크닉은 매우 자주 등장한다. 또한 std::sort의 비교 함수 지정은 반드시 알아두어야 한다.

1-4. 기초 자료구조 (2)

A – 9012 괄호 https://www.acmicpc.net/problem/9012

B – 1874 스택 수열 https://www.acmicpc.net/problem/1874

C – 1158 조세퍼스 문제 https://www.acmicpc.net/problem/1158

D – 1966 프린터 큐 https://www.acmicpc.net/problem/1966

E – 5430 AC https://www.acmicpc.net/problem/5430

문제를 풀기 전에 공부하기: X

학습 유의사항: X

<SET 2>

2-1. 백트래킹 (1)

A – 6603 로또 https://www.acmicpc.net/problem/6603

B – 1182 부분집합의 합 https://www.acmicpc.net/problem/1182

C – 9095 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095

D – 9663 N-Queen https://www.acmicpc.net/problem/9663

문제를 풀기 전에 공부하기: 백트래킹

학습 유의사항: X

2-2. 기초 수학 (1)

A – 1037 약수 https://www.acmicpc.net/problem/1037

B – 1978 소수 찾기 https://www.acmicpc.net/problem/1978

C – 1929 소수 구하기 https://www.acmicpc.net/problem/1929

D – 2609 최대공약수와 최소공배수 https://www.acmicpc.net/problem/2609

문제를 풀기 전에 공부하기: 에라토스테네스의 체, 유클리드 호제법

학습 유의사항: 최대한 효율적으로 구현할 수 있는 방법을 생각하며 구현해 보자.

2-3. 백트래킹 (2)

A – 14889 스타트와 링크 https://www.acmicpc.net/problem/14889

B – 15686 치킨 배달 https://www.acmicpc.net/problem/15686

C – 2661 좋은수열 https://www.acmicpc.net/problem/2661

D – 2580 스도쿠 https://www.acmicpc.net/problem/2580

문제를 풀기 전에 공부하기: X

학습 유의사항: X

2-4. 기초 수학 (2)

A – 2485 가로수 https://www.acmicpc.net/problem/2485

B – 1644 소수의 연속합 https://www.acmicpc.net/problem/1644

C – 6588 골드바흐의 추측 https://www.acmicpc.net/problem/6588

C* - 15711 환상의 짝꿍 https://www.acmicpc.net/problem/15711

D – 1016 제곱 ㄴㄴ 수 https://www.acmicpc.net/problem/1016

문제를 풀기 전에 공부하기: X

학습 유의사항: X

<SET 3>

3-1. DFS와 BFS (1)

A – 1260 DFS와 BFS https://www.acmicpc.net/problem/1260

B – 2667 단지번호붙이기 https://www.acmicpc.net/problem/2667

C – 1697 숨바꼭질 https://www.acmicpc.net/problem/1697

D – 2178 미로 탐색 https://www.acmicpc.net/problem/2178

E – 2606 바이러스 https://www.acmicpc.net/problem/2606

문제를 풀기 전에 공부하기: DFS와 BFS

학습 유의사항: X

3-2. 기초 다이나믹 프로그래밍 (1)

A – 1003 피보나치 함수 https://www.acmicpc.net/problem/1003

B – 1463 1로 만들기 https://www.acmicpc.net/problem/1463

C – 2579 계단 오르기 https://www.acmicpc.net/problem/2579

D – 1932 정수 삼각형 https://www.acmicpc.net/problem/1932

E – 1149 RGB거리 https://www.acmicpc.net/problem/1149

문제를 풀기 전에 공부하기: 다이나믹 프로그래밍

학습 유의사항: 다이나믹 프로그래밍은 탑다운 방식과 바텀업 방식이 있다. 특정 문제는 둘 중 한 가지 방법으로만 풀리기도 하니, 둘의 장단점을 비교해서 두 방식으로 모두 문제를 해결할 수 있도록 하자.

3-3. DFS와 BFS (2)

A – 2206 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206

B – 7576 토마토 https://www.acmicpc.net/problem/7576

B* – 7569 토마토 https://www.acmicpc.net/problem/7569

C – 9466 텀 프로젝트 https://www.acmicpc.net/problem/9466

D – 2636 치즈 https://www.acmicpc.net/problem/2636

E – 2583 영역 구하기 https://www.acmicpc.net/problem/2583

문제를 풀기 전에 공부하기: X

학습 유의사항: X

3-4. 기초 다이나믹 프로그래밍 (2)

A – 11726 2×n 타일링 https://www.acmicpc.net/problem/11726

A* - 11727 2×n 타일링 2 https://www.acmicpc.net/problem/11727

B – 1912 연속합 https://www.acmicpc.net/problem/1912

C – 2293 동전 https://www.acmicpc.net/problem/2293

D – 2156 포도주 시식 https://www.acmicpc.net/problem/2156

E – 11052 카드 구매하기 https://www.acmicpc.net/problem/11052

F – 11053 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053

문제를 풀기 전에 공부하기: X

학습 유의사항: X

<SET 4>

4-1. 그리디 알고리즘 (1)

A – 11047 동전 0 https://www.acmicpc.net/problem/11047

B – 1931 회의실배정 https://www.acmicpc.net/problem/1931

C – 2217 로프 https://www.acmicpc.net/problem/2217

D – 2529 부등호 https://www.acmicpc.net/problem/2529

문제를 풀기 전에 공부하기: 그리디 알고리즘

학습 유의사항: X

4-2. 파라메트릭 서치 (1)

A – 2805 나무 자르기 https://www.acmicpc.net/problem/2805

B – 1654 랜선 자르기 https://www.acmicpc.net/problem/1654

C – 2869 달팽이는 올라가고 싶다 https://www.acmicpc.net/problem/2869

D – 2512 예산 https://www.acmicpc.net/problem/2512

E – 2110 공유기 설치 https://www.acmicpc.net/problem/2110

문제를 풀기 전에 공부하기: 파라메트릭 서치

학습 유의사항: X

4-3. 힙

A – 1927 최소 힙 https://www.acmicpc.net/problem/1927

A* - 11279 최대 힙 https://www.acmicpc.net/problem/11279

B – 11286 절댓값 힙 https://www.acmicpc.net/problem/11286

C – 1715 카드 정렬하기 https://www.acmicpc.net/problem/1715

D – 1655 가운데를 말해요 https://www.acmicpc.net/problem/1655

문제를 풀기 전에 공부하기: 힙

학습 유의사항: std::priority_queue에서 최대 힙의 구현체를 제공한다. 우선순위 큐에 연산자를 추가로 넣는 방법을 반드시 알고 가자.

4-4. 그리디 알고리즘 (2)

A – 1202 보석 도둑 https://www.acmicpc.net/problem/1202

B – 9576 책 나눠주기 https://www.acmicpc.net/problem/9576

C - 13305 주유소 https://www.acmicpc.net/problem/13305

C* – 1826 연료 채우기 https://www.acmicpc.net/problem/1826

D – 1422 숫자의 신 https://www.acmicpc.net/problem/1422

문제를 풀기 전에 공부하기: X

학습 유의사항: X

SET 5~8

https://www.acmicpc.net/workbook/view/2419

<SET 5>

5-1. 파라메트릭 서치 (2)

A – 1939 중량제한 https://www.acmicpc.net/problem/1939

B – 2585 경비행기 https://www.acmicpc.net/problem/2585

C – 3079 입국심사 https://www.acmicpc.net/problem/3079

D – 3090 차이를 최소로 https://www.acmicpc.net/problem/3090

문제를 풀기 전에 공부하기: X

학습 유의사항: X

5-2. 다이나믹 프로그래밍 (1)

A – 1890 점프 https://www.acmicpc.net/problem/1890

B – 1520 내리막길 https://www.acmicpc.net/problem/1520

C – 12015 가장 긴 증가하는 부분 수열 2 https://www.acmicpc.net/problem/12015

D – 9251 LCS https://www.acmicpc.net/problem/9251

D* - 9252 LCS 2 https://www.acmicpc.net/problem/9252

E – 11051 이항 계수 2 https://www.acmicpc.net/problem/11051

문제를 풀기 전에 공부하기: X

학습 유의사항: X

5-3. 분할 정복 (1)

A - 1992 쿼드 트리 https://www.acmicpc.net/problem/1992

B – 11729 하노이 탑 이동 순서 https://www.acmicpc.net/problem/11729

C – 10827 a^b https://www.acmicpc.net/problem/10827

D – 2261 가장 가까운 두 점 https://www.acmicpc.net/problem/2261

문제를 풀기 전에 공부하기: 분할 정복

학습 유의사항: X

5-4. 유니온-파인드 트리 (1)

A – 1717 집합의 표현 https://www.acmicpc.net/problem/1717

B – 4195 친구 네트워크 https://www.acmicpc.net/problem/4195

C – 1976 여행 가자 https://www.acmicpc.net/problem/1976

D – 10775 공항 https://www.acmicpc.net/problem/10775

문제를 풀기 전에 공부하기: 유니온-파인드 트리

학습 유의사항: X

<SET 6>

6-1. 최단 경로 알고리즘 (1)

A – 1753 최단경로 https://www.acmicpc.net/problem/1753

A* - 1916 최소비용 구하기 https://www.acmicpc.net/problem/1916

B – 1238 파티 https://www.acmicpc.net/problem/1238

C – 1261 알고스팟 https://www.acmicpc.net/problem/1261

C* - 4485 녹색 옷 입은 애가 젤다지? https://www.acmicpc.net/problem/4485

D –1504 특정한 최단 경로 https://www.acmicpc.net/problem/1504

문제를 풀기 전에 공부하기: 다익스트라 알고리즘

학습 유의사항: X

6-2. 다이나믹 프로그래밍 (2)

A – 2618 경찰차 https://www.acmicpc.net/problem/2618

B – 1915 가장 큰 정사각형 https://www.acmicpc.net/problem/1915

C – 11066 파일 합치기 https://www.acmicpc.net/problem/11066

D – 2631 줄세우기 https://www.acmicpc.net/problem/2631

문제를 풀기 전에 공부하기: X

학습 유의사항: X

6-3. 최단 경로 알고리즘 (2)

A – 11657 타임머신 https://www.acmicpc.net/problem/11657

B – 11404 플로이드 https://www.acmicpc.net/problem/11404

C – 10159 저울 https://www.acmicpc.net/problem/10159

D – 1613 역사 https://www.acmicpc.net/problem/1613

문제를 풀기 전에 공부하기: 벨만-포드 알고리즘, 플로이드 알고리즘

학습 유의사항: X

6-4. 최소 스패닝 트리

A - 1197 최소 스패닝 트리 https://www.acmicpc.net/problem/1197

B – 1647 도시 분할 계획 https://www.acmicpc.net/problem/1647

C – 2887 행성 터널 https://www.acmicpc.net/problem/2887

문제를 풀기 전에 공부하기: 크루스칼 알고리즘, 프림 알고리즘

학습 유의사항: 크루스칼 알고리즘이 프림 알고리즘보다 비교적 자주 쓰인다. 두 알고리즘 모두 MST에 대한 핵심적인 통찰을 담고 있으니 정당성을 생각해 보며 문제를 풀어 보자.

<SET 7>

7-1. 위상 정렬

A – 2252 줄 세우기 https://www.acmicpc.net/problem/2252

B – 1005 ACM Craft https://www.acmicpc.net/problem/1005

C – 1766 문제집 https://www.acmicpc.net/problem/1766

D – 3665 최종 순위 https://www.acmicpc.net/problem/3665

문제를 풀기 전에 공부하기: 위상 정렬

학습 유의사항: X

7-2. 펜윅 트리와 세그먼트 트리 (1)

A - 2042 구간 합 구하기 https://www.acmicpc.net/problem/2042

B – 2357 최솟값과 최댓값 https://www.acmicpc.net/problem/2357

C – 7578 공장 https://www.acmicpc.net/problem/7578

D – 11505 구간 곱 구하기 https://www.acmicpc.net/problem/11505

문제를 풀기 전에 공부하기: 펜윅 트리, 세그먼트 트리

학습 유의사항: X

7-3. DFS와 BFS (3)

A – 1967 트리의 지름 https://www.acmicpc.net/problem/1967

B – 14867 물통 https://www.acmicpc.net/problem/14867

C – 1726 로봇 https://www.acmicpc.net/problem/1726

D – 6087 레이저 통신 https://www.acmicpc.net/problem/6087

문제를 풀기 전에 공부하기: X

학습 유의사항: X

7-4. 펜윅 트리와 세그먼트 트리 (2)

A – 3653 영화 수집 https://www.acmicpc.net/problem/3653

B – 2243 사탕상자 https://www.acmicpc.net/problem/2243

C – 5676 음주 코딩 https://www.acmicpc.net/problem/5676

D – 1849 순열 https://www.acmicpc.net/problem/1849

E – 2336 굉장한 학생 https://www.acmicpc.net/problem/2336

문제를 풀기 전에 공부하기: X

학습 유의사항: X

<SET 8>

8-1. 계산 기하 (1)

A – 11758 CCW https://www.acmicpc.net/problem/11758

B – 2166 다각형의 면적 https://www.acmicpc.net/problem/2166

C – 3679 단순 다각형 https://www.acmicpc.net/problem/3679

D – 6487 두 직선의 교차 여부 https://www.acmicpc.net/problem/6487

E – 1708 볼록 껍질 https://www.acmicpc.net/problem/1708

문제를 풀기 전에 공부하기: 기초적인 기하 알고리즘(CCW, 면적 구하기, 직선 교차 구하기 등), 볼록 껍질 구하는 알고리즘(Graham’s Scan, Andrew’s Algorithm)

학습 유의사항: X

8-2. 선형 자료구조의 활용

A – 2493 탑 https://www.acmicpc.net/problem/2493

B – 6198 옥상 정원 꾸미기 https://www.acmicpc.net/problem/6198

C – 6549 히스토그램에서 가장 큰 직사각형 https://www.acmicpc.net/problem/6549

D – 11003 최솟값 찾기 https://www.acmicpc.net/problem/11003

문제를 풀기 전에 공부하기: 슬라이딩 윈도우

학습 유의사항: X

8-3. 문자열 (1)

A – 1786 찾기 https://www.acmicpc.net/problem/1786

B – 1305 광고 https://www.acmicpc.net/problem/1305

C – 11656 접미사 배열 https://www.acmicpc.net/problem/11656

D – 5052 전화번호 목록 https://www.acmicpc.net/problem/5052

문제를 풀기 전에 공부하기: KMP 알고리즘, 접미사 배열

학습 유의사항: X

8-4. 다이나믹 프로그래밍 (3)

A – 2098 외판원 순회 https://www.acmicpc.net/problem/2098

B – 1102 발전소 https://www.acmicpc.net/problem/1102

C – 2718 타일 채우기 https://www.acmicpc.net/problem/2718

D – 1657 두부 장수 장홍준 https://www.acmicpc.net/problem/1657

문제를 풀기 전에 공부하기: 비트마스크

학습 유의사항: X

<SET 9>

9-1. 유니온-파인드 트리 (2)

A - 2463 비용 https://www.acmicpc.net/problem/2463

B - 13306 트리 https://www.acmicpc.net/problem/13306

C - 15586 Mootube (Gold) https://www.acmicpc.net/problem/15586

문제를 풀기 전에 공부하기: X

학습 유의사항: X

9-2. 다이나믹 프로그래밍 (4)

A – 2449 전구 https://www.acmicpc.net/problem/2449

B – 16157 블로그 https://www.acmicpc.net/problem/16157

C – 2213 트리의 독립집합 https://www.acmicpc.net/problem/2213

D – 2330 기지국 https://www.acmicpc.net/problem/2300

문제를 풀기 전에 공부하기: X

학습 유의사항: X

9-3. 세그먼트 트리의 활용 (1)

A – 10999 구간 합 구하기 2 https://www.acmicpc.net/problem/10999

B – 1395 스위치 https://www.acmicpc.net/problem/1395

C – 12844 XOR https://www.acmicpc.net/problem/12844

D – 2820 자동차 공장 https://www.acmicpc.net/problem/2820

문제를 풀기 전에 공부하기: 레이지 프로파게이션

학습 유의사항: X

9-4. DFS 스패닝 트리의 활용 (1)

A – 11266 단절점 https://www.acmicpc.net/problem/11266

B – 11400 단절선 https://www.acmicpc.net/problem/11400

C – 2150 Strongly Connected Component https://www.acmicpc.net/problem/2150

D – 1199 오일러 회로 https://www.acmicpc.net/problem/1199

문제를 풀기 전에 공부하기: DFS 스패닝 트리, 타잔의 알고리즘, 코사라주의 알고리즘, 오일러 투어

학습 유의사항: 학습량이 많습니다. 타잔과 코사라주의 알고리즘의 차이점을 명확하게 비교하면서 학습합시다.

----------------------------

아래는 언젠가 추가될 단원들입니다. 좋은 문제가 있다면 추천 바랍니다.

?-1. 계산 기하 (2)

B - 4181 Convex Hull https://www.acmicpc.net/problem/4181

C – 9240 로버트 후드 https://www.acmicpc.net/problem/9240

D – 13310 먼 별 https://www.acmicpc.net/problem/13310

E – 1688 지민이의 테러 https://www.acmicpc.net/problem/1688

문제를 풀기 전에 공부하기: 로테이팅 캘리퍼스, 포인트 인 폴리곤 테스트

학습 유의사항: X

?-2. 문자열 (2)

A – 5670 휴대폰 자판 https://www.acmicpc.net/problem/5670

B -9248 Suffix Array https://www.acmicpc.net/problem/9248

C - 9250 문자열 집합 판별 https://www.acmicpc.net/problem/9250

D – 1701 Cubeditor https://www.acmicpc.net/problem/1701

문제를 풀기 전에 공부하기: LCP 배열, 아호-코라식 알고리즘

학습 유의사항: X

X-1. DFS 스패닝 트리의 활용 (2)

A – 3682 동치 증명 https://www.acmicpc.net/problem/3682

B – 4013 ATM https://www.acmicpc.net/problem/4013

C – 11277 2-SAT – 3 https://www.acmicpc.net/problem/11280

C* - 11281 2-SAT – 4 https://www.acmicpc.net/problem/11281

D – 16367 TV Show Game https://www.acmicpc.net/problem/16367

문제를 풀기 전에 공부하기: 2-SAT

학습 유의사항: X