😊Today Learn

• 조합 알고리즘에 대해서 공부
• 조합 알고리즘 문제를 for문을 반복해서 풀어봄
• for문을 기반으로 재귀함수로 조합 알고리즘을 만드는 연습

반성할 부분과 느낀점.

1. 한가지 함수에 모든 로직을 다 기재하려는 습관이 있음.
   문제를 세부적으로 나누어서 로직을 짜는것이 중요(즉 최소 단위로 쪼개는 것이 중요)
   ex)조합을 구한다음 해당 조합의 요소가 소수인것만 추려내라는 문제가 있으면,
   조합을 만드는 함수, 요소가 소수인것을 추려내는 함수를 따로 만드는 것이 좋음
   이유: 유지보수하기가 좋을 뿐더러 만약 틀린부분이 있으면 디버깅 및 수정하기 좋음
   

2. 무작정 바로 로직을 작성하려는 습관이 있음.
   문제에 대해서 충분히 고민하고, 수도 코드를 최대한 써서 내가 무엇을 하려는지 먼저 청사진을 그려보도록 하자..

3. 재귀함수는 모든 for문을 대처가 가능하기 때문에 재귀함수가 어렵다면 우선 for문을 먼저 만들어보고.. 재귀함수를 만들어 보는 연습을 해보는것도 좋을것 같은 생각이 들었다.

조합(combination)

• 순열의 경우 순서를 중요시하지만 조합의 경우 순서를 고려하지 않음(즉, 중복을 허용하지 않음)

  조합의 경우 [1,2,3]이나 [3,2,1]은 같은것(순서를 고려하지 않기 때문에)

-조합의 일반식(n개중에 r개를 중복없이 선택할 경우)

일반식: nCr = n! / (r! * (n - r)!)

• 순열과 조합의 경우 for문과 재귀의 반복 횟수는 내가 몇개를 선택하는지에 따라 중첩 횟수가 나뉨. 예를들면.. 5개중 3개를 선택한다고 하면 for문과 재귀는 3번씩 중첩해서 수행된다고 보면됨.

for문으로 만든 조합

function boringBlackjack(cards) {
  let count = 0;

    // 1. cards 에서 카드 3장 뽑기
    let length = cards.length;
    // 카드 뽑는 방식은 첫 카드를 cards 의 0번 index 부터 고정해 놓고 1씩 뒤로 옮겨간다
    for (let i = 0; i < length; i++) {
    // 두 번째 카드의 인덱스는 첫 카드 + 1에서 시작해야 하고
      for (let j = i + 1; j < length; j++) {
    // 세 번째 카드의 인덱스는 두 번째 카드 + 1에서 시작해야 한다 
        for (let k = j + 1; k < length; k++) {
          const number = cards[i] + cards[j] + cards[k];
          // 세 카드의 합이 소수이면 경우의 수 + 1
          if (isPrime(number)) count++;
        }
      }
    }
  
    function isPrime(number) {
  
      for (let i = 2; i < number/2; i++) {
        if (number % i === 0) return false;
      }
      return true;
    }
  
    return count;
}

재귀함수로 만든 조합

function boringBlackjack(cards) {
  const result = [];
  function combination(cards, start, value, depth) {
    if (depth === 0) {
      if (isPrime(value)) {
        result.push(value);
      }
      return;
    }

    for (let i = start; i < cards.length; i++) {
      // combination(cards, i + 1, value.concat(cards[i]), depth - 1);
      combination(cards, i + 1, value + cards[i], depth - 1);
    }
  }

  combination(cards, 0, 0, 3);
  return result.length;

  function isPrime(number) {
    for (let i = 2; i < number / 2; i++) {
      if (number % i === 0) return false;
    }
    return true;
  }
}