[알고리즘] 재귀 문제 풀이(백준 27433번, 10870번, 25501번)

1. 팩토리얼2(백준 27433번 문제)

 

27433번: 팩토리얼 2 (acmicpc.net)

27433번: 팩토리얼 2

 

▷ 풀이 코드

import java.util.Scanner;

public class Factorial_backjoon {
​​​​static long factorial(long n) {
​​​​​​​​if(n > 0) {
​​​​​​​​​​​​return n * factorial(n-1);
​​​​​​​​} else {
​​​​​​​​​​​​return 1;
​​​​​​​​}
​​​​}
​​​​
​​​​public static void main(String[] args) {
​​​​​​​​Scanner sc = new Scanner(System.in);
​​​​​​​​
​​​​​​​​long n = sc.nextLong();
​​​​​​​​
​​​​​​​​System.out.println(factorial(n));
​​​​}
}

 

 

 

2. 피보나치 수5(백준 10870번 문제)

 

https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

 

▷ 풀이 코드

import java.util.Scanner;

public class Fibonacci_backjoon2 {
​​​​static long fibonacci(long n) {
​​​​​​​​if(n > 1) return fibonacci(n-1) +  fibonacci(n-2);
​​​​​​​​else if(n == 1) return 1;
​​​​​​​​else return 0;
​​​​}
​​​​
​​​​public static void main(String[] args) {
​​​​​​​​Scanner sc = new Scanner(System.in);
​​​​​​​​
​​​​​​​​long n = sc.nextLong();
​​​​​​​​
​​​​​​​​System.out.println(fibonacci(n));
​​​​}
}

 

 

 

3. 재귀의 귀재(백준 25501번 문제)

 

25501번: 재귀의 귀재 (acmicpc.net)

25501번: 재귀의 귀재

 

▷ 풀이 코드

import java.util.Scanner;

public class Palindrome_backjoon3 {
​​​​static int cnt;
​​​​
​​​​static int palindrome(String a, int x, int y) {
​​​​​​​​cnt++;
​​​​​​​​if(x >= y) return 1;
​​​​​​​​else if(a.charAt(x) != a.charAt(y)) return 0;
​​​​​​​​else return palindrome(a, x+1, y-1);
​​​​}
​​​​
​​​​public static void main(String[] args) {
​​​​​​​​Scanner sc = new Scanner(System.in);
​​​​​​​​
​​​​​​​​int n = sc.nextInt();
​​​​​​​​
​​​​​​​​for(int i=0; i<n; i++) {
​​​​​​​​​​​​String a = sc.next();
​​​​​​​​​​​​System.out.println(palindrome(a, 0, a.length()-1) + " " + cnt);
​​​​​​​​​​​​cnt = 0;
​​​​​​​​}
​​​​​​​​}
​​​​​​​​}

 

 

이번에는 알고리즘 스터디를 통해 재귀 함수에 대해서 공부했습니다!

재귀란 어떤 사건에 자기 자신을 포함하고나 자기 자신을 사용해 정의하는 것입니다.

 

사용하는 이유는 무한으로 루프를 돌려서 결과를 출력할 때 사용합니다.

 

간단한 예시로는 위에서 풀어보았던 팩토리얼, 피보나치수열 등이 있죠!

 

팩토리얼에서 곱셈을 덧셈으로 변경하면 해당 숫자까지의 합을 구할 수 있겠어요!!

 

간단한 예시를 하나 볼까요?

 

재귀의 사용방법 및 출력 순서는 아래와 같습니다.

import java.util.Scanner;

public class Recur {
​​​​static void recur(int n) {
​​​​​​​​if(n > 0) {
​​​​​​​​​​​​recur(n-1);
​​​​​​​​​​​​System.out.println(n);
​​​​​​​​​​​​recur(n-2);
​​​​​​​​}
​​​​}
​​​​
​​​​public static void main(String[] args) {
​​​​​​​​Scanner sc = new Scanner(System.in);
​​​​​​​​
​​​​​​​​System.out.print("정수를 입력하세요 : ");
​​​​​​​​int n = sc.nextInt();
​​​​​​​​
​​​​​​​​recur(n);
​​​​}
}

코드를 순서대로 진행하면 아래와 같이 recur 함수 안에 recur 함수를 자꾸 파고들어가며 n이 0보다 큰 조건이 될때까지 반복합니다.

이렇게 찾으면서 실행되는 순서는 표기한대로 1→2→3→4→5→6→7의 순서로 진행됩니다.

출력 값은 1231421이 출력되며 재귀가 어떻게 진행되는지 알 수 있습니다!

 

재귀 방식도 마찬가지로 코딩테스트할 때 많이 사용된다고 하네요~

 

다양한 문제들을 많이 풀어봐야 익숙해질 것 같네요!

 

다음 스터디때는 재귀의 응용 방법에 대해서 배워볼게요!

 

많은 분들의 피드백은 언제나 환영합니다!  많은 댓글 부탁드려요~~