12주 1일차 - 데일리코딩 뜯어보기

12주 1일차

1. 배운 것

• 데일리코딩 12, 13 문제 레퍼런스 코드 이해

2. 내용 정리

12번 uglyNumbers

const uglyNumbers = function (n) {
  const uglyNumArr = [1];
  
  let idx2 = 0;
  let idx3 = 0;
  let idx5 = 0;
  
  for(let i = 0; i < n; i++) {
    const mulBy2 = uglyNumArr[idx2] * 2;
    const mulBy3 = uglyNumArr[idx3] * 3;
    const mulBy5 = uglyNumArr[idx5] * 5;
    
    let nextUglyNum = Math.min(mulBy2, mulBy3, mulBy5);
		// 나중에 중복을 제거하는 대신 미리 걸러서
		// 오름차순으로 push 하기 위해 Math.min 해서
		// 다음 ugly number는 x2,x3,x5 한 것중 최솟값으로.
    uglyNumArr.push(nextUglyNum);
    
    if (nextUglyNum === mulBy2) idx2++;
    if (nextUglyNum === mulBy3) idx3++;
    if (nextUglyNum === mulBy5) idx5++;
  }
  
  return uglyNumArr[n - 1];

};

• Ugly Numbers : 소인수분해했을 때 2, 3, 5 로만 이루어진 수.

참고

• Ugly Numbers https://velog.io/@eensungkim/Ugly-Numbers-TIL-87일차

---

13번: 경우의 수, 팩토리얼, 백트래킹(DFS)

function orderOfPresentation (N, K) {
    function factorial(n) {
      if (n <= 1) return 1;
      return n * factorial(n - 1);
    }

      let answer = 0;

      const isChecked = new Array(N + 1).fill(false);
// 방문처리할 배열. 0번째는 더미 데이터로.
      
      for (let i = 0; i < K.length; i++) {
        const cur = K[i];
        isChecked[cur] = true; // 방문처리.(이미 발표한 경우를 제외시키기)
        let checkNeeded = isChecked.slice(1, cur).filter(el => el === false).length;
        answer += checkNeeded * factorial(N - 1 - i);

// 이미 발표한 조 만큼을 N에서 제외하고 경우의 수를 구해 answer에 합친다.
      }
      return answer;
}

경우의 수: 요소 개수의 팩토리얼.

[2,3,1] 의 경우의 수는 3! = 3 * 2* 1

모든 경우의 수를 다 계산해서 indexOf 하면 수많은 경우의 수를 다 탐색해야 함.

이 문제는 모든 경우의 수를 2차원 배열로 구해서 K의 인덱스를 찾는게 아니라 K의 각 1번째부터 마지막 인덱스의 요소들을 각 인덱스의 값인 숫자(조)가 고정되었을 때 나머지 조의 경우의 수를 answer에 전부 더한 값을 리턴하는 문제이다.

(ex: 발표 순서가 2, x, y 일 때 전체 조에서 2조를 제외한 나머지 조가 x에 들어갈 경우의 수, y에 들어갈 경우의 수)

// 이해가 잘 안되었던 부분

// 1. 체크하지 않은 조의 갯수를 구하는 방법
let checkNeeded = isChecked.slice(1, cur).filter(el => el === false).length;
// cur(현재 조) 는 체크해서 true로 바뀌었다.
// isChecked 배열 인덱스 0은 더미데이터라서 1부터 slice
// slice(1, cur) 이므로 인덱스 1부터 cur 전까지 slice해서
// 그 안의 false의 갯수가 체크되지 않은 조의 갯수이다.

// 2. 각 조별 경우의 수 구하기
answer += checkNeeded * factorial(N - 1 - i);
// 정답에 계속 경우의 수를 + 해주다 우리가 찾는 발표 순서

참고

• 문제 해설 https://wnsdufdl.tistory.com/77
• 순열 알고리즘 https://www.youtube.com/watch?v=0tcgYHU8IIs&t=105s
• 순열과 조합 https://velog.io/@devjade/JavaScript로-순열과-조합-알고리즘-구현하기
• 순열 이론 https://velog.io/@rohkorea86/순열-알고리즘
• 부분집합 https://prod.velog.io/@devjade/부분집합-멱집합-알고리즘
• 멱집합 https://jun-choi-4928.medium.com/javascript로-멱집합-powerset-리턴하는-함수-구현하기-f1cce8cc3268
• 백트래킹 https://www.youtube.com/watch?v=H1Bvm3VF03Y

---

react-spring/@parallax

개인 포폴앱 구현시 만들고자 하는 인터랙티브 효과를 위해 react-spring 라이브러리를 찍먹해보았다.