Recursive

eagerithm · Jun 8, 2022 · fc33d69 · fc33d69
1 parent 6563cdd
commit fc33d69
Show file tree

Hide file tree

Showing 6 changed files with 293 additions and 1 deletion.
diff --git a/haseung/README.md b/haseung/README.md
@@ -98,4 +98,14 @@
 |  7   |   2908    |       수학, 구현       | 28-05-2022 |       상수        | [Javascript](../haseung/String/06_2908.js)  |
 |  8   |   5622    |          구현          | 30-05-2022 |      다이얼       | [Javascript](../haseung/String/06_5622.js)  |
 |  9   |   2941    |      구현,문자열       | 30-05-2022 | 크로아티아 알파벳 | [Javascript](../haseung/String/06_2941.js)  |
-|  10  |   1316    |  수학, 구현, 사칙연산  | 30-05-2022 |  그룹 단어 체커   | [Javascript](../haseung/String/06_1316.js)  |
+|  10  |   1316    |  수학, 구현, 사칙연산  | 31-05-2022 |  그룹 단어 체커   | [Javascript](../haseung/String/06_1316.js)  |
+
+## 07\_재귀
+
+| 번호 | 백준 번호 |   분류    | 풀이 날짜  |        문제         |                    풀이                     |
+| :--: | :-------: | :-------: | :--------: | :-----------------: | :-----------------------------------------: |
+|  1   |   10872   | 수학,구현 | 03-06-2022 |      팩토리얼       | [Javascript](../haseung/String/07_10872.js) |
+|  2   |   10870   | 수학,구현 | 03-06-2022 |    피보나치 수 5    | [Javascript](../haseung/String/07_10870.js) |
+|  3   |   10809   | 구현,재귀 | 04-06-2022 | 재귀함수가 뭔가요?  | [Javascript](../haseung/String/07_17478.js) |
+|  4   |   2675    |   재귀    | 04-06-2022 |    별 찍기 - 10     | [Javascript](../haseung/String/07_2447.js)  |
+|  5   |   1157    |   재귀    | 06-06-2022 | 하노이 탑 이동 순서 | [Javascript](../haseung/String/07_11729.js) |
diff --git a/haseung/Recursive/07_10870.js b/haseung/Recursive/07_10870.js
@@ -0,0 +1,33 @@
+// 문제
+// 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
+
+// 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.
+
+// n=17일때 까지 피보나치 수를 써보면 다음과 같다.
+
+// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
+
+// n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.
+
+// 입력
+// 첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.
+
+// 출력
+// 첫째 줄에 n번째 피보나치 수를 출력한다.
+
+// 예제 입력 1
+// 10
+// 예제 출력 1
+// 55
+
+const inputs = require("fs").readFileSync(0, "utf-8").toString().split(" ");
+
+const input = Number(inputs[0]);
+
+function pibonacci(test) {
+  if (test === 0) return 0;
+  if (test === 1 || test === 2) return 1;
+  return pibonacci(test - 1) + pibonacci(test - 2);
+}
+
+console.log(pibonacci(input));
diff --git a/haseung/Recursive/07_10872.js b/haseung/Recursive/07_10872.js
@@ -0,0 +1,28 @@
+// 문제
+// 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.
+
+// 입력
+// 첫째 줄에 정수 N(0 ≤ N ≤ 12)이 주어진다.
+
+// 출력
+// 첫째 줄에 N!을 출력한다.
+
+// 예제 입력 1
+// 10
+// 예제 출력 1
+// 3628800
+// 예제 입력 2
+// 0
+// 예제 출력 2
+// 1
+
+const inputs = Number(require("fs").readFileSync(0, "utf-8").toString());
+
+function factorial(num) {
+  if (num <= 1) {
+    return 1;
+  }
+  return num * factorial(num - 1);
+}
+
+console.log(factorial(inputs));
diff --git a/haseung/Recursive/07_11729.js b/haseung/Recursive/07_11729.js
@@ -0,0 +1,53 @@
+// 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
+
+// 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
+// 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
+// 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
+
+// 아래 그림은 원판이 5개인 경우의 예시이다.
+
+//![](https://velog.velcdn.com/images/gktmd652/post/9408c887-b535-484c-9608-8c3069435b84/image.png)
+
+// 입력
+// 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.
+
+// 출력
+// 첫째 줄에 옮긴 횟수 K를 출력한다.
+
+// 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
+
+// 예제 입력 1
+// 3
+// 예제 출력 1
+// 7
+// 1 3
+// 1 2
+// 3 2
+// 1 3
+// 2 1
+// 2 3
+// 1 3
+
+const inputs = Number(require("fs").readFileSync(0, "utf-8").toString()); //원판의 개수
+
+let count = 0;
+let answer = [];
+
+// num : 원반의 개수
+// from : 출발지 기둥 번호
+// to : 목적지 기둥 번호
+// other : 나머지 기둥 번호
+
+function Hanoi(num, from, other, to) {
+  if (num === 0) return;
+  else {
+    Hanoi(num - 1, from, to, other);
+    answer.push([from, to]);
+    count++;
+    Hanoi(num - 1, other, from, to);
+  }
+}
+
+Hanoi(inputs, "1", "2", "3");
+console.log(count);
+console.log(answer.map((element) => element.join(" ")).join("\n"));
diff --git a/haseung/Recursive/07_17478.js b/haseung/Recursive/07_17478.js
@@ -0,0 +1,95 @@
+// 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다.
+
+// 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대학교가 자신과 맞는가에 대한 고민을 항상 해왔다.
+
+// 중앙대학교와 자신의 길이 맞지 않다고 생각한 JH 교수님은 결국 중앙대학교를 떠나기로 결정하였다.
+
+// 떠나기 전까지도 제자들을 생각하셨던 JH 교수님은 재귀함수가 무엇인지 물어보는 학생들을 위한 작은 선물로 자동 응답 챗봇을 준비하기로 했다.
+
+// JH 교수님이 만들 챗봇의 응답을 출력하는 프로그램을 만들어보자.
+
+// 입력
+// 교수님이 출력을 원하는 재귀 횟수 N(1 ≤ N ≤ 50)이 주어진다.
+
+// 출력
+// 출력 예시를 보고 재귀 횟수에 따른 챗봇의 응답을 출력한다.
+
+// 예제 입력 1
+// 2
+// 예제 출력 1
+// 어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
+// "재귀함수가 뭔가요?"
+// "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
+// 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
+// 그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
+
+// ____"재귀함수가 뭔가요?"
+// ____"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
+// ____마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
+// ____그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
+
+// ________"재귀함수가 뭔가요?"
+// ________"재귀함수는 자기 자신을 호출하는 함수라네"
+// ________라고 답변하였지.
+// ____라고 답변하였지.
+// 라고 답변하였지.
+// 예제 입력 2
+// 4
+// 예제 출력 2
+// 어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
+// "재귀함수가 뭔가요?"
+// "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
+// 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
+// 그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
+// ____"재귀함수가 뭔가요?"
+// ____"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
+// ____마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
+// ____그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
+// ________"재귀함수가 뭔가요?"
+// ________"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
+// ________마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
+// ________그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
+// ____________"재귀함수가 뭔가요?"
+// ____________"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
+// ____________마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
+// ____________그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
+// ________________"재귀함수가 뭔가요?"
+// ________________"재귀함수는 자기 자신을 호출하는 함수라네"
+// ________________라고 답변하였지.
+// ____________라고 답변하였지.
+// ________라고 답변하였지.
+// ____라고 답변하였지.
+// 라고 답변하였지.
+
+const recursive = (num) => {
+  if (num === 0) {
+    return [
+      '"재귀함수가 뭔가요?"',
+      '"재귀함수는 자기 자신을 호출하는 함수라네"',
+      "라고 답변하였지.",
+    ];
+  }
+  const prev = recursive(num - 1);
+  let ret = [
+    '"재귀함수가 뭔가요?"',
+    '"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.',
+    "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.",
+    '그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."',
+  ];
+  for (let line of prev) {
+    ret.push("____" + line);
+  }
+  ret.push("라고 답변하였지.");
+  return ret;
+};
+
+const jh = () => {
+  const inputs = require("fs").readFileSync(0, "utf-8").toString();
+  let stack = [];
+  stack.push("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.");
+
+  stack.push(...recursive(inputs));
+  console.log(stack.join("\n"));
+};
+
+jh();
diff --git a/haseung/Recursive/07_2447.js b/haseung/Recursive/07_2447.js
@@ -0,0 +1,73 @@
+// 문제
+// 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.
+
+// 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.
+
+// ***
+// * *
+// ***
+// N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.
+
+// 입력
+// 첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.
+
+// 출력
+// 첫째 줄부터 N번째 줄까지 별을 출력한다.
+
+// 예제 입력 1
+// 27
+// 예제 출력 1
+// ***************************
+// * ** ** ** ** ** ** ** ** *
+// ***************************
+// ***   ******   ******   ***
+// * *   * ** *   * ** *   * *
+// ***   ******   ******   ***
+// ***************************
+// * ** ** ** ** ** ** ** ** *
+// ***************************
+// *********         *********
+// * ** ** *         * ** ** *
+// *********         *********
+// ***   ***         ***   ***
+// * *   * *         * *   * *
+// ***   ***         ***   ***
+// *********         *********
+// * ** ** *         * ** ** *
+// *********         *********
+// ***************************
+// * ** ** ** ** ** ** ** ** *
+// ***************************
+// ***   ******   ******   ***
+// * *   * ** *   * ** *   * *
+// ***   ******   ******   ***
+// ***************************
+// * ** ** ** ** ** ** ** ** *
+// ***************************
+
+const inputs = Number(require("fs").readFileSync(0, "utf-8").toString());
+
+let str = "";
+
+const Star = (i, j) => {
+  if (i % 3 === 1 && j % 3 === 1) {
+    str += " ";
+  } else {
+    if (Math.floor(i / 3) === 0 && Math.floor(j / 3) === 0) {
+      str += "*";
+    } else {
+      Star(Math.floor(i / 3), Math.floor(j / 3));
+    }
+  }
+};
+
+for (let i = 0; i < inputs; i++) {
+  for (let j = 0; j < inputs; j++) {
+    Star(i, j);
+  }
+  if (i !== inputs - 1) {
+    str += "\n";
+  }
+}
+
+console.log(str);