[수학] 3. 경우의 수, 순열

in 자료구조 on 수학




1. 경우의 수

  • 어떤 사건 혹은 일이 일어날 수 있는 경우의 가짓수를 수로 표현


일상 생활에서의 경우의 수

  • 주사위 : 던지는 결과, 1~6 사이의 숫자이므로 경우의 수는 6
  • 윷 : 던지는 결과, 도, 개, 걸, 윶, 모 이므로 경우의 수는 5
  • 가위바위보 : 게임 결봐, 가위, 바위, 보 중에 하나를 낼 수 있으므로 경우의 수는 2
  • 동전 : 던지는 결과, 앞면 혹은 뒷면이르모 경우의 수는 2


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

  • 순열 : 서로 다른 n개의 원소 중에서 r을 중복 없이 골라 순서에 상관 있게 나열하는 경우의 수 nPr
  • 조합 : 서로 다른 n개의 원수 중에서 r을 중복 없이 골라 순서에 상관 없이 나열하는 경우의 수 nCr
  • 중복 순열 : 서로 다른 n개의 원소 중에서 r개를 중복 있게 골라 순서에 상관 있게 나열하는 경우의 수 nH



2. 순열 (Permutation)

  • 서로 다른 n개의 원소 중에서 r개를 중복 없이 골라 순서에 상관 있게 나열하는 경우의 수 nPr
  • nPr = n! / (n-r)!
  • 3개의 알파벳으로 단어를 만드는 경우의 수 : 3P3 = 3 _ 2 _ 1 = 6
  • for 문으로 구현하면 뽑는 갯수 늘면 for 문도 늘어난다 (지양)
  • 재귀 함수로 구현 지향
let input = ["a", "b", "c"];
let count = 0;

function permutation(arr) {
  // 첫번째 위치시킬 요소 a? b? c?
  for (let i = 0; i < arr.length; i++) {
    // 두번째 위치시킬 요소
    for (let j = 0; j < arr.length; j++) {
      // 첫번째 === 두번째 같을 경우
      // 있을 수 없기 때문에 skip
      if (i === j) continue;
      // 세번째 위치시킬 요소
      for (let k = 0; k < arr.length; k++) {
        if (i === k) continue;
        if (j === k) continue;
        console.log(arr[i], arr[j], arr[k]);
        count++
      }
    }
  }
}

permutation(input);
console.log(count);

// output
// a b c
// a c b
// b a c
// b c a
// c a b
// c b a
//6

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

// arr : 배열 s : start 위치 r : 뽑을 갯수(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]]; // swap
    permutation(arr, s + 1, r)
    [arr[s], arr[i]] = [arr[i], arr[s]]; // 원상복귀
  }
}

permutation(input, 0, 2);
console.log(count);

// output
// a b c
// a c b
// b a c
// b c a
// c a b
// c b a
//6



3. 조합(Combination)

  • 서로 다른 n개의 원수 중에서 r을 중복 없이 골라 순서에 상관 없이 나열하는 경우의 수
  • nCr = n!/(n-r)!r!
  • 4개의 숫자 카드에서 2개를 뽑는 경우의 수 : 4C2 = 6
let input = [1, 2, 3, 4];
let count = 0;

function combination(arr) {
    // i = 3 v = 4
  for (let i = 0; i<arr.length; i++){
      // i 이후의 값만 선택 가능하도록
      // j = 4 j < 4 자동 skip
      for (let j = i+1; j<arr.length; j++){
          console.log(arr[i],arr[j])
          count++
      }
  }
}

combination(input);
console.log(count);

// output
// 1 2
// 1 3
// 1 4
// 2 3
// 2 4
// 3 4
// 6

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 - i >= r - s; i++) {
    data[s] = arr[i];
    combination(arr, data, s + 1, i + 1, r);
  }
}

combination(input, output, 0, 0, 2);
console.log(count);

// output
// [ 1, 2 ]
// [ 1, 3 ]
// [ 1, 4 ]
// [ 2, 3 ]
// [ 2, 4 ]
// [ 3, 4 ]
// 6



4. 점화식

  • 점화식(재귀식) : 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식
  • 등차 수열 : 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)


등차수열

let result;

// s : start
// t : 몇씩 증가
// number : 몇번 반복
function forloop(s, t, number) {
  let acc = 0;

  for (let i = 1; i <= number; i++) {
    if (i == 1) {
      acc += s;
    } else {
      acc += t;
    }
    console.log(i, acc);
  }
  return acc
}

// 3부터 시작해서 2씩증가하는 등차수열의 5번째 값 찾기
result = forloop(3, 2, 5);
console.log(result);

//output
// 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 = recursive(3, 2, 5);
console.log(result);

// number : 5 recursie(s,t,4) + 2 = s + 2 + 2 + 2
// number : 4 recursie(s,t,3) + 2 = s + 2 + 2 + 2
// number : 3 recursie(s,t,2) + 2 = s + 2 + 2
// number : 2 recursie(s,t,1) + 2 = s + 2
// number : 1 s


등비수열

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

console.log(forloop(3, 2, 5));

function recursive(s, t, number) {
  // 종료 조건
  if (number == 1){
      return s
  }
  return recursive(s, t, number-1) * t
}

console.log(recursive(3, 2, 5));


팩토리얼

function forloop(n) {
    let acc = 1
    for (let i = n; i>0; i--){
        acc *= i
    }
    return acc
}

console.log(forloop(5))
// 120

function recursive(n) {
    if (n == 1){
        return n
    }
    return recursive(n-1) * n
    
}

console.log(recursive(5))
// 120


피보나치 수열

function recursive(n) {
    if (n-1 == 0 || n == 0){
        return n
    }
    return recursive(n-1) + recursive(n-2)
    
}

console.log(recursive(5)) // 5
console.log(recursive(6)) // 8
console.log(recursive(7)) // 13
console.log(recursive(8)) // 21
  • f(n) = f(n-1) + f(n-2)
  • 양수에서 멈출 수 있도록 break 걸어줘야 한다.
  • f(1) = 1
  • f(2) = 1
  • f(3) = 2
  • f(4) = 3



나의 회고 🤫

순열과 조합의 재귀함수 부분을 몇번이고 복습해도 이해가 잘 가지 않는다…ㅠㅠ
아직 재귀함수에 익숙하지 않아서 벌어지는 문제 같아서 쭉 공부해나가고 가끔 와서 그때는 이해가 갔는지 다시 확인해봐야겠다.
재귀함수 사용하는거 너무 쿨하고 멋진데 나는 아직 그 실력이 안되는 것 같아 너무 아쉽다.
공부를 어느 정도 했을 때는 이 글을 보면서 “이땐 그랬지….ㅋㅋ”하고 넘어갈 수 있는 실력자가 됐으면 좋겠다😭