[Algorithm] recursive(재귀 알고리즘)

백준 17478 문제

 

• 재귀란 어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을 때를 의미한다. 
• 재귀를 효과적으로 사용하면 무한한 값에 대한 정의 뿐만 아니라 프로그램도 간결하게 구할 수 있다.
• 보통 큰 문제를 작은 부분 문제로 나눠서 풀 때 사용한다.(ex. 팩토리얼, 피보나치 같은 작은 규칙 → 큰 규칙)

1. 기저 사례(재귀를 종료시킬 조건(재귀 깊이)) 
2.  반복 작업 메인 로직 (재귀 호출을 위한 점화식)

• 기저 사례는 재귀함수를 멈춰줘야 하기 떄문에 재귀 함수 가장 위에 있다.
• 메인 로직 같은 경우는 같은 일을 하는 함수이므로 점화식 같은 규칙을 추론해낼줄 알아야한다. 

factorial 구하기

재귀를 사용한 예로 가장 먼저 음이 아닌 정수의 팩토리얼 값을 구하는 프로그램이 있다. 음이 아닌 정수 n!은 다음과 같이

재귀적으로 정의할 수 있다.

 

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 scn = new Scanner(System.in);
		
		System.out.print("정수를 입력하세요 : ");
		int x = scn.nextInt();
		
		System.out.println(x + "의 팩토리얼은 " + factorial(x) + "입니다.");
	}

}

팩토리얼은 n-1개의 팩토리얼 값을 구하기 위해 다시 factorial 메서드를 호출한다. 

유클리드 호제법을 통한 최대공약수 구하기

두 정수의 최대공약수를 재귀적으로 구하는 방법은 두 정수를 직사각형 두 변의 길이라고 생각하면 두 정수의 최대공약수를 구하는 문제는 다음 문제로 바꿀 수 있다.

직사각형을 정사각형으로 빈틈없이 채운다.
이렇게 만들어진 정사각형 가운데 가장 긴 변의 길이를 구하자

 

먼저 짧은 변의 길이를 한 변으로 하는 정사각형으로 채운다. 남은 직사각형에도 같은 작업을 반복한다. 정사각형 만으로 구성했을 때 한 변의 길이가 최대 공약수가 된다.

public class EuclidGCD {
	static int gcd(int x , int y) {
		if(y == 0) 
			return x;
		else 
			return gcd(y,x%y);
	}
	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		
		System.out.println("두 정수의 최대공약수를 구합니다.");
		
		System.out.print("정수를 입력하세요 : ");
		int x = scn.nextInt();
		System.out.print("정수를 입력하세요 : ");
		int y = scn.nextInt();
		
		System.out.println("최대공약수는 "+ gcd(x,y) + "입니다.");
	}

}

두 정수가 주어질 경우 큰 값을 작은 값으로 나누었을 때 나누어 떨어지면 최대공약수이다.  위 코드에서 나누어 떨어질 때 까지 gcd(y , x % y)를 반복하여 최대공약수 값을 구할 수 있다.

 

+ 최소공배수는 두 수를 곱한후 최대공약수를 나누는 방식으로 구할 수 있다.(python 코드로 일단 구현해보았다.. 코테는 파이썬이 익숙해서..)

def GCD(n,m) :

    if m == 0 :

        return n

    else :

        return GCD(m,n%m)

 

def LCM(n,m) :

    return int((n*m)/GCD(n,m))

n,m = map(int,input().split())

 

print(LCM(n,m))

하노이의 탑

 

하노이의 탑은 작은 원반이 위에, 큰 원반이 아래에 위치하도록 쌓은 원반을 3개의 기둥 사이에서 옮기는 문제이다. 

모든 원판은 크기가 다르고 처음에는 모든 원판이 규칙에 맞게 첫번째 기둥에 쌓여 있다.

이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮기면 된다. 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수 없다.

public class Hanoi {
	static void move(int no, int x , int y) {
		if(no > 1)
			move(no-1,x,6-x-y);
		System.out.println("원반[" + no + "]를 " + x + "번 기둥에서 " + y + "번 기둥으로 옮김");
		
		if(no > 1)
			move(no -1 ,6-x-y,y);
	}
	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		
		System.out.println("하노이의 탑");
		System.out.print("원반의 개수:");
		int n = scn.nextInt();
		
		
		move(n,1,3);
	}

}

1번 기둥(start)에 N개의 원판이 있고 3번 기둥(mid)으로 옮겨야 한다고 가정했을때, N개의 원판을 모두 3번 기둥으로 옮기는 방법은 다음과 같다. 

1. 1번 기둥에 위치한 N개의 원판 중, 위에 있는 N-1개의 원판을 2번 기둥(to)으로 옮긴다. → hanoi(n-1,start,mid,to)
2. 1번 기둥에 남아있는 1개의 원판을 3번 기둥으로 옮긴다. => hanoi(1,start,to,mid)
3. 2번 기둥에 있는 N-1개의 원판을 3번 기둥으로 옮긴다.  => hanoi(n-1,to,start,mid)

def hanoi(n,start,mid,end) :

  if n == 1 :
    print(start,end, sep = " ")
    
  else :
    hanoi(n-1,start,end,mid)
    hanoi(1,start,mid,end)
    hanoi(n-1,mid,start,end)

n = int(input())
print(2**n-1)

if n <= 20 :
  hanoi(n,1,2,3)

재귀 함수 대표 문제

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

 

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

 

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

 

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