[코테] 조합과 순열

문제를 풀때 재귀로 생각하는게 아직 힘이든다 

 

특히 재귀가 전부가 아니라 전체문제에서 일부분일 경우 이후 과정을 생각하는것은 어려운 일이다.

 

조합 과 순열은 대표적으로 재귀로 푸는 경우가 많은데 숙지를 위해서 적어두자

 

문제를 풀다보면 여러가지 속성이 있고 조합했을 때 결과가 어떠한 조건에 해당되는 경우를 확인하고  요구에 맞게 리턴을 해야하는 경우들이 있다.

 

이런경우 (조합) + (조건 탐색)의 형태로 문제를 풀게되는데 

조건 탐색같은 경우는 문제마다 다 달라질수 있지만 조합하는 경우는 어떤 문제든 공통이 되는부분이라서 빠르게 풀고 가줘야 하는 부분이다. 

 

여기서 조합이 아닌 순열이라는 개념이 있는데 (조합)+(순서까지 중요) => 순열 이라고 판단하면 된다.

 

예를 들자면 [1,10,2,20,3,30] =>[1.10] 과 [10,1] 가 다른경우다 > 순열 ,,, 같은경우다> 조합 의 형태로 문제를 풀어주면 된다.

 

조합에서 특정 갯수의 조합을 구하는 로직을 짜면 되고 그리고 특정갯수가 아닌 전체적으로 나올수 있는 모든 조합이 필요한 경우 for문을 추가해서 사용할수 있다.\

//특정개수 조합구하기
function getcombination(arr,number){
    if(number===1){ // 한개일때
        return arr.map(el=>[el])
    }
    let result = []
    arr.forEach((fixed,idx,origin)=>{
        let rest = origin.slice(idx+1)
        let combinations = getcombination(rest,number-1)
        let attached = combinations.map(el=>[fixed,...el])
        result.push(...attached)
    })
    return result
}

//특정개수 순열구하기
function getpermutation(arr,number){
    if(number===1){
        return arr.map(el=>[el])
    }
    let result = []
    arr.forEach((fixed,idx,origin)=>{
        let rest = [...origin.slice(0,idx),...origin.slice(idx+1)]
        let combinations = getcombination(rest,number-1)
        let attached = combinations.map(el=>[fixed,...el])
        result.push(...attached)
    })
    return result
}

출처:jun-choi-4928.medium.com/javascript%EB%A1%9C-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-21df4b536349

JavaScript로 순열과 조합 알고리즘 구현하기

감사합니다.