코후닝

알고리즘 분류: 구현, 문자열 문제 링크: https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 【 풀이 】 각 문자들이 끊기지 않으면서 연속해서 나타나는 경우의 단어의 개수를 세는 문제이다. 우선 각 문자의 등장 여부를 나타내는 알파벳 배열을 선언. 테스트 케이스 내에서 문자열을 입력받은 뒤 문자열의 각 글자를 검사. 이미 글자가 한번 나왔고, 연속되지 않는다면 break. 여기에 해당하지 않는다면, 글자에 해당하는..

알고리즘 분류: 자료구조, 우선순위 큐 문제 링크: 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분할한 종이..