TIL 18 (2021.10.24)

오늘은 월, 화에 학습할 express에 대해서 예습을 진행했습니다. http 모듈을 express로 리팩토링했었는데, 요청에 따른 응답은 오지만, 콘솔도 확인이 안되어서(undefined) 예습하는 데 큰 어려움이 있었습니다. 학습했던 내용은 정규과정에 맞춰서 내일 TIL을 작성하도록 하겠습니다. 그리고 보일러플레이트도 다 완성이 되었는데 내일 아침에 한 번 더 검토 후 해당 과제는 마칠 예정입니다.

 

express 때문에 생각보다 오랜 시간이 흘러 계획했던 걸 다 진행 못해서 아쉽지만, 어려움을 느꼈던 토이 문제를 검토하면서 유익한 시간을 보내서 다행입니다.

 

이번 한 주도 열심히 학습하고 복습하고 보내겠습니다.

---

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.
버블 정렬(bubble sort)은 여러 정렬 알고리즘(삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬 등) 중 가장 기본적인 알고리즘입니다.
버블 정렬 알고리즘은 아래와 같습니다.
첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
1, 2를 마지막까지 반복합니다. (마지막에서 두 번째 요소와 마지막 요소를 비교)
1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다.
1~3의 과정을 첫 요소부터 다시 반복합니다.5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 번째로 밀려납니다.
1~3의 과정을 총 n번(배열의 크기) 반복합니다.
이 모습이 마치 '거품이 밀려 올라가는 것과 같은 모습'과 같아서 bubble sort라고 부릅니다.

버블 솔트의 경우, 정보처리기사 필기에서 나와서 학습했었기에 쉽게 이해할 수 있었지만, 해당 코드 구현은 어려웠습니다. 처음에 수도코드 작성했던 건 삭제가 되어서 그 당시에 참고했었던 코드로 학습해보도록 하겠습니다.

const bubbleSort = function (arr) {
  // 마지막 요소에 제일 큰 수가 갈 수 있도록 반복문을 한 번 돌린다.
  if (arr.length === 0) {
    return arr;
  } // 배열의 길이가 0이라면 빈 배열을 리턴한다.

  for ( let n = 0; n < arr.length; n++ ) { // 만약 배열이 [2, 4, 3, 1]이라면,
    // 배열의 요소들을 순회한다.
    let time = 0 // 버블솔트 횟수도 계산을 하며, 이미 정렬이 되어있을 경우를 대비해서 변수를 만들어 놓는다. 
    for ( let i = 0; i < arr.length - 1 - n; i++ ) { // n = 0일 경우, i는 3까지(마지막요소), n = 1일 경우, i는 2가 되는데, => 버블을 진행하면,
      if (arr[i] > arr[i+1]) { // 한 번 돌 때, 제일 큰 수가 뒤로 가기 때문에, 다음 회차에서 맨 마지막 요소에 대한 비교는 빠질 수 있다.
        time++ // 만약에 0번째 요소가 1번째 요소보다 크다면,
        let a = arr[i] 
        let b = arr[i+1]
        arr[i+1] = a // 둘을 변수에 담아서 값을 바꿔준다.
        arr[i] = b
      }
    }
    if (time === 0) { // 바꿀 요소가 전혀 없다면 time은 0이 되어서 반복문이 멈추게 된다.
      break;
    } 
  }

  return arr
}

이중반복문을 사용하는 것이 처음에는 이해가 될 질 않았는데, 이렇게 코드 리뷰를 통해서 해당 코드가 정확하게 버블 솔트를 이용한다는 것을 깨달을 수 있었습니다. 아직은 많이 부족하지만 이러한 코드를 구현할 수 있도록 노력하겠습니다.

---

기존에 재귀에서 학습했던 피보나치 수열의 시간 복잡도는 O(2^N)가 나타나는데, 시간복잡도가 O(N)로 문제를 해결하는 토이 문제.

