boj - 단계별로 풀어보기

boj 단계별로 풀어보기를 정리하고자 합니다.

(기준일: 2021.12.28)

 

 

단계	제목	설명	총 문제
1	입출력과 사칙연산	입력, 출력과 사칙연산을 연습해 봅시다.	11
2	if문	if문을 사용해 봅시다.	5
3	for문	for문을 사용해 봅시다.	11
4	while문	while문을 사용해 봅시다.	3
5	1차원 배열	배열을 사용해 봅시다.	7
6	함수	함수를 정의하면 코드가 깔끔해지고 관리하기 쉬워집니다.	3
7	문자열	문자열을 다루는 문제들을 해결해 봅시다.	10
8	기본 수학 1	수학 문제로 수학적 사고력을 길러 봅시다.	9
9	기본 수학 2	소수와 기하를 다뤄 봅시다.	11
10	재귀	재귀함수를 다뤄 봅시다.	4
11	브루트 포스	가장 간단한 알고리즘인, 모든 경우의 수를 검사하는 브루트 포스 알고리즘을 배워 봅시다.	5
12	정렬	배열의 원소를 순서대로 나열하는 알고리즘을 배워 봅시다.	10
13	집합과 맵	수정 예정	0
14	백트래킹	모든 경우를 탐색하는 백트래킹 알고리즘을 배워 봅시다.	8
15	동적 계획법 1	기초적인 동적 계획법 문제들을 풀어봅시다.	16
16	그리디 알고리즘	특정 상황에서 성립하는 그리디 알고리즘을 배워 봅시다.	5
17	정수론 및 조합론	정수론과 조합론을 배워 봅시다.	12
18	스택	스택을 구현하고 사용해 봅시다.	6
19	큐, 덱	큐와 덱을 구현하고 사용해 봅시다.	7
20	분할 정복	재귀를 응용하는 알고리즘, 분할 정복을 익혀 봅시다.	10
21	이분 탐색	이분 탐색 알고리즘을 배워 봅시다.	7
22	우선순위 큐	가장 작은/큰 원소를 뽑는 자료구조를 배워 봅시다.	4
23	동적 계획법 2	조금 더 어려운 동적 계획법 문제를 풀어 봅시다.	7
24	DFS와 BFS	그래프를 순회하는 알고리즘을 배워 봅시다.	11
25	최단 경로	그래프의 간선에 가중치가 없으면 BFS로 최단거리를 찾을 수 있습니다. 가중치가 있다면 어떨까요?	7
26	투 포인터	투 포인터 알고리즘과 meet in the middle 알고리즘을 배워 봅시다.	5
27	동적 계획법과 최단거리 역추적	지금까지는 최솟값, 최댓값, 최단거리만 찾았습니다. 이번에는 실제 최적해와 최단경로를 찾아 봅시다.	9
28	트리	대표적인 그래프 종류 중 하나인 트리를 다뤄 봅시다.	7
29	유니온 파인드	유니온 파인드(또는 disjoint set, 상호 배타적 집합, ...) 자료구조를 배워 봅시다.	4
30	최소 신장 트리	최소 비용으로 그래프의 모든 정점을 연결해 봅시다.	6
31	트리에서의 동적 계획법	트리에 동적 계획법을 적용해 봅시다.	4
32	기하	조금 더 어려운 기하 문제를 풀어 봅시다.	8
	boj 2166 - 다각형의 면적
	boj 11758 - CCW
	boj 17386 - 선분 교차 1
	boj 17387 - 선분 교차 2
	boj 20419 - 선분 교차 3
	boj 2162 - 선분 그룹
	boj 7869 - 두 원
	boj 1069 - 집으로
33	동적 계획법 3	비트마스크를 배우고, 동적 계획법에 적용해 봅시다. 그 후에는 선형이 아니라 원형으로 구성된 문제를 다룹니다.	6
34	문자열 알고리즘 1	KMP 알고리즘과 트라이 자료구조를 다뤄 봅시다.	7
35	위상 정렬	간선에 방향이 있는 그래프의 정점을 나열해 역방향이 없게 만드는 알고리즘을 다뤄 봅시다.	4
36	최소 공통 조상	트리에서 두 정점의 최소 공통 조상을 구하는 자료구조를 배워 봅시다.	5
	boj 3584 - 가장 가까운 공통 조상
	boj 17435 - 합성함수와 쿼리
	boj 11438 - LCA2
	boj 3176 - 도로 네트워크
	boj 13511 - 트리와 쿼리 2
