School algo02 전수조사에서 조합에 관한것(작성중)

매개변수가 여러개 있는것은 체크와 대입을 위한 것이다. n개중 r개를 선택하는 문제인 조합, 3자리 짝수찾기 문제등은 트리를 내려가면서 이것은 넣고 저것은 넣지 않고, 이것은 넣고 저것은 넣지 않고의 과정을 수없이 반복하기 때문에 매개변수가 많아지는 것이다. 재귀 트리 그림을 그려가면서 이 과정의 디테일한 모습이 머릿속에 그려져야 한다. 그리고 강조하지만 체크없는 대입은 없다대부분임). 항상 조건문을 통해 체크가 이뤄지고 조건에 성립할시 대부분의 경우 대입이 일어난다. 

 

Solution1. 아래와 같이 해결가능하지만 매개변수가 많이 존재하는게 걸림.

Java!

import java.util.*;

//index를 이용한 좀더 자유로운(내가 입력하는 n개의 수를 담을 real배열하나를 추가하여 n개의 수를 담을수있음) 조합코드.
//index=> 오직 추가했을때만 증가한다 arr[index]=real[target]과 연관된다(print함수를 통해 실질적으로 출력되는 것이 
//arr[index]이므로 오직 추가되었을때만 증가하는 것
//n ==> 항상그대로
//r ==> 오직 추가했을때만 감소
//target ==> 추가하던 안하던 증가한다. 1.n=target을 검사하기 위해!(추가하던 안하던 총 원소의 개수는 n개로 제한되어 있으므로)
//2. arr[index]의 값을 설정하기 위해!(arr[index]=real[targetf])
public class Main {
	public static void main(String[] args) {
		int[] arr = new int[3];
		int[] real = { 3, 6, 9 };
		combination(arr, 0, 3, 2, 0, real);
	}
	

	public static void combination(int[] arr, int index, int n, int r, int target, int[] real) {
		if(r==0)
			print(arr, index);//index는 원소를 포함할 때만 증가 되므로 무분별하게 커지는 target이 아닌 index를 넣는 것이 맞음.
		else if(n==target) 
			return;
		else {
			arr[index]=real[target];
			combination(arr, index+1, n, r-1, target+1, real);//뽑는경우
			combination(arr, index, n, r, target+1, real);//뽑지않는 경우
		}
	}	
	public static void print(int[] arr, int length) {
		for (int i = 0; i < length; i++)
			System.out.print(arr[i] + " ");
		System.out.println("");
	}	
}

