[27일차] 순열, 조합 , GCD, LCM

유태형·2022년 6월 5일

Java 알고리즘 코드스테이츠

코드스테이츠

목록 보기

27/77

오늘의 목표

순열
재귀 순열
조합
재귀 조합
GCD
LCM

내용

순열

순열은 순서가 있는 선택의 경우의 수 입니다. 예를들어 A, B, C, D중 3개를 선택한다고 가정하면 A,B,C와 B,C,A는 순서가 다르기 때문에 다른 경우의 수로 각각 카운트 합니다.

nPr 수식어로 n개중에 r개의 요소를 선택하여 순열을 만드는 식은 다음과 같습니다.
nPr = n! / (n-r)!
ex) 5개의 요소중 3개를 뽑아 순열을 만드는 과정
5P3 = 5! / (5-3)! = 5! / 2! = 5x4x3x2x1 / 2x1 = 60입니다.

이제 순열은 어떻게 구하는지 알았으니 자바로 구현해보겠습니다.
n은 for문 하나당 반복횟수, r은 for문 중첩 횟수로 생각하면 반복문으로 조합을 구현할 수 있습니다.
n = 5, r = 3인 경우입니다.

String[] alpha = new String[]{"A","B","C","D","E"};
ArrayList<String[]> result= new ArrayList<>();

for(int i=0; i<alpha.length;i++)
	for(int j=0; j<alpha.length;j++)
    	for(int k=0; k<alpha.length;k++){
        	if(i==j||i==k||j==k) continue;
            result.add(new String[] {alpha[i],alpha[j],alpha[k]});
        }
        
return result;

n은 전체 요소의 갯수입니다. 배열의 길이 alpha.length와 동일합니다.
k는 3이므로 for문이 3중첩인것을 확인 할 수있습니다.
요소의 순서가 바뀐경우는 가능하지만 같은 요소가 2번이상 들어가는 경우는 존재하지 않으므로 제외합니다.
결과는 각각 서로 다른 요소들을 포함하고 있습니다.(순서는 다를 수 있음)

재귀 순열

반복문으로 재귀를 구현하기 위해서는 r은 사전에 알고 있어야 하며, r의 값은 고정적이어야 합니다. 실행시간 도중에 for문의 갯수가 바뀔 수는 없습니다.
r의 값을 알 수 없는 경우, 계속 바뀔 경우 재귀를 이용하여 순열을 구현할 수 있습니다.

재귀 알고리즘 : https://youtu.be/MjW10t9ppok

해당 영상을 시청하면 재귀 과정을 이해하는데 큰 도움이 됩니다.

재귀 순열은 3가지 메서드가 필요합니다.
permutation() : 순열을 재귀 적으로 처리할 함수
swap() : 요소들간 순서를 바꾸는 함수
print() : 해당 순열을 저장할 수 있는 함수

public void permutation(ArrayList<String[]> result, String[] data, int depth, int n, int r){
	if(depth == r){ //종료 조건
    	print(result,data,r);
        return;
    }
    
    for(int i = depth; i < n; i++){ //시작위치부터 마지막 위치까지
    	swap(data,depth,i); //현재위치와 시작위치를 바꿈
        permutation(result,data,depth+1,n,r); //재귀 호출
        swap(data,depth,i); //재귀 호출 후 원 상태 복구
    }
}

public void print(ArrayList<String[]> result, String[] data, int r){
	String[] input = new String[r]; //현재 순열을 담을 배열
    //배열 변수는 레퍼런스값을 가지므로 새로운 배열 생성해야함
    for(int i = 0; i<r; i++) //배열 복사
    	input[i] = data[i];
    result.add(input); //배열을 결과 리스트에 저장
}

public void swap(String[] data, int depth, int i){
	String temp = data[depth];
    data[depth] = data[i];
    data[i] = temp;
}

깊이가 현재 순열의 r개수와 동일하다면 즉 0번~depth번 인덱스가 r개의 갯수만큼 순열이 완성되었다면 결과에 담습니다.
n개의 요소에 0~depth번째 인덱스 만큼 순열로 바뀌어져 있고 유의미한 순열을 가지고 depth+1 ~ n은 무의미한 순열이 있으므로 r만큼 0~depth인덱스를 뽑아서 순열을 만든다고 생각하면 이해하기 편할겁니다.

