학습방향

for문을 통해서 구현해보고, 그 이후 재귀를 통해서 구현해보자.

구현 원리를 충분히 이해하는 것이 추후 응용문제 풀이에 도움이 된다.

순열

서로 다른 n개의 원소 중 순서를 고려하여 r개의 원소를 선택하는 방법이다.

예를 들어 [’a’,’b’,’c’]를 사용하여 2개의 원소를 선택하는 방법을 직접 다 써보면 다음과 같다.

ab, ac , ba, bc, ca , cb

이를 그림으로 나타내면 다음과 같다.

그림을 통해서 a,b,c 모두 한번씩 선택해야 함을 알 수 있고, 또, 각각의 선택에서 다음 선택을 할 때는 , 이전에 선택한 요소를 빼고 남은 요소들을 한번씩 선택해야 함을 알 수 있다.

이를 단순 for문으로 구현한다면 다음과 같을 것이다.

for(let i = 0; i< arr.length; i++){
    for(let j = 0; j < arr.length; j++){
        if(arr[i] === arr[j]) continue
        console.log(`[${arr[i]},${arr[j]}]`)
    }
}

2개의 요소를 뽑아야 하기 때문에 이중 반복문을 사용하였고, 현재 뽑은 요소가 외부 반복문에서 뽑은 요소와 같으면 안되기 때문에 조건문을 주었다. 여러개인 경우 조건도 or로 연결해서 구현할수있다.

이제 저 조건문을 빼기만 하면 중복순열을 얻을 수 있다.

단, 여러 개를 선별하는 경우에는 다중 for문 사용이 어렵다. 그러므로 이때는 일반화를 위하여 재귀를 사용하는 것이 적절할 것이다.

재귀를 사용한 코드는 다음과 같다.