(여기서 잠깐!!! 그렇다면 중복조합을 구하는 코드는 어떻게 될까? 위에 제시된 조합을 구하는 코드와 비교해 보면 다른점은 오직!!! target+1대신에 target으로 들어간 것 뿐이 없다. 생각해 보면 그것이 당연함을 알것이다! 아래는 중복조합을 구하는 코드이다.(매개변수가 6개씩이나 되는 코드를 굳이 위에 기록한것은 이때문이기도 하다. 즉 비교해 보라는 거다.위 코드와 아래코드를. 만약 매개변수가 4개라면 이런 중복조합을 구하는 코드가 구하기 힘들어질 것이다. 단순히 visited를 이용해 참,거짓을 판별해서 중복해서 출력을 할수는 없으니. 그래도 visited배열을 이용하겠다면 map자룍구조를 이용해야 하지 않을까?해당 수가 거짓인지 참인지, 그리고 참이라면 몇번 참인지를 나타내기 위해 말이다.)

import java.util.*;

//index를 이용한 "중복"조합코드
public class Main { 
	public static void main(String[] args) { 
		int[] arr = new int[3];
		int[] real= {3,6,9};
		Scanner sc=new Scanner(System.in);
		int r=sc.nextInt();
		for(int i=0;i<r;i++)
			combination(arr, 0, 3, i, 0,real);
	} 
	public static void combination(int[] arr, int index, int n, int r, int target,int[]real) { 
		if (r == 0) 
			print(arr, index); 
		else if (target == n) 
			return; 
		else { 
			arr[index] = real[target];
			combination(arr, index + 1, n, r - 1, target ,real); //뽑는 경우
			combination(arr, index, n, r, target + 1,real); //뽑지 않는경우
		} 
	}
	public static void print(int[] arr, int length) {
		for (int i = 0; i < length; i++) 
			System.out.print(arr[i] + " ");
		System.out.println(""); 
	} 
}

이상 중복조합에 관한 코드였고 다시 조합으로 돌아가자!

 

Python!

def combination(arr, index, n, r, target, real):
    if(r==0):
        printing(arr,index)
    
    elif(target==n):
        return 
    else:
        arr[index]=real[target]#특정숫자를 포함할때의 함수정의 부분의 매개변수가 위와같이 구성되고
        #구체적 값의 지정이 arr[index]=real[target]와 같고 재귀함수호출부분에서 아래와 같이 매개변수가
        #구성됨을 유기적으로 생각해야 한다. 방법이 없다. 훈련이다!
        combination(arr, index+1, n, r-1, target+1, real)
        combination(arr, index, n, r, target+1, real)

def printing(arr, length):
    for i in range(length):
        print(arr[i], end=' ')
    print()

def main():
    arr=[-1,-1,-1,-1]
    real=[4,2,3,1]
    combination(arr, 0, 4, 2, 0, real)
main()

 

Solution2. 매개변수를 6개에서 4개로 줄인 해결책!

 

Java!

public class Main {
	public static void main(String[] args) {
		int[] arr = { 3, 5, 7 };
		boolean[] visited = new boolean[arr.length];
		combination(arr, visited, 2, 0);
	}
	private static void combination(int[] arr, boolean[]visited, int r, int depth) {
		if(r==0)
			printing(arr, visited);
		else if(depth==arr.length)
			return;
		else {
			visited[depth]=true;
			combination(arr, visited, r-1, depth+1);
			visited[depth]=false;//첫번째 combination코드와 비교하면 첫번째 코드에서는 같은 레벨에서서 arr[index]를 real[target]으로 
			//같은 값으로 정의하고 다음레벨에서 같은 index를 대상으로 arr[index]를 제정의 하였다. 하지만 여기서는 아예 같은 레벨에서 visited[depth]를
			//다른값으로 정의한다. 
			combination(arr, visited, r, depth+1);
		}
	}
	private static void printing(int[]arr, boolean[]visited) {
		int length=arr.length;
		for(int i=0;i<length;i++) {
			if(visited[i]==true)
				System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
	
}

Python!

def combination(arr, visited, r, depth):
    if(r==0):
        printing(arr, visited)
    elif(len(arr)==depth):
        return
    else:
        visited[depth]=True
        combination(arr, visited, r-1, depth+1)
        visited[depth]=False
        combination(arr, visited, r, depth+1)

def printing(arr, visited):
    length=len(arr)
    for i in range(length):
        if(visited[i]!=False):
            print(arr[i], end=" ")
    print()

def main():
    arr=[3,1,4,5]
    visited=[False]*4
    combination(arr, visited, 2, 0)
main()

 

#3자리 짝수찾기 문제

#내려가면서 3자리 수인지 3자리 수라면 짝수인지.

#내려가면서 백의 자리를 고르는 중인지, 그렇다면 0이 아니게

#올라오면서 이전의 자리의 수와 같을시 인덱스 하나증가시키기

# 여러 숫자중 어떤것은 뽑고 어떤 것은 뽑지 않는 것을 각각의

# 경우로 나뉘어 모두 기록해 놓아야 한다. 그래서 이렇게 매개

# 변수의 관계가 복잡해 지는 것이다. 하지만 공통점은 어떤 기저

# 사례에 이르렀음을 알려주는 매개변수가 반드시 있고 기저사례에

#  해당됐을때에는 그동안 특정 배열이나 리스트에 저장되어 있던 결

# 과물을 출력하거나 결과물로 따로 저장해 놓기 마련이다.