[Daily Coding 7]시간복잡도/문자열, 숫자 정수로 변환/Stack, Queue, DFS, BFS/진수 변환/while 문/재귀 호출 횟수/Binary Tree, Binary Search Tree

hameee·2023년 1월 8일

Daily Coding

목록 보기

7/10

1.시간복잡도

// O(1)
function timesTwo(num) {
  return 2 * num
}

// O(n)
function reverseArray(arr) {
  let newArr = []
  for (let i = arr.length - 1; i >= 0; i--) {
    newArr.push(arr[i])
  }
  return newArr
}

// O(n^2)
// arr1.length -> n
function multiplyAll(arr1) {
  let total = 0
  for (let i of arr1) {
    for (let j of arr1) {
      total += i * j
    }
  }
  return total
}

// O(nm)
// arr1.length -> n, arr1.length -> m
function multiplyAll(arr1, arr2) {
  let total = 0
  for (let i of arr1) {
    for (let j of arr2) {
      total += i * j
    }
  }
  return total
}

// O(2^n)
// 함수가 호출될 때마다 2번씩 또 호출 -> 이것을 트리의 높이(n)만큼 반복
function fibonacci(num) {
  if (num === 0) return 0
  else if (num === 1) return 1
  return fibonacci(num - 1) + fibonacci(num - 2)
}

// O(log(n))
// 이진 검색
function binarySearch(k, arr, start, end) {
  if(start > end) return -1;
  middle = (start + end) / 2;
  if(arr[middle] === k) return middle;
  else if(arr[middel] > k) return binarySearch(k, arr, start, middle - 1);
  else return binarySearch(k, arr, middle + 1, end);
}

// O(log(n^n)) = O(nlog(n))
function linearithmic(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 1; j < n; j = j * 2) {
      console.log("Hello")
    }
  }
}

참고 영상
이론: https://youtu.be/6Iq5iMCVsXA
문제 풀이: https://youtu.be/QBZnX_P_dj4

참고 사이트
https://itprogramming119.tistory.com/entry/Javascript-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EC%A0%95%EB%A6%AC-%EB%B0%8F-%EC%98%88%EC%A0%9C

2.정수로 변환해주는 메서드

주의. 정수는 모두 10진수, 2진법은 정수의 표현법 중 하나

1) 문자열 -> 정수

-parseInt(문자열, 인자로 넣은 문자열의 진수)
문자열 인자를 파싱하여 특정 진수의 정수를 반환, 숫자 넣어도 오류 안 남

첫 문자열이 숫자가 아닌 경우(부호는 상관없음) -> NaN
중간 문자열이 숫자가 아니면 -> 숫자인 부분까지만 인식

parseInt('-4.123') // -4
parseInt(-4.123) // -4(인수가 숫자여도 오류 안남)
parseInt('--4.123') // NaN
parseInt('a4.123') // NaN
parseInt('41a2.3') // 41
parseInt('100', 2) // 4

2) 숫자 -> 정수

-Math.trunc(숫자)
주어진 값의 소수부분을 제거하고 숫자의 정수부분을 반환

Math.trunc(-4.123) // -4

-올림, 반올림, 내림
Math.ceil(숫자)
Math.round(숫자)
Math.floor(숫자)

3.천단위로 콤마 찍기

Number.toLocaleString()
주의. 문자열로 반환

let num = 1234567;
num.toLocaleString() // "1,234,567"

4.Stack, Queue, DFS, BFS

1) stack/queue의 노드 출력 과정

시작 노드 stack/queue에 추가 -> stack/queue에서 노드 꺼냄 -> 해당 노드의 자식 노드들을 stack/queue에 추가 -> 꺼낸 노드 출력 -> 회색 부분 반복

2) stack

-Last In First Out, LIFO
-깊이 우선 탐색(Depth First Search, DFS)에 이용

3) queue

-Fist In First Out, FIFO
-너비 우선 탐색(Breadth First Search, BFS)에 이용

참고 동영상: https://youtu.be/_hxFgg7TLZQ

5.진수 변환

1) 10진수 -> n진수

: Number.toString(n)

// toString 앞 -> 숫자, toStirng 반환 값 -> 문자열
let num = 4
num.toString(2) // '100'

2) n진수 -> 10진수

: parseInt(Number/Stirng, n)

parseInt('100', 2)// 4
parseInt(100, 2)// 4

6.while 문

2로 나누어떨어질 때까지 2로 나누기

while(num % 2 === 0) {
  num = num / 2
}

7.재귀는 가능한 적게 호출

// 변수에 재귀 호출문을 담고 이후 변수를 사용 -> 테스트 케이스 통과
function power(base, exponent) {
  if (exponent === 0) return 1;

  const half = parseInt(exponent / 2);
  const temp = power(base, half);
  const result = (temp * temp) % 94906249;

  if (exponent % 2 === 1) return (base * result) % 94906249;
  else return result;
}

// 필요할 때마다 재귀 호출 -> 테스트 케이스 통과 못 함
function power(base, exponent) {
  if (exponent === 0) return 1;

  const half = parseInt(exponent / 2);
  const result = (power(base, half) * power(base, half)) % 94906249;

  if (exponent % 2 === 1) return (base * result) % 94906249;
  else return result;
}