본문 바로가기

[C++] 알고리즘 교육119

[알고리즘 8.1.4] 재귀함수 - dessert 문제 농부 존은 소들의 저녁식사 줄 세우는 새로운 방법을 개발 했다. N(1~15)마리의 소들을 순서대로 세 워놓은 후, 각 소들 사이에 +, - , . 셋 중 1가지가 써져있는 냅킨을 배치해서 최종 결과가 0 이 되게 해야 하는 것이다. 점(.)이 써져있는 냅킨을 통해 더 큰 수를 만들 수 있게 된다. 아래와 같은 경우를 보자. (ps .이 써져있는 냅킨은 '공백'이라고 생각하면 된다.) 1-2.3-4.5+6.7 이와 같은 배치는 1-23-45+67 을 나타낸다. 결과는 0 이다. 10.11은 1011 로 해석된다. 입력 첫 째 줄에는 소들의 수 N(1 ≤ N ≤ 15)이 입력된다. 출력 처음 20줄에 대해 가능한 20가지 답을 출력하는데, 사전 순으로 앞선 것을 출력한다. 순서는 +가 가장 앞서고 -.. 2019. 4. 25.
[알고리즘 8.1.3] 재귀함수 - division 문제 임의의 자연수는 그보다 작은 자연수들의 합으로 표현될 수 있다. 예를 들어 4의 경우, 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1 위와 같은 방법으로 표현 될 수 있다. 이 때 , 숫자의 구성이 같으면서 그 순서만이 다른 경우는 같은 경우로 생각하는데, 예를 들어 다음 세 가지 경우는 모두 같은 경우이다. 2 + 1 + 1, 1 + 2 + 1 , 1 + 1 + 2 자연수 n을 입력 받아 이를 n보다 작은 자연수들의 합으로 나타내는 방법을 모두 출력하는 프로그램을 재귀 호출을 사용하여 작성하시오. 입력 첫 줄에 2 이상 20 이하의 자연수 n이 주어진다. 출력 첫째 줄부터 모든 방법을 한 줄에 하나씩 출력한다. 하나의 식 안에는 큰 숫자가 앞으로 오도록 하고, 전체적으로는 앞의 숫자가 .. 2019. 4. 25.
[알고리즘 8.1.2] 재귀함수 - tobin 문제 두 정수 n, k를 입력받아 k개의 1을 가진 n자리 이진 패턴을 출력하는 프로그램을 작성하세요. 입력 두 정수 n, k가 입력으로 주어진다. ( 0 < n =n){ if(y==r){ for(int i=0; i 2019. 4. 25.
[알고리즘 8.1.1] 재귀함수 - 순열 구하기 문제 서로 다른 n개의 원소들 중에서 r개만을 뽑아 일렬로 나열하는 것을 순열이라 한다. 예를 들어, 3개의 원소 a, b, c 중에서 2개만을 뽑아 나열하면 ab, ac, ba, bc, ca, cb 의 6가지 경우가 있다. n과 r이 주어질 때, n개의 소문자 중에서 r개만을 뽑아 나열하는 모든 경우를 출력하는 프로그램을 작성하시오. 단, a부터 시작하여 연속으로 n개의 알파벳을 갖고 있다고 하자. 입력 첫 번째 줄에 n과 r이 주어진다. ( 1 ≤ n ≤ 10, 0 ≤ r ≤ min(n, 7) ) 출력 각 줄에 n개의 소문자 중에서 r개만을 뽑아 나열하는 경우를 사전순으로 나열한 결과를 출력한다. 예제 입력 4 2 예제 출력 ab ac ad ba bc bd ca cb cd da db dc 1 2 3 .. 2019. 4. 25.
[알고리즘 7.1.3] 재귀함수 - mountain 문제 봉우리가 여러개인 산 모양을 출력한다. 산 모양은 그림과 같고 좌우 대칭이다. 입력 첫 번째 줄에 숫자를 입력 받는다. 숫자의 크기는 20보다 작은 자연수이다. 출력 출력 예의 형식으로 출력한다. 예제 입력 3 예제 출력 1213121 예제 입력 5 예제 출력 1213121412131215121312141213121 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include void mon(int n){ if(n==1){ printf("1"); }else{ mon(n-1); printf("%d",n); mon(n-1); } } int main() { int n; scanf("%d",&n); mon(n); return 0; } 2019. 4. 25.
[알고리즘 7.1.2] 재귀함수 - binary 문제 숫자를 입력 받아 이진수로 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에 숫자를 입력 받는다. 숫자의 크기는 1,000보다 작거나 같다. 출력 첫째 줄에 숫자를 이진수로 바꾸어 출력한다. 예제 입력 14 예제 출력 1110 예제 입력 31 예제 출력 11111 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include void binary(int a){ if(a==0) printf("0"); else if(a==1) printf("1"); else{ binary(a/2); printf("%d",a%2); } } int main() { int n; scanf("%d",&n); binary(n); return 0; } 2019. 4. 25.
[알고리즘 7.1.1] 재귀함수 - 팩토리얼 문제 N 팩토리얼 (N!)은 1부터 N까지의 곱으로 정의된다. 예를 들어 3! = 1 x 2 x 3 = 6 4! = 1 x 2 x 3 x 4 = 24 이다. N이 주어질 때, N!을 계산하는 프로그램을 작성하시오. 입력 첫 번째 줄에 숫자 N이 주어진다. ( 1 ≤ N ≤ 10 ) 출력 첫째 줄에 N!을 출력한다. 예제 입력 4 예제 출력 24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include int fac(int a){ if(a==0) return 1; else return a*fac(a-1); } int main() { int n; scanf("%d",&n); printf("%d",fac(n)); return 0; } 2019. 4. 25.
[알고리즘 10.2.4] 매개 변수 탐색 - 중복 없는 구간 문제 n개의 숫자가 주어지고, 이 중에서 r개의 연속된 숫자를 선택했을 때, 이 연속 부분 내에는 숫자가 중복되지 않기를 원한다. 예를 들어, 다음과 같이 10개의 숫자에서 3개의 연속된 숫자를 선택할 수 있다. 이렇게 선택을 하면, 선택된 숫자들 사이에서는 중복이 존재하지 않는다. r의 최댓값을 구하는 프로그램을 작성하시오. 위의 경우, (4, 2, 1, 3)을 선택하면 되므로 r의 최댓값은 4이다. r이 5 이상이 될 경우, 중복 없이 연속 부분을 선택하는 것이 불가능하다. 입력 첫째 줄에는 숫자의 개수 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 둘째 줄에 n개의 숫자가 주어진다. 각 숫자는 항상 1보다 크거나 같고, n보다 작거나 같다. 출력 r의 최댓값을 출력한다. 예제 입력 10 1 3.. 2019. 4. 25.
[알고리즘 10.2.3] 매개 변수 탐색 - NN단표 문제 알랩이는 구구단표처럼 NN단표를 만들었다고 한다. NN단표는 2차원 배열의 모양으로 곱셈 1단부터 N단까지의 값들을 적어놓은 형태이다. NN단표의 배열을 A라고 했을 때, 배열의 들어가는 수 A[i][j]=i*j이다.(즉, 4행 7열에는 28, 7행 5열에는 35가 들어가 있다.) 알랩이는 N단까지 나온 숫자들 중에서 K번째로 작은 수를 찾고 싶어한다. 이때, 중복되는 여러 수들을 고려한다. 즉 N*N개의 모든 수들 중에서 K번째 수를 구하는 것이다. 입력 첫째 줄에 배열의 크기 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄에 K가 주어진다. K는 N*N보다 작거나 같은 자연수이다. 출력 K번째 원소를 출력한다. 예제 입력 3 7 예제 출력 6 1 2 3 4 5 6 7 8.. 2019. 4. 25.
[알고리즘 10.2.2] 매개 변수 탐색 - 나무 자르기 문제 얼마전에 큰맘 먹고 새로운 절단기를 구입한 목수 윤성이는 나무 M미터가 필요하다. 절단기는 다음과 같이 동작한다. 먼저, 윤성이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 윤성이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 목수 윤성이는 과유불급을 좌우명으로 삼고 있.. 2019. 4. 25.
[알고리즘 10.2.1] 매개 변수 탐색 - 2차식 정답 추측 (*이진탐색 외 방법) 문제 2차식 f(x) = x*x+ x 가 있고, 숫자 a가 주어진다. 우리는 f(x) = a 를 만족하는 x의 값을 찾고 싶지만, 보통 이 값은 정수로 떨어지지 않는 경우가 많다. 예를 들어, f(x) = 20 을 풀고자 한다면, x = 4이기 때문에 이는 정수이지만, f(x) = 103 을 풀고자 한다면 이는 x = 9.6612... 로써 정수가 아니다. 이 문제에서는 x의 정수부분이 얼마인지를 구하는 프로그램을 작성하시오. 예를 들어, f(x) = 103 을 풀고자 한다면, x = 9.6612... 이기 때문에 정수부분은 9가 된다. 입력 첫 번째 줄에 숫자 a가 주어진다. ( 1 ≤ a ≤ 1,000,000,000,000,000,000 ) 출력 f(x) = a 를 만족하는 x의 정수부분을 출력한다... 2019. 4. 25.
[알고리즘 10.1.4] 이진탐색 - 두 용액 문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액.. 2019. 4. 25.
[알고리즘 10.1.3] 이진탐색 - 숫자 개수 세기 문제 n개의 숫자가 주어지고, q개의 질문이 주어진다. 각각의 질문은 n개의 숫자 중에서 특정 숫자가 몇개나 있는지를 묻는다. q개의 질문에 모두 답하는 프로그램을 작성하시오. 입력 첫 번째 줄에 숫자의 개수 n, 그리고 질문의 개수 q가 주어진다 ( 1 ≤ n ≤ 100,000, 1 ≤ q ≤ 100,000) 두 번째 줄에 n개의 숫자가 주어진다. 세 번째 줄에 q개의 질문이 주어진다. 주어지는 q개의 질문에 해당하는 숫자 범위는 100,000,000이하이다. 출력 각 질문에 대하여 숫자의 개수를 한 줄에 하나씩 출력한다. 예제 입력 10 4 1 3 4 3 2 3 1 2 5 10 1 3 9 10 예제 출력 2 3 0 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1.. 2019. 4. 25.
[알고리즘 10.1.2] 이진탐색 - 숫자박스 문제 숫자박스에는 자연수들이 적혀있는 종이들이 N장 들어있다. 숫자 M개가 주어졌을 때, 이 숫자가 적혀있는 숫자가 상자 안에 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 윤성이가 가지고 있는 숫자 정보의 개수 N (1 ≤ N ≤ 300,000)이가 주어진다. 둘째 줄에는 숫자 정보들이 주어진다. 숫자는 1,000,000이하의 정수이다. 두 숫자 카드에 같은 숫자가 적혀있는 경우는 없다. 셋째 줄에는 M (1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 윤성이가 숫자 박스에 있는지 아닌지를 구해야 할 M개의 숫자가 주어지며, 이 숫자는 공백으로 구분되어져 있다. 이숫자도 1,000,000이하의 정수이다. 출력 첫째 줄에 입력으로 주어진 M개의 숫자에 대해서, 각 숫자가 숫자 상자.. 2019. 4. 25.
[알고리즘 10.1.1] 고급정렬 - 이진탐색 문제 n개의 오름차순으로 정렬된 숫자가 주어지고, 그 후 q개의 질문이 주어진다. 각각의 질문은 특정 숫자가 n개의 숫자 내에 존재하는지를 판별하는 것이다. 모든 q개의 질문에 대하여 답을 하는 프로그램을 작성하시오. 입력 첫 번째 줄에 숫자의 개수 n, 그리고 질문의 개수 q가 주어진다 ( 1 ≤ n ≤ 100,000, 1 ≤ q ≤ 100,000) 이는 오름차순으로 정렬되어 주어진다. 두 번째 줄에 n개의 숫자가 주어진다. 세 번째 줄에 q개의 질문이 주어진다. 각 수는 21억보다 작은 정수다. 출력 각 질문에 대하여 숫자가 존재하면 YES, 아니면 NO를 한 줄에 하나씩 출력한다. 예제 입력 10 4 1 2 4 8 10 11 12 14 15 19 4 5 8 17 예제 출력 YES NO YES NO .. 2019. 4. 25.

티스토리툴바