코후닝

알고리즘 분류: 수학, 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 【 풀이 】 수학적 사고와 동적계획법을 이용하여 해결하는 문제이다. 문제에서 원하는 건 피보나치 수를 저장하는 배열 F가 주어졌을 때, F[n]에 해당하는 피보나치 수를 구하는 데 필요한 코드1에 해당하는 한 줄, 코드2에 해당하는 한 줄이 각각 몇번 실행되는지를 구하는 것이다. 직접 해보면 알 수 있지만, 결국 코드1은 n이 ..

알고리즘 분류: 수학, 사칙연산 문제 링크: https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 【 풀이 】 간단한 수학 문제이다. 총감독관은 꼭 필요하고 한 명씩만 배치될 수 있으니 시험장마다 +1 부감독관은 시험장 사람 수에서 B를 뺀 값에서 C를 나눈 값이다. 즉 (arr[i] - b) / c 가 필요한 부감독관의 수인데, arr[i] - b 가 c보다 더 작은 경우까지 생각해야 하기 ..

알고리즘 분류: 분할 정복, 재귀 문제 링크: https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 【 풀이 】 분할 정복 알고리즘과 재귀를 이용하여 해결하는 문제이다. 분할 정복 알고리즘이란 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법이다. 이 문제에 따르면 종이(배열) 안의 숫자들이 모두 같다면, 그 종이는 분할하지 않고 넘어간다. 종이 내에 다른 숫자가 하나라도 포함된다면, 그 종이를 9분할 한다. 9분할한 종이..

알고리즘 분류: 수학, 사칙연산 문제 링크: https://www.acmicpc.net/problem/4344 4344번: 평균은 넘겠지 대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. www.acmicpc.net 【 풀이 】 테스트 케이스마다 학생 점수의 총평균 중 평균을 넘는 사람의 비율이 얼마나 되는지 구하는 문제이다. 총점수에서 학생 수만큼 나누어 평균을 구하고 평균을 넘는 사람의 수를 구한 다음, 총학생의 수에서 평균을 넘는 사람의 수를 나누고 *100을 해주면 된다. 【 코드 】 #include #include using namespace std; int main(void) { int T; cin >> T; for (int t =..

알고리즘 분류: 수학, 문자열, 그리디 알고리즘, 파싱 문제 링크: https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 【 풀이 】 문자열을 잘 쪼개서 숫자로 변환시켜 적절히 더하는 문제이다. '-' 기호가 처음 나온 경우, 그 위치 기준 뒤에 있는 모든 숫자들을 빼면 식의 값을 최소로 만들 수 있다. 원리는 다음과 같다. 55 - 50 + 40 => 55 - (50 + 40) 50 - 40 + 30 - 20 + 10 => 50 - (40 +..

알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 링크: https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 【 풀이 】 정점, 간선, 번호가 순서대로 주어지면 DFS와 BFS로 정점 방문 순서를 출력하면 되는 문제이다. 단 주의해야 할 점은 DFS와 BFS를 구현하기 전에, 인접리스트를 사용하였다면 인접리스트를 정렬해 주는 작업이 필요한데, 이는 정점 번호가 더 작은 순부터 ..