Kangho_Story

12​10 4200151050100500100050001000050000​알고리즘 분류그리디 알고리즘문제 설명준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.입력 설명첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)출력 설명첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.예제 입력10 420015105010050010005000100..

5​알고리즘 분류그래프 이론그래프 탐색BFS문제 설명뱀과 사다리 게임을 즐겨하는 큐브러버는 어느 날 궁금한 점이 생겼다.주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까?게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10 ×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀 있다.플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다. 도착한 칸이 사다..

알고리즘 분류수학문제 설명n개의 수가 주어졌을 때 이 수들의 최소공배수를 구하는 프로그램을 작성해 보세요. 단, 재귀함수를 이용하여 문제를 해결해 주세요.입력 설명첫 번째 줄에 정수 n이 주어집니다.두 번째 줄에 n개의 수가 공백을 사이에 두고 주어집니다.1 ≤ n ≤ 101 ≤ 원소의 범위 ≤ 10출력 설명첫 번째 줄에 n개의 수들의 최소공배수를 출력합니다.예제 입력61 5 7 9 2 6예제 출력630아이디어최대공약수와 최소공배수를 구하는 함수를 만들고 모든 입력받은 값을 벡터에 저장하여 소모하면서 연속적으로 최소공배수를 구한다.알고리즘최대공약수는 유클리드 호제법을 이용하면 간단하게 구할 수 있다.유클리드 호제법에 따르면 a와 b의 최대 공약수는 b와 a% b의 최대 공약수와 같다.따라서 만약 b가 0..

알고리즘 분류다이나믹 프로그래밍브루트포 알고리즘문제 설명라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52.자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현..

알고리즘 분류문자문제 설명N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.P1 IOIP2 IOIOIP3 IOIOIOIPN IOIOI...OI (O가 N개)I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.입력 설명첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.출력 설명S에 PN이 몇 군데 포함되어 있는지 출력한다.서브테스크번호배점제한150N ≤ 100, M ≤ 10 000.250추가적인 제약 조건이 없다.예제 입력113OOIOIOIOIIOIIOOIOIOIOIIOIIOOIOIOIOIIOIIOOIOIOIOIIOIIOOIOIOIOIIOII21..

알고리즘 분류다이나믹 프로그래밍문제 설명정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.입력 설명첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.출력 설명각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.예제 입력34710 예제 출력744274아이디어기존 숫자에서 맨 앞자리에 1이 더해지는가 2가 더해지는가 3이 더해지는가 이렇게 세 가지로 나눠서 점화식..

알고리즘 분류시뮬레이션문제 설명입력 설명첫 번째 줄에는 격자의 크기를 나타내는 n과 폭탄을 터뜨릴 횟수 m이 공백을 사이에 두고 주어집니다.두 번째 줄 부터는 n개의 줄에 걸쳐 각 행에 해당하는 n개의 숫자가 공백을 사이에 두고 주어집니다.그 다음 줄 부터는 m개의 줄에 걸쳐 폭탄을 터뜨릴 열의 위치 c가 순서대로 주어집니다. (1 ≤ c ≤ n)1 ≤ n ≤ 2001 ≤ m ≤ 10출력 설명m번에 걸쳐 폭탄이 터지고 중력이 작용한 것을 반복한 이후의 결과를 출력합니다.n개의 줄에 걸쳐 각 행에 해당하는 n개의 숫자를 공백을 사이에 두고 출력합니다. 만약 해당 위치에 아무 숫자도 적혀있지 않은 경우라면 0을 출력합니다.예제 입력4 41 1 2 33 2 2 33 1 6 24 5 4 42222 4 31 2 ..

02132100​알고리즘 분류자료구조우선순위 큐문제 설명널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.배열에 자연수 x를 넣는다.배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다.입력 설명첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.출력 설명입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 ..

1) c++과 c의 표준 스트림의 동기화 끄기int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0;}C++의 cin과 cout은 실행 속도가 느리지만 위의 코드와 main 아래에 적어주면 실행 속도를 단축할 수 있다.다만 주의할 점은 해당 방법 사용 시 C++의 cout, cin 등의 입출력 방식과 printf, scanf 등의 C언어 방식의 입출력을 혼용하면 안 된다. 그리고 이는 싱글 스레드 환경에서만 효율적이므로 실무에서는 사용하지 말자. 2) endl 대신 "\n" 사용하기둘 다 개행할 때 사용하는 코드이지만 endl은 개행 후 버퍼를 비워주기 때문에 "\n"에 비해서 속도가 더 느리다.따라서 endl대신 "\n"을..

