완전탐색, 재귀함수 기본

📌 완전탐색(Brute Force)

✅ 완전 탐색이란?

모든 경우의 수를 다 체크해서 정답을 찾는 방법 (무식하게 가능한 거 다 해보겠다는 방법을 의미함)
예를 들어, 숫자 4자리의 암호로 구성된 자물쇠를 완전탐색으로 풀어보려고 한다면?
- 무식하게 0000 ~ 9999 까지 모두 시도해보면 된다.

📌 재귀함수 개념(Recursive Function)

✅ 재귀함수란?

자기가 자기자신을 호출하는 함수라고 생각하면 된다.
기본적으로 스택프레임을 이용한다 !!!!

✅ 재귀함수 연습

재귀함수로 숫자 n을 입력받고 1부터 n까지 출력
재귀함수로 n부터 1까지 출력해보기
숫자 n을 입력받고 재귀함수로 n! 계산해서 출력해보기

📌 피보나치

문제

💡 피보나치 수는 0과 1로 시작한다.

0번째 피보나치 수는 0,

1번째 피보나치 수는 1

라고 할 때

숫자 n을 입력받으면, 0번째 피보나치 수 부터 n번째 피보나치 수 까지를 출력하는 프로그램을 작성하여라.

입력 예시

출력 예시

0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597

✅ 반복문을 이용하여 풀기

정답코드
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int count = 0; for(int x : solution(n)) { if(count != n) { System.out.print(x + ","); } else { System.out.print(x); } count++; } } private static int[] solution(int n) { int[] answer = new int[n+1]; if (n >= 0) answer[0] = 0; if (n >= 1) answer[1] = 1; if (n >= 2) answer[2] = 1; for(int i=3; i<=n; i++) answer[i] = answer[i-2] + answer[i-1]; return answer; } }

✅ 재귀함수를 써서 풀기

정답코드
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); solution(n); } private static void solution(int n) { for(int i=0; i<=n; i++) { if(i != n) { System.out.print(recursive(i)+","); } else { System.out.print(recursive(i)); } } } private static int recursive(int n) { if(n == 0) return 0; else if(n == 1) return 1; else if(n == 2) return 1; else { return recursive(n-1) + recursive(n-2); } } }

✅ 메모이제이션을 적용해서 시간 줄이기

메모이제이션이란 ?

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.
정답코드

 import java.util.*;

 public class Main {

     static int[] fibo;

     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int n = sc.nextInt();
         solution(n);
         for(int i=0; i<=n; i++) {
             if(i == n) {
                 System.out.println(fibo[i]);
             } else {
                 System.out.print(fibo[i] + ",");
             }
         }
     }

     private static void solution(int n) {
         fibo = new int[n+1];
         recursive(n);
     }

     private static int recursive(int n) {
         //if(fibo[n] != 0) return fibo[n];
         if(n == 0) return fibo[n] = 0;
         else if(n == 1) return fibo[n] = 1;
         else if(n == 2) return fibo[n] = 1;
         else {
             return fibo[n] = recursive(n-1) + recursive(n-2);
         }
     }
 }