// 이미 해결한 문제의 정답을 따로 기록해두고,
// 다시 해결하지 않는 기법
// fibo(10) // = fibo(9) + fibo(8)
// = fibo(8) + fibo(7) + fibo(7) + fibo(6)
// 여기까지만 보아도 동일한 문제가 중복으로 계산되는 것을 알 수 있다.
// 이를 통해서 함수 내부에 피보나치 값들이 담길 배열을 하나 만들어준다.
// 여기에다가 값을 넣음으로써 해당 배열에서 값을 찾게되면 시간 복잡도를 줄일 수 있다.

function fibonacci(n) {
  newArr = [0, 1];
  
  let fib = (n) => {
    if(newArr[n] !== undefined) return newArr[n];
    newArr.push(fib(n-1) + fib(n-2));
    return newArr[n]
  }
  return fib(n)
}

재귀를 풀면서 이렇게 배열에 넣어서 푸는 방식을 구현했던 적이 있었는데, 그때 당시에는 이게 시간 복잡도를 줄일 수 있는 방법이라 생각 못하고, 코드가 길어진다는 생각에 아쉬움을 느꼈습니다. 그래서 일반적인 피보나치 수열 알고리즘으로 다시 코플릿을 풀었었는데, 그때 확실히 학습했더라면 이번 토이 문제도 바로 풀 수 있지 않았을까라는 생각이 들어 아쉬웠습니다.

---

세로 길이 2, 가로 길이 n인 2 x n 보드가 있습니다. 2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴해야 합니다.
타일링 문제를 해결하는 효율적인 알고리즘(O(N))이 존재합니다. 반드시 직접 문제를 해결하시면서 입력의 크기에 따라 어떻게 달라지는지 혹은 어떻게 반복되는지 관찰하시기 바랍니다.

처음 이 문제를 봤을 때, 해당 문제를 잘 못 이해해서 접근을 못했었습니다. 정규시간이 끝나고 나서야 피보나치 수열과 비슷하구나 라는 생각을 했었는데, 정확하게는 구현을 못했습니다. 아쉬움이 큰 문제인 만큼, 코드 리뷰를 통해서 문제를 확실하게 이해하고, 접근하는 방법을 길러야겠습니다. 이 방법 피보나치 수열과 동일하게 값을 저장함으로써, 시간 복잡도를 줄일 수 있습니다.  

let tiling = function (n) {


  const fibonacci = (n) => {
    const dp = new Array(n+1).fill(0); // n이 4일 경우, 배열에서는 5번째 인덱스에 해당하기 때문에 1을 더해서 배열을 만든다.
    dp[0] = 1;  dp[1] = 1; // 배열의 0, 1번째 요소는 1로 넣어준다.
                            // n이 1일 경우, 경우의 수는 1개이며, 2일 경우 경우의 수는 2개이기 때문에
    for(let i = 2; i <= n; i++) { // 2부터 n까지 반복을 하면서 배열에 값을 넣어준다.
      dp[i] = dp[i-2] + dp[i-1]; 
    }

    return dp[n]; // 배열의 해당 값을 불러온다.
  }
  return fibonacci(n);
}

// dynamic with tabulation: O(N)
// tabulation은 데이터를 테이블에 정리하면서 bottom-up 방식으로 해결하는 기법을 말합니다.
// let tiling = function (n) {
//   const memo = [0, 1, 2];
//   if (n <= 2) return memo[n];
//   for (let size = 3; size <= n; size++) {
//     memo[size] = memo[size - 1] + memo[size - 2];
//   }
//   return memo[n];
// };

위의 코드는 구글링을 통해서 학습했던 방법이며, 두번째 방식이 레프런스 입니다. 윗 방식도 좋은 방식이지만, 레프런스가 조금 더 작성하기 편리한 부분이 있는 거 같아 해당 방식으로 학습해서, 다음에 비슷한 문제가 나올 때 활용할 수 있도록 노력하겠습니다.(피보나치의 경우 2가 1이지만, 해당 문제의 경우 2는 2이기 때문에, 한 숫자씩 당겨진다고 볼 수 있습니다. 피보나치 1, 1, 2.. 해당 문제는 1, 2, 3, 5...)