티스토리 뷰

알고리즘

재귀 함수

안드로이드용용 2016. 7. 29. 11:43

재귀 함수의 필요성


예제: 중첩 반복문 대체하기 

0번부터 차례대로 번호 매겨진 n개의 원수 중 네 개를 고르는 모든 경우의 수를 출력하라


보통 아래와 같이 작성할 수 있다.

for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
				for (int k = j + 1; k < n; k++) {
					for (int l = k + 1; l < n; l++) {
						System.out.println(i + "," + j + "," + k + "," + l);
					}
				}
			}
		}

만약 다섯개를 골라야 한다면? 6개를 골라야 한다면 ? 7개를 골라야한다면? (5중, 6중, 7중 for문을 쓰면 되지만 코드가 길고 복잡해진다.)


재귀호출을 사용하면 단순한 반복문보다 간결하고 유연한 코드를 작성할 수 있다.


원소를 고른 뒤 남은 원소를 고르는 작업을 자기 자신을 호출해 떠넘긴다. 

알아야 할 사항

  • 원소들의 총 개수
  • 더 골라야 할 원소들의 개수
  • 지금까지 고른 원소들의 번호
재귀함수 사용
	// n : 전체 원소 수
	// picked: 지금까지 고른 원소들의 번호
	// toPick : 더 고를 원소의 수
	public static void pick(int n, ArrayList list, int toPick) {
		// 기저 사례 : 더 고를 원소가 없을 때 고른 원소들을 출력
		if (toPick == 0) {
			printPicked(list);
			return;
		}
		;
		// 고를 수 있는 가장 작은 번호를 계산한다.

		int smallest = 0;
		if (list.isEmpty()) {
			smallest = 0;
		} else {
			smallest = list.get(list.size() - 1) + 1;
		}
		// 원소 하나를 고른다
		for (int next = smallest; next < n; next++) {
			list.add(next);
			pick(n, list, toPick - 1);
			list.remove(list.size() - 1);

		}
	}

	private static void printPicked(ArrayList list) {

		for (Integer i : list)
			System.out.print(i + " ");
		System.out.println();
	}

이와 같이 제귀 호출을 이용하면 특정 조건을 만족하는 조합을 모두 생성하는 코드를 쉽게 작성할 수 있기 때문에 완전 탐색을 구현할 때 아주 유용한 도구이다.

문제 : 소풍 (난의도 하)

소풍을 갈 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 항상 서로 친구인 학생들끼리만 짝을 짓는 방법을 구하시오


시간 메모리 제한 : 1초 이내에 실행되어야 하고 64MB 이하의 메모리만을 사용


입력

1번째 줄 : 테스트 케이스 수

2번째 줄: 학생 수 + 친구 쌍의 수


출력

한줄에 모든 학생을 친구끼리만 짝지어줄 수 있는 방법


예제 입력

3

2 1

0 1

4 6

0 1 1 2 2 3 3 0 0 2 1 3

6 10

0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5


풀이

//잘못된 재귀
	// 잘못된 재귀 호출 코드
	public static int countPairings(boolean taken[]) {
		// 기저 사례 : 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
		boolean finished = true;
		for (int i = 0; i < n; i++)
			if (!taken[i])
				finished = false;
		if (finished)
			return 1;
		int ret = 0;
		// 서로 친구인 두 학생을 찾아 짝을 지어준다.
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (!taken[i] && !taken[j] && areFriends[i][j]) {
					taken[i] = taken[j] = true;
					ret += countPairings(taken);
					taken[i] = taken[j] = false;
				}
			}
		}
		return ret;
	}


같은 학생 쌍을 두 번 짝지어 줍니다. (1,0)과 (0,1)을 따로 세고 있다.

다른 순서로 학생들을 짝지어 주는 것을 서로 다른 경우로 세고 있음. (0,1)후에 (2,3)을 짝지어주는 것과 (2,3) 후에 (0,1)을 짝지어주는 것은 같은 방법인데 다른 경우로 세고 있다.


올바른 방법 : 사전 순으로 가장 먼저 오는 답 하나만을 세는 것

// 수정 된 재귀 호출 코드
	// taken[i] = i번째 학생이 짝을 이미 찾았으면 ture, 아니면 false
	public static int correctcountParing(boolean taken[]) {
		int firstFree = -1;
		for (int i = 0; i < n; i++) {
			if (!taken[i]) {
				firstFree = i;
				break;
			}
		}
		// 기저 사례 : 모든 학생이 짝을 찾았으면 한가지 방법을 찾았으니 종료
		if(firstFree == -1) return 1;
		int ret = 0;
		// 이 학생과 짝지을 학생을 결정한다.
		for(int pairWith = firstFree+1; pairWith < n; pairWith++) {
			if(!taken[pairWith] && areFriends[firstFree][pairWith]) {
				taken[firstFree] = taken[pairWith] = true;
				ret += correctcountParing(taken);
				taken[firstFree] = taken[pairWith] = false;
			}
		}
		return ret;
	}




여행하는 외판원 문제 (TSP : traveling Sale-man Problem)

public static int n; // 도시 수
	public static double dist[][] = new double[100][100]; // 두 도시간의 거리를 저장하는 배열
	
	//path : 지금까지 만든 경로
	//visied : 각 도시의 방문 여부
	//currentLength : 지금까지 만든 경로의 길이
	//나머지 도시들을 모두 방문하는 경로 중 가장 짧은 것의 길이를 반환
	public double shortestPath(ArrayList path, boolean[] visited, double currentLength) {
		//기저 사례 : 모든 도시를 다 방문했을 때는 시작도시로 돌아가고 종료한다.
		if(path.size() == n) {
			return currentLength + dist[path.get(0)][path.get(path.size()-1)];
		}
		double ret = Double.MAX_VALUE;
		// 다음 방문 할 도시를 전부 시도 해 본다.
		for (int next =0 ; next < n ; next++) {
			if(visited[next]) continue;
			int here = path.get(path.size()-1);
			path.add(next);
			visited[next] = true;
			//나머지 경로를 재귀 호출을 통해 완성하고 가장 짧은 경로의 길이를 얻는다.
			double cand = shortestPath(path, visited, currentLength+ dist[here][next]);
			ret = Math.min(ret, cand);
			visited[next] = false;
			path.remove(path.size()-1);
		}
		return ret;
	}


'알고리즘' 카테고리의 다른 글

분할정복  (0) 2016.08.04
최대 연속 부분 구간 합 최대가 나오는 알고리즘 풀이  (0) 2016.07.27
댓글
댓글쓰기 폼
공지사항
최근에 달린 댓글
Total
66,013
Today
0
Yesterday
10
TAG
more
«   2022/12   »
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
글 보관함