순열과 조합(코딩테스트)

순열(Permutation)과 조합(Combination)의 차이

순열과 조합의 가장 큰 차이점은 순서의 고려 여부입니다:

• 순열(nPr): 순서가 중요한 경우 사용
• 조합(nCr): 순서가 상관없는 경우 사용

시간 복잡도 이해하기

For문이 중첩될 때마다 시간 복잡도가 n배씩 증가합니다. 특별한 경우로 n/2씩 감소하는 경우 시간 복잡도는 O(log N)이 됩니다.

JavaScript로 구현하는 순열

function permutation(arr, r, output = [], visited = new Array(arr.length).fill(false)) {
    if (output.length === r) {
        console.log(output);
        return;
    }
    
    for (let i = 0; i < arr.length; i++) {
        if (!visited[i]) {
            visited[i] = true;
            output.push(arr[i]);
            permutation(arr, r, output, visited);
            output.pop();
            visited[i] = false;
        }
    }
}

주요 매개변수:

• arr: 원본 배열
• r: 선택할 요소의 개수
• output: 현재까지의 순열 결과
• visited: 방문 여부 체크 배열

JavaScript로 구현하는 조합

function combination(arr, r, data = [], idx = 0, start = 0) {
    if (idx === r) {
        console.log(data);
        return;
    }
    
    for (let i = start; i <= arr.length - (r - idx); i++) {
        data[idx] = arr[i];
        combination(arr, r, data, idx + 1, i + 1);
    }
}

주요 매개변수:

• arr: 원본 배열
• r: 선택할 요소의 개수
• data: 현재까지의 조합 결과
• idx: 현재 선택한 개수
• start: 탐색 시작 위치

수식 정리

• 순열(nPr): n!/(n-r)!
• 조합(nCr): n!/(n-r)!r!