재귀 알고리즘
개념을 먼저 익힌 후에 백준 알고리즘을 푸는식으로 해야겠다. 맨땅에 헤딩식으로 하면 나는 잘 이해가 안되는 것 같다. 천천히 하더라도 깊이있게 해보자❗
재귀란?
어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다.
바로 예제로 가보도록 하자
팩토리얼 구하기
재귀의 예시로 팩토리얼이 있다.
n!(팩토리얼) 은 n * n-1 * n-2 * ... 이다.
이것을 그대로 코드로 표현하면 다음과 같다.
import java.util.Scanner;
public class Factorial {
static int factorial(int n) {
if(n > 0)
return n * factorial(n - 1);
else
return 1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(n + "! = " + factorial(n));
}
}동작형식을 자세하게 보면 factorial(int n)은 n이 0보다 크면 n * factorial(n - 1) 를 호출하고 아니면 1을 반환한다.
풀어서 써보자.
예를 들어 n값에 3을 넣었다고 가정한다.
n = 33 * factorial(2);2 * factorial(1);1 * factorial(0);return 1
이 순서로 들어가게 될텐데,
맨 마지막의 1부터 1 * 2 * 3 이 되는 것이다.
호출은 n = 3부터 시작했으니 정렬이 되면 3 * 2 * 1이 되게 된다.
이렇게 해서 3! 의 답인 6을 얻게된다.
내가 재귀를 볼때 막힘없이 봐야 이해가 쏙 되는것 같은 느낌 😂
한번에 안읽히면 머릿속에서 무한루프를 도는느낌이다.
항상 끝부터 쭉 나간다음 생각해 보는것이 이해가 잘된다❗
재귀 안썼을 때
static int factorial(int n) {
int count = 1;
for(int i = n; i > 0; i--) {
count *= i;
}
return count;
}유클리드 호제법
최대공약수를 재귀로 구할 수 있다.
두 정수를 직사각형 두 변의 길이라고 가정하면 최대 공약수를 구하는 문제는 다음과 같아질 수 있다.
직사각형을 정사각형으로 완전히 채우고, 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하자
4와 22 의 최대 공약수를 구해보자고 가정하면
- 22 x 4에서 4를 한변으로 하는 정사각형으로 분할한다.
- 5개의 4 x 4 정사각형이 생기고 2 x 2 두개가 남는다.
- 이렇게 더이상 나눌 수 없는 2 x 2 정사각형이 생겼으므로 2가 최대 공약수이다.
public class Euclid {
static int solution(int x, int y) {
if(y == 0) {
return x;
}
return solution(y, x % y);
}
public static void main(String[] args) {
int x = 22;
int y = 4;
System.out.println(solution(x, y));
}
}단순하게 해석하면 0일때까지 계속 solution 자기 자신을 호출하면서 맨 마지막에 남은 x를 돌려주는 것이다.
재귀 안썼을 때
static int gcd2(int x, int y) {
while (y != 0) {
int temp = y;
y = x % y;
x = temp;
}
return x;
}배열 모든 요소의 최대 공약수
public class EucArray {
static int euc(int x, int y) {
while (y != 0) {
int temp = y;
y = x % y;
x = temp;
}
return x;
}
static int eucArray(int[] arr, int index, int length) {
if(length == 1) {
return arr[index];
}
if(length == 2) {
return euc(arr[index], arr[index + 1]);
}
return euc(arr[index], eucArray(arr, index + 1, length - 1));
}
public static void main(String[] args) {
int[] arr = {3, 6, 8, 12, 15};
System.out.println(eucArray(arr, 0, arr.length));
}
}막상 풀어보니까 이렇게 복잡한거는 재귀보다는 다른 방법이 나아보이는....
'CS' 카테고리의 다른 글
| 불 논리 회고 (0) | 2022.08.07 |
|---|---|
| HTTP (0) | 2022.08.07 |
| 불 논리 정리 (0) | 2022.08.07 |
| [알고리즘] 그리디 (0) | 2022.08.04 |
