Kangho_Story

99​210​알고리즘 분류수학브루트포스 알고리즘문제 설명어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 입력 설명첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다.출력 설명첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다.예제 입력11012101000500예제 출력991105144119아이디어각 자리의 숫자가 등차수열을 이루는지 확인해야 한다.우선 1자리뿐인 1~9는 모두 한수이다.또한 10~99는 각 자리의 숫자가 모두 등차수열을 이루므로 10~99도 모두 한수이다.n은 ..

181-100011-1-12-20000000​알고리즘 분류자료 구조우선순위 큐문제 설명절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.배열에 정수 x (x ≠ 0)를 넣는다.배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러 개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다.입력 설명첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되..

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

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까지 더한 후 출력한다. -> 최..