알고리즘 분류시뮬레이션문제 설명입력 설명첫 번째 줄에는 격자의 크기를 나타내는 n이 주어집니다.두 번째 줄 부터는 n개의 줄에 걸쳐 각 행에 해당하는 n개의 숫자가 공백을 사이에 두고 주어집니다.그 다음 줄에는 폭탄이 터질 중심 위치의 정보를 나타내는 (r, c) 값이 공백을 사이에 두고 주어집니다. 이는 r행 c열이 중심 위치임을 의미합니다.1 ≤ n ≤ 2001 ≤ r, c ≤ n출력 설명폭탄이 터지고 나서 중력이 작용한 뒤의 결과를 출력합니다.n개의 줄에 걸쳐 각 행에 해당하는 n개의 숫자를 공백을 사이에 두고 출력합니다. 만약 해당 위치에 아무 숫자도 적혀있지 않은 경우라면 0을 출력합니다.예제 입력4 1 2 4 3 3 2 2 3 3 1 6 2 4 5 4 4 2 3  4 1 2 4 3 3 2 2 ..

알고리즘 분류시뮬레이션문자문제 설명길이가 n인 문자열 A가 주어졌을 때, 적절하게 특정 횟수만큼 오른쪽으로 shift하여, shift 된 이후의 문자열에 Run-Length Encoding을 진행했을 때의 길이가 최소가 되도록 하려고 합니다.Run-Length Encoding이란 간단한 비손실 압축 방식으로, 연속해서 나온 문자와 연속해서 나온 개수로 나타내는 방식입니다. 예를 들어, 문자열 A가 aaabbbbcaa인 경우 순서대로 a가 3번, b가 4번, c가 1번 그리고 a가 2번 나왔으므로 Run-Length Encoding을 적용하게 되면 a3b4c1a2이 되며 길이는 8이 됩니다.만약 문자열 A에 해당하는 aaabbbbcaa를 오른쪽으로 2번 shift를 하게 되면 aaaaabbbbc가 되며, ..

알고리즘 분류시뮬레이션문제 설명입력 설명첫 번째 줄에는 n과 m이 공백을 사이에 두고 주어지고, 두 번째 줄부터 (n+1)번째 줄까지는 각 행의 숫자가 공백을 사이에 두고 주어집니다.1 ≤ n, m ≤ 20-1,000 ≤ 정수 값 ≤ 1,000출력 설명모든 값이 양수로만 이루어져 있는 직사각형 중 최대 크기를 출력해주세요. 만약 그러한 직사각형이 없다면, -1을 출력해주세요.예제 입력3 3 1 2 3 3 4 5 6 7 8 4 5 6 -2 4 -3 1 3 6 7 -4 1 6 1 8 15 -5 3 -5 1 16 3예제 출력9 6아이디어x1 ~ x2, y1 ~ y2 범위의 직사각형을 모두 체크하여 가장 큰 직사각형의 크기를 출력한다.알고리즘x1 ~ x2, y1 ~ y2 범위의 직사각형의 내부 원소가 모두 양수..

6 51 22 55 13 44 6​알고리즘 분류그래프 이론그래프 탐색DFSBFS문제 설명방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.입력 설명첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.출력 설명첫째 줄에 연결 요소의 개수를 출력한다. 예제 입력6 51 22 55 13 44 6 6 81 22 55 13 44 65 42 42 3예제 출력21아이디어인접행렬로 컴포넌트 연결 상태를 표현하고 DFS를 이용해서 연결된 것들끼리 같은 ..

알고리즘 분류그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐문제 설명과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.입력 설명첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입..

5 35 4 3 2 11 32 45 5​알고리즘 분류누적 합문제 설명수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.입력 설명첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.출력 설명총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.예제 입력5 35 4 3 2 11 32 45 5예제 출력1291  제한1 ≤ N ≤ 100,0001 ≤ M ≤ 100,0001 ≤ i ≤ j ≤ N아이디어1. n칸 배열에 입력받은 수를 모두 저장하고 매번 i ~ j까지 더한 후 출력한다. -> 최..