본문 바로가기

[C++] 알고리즘 교육/7~8. 재귀함수8

[알고리즘 8.1.5] 재귀함수 - inequal 문제 두 종류의 부등호 기호 ‘’가 k 개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. A ⇒ 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 3 1 7 0 이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들.. 2019. 4. 26.
[알고리즘 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. 26.
[알고리즘 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. 26.
[알고리즘 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.

티스토리툴바