일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- backtracking
- priority_queue
- 분할정복
- 유니온파인드
- BOJ
- 다이나믹프로그래밍
- 문자열
- 그리디
- 세그먼트트리
- 분리집합
- Greedy
- 알고스팟
- Algospot
- 동적계획법
- 이분탐색
- DFS
- 재귀
- 누적합
- 스택
- 알고리즘문제해결전략
- 백준
- stack
- 너비우선탐색
- 완전탐색
- BFS
- 백트래킹
- union-find
- acm
- DP
- 종만북
- Today
- Total
목록Problem Solving/BOJ 문제풀이 (34)
DAMPER's blog
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/LWnmI/btq4SbK7A8C/teKwtxmX4buKy0bFJCvSWK/img.png)
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 한 학생당 한 명만 지목할 수 있으므로 단조로운 형태의 그래프가 형성된다. 위 표를 그래프로 그려보면 다음과 같다. 이 때, 사이클을 형성하는 그룹({3}, {4, 6, 7})만 팀에 속하고, 나머지는 팀에 속하지 못한다. dfs로 해당 루트에 group number를 부여해 이미 왔던 곳인데 group number가 같다면 사이클이 형성된 것이므로 해당 갯수만큼 모두 합하여 전체 노드 갯수에서 빼면 ..
https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 최대 힙과 최소 힙 둘 다 사용하여, 작은 쪽 반은 최대 힙에 저장하고, 큰쪽 반은 최소 힙에 저장하여 해결할 수 있는 문제이다. 처음 문제를 보고 힙을 쓸 생각은 했지만, 힙 2개를 사용할 생각을 못했다. 힙을 써야겠다고 생각한 이유 문제에서 어떤 입력값이 주어질 때마다 정렬을 해야하는 경우 (다수 그리디 문제에서 이런 문제가 있음.) 힙을 써야한다고 생각했다. 이 문제에서는 어..
https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-와샬 알고리즘 기본 문제. 플로이드-와샬 알고리즘은 '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하는 알고리즘이다. 플로이드-와샬 알고리즘의 핵심 아이디어는 '거쳐가는 정점'을 기준으로 최단거리는 구하는 것이다. i 정점으로부터 j 정점으로 갈 때, k정점을 지나서 가는 경로가 더 빠른지, 다른 경로 빠른지 구하면 된다. DP적인 성격을 띄며 어떤 경로가 지금까지 확인해본 경로보다..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/b41FD3/btq4VNbep6r/7Y63HURUkS7nSuFBh6BOIk/img.png)
https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net \( N \times N \) 개의 수가 \( N \times N \) 크기의 표에 채워져 있고 x1행 y1열부터, x2행 y2열까지의 합을 구하는 프로그램을 작성하는 문제. DP 문제로, 1행 1열 부터 자기자신까지의 합을 저장하여 DP 배열을 만든다. \( DP[x][y] = DP[x-1][y] + DP[x][y-1] - DP[x-1][y-1] + A..
www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 처음엔 플로이드 와샬 문제인 줄 알았지만 \( 1 \leq N \leq 1000 \) 이라 고민을 많이 했던 문제. 플로이드 와샬 문제라고 생각한 이유는 각각의 노드부터 x까지의 거리와 x부터 각각의 노드까지의 거리를 알아야 했기 때문이다. 단방향 그래프이기 때문에 각각의 노드부터 x까지의 거리와 x부터 각각의 노드까지의 거리가 같지않다. 그래서 '거의' 모든 경로를 알아야한다고 ..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/dBDU3T/btq4c1gWZAx/7BWhiWxdY79Wx3AgM6gOK1/img.png)
www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 딱 실버 분할정복 문제. '-'만 \( 3^{N} \)개 있는 문자열을 3등분으로 나누어 가운데 부분은 공백(space)로 바꾸고 왼쪽, 오른쪽은 다시 같은 작업을 반복하는 문제. 다음 그림과 같이 (부분)문자열의 첫번째 인덱스를 start로 하고, 3등분한 문자열의 오른쪽 부분의 첫번째 인덱스를 end 라고 하자. size를 3등분된 문자열의 크기라고 할 때, end = start+size+size 라고 할 ..