결과를 담는 리스트를 클래스 변수로 선언하게 되면 처음 하나의 순열은 괜찮지만 순열을 여러개 처리해야 할 경우 이전 값이 오류의 원인이 됩니다.

0~depth만큼 순열이 완성되면 1개의 요소를 더 추가하여 0~depth+1 <= r만큼 순열을 또 다시 만드는 과정을 반복합니다.

조합

조합은 순열과 다르게 순서를 고려하지 않습니다. 순서를 고려하지 않는다는 것은 순서가 달라도 같은 부분집합으로 생각합니다.

순열과 같이 A,B,C,D,E가 존재하고 그 중 3개인 요소를 뽑아 조합을 만든다고 가정하겠습니다.

n = 5, r = 3이므로 A,B,C와 B,C,A는 같은 요소로 인정합니다. 포함 여부만 고려하고 요소간 순서에 의미를 두지 않습니다.

nCr 수식어는 n개의 요소중 r개의 요소를 조합한다는 의미입니다.

ex) 5개중 3개의 요소를 뽑아 조합을 구성합니다.
5C3 = 5! / 3!(5-3)! = 5! / 3!2! = 5x4x3x2x1 / 3x2x1x2x1 = 10

조합도 순열과 마찬가지로 반복문으로 구현시 n개만큼 for문당 최대 반복횟수, r개만큼 for문 중첩횟수를 가집니다.

String[] alpha = new String[] {"A","B","C","D","E"};
ArrayList<String[]> result= new ArrayList<>();

for(int i=0;i<alpha.length;i++)
	for(int j=i+1;j<alpha.length;j++)
    	for(int k=j+1;k<alpha.length;k++)
        	result.add(new String[]{alpha[i],alpha[j],alpha[k]});
            
return result;

순열과 다른점은 조합은 순서를 인정하지 않기 때문에 내부 중첩문은 외부 중첩문의 위치에서 +1한 위치, 무조건 한단계 뒤에서 시작함으로써 뒷 원소가 앞 원소보다 먼저있는 요소를 선택하지 못하도록 합니다.

조합 재귀

조합 재귀도 조합,순열 반복문과 마찬가지로 순열 재귀와 전체적으로 유사하면서도 세부 조건들이 다르게 구성됩니다.

순열 재귀가 swap()을 통해 요소들의 순서들을 바꾸어 가며 모든 경우를 재귀호출 했던 것과 달리 visited[] 배열등을 이용해 사용했냐 안했냐로 완전탐색을 수행합니다.
순열 재귀는 r개의 갯수는 변화가 없었지만 조합 재귀에서는 visitied[i] = true로 해당 요소가 뽑히면 r-1로 r의 갯수는 -1개 줄어듭니다.
순열 재귀는 r의 수는 항상 일정하므로 종료조건이 depth == r이지만 조합 재귀는 r의 수가 요소 선택시 -1씩 줄어드므로 r == 0이 종료조건 입니다.

조합 재귀는 요소들의 순서를 고려하지 않기 때문에 방문여부를 체크하는 boolean[]를 사용하므로 swap()을 사용하지 않습니다.

순열 재귀와 마찬가지로 요소의 갯수 r개를 알수 없거나 실행시간 동안 정해져 있지 않고 변할 수 있을때 재귀를 이용합니다.

public void combination(ArrayList<String[]> result, String[] data, boolean[] visitied, int depth, int n, int r){
	if(r == 0){ //종료조건, 더이상 뽑을 요소x
    	print(result,data,visitied,n); //리스트에 담기
        return;
    }
    for(int i=detph;i<n;i++){ //현재부터 마지막까지
    	visited[i]=true; //방문한 경우
        combination(result,data,visited,i+1,n,r-1);
        //현재위치 + 1 이동, 뽑을 갯수 -1
        visited[i]=false; //다시 방문하지 않은 경우,백트래킹
    }
}

public void print(ArrayList<String[]> result, String[] data, boolean[] visited, int n){
	ArrayList<String> input = new ArrayList<>();
    for(int i=0;i<n;i++){
    	if(visited[i]) //방문했던 요소면
        	input.add(data[i]); //추가
    }
    result.add(input.toArray(new String[0])); //결과 리스트에 추가
}

