The Other Algorithms

Cartesian product

두 개의 set에서 각 요소의 곱을 나타내는 방법이다.

예를 들어, A = [1, 2] / B = [3, 4] 가 있다면 AxB = [[1, 3], [1, 4], [2, 3], [2, 4]]  이런 식으로 나타내게 된다.

function cartesian(arr1, arr2) {
  const result = [];

  for (let i = 0; i < arr1.length; i++) {
    for (let j = 0; j < arr2.length; j++) {
      result.push([arr1[i], arr2[j]])
    }
  }

  return result
}

 

이렇게 되면 Big O는 O(mn)가 된다. arr1과 arr2의 길이가 다르기 때문에 그걸 곱한 게 새로운 배열의 길이가 되고

O(mn)은 작은 것은 보지 않기 때문에 결과적으로는 O(n)이 된다.

 

Climbing staircase

문제: 주어진 계단 수(n)에 따라서 올라갈 수 있는 방법이 몇 개가 있는지 리턴해라. 계단은 1개 혹은 2개씩 올라갈 수 있다.
예를 들어 n = 3 -> (1, 1, 1) (1, 2) (2, 1) ===> 3

 

계단을 한 개 올라가는 경우: (1), 리턴값: 1

계단을 두 개 올라가는 경우: (1, 1) (2), 리턴값: 2

계단을 세 개 올라가는 경우: (1, 1, 1) (1, 2) (2, 1), 리턴값: 3

계단을 네 개 올라가는 경우: (1, 1, 1, 1) (2, 1, 1) (1, 2, 1) (1, 1, 2) (2, 2), 리턴값: 5

 

이런 식으로 피보나치와 같이 [개수 - 1] 과 [개수 - 2]의 합과 같다. 

function climbing(n) {
  const noOfWays = [1, 2]

  for (let i = 2; i <= n; i++) {
    noOfWays[i] = noOfWays[i-1] + noOfWays[i-2]
  }

  return noOfWays[n-1]
}

 

Big O -> O(n)