문제 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 설명 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 풀이 방식 문제 자체는 쉬워서 풀이할것도 없다. C++과 같은 경우 vector을 사용해 algorithm.h 에 내장된 sort 함수를 사용해주면 된다. 다만 문제가 되는 부분은 이 부분이다. // case 1 for (int i = 0; i < n; i++) cout v[i]; sort(v.begin(), v.end()); for (int i = 0; i ..

문제 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 설명 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 정점의 개수가 N, 간선의 개수가 M, 시작하는 정점의 번호가 V이다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점..

문제 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 설명 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 단, 2가 주어진다면 방법의 수에 2도 포함이 된다. 그리고 4를 구현함에 있어서 1+1+2, 2+1+1 같은 경우는 다른 경우로 판단한다. 예를 들어,정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 풀이 방식 이 문제는 해당 문제와 비슷한 유형의 Dynamic Programming 문제이다. 이전 결과..

문제 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 설명 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 사용해서, 가치의 합이 k원이 되도록 하고 싶다. 각각의 동전은 몇 개라도 사용할 수 있다. 그 경우의 수를 쓰시오. ! 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 풀이 방식 이 문제는 DP 알고리즘을 통해 푸는 문제이다.즉, 전의 결과의 값이 현재의 값을 정하는데 반영이 된다. 다음 예시를 통해 알아보자. 3 10 1 2 5 만약 n = 3, k=..

문제 2012번: 등수 매기기 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다. www.acmicpc.net 문제 설명 2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다. KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다. 자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 ..

문제 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 설명 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 풀이 방식 해당 문제는 주어진 값을 이용하여 어떠한 값을 최소 횟수로 만들어 내는 것이 관건이다. 10 4790 1 5 10 50 100 500 1000 5000 10000 500..

문제 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 문제 설명 크기가 2N x 2N 인 2차원 배열을 Z모양으로 탐색하려고 한다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 풀이 방식 해당 문제는 분할 정복과 관련된 문제이다. 배열을 Z 모양으로 다음과 같이 탐색순서가 매겨진다. n = 2 일때의 그림을 잘 살펴 보면 Z는 일정한 범위를 순차적으로 탐색하고 있다. 그래서 이를 Z의 탐색순서 대로 1~4사분면으로 쪼갠뒤 (5,3)을 방문할때의 탐색순서를 찾으..

문제 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 설명 자연수 A를 B번 곱한 수를 알고 싶다. 단, 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 풀이 방식 이 문제는 pow를 직접 구현하는 문제이다. 처음에는 cmath 라이브러리에 있는 pow를 %로 나누어서 답을 내면 되겠다~ 했는데 자료형 이슈로 안되었고 했어도 아마 시간문제로 인해서 안되었을 것 같다. 당연히 for문을 통해서 구현 하더라도 연산 횟수가 많아서 안됬을 것이다. 그래서 이번 풀이에는 분할 정복의 개념이 사용되었다. 예를 들어, 짝수일 때는 $$A^{4} ..