0 ~ n개의 요소중에 i번째 요소를 포함 시키면 visited[i] = true, 뽑을 갯수 r은 -1처리한 후 다음 요소로 넘어갑니다.
i번째 요소를 포함 시키지 않으면 visitied[i] = false, 뽑을 갯수는 그대로 r개를 유지하고 다음 요소로 넘어갑니다.
모든 요소를 뽑느냐 안 뽑느냐로 나뉘어 r개만큼 뽑을 때 까지 완전탐색을 수행합니다.

GCD

GCD는 최대 공약수의 약자 입니다. 최대공약수랑 두 수 모두 나뉘어 질 수 있는 수들 중 가장 큰 값을 나타 냅니다.
즉, A 와 B 모두 나뉘어 질수 있는 수들의 집합 C중 가장 큰 max값 입니다.

자세한 최대공약수의 증명은 너무 수학적인 관계라 잘 정리된 사이트를 안내하겠습니다.

TCP School : http://www.tcpschool.com/codingmath/common

GCD는 유클리드 호제법으로 간단하게 구현될 수 있습니다. 유클리드 호제법은 나머지 연산을 이용하여 큰수와 작은수 간의 나머지를 계속 구하여 작은 수가 0이 될때, 큰 수의 값이 최대 공약수가 되는 원리를 이용한 알고리즘입니다.

public int GCD(int a, int b){
	int gcd = 1;
    while(b != 0){ //작은 수가 0이 아닐때 까지
    	gcd = a % b; //나머지
        a = b; //a는 b값
        b = gcd; //b는 나머지 값
    }
    return a; //작은 수가 0일때 큰 수가 최대 공약수
}

여기서 b가 작은수, a가 큰 수 임을 확인할 수 있습니다. 그렇다면 gcd연산전에 a와 b의 대소 관계를 확인해야 하는가 의문을 가질 수 있습니다.

a가 b보다 크면 원래대로 진행 되고, b가 a보다 크더라도 첫번째 while반복에서 a와 b가 서로 값이 바뀌게 됩니다.

a = 12, b = 8인 경우

n	a	b
0	12	8
4	8	4
0	4	0

반대로, a = 8, b = 12인 경우

n	a	b
0	8	12
8	12	8
4	8	4
0	4	0

로 b가 a보다 큰 경우 while문의 첫 반복에서 두 값이 서로 바뀌는 것을 확인 할 수 있습니다.

LCM

최대공약수는 두 수의 공약수중 최대 값입니다. 반대로 두 수의 공배수중 최소 값을 최소 공배수, LCM이라고 부릅니다.

LCM도 유클리드 호제법을 이용해 쉽게 구할 수 있습니다.
그 전에 모든 수는 소수 제곱들의 곱으로 표현할 수 있는걸 알아야 합니다.

24 = 2^3 x 3
30 = 2 x 3 x 5

24와 30은 각각 다음 소수들로 표현될 수 있습니다.
두 수를 곱한다면 2^1 과 3^1은 중복되어 두 번 곱해집니다.
이 때, 중복되어 두번 곱해지는 수들의 곱이 GCD입니다.

두수를 곱한다음 GCD로 나누어준다면 두 번 곱해지는 수들이 없어질 것이고, 각 두 수에서 최소한으로 곱한 최소 공배수가 될 것입니다.

LCM(a,b) = a * b / GCD(a,b)

public int LCM(int a, int b){
	return a * b / GCD(a,b);
}

LCM을 구현하기 위해선 GCD를 먼저 구현해야 합니다.

후기

순열과 조합 GCD, LCM은 알고리즘 문제를 풀다 보면 종종 나오므로 알아두는 것이 100번 유익합니다. 특히 순열과 조합을 재귀로 구현하는 것은 어느 코딩테스트 문제풀이 사이트를 가도 존재할 정도 입니다. 또 GCD와 LCM은 단독으로 사용 되는 경우는 잘 없지만 융합되어 사전에 구현되어야 할 사항으로 종종 등장하기도 할 정도입니다. 긴가 민가 했었던 4가지를 오늘 확실히 짚고 넘어갈 수 있었습니다.