[알고리즘 문제해결 전략] 재귀함수

재귀 함수를 만들 key point를 `알고리즘 문제해결 전략`을 보고 정리해보려고 한다.

 

원자성 : 더이상 쪼개지지 않는 성질

  재귀함수에서는 원자성을 갖는 작업들을 가리켜 기저사례(base case)라고 한다.

1부터 n까지의 합을 계산하는 반복 함수를 생각해보자

n*(n-1)*(n-2)*...*1

이 식은 n개의 숫자들로 이뤄져있다. 여기서 원자성은 무엇일까? 

1이다. n=1인 case와 그 외 case로 나눠서 코드로 생각해보면

일단 n != 1부터

int recursiveSum(int n) {
	return n + recursiveSum(n-1);
}

이것을 생각할 수 있다. n=1일때 이 식을 사용하면 갯수는 양수이어야 하므로 문제가 생긴다. 그래서 base case를 나눠 다시 코드를 생각해보면 

int recursiveSum(int n) {
	if(n == 1) return 1;
    return n + recursiveSum(n-1);
}

이렇게 된다.

 

연습!!

NCM : N개 중 M개 고르기

B.C : 아무것도 고르지 않을때(m=0) 또는 고를 수 있는 원소가 없을 때(n=0, m>0)

import java.util.ArrayList;
import java.util.List;

public class Test {
	public static void main(String[] args) {
		int n = 5; // n 값 설정
        	int m = 3; // m 값 설정
        List<Integer> picked = new ArrayList<>(); // 결과를 저장할 리스트

        NCM(n, picked, m);
	}
	
	// picked : 지금까지 고른 원소들의 번호
	public static void NCM(int n, List<Integer> picked, int m) {
		// 종료 조건: 더 이상 고를 것이 없으면 결과 출력
		if(m == 0) {
			printPicked(picked); 
			return;
		}
		
		// 리스트가 비어있는지 확인하여 최소한으로 선택 가능한 숫자 결정
       		// 처음에는 0부터 시작하고, 그 이후에는 마지막으로 고른 숫자의 다음 숫자부터 시작
		int smallest = picked.isEmpty() ? 0 : picked.get(picked.size() - 1) + 1;
		// 예를 들면, n이 5이고 현재 picked 리스트가 [1, 2]라면 smallest는 3
        
		// smallest부터 n까지 반복
		for (int next = smallest; next < n; ++next) {
			// 다음 숫자를 선택
			picked.add(next);
			// 나머지 숫자들을 재귀적으로 선택
            	NCM(n, picked, m - 1);
            	// 선택된 숫자를 다시 되돌림 (백트래킹)
            	picked.remove(picked.size() - 1);
            	// 예를 들면, 처음에 0을 골랐더라도 이후에는 1, 2, 3, 4 중에 고를 수 있음
        }
		
	}
	
	public static void printPicked(List<Integer> picked) {
	    for (int num : picked) {
	        System.out.print(num);
	    }
	    System.out.println();
	}

}

 

보글 문제

Y에 근접한 경우의 수 : 8

B.C : 1. 위치(y, x)에 있는 글자가 원하는 단어의 첫 글자가 아닌 경우 항상 실패

         2. (1번 경우에 해당되지 않을 경우) 원하는 단어가 한 글자인 경우 항상 성공

public class WordSearch {
    private static final int[] dx = {-1, -1, -1, 1, 1, 1, 0, 0};
    private static final int[] dy = {-1, 0, 1, -1, 0, 1, -1, 1};
    private static char[][] board = {
            {'N', 'N', 'N', 'N', 'S'},
            {'N', 'E', 'E', 'E', 'N'},
            {'N', 'E', 'Y', 'E', 'N'},
            {'N', 'E', 'E', 'E', 'N'},
            {'N', 'E', 'E', 'E', 'N'}
    };
    
    public static void main(String[] args) {
        System.out.println(hasWord(2, 2, "YES"));
    }

    private static boolean hasWord(int y, int x, String word) {
    	// B.C 1: 시작 위치가 범위 밖이면 무조건 실패
        if (!inRange(y, x)) return false;
        // B.C 2: 첫글자가 일치하지 않으면 실패
        if (board[y][x] != word.charAt(0)) return false;
        // B.C 3: 단어의 길이가 1이면 성공
        if (word.length() == 1) return true;
        // 인접한 8칸 검사한다.
        for (int direction = 0; direction < 8; ++direction) {
            int nextY = y + dy[direction];
            // 다음 칸이 범위 안에 있는지, 첫 글자는 일치하는지 확인할 필요가 없다.
            int nextX = x + dx[direction];
            if (hasWord(nextY, nextX, word.substring(1))) {
                return true;
            }
        }
        return false;
    }

    private static boolean inRange(int y, int x) {
        int boardHeight = board.length;
        int boardWidth = board[0].length;
        return 0 <= y && y < boardHeight && 0 <= x && x < boardWidth;
    }
}

 

소풍

예제 입출력 분석

3 // 테스트 케이스 수(C<=50)

2 1 // 학생의 수(2<=n<=10), 친구 쌍의 수(0<=m<=n(n-1)/2)

0 1 // 서로 친구인 두 학생의 번호 // 출력 결과 : 1

4 6 // 학생의 수(2<=n<=10), 친구 쌍의 수(0<=m<=n(n-1)/2)

0 1 1 2 2 3 3 0 0 2 1 3 // 서로 친구인 두 학생의 번호 // 출력 결과 : 3

6 10 // 학생의 수(2<=n<=10), 친구 쌍의 수(0<=m<=n(n-1)/2)

0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5 // 서로 친구인 두 학생의 번호 // 출력 결과 : 4