[코드 구현] 순열과 조합

Ik·2022년 12월 20일

Algorithm

목록 보기

18/18

백준 1010 문제를 풀며 의문이 들어 기록

처음 문제를 보며 최대 N개의 다리를 놓을 수 있으며 모든 경우의 수를 찾는 것이고 다리가 겹치는 부분은 존재하지 않아야 한다는 것은 알고 있었다
때문에 재귀를 이용해 숫자를 하나씩 늘리며 앞 숫자보다 크지 않는 경우의 조합을 구현하려다 실패

구글링 중에 단순히 조합을 적용해 푸는 것을 확인

1. 이 때 첫번째는 조합과 순열의 관계에 대해 기억이 안난다는 것
1. 두번째는 단순히 조합을 찾는게 다리가 겹치지 않는 조건에 위배되지 않는지 확인이 안되는 것

순열이란

Permutation
수의 순서를 고려해 나열하는 것
- (1,2)와 (2,1)은 다른 것으로 취급

구현 코드(Python)

def permutation(arr, r):
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]

    def generate(chosen, used):
        if len(chosen) == r:
            print(chosen)
            return
	
        for i in range(len(arr)):
            if not used[i]:
                chosen.append(arr[i])
                used[i] = 1
                generate(chosen, used)
                used[i] = 0
                chosen.pop()
    generate([], used)

설명

(노란색 구조를 index만큼 반복) * (빨강 구조(index))

구현코드(Java)

package algorithm;

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

public class expri {
	
	static int answer = 0;
	static List<Integer> finalResult = new ArrayList<>();	
	
	public static void main(String[] args) {
	
		int[] arr = {1,2,3};
		int[] result = new int[arr.length];
		boolean[] visited = new boolean[arr.length];
		
		for(int i = 0; i<arr.length; i++) {
			permutation(arr, result, visited, 0, i+1);
		}
	}
	
	static void permutation(int[] arr, int[] result, boolean[] visited, int depth, int r) {
		
		if(depth == r) {
			for(int i =0; i<r; i++) {
				System.out.print(result[i]+" ");
			}
			System.out.println();
			return;
		}
		
		for(int i =0; i<arr.length; i++) {
			if(!visited[i]) {
				visited[i] = true;
				result[depth] = arr[i];
				permutation(arr, result, visited, depth+1,r);
				visited[i] = false;
			}
		}
	}

}

설명

main 함수에서 목표하는 순열 길이를 permutation 함수에 보내고 방문 유무를 판단해 목표하는 순열 길이에 따른 순열을 저장한다
필기처럼 숫자 3을 가정한다면

main 반복문
	목표하는 순열 길이 1인 경우,
	permutation 반복
    return
	목표하는 순열 길이 2인 경우,
	permutation 반복
    return
	목표하는 순열 길이 3인 경우,
	permutation 반복
    return

위에 내용처럼 반복된다

백트래킹 사용하는 이유는 유망하지 않은 경우 다시 되돌아와야되기 때문
ex) 1 => 2 => 3 후에 함수가 종료된다면 1 => 3 => 4 를 진행하고 이 후에 1 => 4 => 2처럼 되돌아오며 방문 표시를 방문하지 않은 것으로 바꾸는 이유

참조

조합이란

Combination
수의 순서를 고려하지 않고 나열하는 것
- (1,2)와 (2,1)은 같은 것
- 순서 다르되 같은 원소들로 이루어져있기에 같이 취급

코드 구현(Python)

def combinations(arr,r):
    for i in range(len(arr)): 
        if r == 1:  
            yield [arr[i]]
        else:
            for next in combinations(arr[i+1:],r-1): 
                yield [arr[i]] + next

for combi in combinations([1,2,3,4],3):
    print(combi)

설명

코드 구현(Java)

조합의 경우 순열과의 차이점은 순서가 달라도 구성이 같으면 같은 것으로 취급한다

때문에 여기서 중요한 것은 순열과 로직은 유사하게 진행되지만 시작 지점을 정의해주고 시작 지점 이후부터 반복을 진행한다


public class Main {
    static void comb(int[] arr, boolean[] visited, int n, int depth, int start){
        if (depth == n) {
            for(int i = 0; i < arr.length; i++){
                if(visited[i]){
                   System.out.print(arr[i] + " ");
                }
            }
            System.out.println();
            return;
        }

        for(int i = start; i < arr.length; i++){
            visited[i] = true;
            comb(arr, visited, n, depth+1, i+1);
            visited[i] = false;
        }
    }

    public static void main(String[] args) throws Exception {

        int[] arr = {1, 2, 3, 4};

        boolean[] visited = new boolean[4];

        for(int i = 0; i < 4; i++){
            comb(arr, visited, i+1, 0, 0);
        }
    }
}

출력

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

참조

https://m.blog.naver.com/kmh03214/221685090465

문제 해결

조합과 순열 관계에 대해 명확히 확인했고
조합의 경우 순서를 고려하지 않기에 원소 구성이 같으면 같은 원소로 취급,
이는 (1,2,3) = 다리 겹치지 않는 경우, (1,3,2) = 다리 겹치는 경우의 상황을 고려할 필요가 없다,
(1,2,3) 이나 (1,3,2)나 결국 조합상으로 같은 취급이기에 원소 구성과 관련해 겹치는 부분 없다

이전 포스트