Kangho_Story

알고리즘 분류정렬문자열문제 설명n개의 숫자가 주어졌을 때, 순서대로 숫자를 읽다가 홀수 번째의 원소가 주어질 때마다 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성해 보세요. 여기서 중앙값이란, 어떤 주어진 값들을 오름차순으로 정렬했을 때 가장 중앙에 위치하는 값을 의미합니다.입력 설명첫 번째 줄에는 숫자 n이 주어집니다.두 번째 줄에는 n개의 숫자가 공백을 사이에 두고 주어집니다.1 ≤ n ≤ 100, n은 홀수0 ≤ 주어지는 숫자 ≤ 100,000출력 설명n개의 숫자를 순서대로 읽으며 홀수 번째 수를 읽을 때 마다 지금까지 입력받은 값 중 중앙값을 차례대로 공백을 사이에 두고 출력합니다.예제 입력51 2 3 4 591 5 2 9 7 4 6 10 11예제 출력1 2 31 2 5 5 6아이디어n..

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

알고리즘 분류문자문제 설명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 ..

알고리즘 분류시뮬레이션문자문제 설명길이가 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를 이용해서 연결된 것들끼리 같은 ..