37	강한 연결 요소	Strongly connected component를 다뤄 봅시다.	8
38	세그먼트 트리	구간 쿼리를 효율적으로 수행하는 자료구조를 배워 봅시다.	9
39	스위핑	스위핑 알고리즘을 배워 봅시다.	6
40	동적 계획법 4	동적 계획법의 세계는 끝이 없습니다.	10
41	컨벡스 헐	모든 점을 포함하는 가장 작은 볼록 다각형을 만들어 봅시다.	5
42	이분 매칭	이분 매칭 알고리즘에 대해 배워 봅시다.	6
43	네트워크 플로우	네트워크 플로우 알고리즘에 대해 알아봅시다.	8
44	MCMF	최소 비용으로 최대 유량을 흘려 봅시다.	4
45	더 어려운 수학	포함-배제 정리, 빠른 소수 판정, 중국인의 나머지 정리 등을 다룹니다.	5
46	고속 푸리에 변환	두 다항식을 O(NlogN) 만에 곱할 수 있다고 하면 믿으시겠습니까? 놀랍게도 가능합니다!	5
47	문자열 알고리즘 2	매니커, Z, 접미사 배열, 아호 코라식을 배워 봅시다	12
48	어려운 구간 쿼리	세그먼트 트리 with lazy propagation, Mo's algorithm, 그리고 persistent segment tree (추가 예정)를 배워 봅시다.	8
49	동적 계획법 최적화	다양한 동적 계획법 최적화 테크닉을 배워 봅시다.	8
50	매우 어려운 자료구조와 알고리즘 (수정 예정)	일반적인 대회에서 통용되는 알고리즘의 최전선까지 가 봅시다.	10

 

37. 최소신장 트리

최소 비용으로 그래프의 모든 정점을 연결해 봅시다. [프림 설명 포스트] [크루스칼 설명 포스트] [백준 링크]

 

1. boj 9372 - 상근이의 여행 [포스트] [백준]

2. boj 1197 - 최소 스패닝 트리  [포스트] [백준]

3. boj 4386 - 별자리 만들기  [포스트] [백준]

4. boj 1774 - 우주신과의 요감  [포스트] [백준]

5. boj 6497 - 전력난  [포스트] [백준]

6. boj 17472 - 다리만들기 2  [포스트] [백준]

 

44. 세그먼트 트리

구간 쿼리를 효율적으로 수행하는 자료구조를 배워 봅시다. [알고리즘 설명 포스트] [백준 링크]

 

1. boj 2042 - 구간 합 구하기 [포스트] [백준]
2. boj 11505 - 구간 곱 구하기 [포스트] [백준]
3. boj 2357 - 최솟값과 최댓값 [포스트] [백준]
4. boj 1517 - 버블 소트 [포스트] [백준]
5. boj 9345 - 디지털 비디오 디스크(DVDs) [포스트] [백준]
6. boj 16975 - 수열과 쿼리 21 [포스트] [백준]
7. boj 12899 - 데이터 구조 [포스트] [백준]
8. boj 1168 - 요세푸스 문제 2 [포스트] [백준]

 

46. 스위핑

스위핑 알고리즘을 배워 봅시다. [알고리즘 설명 포스트] [백준 링크]

 

1. boj 2170 - 선 긋기 [포스트] [백준]

2. boj 2836 - 수상 택시 [포스트] [백준]

3. boj 5419 - 북서풍 [포스트] [백준]

4. boj 17131 - 여우가 정보섬에 올라온 이유 [포스트] [백준]

5. boj 7626 - 직사각형 [포스트] [백준]

6. boj 11012 - Egg [포스트] [백준]

 

49. 이분 매칭

이분 매칭 알고리즘에 대해서 배워봅시다. [알고리즘 설명 포스트] [백준 링크]

 

1. boj 11375 - 열혈강호 [포스트] [백준]

2. boj 11376 - 열혈강호2 [포스트] [백준]

3. boj 1017 - 소수쌍 [포스트] [백준]

4. boj 1617 - 상어의 저녁식사 [포스트] [백준]

5. boj 1867 - 돌멩이 제거 [포스트] [백준]

6. boj 11014 - 컨닝 2 [포스트] [백준] - 미완성