경우의 수

완전탐색으로 경우의 수를 푸는 알고리즘

 

1) 순열: 서로 다른 n개의 원소중에 r를 중복 없이 골라 순서에 상관있게 나열하는 경우의 수 

    3개의 알파벳으로 단어를 만드는 경우의 수 

 

for문을 사용하면 3번중첩되기 때문에 좋은 코드가 될 수 없다

let input -["a", "b", "c"]
let count = 0;

function permutation(arr){
	// for i -> 첫번째 index 위치시킬 요소 a,b,c [i,0,0]
    for(let i = 0; i < arr.length; i++){
		//for j =>  두번째 index 위치시킬 요소[i,j,0]
    	for(let j = 0; k <arr.length; j++){
        	if(i ==j) continue;
            // for k => 세번째 index위치시킬 요소 [i, j,l]
            if(i == k) continue;
            if(j == k) continue;
            
            condole.log(arr[i], arr[j], arr[k]);
        }
    }
}

permutation(input)

 

 

그래서 재귀함수를 사용합니다.

let input -["a", "b", "c"]
let count = 0;

function permutation(arr,s,r){
	//1. 재귀 함수를 멈춰야할 조건
    if(s == r){
    	count++;
        console.log(arr);
        return;
    }
    
    //2. 재귀를 돌면서 변경되어야 될 부분 . 메인 로직
	for(let i = s; i< arr.length; i++){
    	[arr[s], arr[i]] = [arr[i], arr[s]]; // 스왑
    	permutation(arr, s + 1, r); 
        [arr[s], arr[i]] = [arr[i], arr[s]];// 원상복귀
    }
}

permutation(input, 0, 2)

 

 

 - 조합 : 서로 다른 n개의 원소중에서 r를 중복없이 골라 순서에 상관없이 나열하는 경우의 수

4개의 숫자 카드에서 2개를 뽑는 경우의 

 

for문을 사용하면 2번 중첩되기 때문에 좋은 코드가 될 수 없다

let input = [1,2,3,4]
let count = 0;

function combination(arr){
	//for-> 뽑는 개수 
    for(let i = 0; i < arr.length; i++){
    	for(let j = 1; i < arr.length; j++){
        	count++;
        }
    }
}

combination(input);

그래서 재귀함수를 사용합니다.

let input = [1,2,3,4]
let count = 0;
let output = [];

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

combination(input, output, 0, 0, 2);

 

 

점화식 : 수열에서 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식

등차수열 F(n) = F(n-1) + a

등비수열 F(n) = F(n-1) * a

팩토리얼 F(n) = F(n-1) * n

피보나치 수열 F(n) = F(n-1) +  F(n-2)

 

등차수열 예제 - 1

let result;
function forloop(s, t, number){
	let arr = 0;
    
    for(let i = 1;  i <= number; i++){
    	if(i == 1)
        	acc += s
        else
        	acc += t;
        console.log(i, acc);
     }
   return acc;
 }
 result = forloop(3,2,5)
 console.log(result);

 

1 3

2 5

3 7

4 9

5 11

11 

 

재귀함수

let result;
function recursive(s, t, number){
    if(number == 1)
        return s;
 	}
   return recursive(s,t, number-1) + t;
 }
 result = forloop(3,2,5)
 console.log(result);

1 3

2 5

3 7

4 9

5 11

11 

 

등비수열 예제 - 1

let result;
function forloop(s, t, number){
	let arr = 0;
    
    for(let i = 1;  i <= number; i++){
    	if(i == 1)
        	acc *= s
        else
        	acc *= t;
        console.log(i, acc);
     }
   return acc;
 }
 result = forloop(3,2,5)
 console.log(result);

 

1 3

2 6

3 12

4 24

5 48

48

 

재귀함수

let result;
function recursive(s, t, number){
    if(number == 1)
        return s;
 	}
   return recursive(s,t, number-1) * t;
 }
 result = recursive(3,2,5)
 console.log(result);

1 3

2 6

3 12

4 24

5 48

48

 

팩토리얼 예제 - 1

 

재귀함수

let result;
function recursive(number){
    if(number == 1)
        return s;
 	}
   return recursive(number - 1) * number;
 }
 result = recursive(5)
 console.log(result);

 

120

 

피보나치 수열 예제 - 1

 

재귀함수

let result;
function recursive(number){
    if(number == 1 || number ==0)
        return number;
 	}
   return recursive(number - 1) + recursive(number - 2);
 }
 result = recursive(5)
 console.log(result);

5

 

- 중복 순열: 서로 다른 n개의 원소 중에서 r개를 중복있게 골라 순서에 상관없이 나열하는 경우의 수