자료구조/알고리즘 - 중복 순열/순열/조합, DP의 알고리즘 예시

중복 순열/순열/조합

조합: 순서 상관x
순열: 순서 상관 o
중복순열: 순서도 상관x, 중복도 상관x

 

먼저 반복문(for문)만으로 만들어서 생각해보자

for문을 이용한 순열/조합

중복 순열

중복 순열: 3개 중 3개를 뽑아서 중복 순열을 만든다면?
→ for 반복문을 3중으로 쓰면 된다 (3중 for문)

// 3개 중 3개를 뽑는 중복순열의 예

let result=[];
const game = ['rock', 'paper', 'scissors'];

for(let i=0;i < game.length; i++){
    for(let j=0;j < game.length; j++){
        for(let k=0; k< game.length; k++){
            result.push([game[i], game[j], game[k]]);
        }
    }
}
return result;

단, 이는 시간복잡도를 고려치 못한 구문으로, 시간 복잡도 면에서 비효율적
→ O(N^3); O(N^2)의 복잡도 형태를 가짐

순열

3개 중에서 3개를 뽑아서 순열을 만들자 for 반복문
→ 중복 순열에서 중복되는 경우를 제외시키면 된다

// 3개 중 3개를 뽑는 중복순열의 예

let result=[];
const game = ['rock', 'paper', 'scissors'];

for(let i=0;i < game.length; i++){
    for(let j=0;j < game.length; j++){
        for(let k=0; k< game.length; k++){
            // 중복되는 경우에는 그냥 넘어가자(제외)
            if(i===j || j===k || k===i) continue;
            result.push([game[i], game[j], game[k]]);
        }
    }
}
return result;

조합

3개 중 2개를 뽑아서 조합을 만들자 for 반복문

let result=[];
const game = ['rock', 'paper', 'scissors'];

for(let i=0;i < game.length; i++){
    for(let j=i+1;j < game.length; j++){    //    j는 항상 i보다 1 크다
        // 앞에 하나를 빼서 나열한 상태에서 나머지를 붙인다는 개념이므로!
        result.push([game[i], game[j]]);    
    }
}
return result;

• 여기서 의문점? 그런데 7개중 6개를 뽑아서 만든다면, 6중 포문?
  11개 중 10개는 10중 포문?

→ 로직 짜는 거 자체가 노답이다...(시간 복잡도 또한 노답)

 

반복문으로 할 수 있다면?
→ 재귀로도 할 수 있다는 것을 떠올려야 한다

재귀 함수를 이용한 순열/조합

중복 순열

3개중 3개를 뽑아서 중복 순열을 만들자 with 재귀

// 3개 중 3개를 뽑는 중복순열의 예 (재귀)

let result=[];    // 결과를 담을 배열
const game = ['rock', 'paper', 'scissors'];

const recursion= function(cnt, bucket){
    if(cnt===0){    // 탈출 조건    //출입국 심사 관리소 역할    //cnt는 1씩 감소하도록 설계
    result.push(bucket);
    return;    //해당 함수가 종료됨
    }

for(let i=0;i < game.length; i++){
    const pick=game[i];
    recursion(cnt-1, bucket.concat(pick));
    // 1개 넣은 상태(pick)에서 나머지들을 채우는 거니깐(재귀)
// 리턴으로 해당 함수가 종료되었어도 아직 반복문은 다 돌지 않았으니깐 다시 반복문의
// 인덱스가 올라가면서 다시 진입한다는 것!(바로 윗 단계로 올라간다 생각하면 된다)

}
}

recursion(3, []);    //3개를 뽑으므로 3, 초기 배열은 []로 시작

순열, 조합도 결국 이 구조를 응용한 거라서 나머지(rest)부분만 바뀌는 구조(나머지에 대한 코드 로직만 작성하고 수정하면 됨)

 

DP(동적 프로그래밍)

작은 문제를 풀어서 그 답을 구한다. 그 답을 좀 더 큰 문제를 구하는데 사용한다.(여러 번 반복해서 사용)

 

구해 둔 작은 문제의 답을 메모해두고, 그 것을 참조하면서 푸는 것
→ 구해 둔 작은 문제를 또 다시 풀지 않는다는 게 중요!

 

아래의 배낭(knapsack) 문제 알고리즘이 대표적인 예

// 화폐 종류 (type)을 가지고 특정 금액(target)을 만드는 알고리즘의 예

// target 10 이면
// 지폐 종류가 1 2 5 가 있다고 가정 // type=[1,2,5]
// 1 2 5를 가지고 10을 만드는 경우의 수

//bag이라는 경우의 수를 저장하는 배열을 생성
// 이 배열의 길이는 target+1의 크기만큼 되도록 더미 배열 생성
// 인덱스는 항상 0부터 시작하므로 내가 원하는 값의 경우의 수를 직관적으로 보기 위해...

//bag[0]=1 을 한 이유는 0원을 만드는 방법은 아무것도 안넣는 방법 1가지 이므로
//동전종류(type) / target(구하고자하는 금액)
 // 1 2 3 4 5 6 7 8 9 10 <- 만들어야 하는 액수(인덱스로 쳐서 생각)
//1 1 1 1 1 1 1 1 1 1 1 <-만들수있는 방법 가짓수
//2 0 1 1 2 2 3 3 4 4 5 // 3을 구할때, 3에서 2는 반드시 들어가야 한다. 그렇다면, 3-2=1 , 1을 구하는 모든 경우의 수(total)를 구하는 것과 같다
//5 0 0 0 0 1 1 2 2 3 4
//t2 1 2 2 3 3 4 4 5 5 6 // 2까지 탐색시의 total

//t5 1 2 2 3 4 5 6 7 8 10 // 5까지 탐색시의 total

//    이를 이용한 코드

let bag = new Array(target+1).fill(0) // 타겟의 크기+1 만큼 공간을 가지는 변수 // 배열의 길이는 target 숫자보다 1만큼 더 크다
//bag에 경우의 수의 합을 넣는다
bag[0]=1; //초기값으로 1을 가지고 시작 [1, 0,0,0,0,..., 0] // 0 1 2 3 4 5로 생각!
// let result=0;
for(let i=0;i < type.length;i++){ 
    for(let j=1;j <= target;j++){//target의 길이만큼 반복 대신 1부터 시작
        if(type[i] <= j){ // 지폐 숫자보다 크다면 
            bag[j]=bag[j]+bag[j-type[i]]; // 기존 경우의 수에 type[i]를 뺀 금액을 만들 수 있는 경우의 수를 더해준다
        }
    }
}

return bag[target];