재귀, 이진탐색(Binary Search), 백트래킹(Backtracking)

재귀(Recursion)

재귀(Recursion) - 자기 자신을 호출하여 자신을 반복적으로 호출하면서 결과를 도출

팩토리얼 - 1부터 n까지의 모든 값을 곱하는 방식

n! 는 1 * 2 * 3 * …. * (n-1) * n 이다. 여기서 맨 끝에 n만 제외하면 (n-1)! 이다.

결론적으로 n! = n * (n-1)! 이다. 또 (n-1)!는 …반복

5! = 5 * 4!;

4! = 4 * 3!;

…

1! = 1 * 0!;

0! = 1;

 

Java 코드 - 재귀 팩토리얼

    // 재귀 - 팩토리얼
    public static int factorial(int n) {
        if (n == 0) { // 기본 케이스
            return 1;
        } else { // 재귀 케이스
            return n * factorial(n - 1);
        }
    }

 

Java 코드 - 재귀 문자열 뒤집기

    // 재귀 - 문자열 뒤집기
	public static String reverseString(String str) {
	    if (str.length() == 0) {
	        return str;
	    } else {
	        return reverseString(str.substring(1)) + str.charAt(0);
	    }
	}

 

Java 코드 - 재귀 피보나치 수열

	// 재귀 - 피보나치
	public static int fibonacci(int n) {
	    if (n == 0) {
	        return 0;
	    } else if (n == 1) {
	        return 1;
	    } else {
	        return fibonacci(n-1) + fibonacci(n-2);
	    }
	}

 

Java 코드 - 재귀 하노이의 탑

	// 재귀 - 하노이  탑
	public static void movePrint() {
		move(3, 1,2,3);
	    int[][] answer = list.stream()
                .toArray(int[][]::new);
	    System.out.println(Arrays.deepToString(answer));
	}
	static List<int[] > list = new ArrayList<>();
    public static void move(int cnt, int start, int mid, int end) {
        if (cnt == 0) {
            return ;
        }
        move(cnt - 1, start, end, mid);
        list.add(new int[]{start, end});
        move(cnt - 1, mid, start, end);
	}

[4, 2, 3, 11, 5, 20, 44, 8, 10, 7]
start
[[1, 3], [1, 2], [3, 2], [1, 3], [2, 1], [2, 3], [1, 3]]
end

 

이진 탐색(Binary Search)

이진 탐색(Binary Search) - 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다.

대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 찾는 방식

시간 복잡도 - O(log n)

원리

1.중앙값 선택

2.중앙값 > 타겟 데이터일 때 중앙값 기준으로 왼쪽 데이터들을 선택

3.중앙값 < 타겟 데이터일 때 중앙값 기준으로 오른쪽 데이터들을 선택

4.반복하다가 중앙값이 타겟 데이터일 경우 종료

 

다만, 이진 탐색의 경우 정렬이 되어있어야 한다. 그래야 중앙값과 타겟 데이터 비교 시 왼쪽 데이터들을 볼껀지 오른쪽을 볼건지 결정을 하게 된다.

 

Java 코드 - 재귀 이진 탐색

    // 재귀 - 이진 탐색
    public static int binarySearch(int[] arr, int low, int high, int key) {
        if (high >= low) {

            int mid = low + (high - low) / 2;
            
            if (arr[mid] == key) {
                return mid;
            }
            else if (arr[mid] > key) {
                return binarySearch(arr, low, mid - 1, key);
            }
            else {
                return binarySearch(arr, mid + 1, high, key);
            }
        }
        return -1;
    }

 

백트래킹(Backtracking)

백트래킹(Backtracking) - 알고리즘 기법 중 하나로, 재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식.

현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의 수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것이다. 즉, 더 이상 탐색할 필요가 없는 상태를 제외하는 것으로 가지 치기라고도 한다.

 

문제

N과 M (1)

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	100761	64134	41240	62.709%

 

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

예제 입력 1 복사

3 1

예제 출력 1 복사

1
2
3

예제 입력 2 복사

4 2

예제 출력 2 복사

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

예제 입력 3 복사

4 4

예제 출력 3 복사

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

 

Java 코드 - 백트래킹

public class Backtracking {
	public static int[] arr;
	public static boolean[] visit;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		// 4 2   3 1 
		arr = new int[M];
		visit = new boolean[N];
		dfs(N, M, 0);
		
	}

	public static void dfs(int N, int M, int depth) {
		if(depth == M) {
			for(int val : arr) {
				System.out.print(val + " ");
			}
			System.out.println();
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(!visit[i]) {
				visit[i] = true;
				arr[depth] = i+1;
				dfs(N, M, depth + 1);
				
				visit[i] = false;
			}
		}

	}
}

3 1
1 
2 
3