본문 바로가기

전체 글

 (104)
9466 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 한 학생당 한 명만 지목할 수 있으므로 단조로운 형태의 그래프가 형성된다. 위 표를 그래프로 그려보면 다음과 같다. 이 때, 사이클을 형성하는 그룹({3}, {4, 6, 7})만 팀에 속하고, 나머지는 팀에 속하지 못한다. dfs로 해당 루트에 group number를 부여해 이미 왔던 곳인데 group number가 같다면 사이클이 형성된 것이므로 해당 갯수만큼 모두 합하여 전체 노드 갯수에서 빼면 ..
1655 가운데를 말해요 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 최대 힙과 최소 힙 둘 다 사용하여, 작은 쪽 반은 최대 힙에 저장하고, 큰쪽 반은 최소 힙에 저장하여 해결할 수 있는 문제이다. 처음 문제를 보고 힙을 쓸 생각은 했지만, 힙 2개를 사용할 생각을 못했다. 힙을 써야겠다고 생각한 이유 문제에서 어떤 입력값이 주어질 때마다 정렬을 해야하는 경우 (다수 그리디 문제에서 이런 문제가 있음.) 힙을 써야한다고 생각했다. 이 문제에서는 어..
11404 플로이드 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-와샬 알고리즘 기본 문제. 플로이드-와샬 알고리즘은 '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하는 알고리즘이다. 플로이드-와샬 알고리즘의 핵심 아이디어는 '거쳐가는 정점'을 기준으로 최단거리는 구하는 것이다. i 정점으로부터 j 정점으로 갈 때, k정점을 지나서 가는 경로가 더 빠른지, 다른 경로 빠른지 구하면 된다. DP적인 성격을 띄며 어떤 경로가 지금까지 확인해본 경로보다..
11660 구간 합 구하기 5 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..
1238 파티 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부터 각각의 노드까지의 거리가 같지않다. 그래서 '거의' 모든 경로를 알아야한다고 ..
4779 칸토어 집합 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 라고 할 ..
2. 재귀 함수 저번 글까지는 맛보기였고 지금부터가 진짜입니다. 이번 시간에 진행할 내용은 재귀함수 입니다. 재귀함수는 알고리즘에 있어서 매우매우 중요합니다. 여러 알고리즘들이 재귀함수를 베이스로 가지고 있기도 하고, 재귀 함수 대한 이해 없이는 진행할 수 없는 알고리즘도 수없이 많습니다. 재귀함수는 자기 자신을 호출하는 함수입니다. 반복문을 사용하는 코드는 항상 재귀함수를 통해 구현이 가능합니다.(물론 그 반대도 가능합니다.) 우리가 어떤 문제를 재귀함수로 푼다는 것은, 귀납적인 방법으로 문제를 푼다는 뜻입니다. 수학적 귀납법을 생각해보면 1. 기본 가정 2. 귀납 가정 3. 귀납 증명 이 세가지 단계를 통해 우리는 귀납적으로 증명할 수 있습니다. 예를 들어, \( 1+3+5+ ... + (2n-1) = n^{2} \..
1.-(2) 기본 정렬 알고리즘 - Bubble Sort (버블정렬) 이번 시간에 다뤄볼 알고리즘은 저번 시간에 이어 기본 정렬 알고리즘인 Bubble Sort 입니다. Bubble Sort는 Selection Sort와 함께 가장 기본적인 정렬 알고리즘에 속합니다. Bubble Sort의 동작 과정 1. 첫번째 수 부터 N-1 번째 수 까지 가면서 해당 수와 바로 다음 수를 비교한다. 2. 해당 수 보다 바로 다음 수가 더 작다면, 둘의 자리를 바꿔 큰 수가 뒤에 오도록 한다. 3. N번째 수에 도달하게 되면 그 자리에는 가장 큰 수가 오게된다. 4. 1~3 과정을 N-2번째 수 까지, N-3번째 수까지 ... ... 첫번째 수 까지 하게되면 모든 수가 오름차순으로 정렬된다. 1, 2, 3번과정을 수행하면 다음과 같이 진행됩니다. 여기서 초록색 부분은 현재까지 정렬된 구..

티스토리툴바