본문 바로가기

Problem Solving

 (85)
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번과정을 수행하면 다음과 같이 진행됩니다. 여기서 초록색 부분은 현재까지 정렬된 구..
1.-(1) 기본 정렬 알고리즘 - Selection Sort(선택정렬) 이번 시간에는 기본적인 정렬 알고리즘을 배울겁니다. 정렬 알고리즘은 정말 여러가지 있지만 오늘 다뤄볼 정렬은 Selection Sort (선택정렬) 입니다. 첫 시간이기에 쉬운 정렬 알고리즘을 다룹니다. 정수를 오름차순으로 정렬하므로 내림차순이나 다른 특정한 순서로 정렬하고 싶으면 조건을 바꾸시면 됩니다. 먼저 Selection Sort 입니다. Selection Sort 는 \( n \) 개의 수 중에 가장 작은 수를 찾아(혹은 가장 큰 수를 찾아) 아직 정렬되지 않은 부분의 맨 앞자리에 위치시키는 방법으로 정렬을 수행합니다. 위와 같이 정렬을 하고자 할 때, 1. 5, 1, 3, 4, 2 를 모두 확인하면서 가장 작은 수를 찾습니다. -> 이 때 가장 작은 수는 1 입니다. 2. 그럼 이 1과, 현재..
0. Intro 전북대학교 알고리즘 동아리 'COALA'에서 진행하는 기초 알고리즘 튜터링 내용을 기록합니다. 이 튜터링을 진행하기에 앞서 필요한 지식은 다음과 같습니다. 1. C/C++ 기본 문법에 대해 알고 있어야합니다. 2. 함수 사용 및 재귀함수가 무엇인지 알고 있어야 합니다. 알고리즘 문제를 잘 해결하기 위해서는 3가지가 필요합니다. 1. 여러 알고리즘, 자료구조 등 배경지식이 필요합니다. 2. 배경지식을 현재 문제 상황에 맞게 잘 선택, 변형할 줄 아는 능력(문제해결능력)이 필요합니다. 3. 생각한 풀이를 코드로 나타낼 수 있는 능력(구현력)이 필요합니다. 우리는 이 세가지 능력을 기르는 연습을 해야합니다. www.acmicpc.net Baekjoon Online Judge Baekjoon Online Jud..

티스토리툴바