코후닝

알고리즘 분류: 자료구조, 우선순위 큐 문제 링크: https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 【 풀이 】 C++ STL의 priority_queue(우선순위 큐)를 이용하면 쉽게 해결할 수 있다. 우선순위 큐는 큐의 한 종류로, 우선순위에 따라 정렬된 큐이다. 특정 원소가 삽입(push)되면 주어진 우선순위에 따라 큐가 정렬되고, 삭제(pop)은 정렬된 큐의 맨 앞에서 이루어진다. 특정 원소를 삽입해서 생기는 정렬 과..

알고리즘 분류: 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 【 풀이 】 피보나치 함수의 호출 횟수를 출력하는 문제이다. 문제의 코드에 호출될 때마다 횟수를 더해주는 코드를 작성해서 그 횟수를 출력하면 당연히 시간 복잡도에 걸려 시간 초과가 발생하게 된다. 하지만 그 횟수 출력으로 우리가 따로 횟수를 확인해 규칙을 찾고 점화식을 도출해 동적계획법으로 해결하면 된다. 규칙을 찾아본 결과 n[0] = 1 n[1]..

알고리즘 분류: 수학, 다이나믹 프로그래밍 문제 링크: 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 =..