JS 알고리즘 공부1.with BaaaaaaaarkingDog

BaaaaaaaarkingDog님의 알고리즘 강의 블로그를 보며 기본을 다지고 정리하려고 한다. 하지만 BaaaaaaaarkingDog님이 기본적으로 사용하는 언어는 C, C++ 기반이기 때문에 나는 javascript를 이용해 코딩테스트를 준비하려고 한다.

# OT

코딩 테스트 사이트들

백준(https://www.acmicpc.net/)

프로그래머스(https://programmers.co.kr/)

구름(https://www.goorm.io/)

 

코딩테스트에 필요한 능력

1. 배경 지식 : 알고리즘, 자료구조, 프로그래밍 언어적 테크닉 등 활용할 수 있는 지식
2. 문제 해결 능력 : 배경지식을 잘 활용해 문제를 해결할 수 있는 능력
3. 구현력 : 문제를 해결했다면 코드로 구현할 수 있는 능력

# 기초 코드 작성 요령 1

테스트는 시간과 메모리 공간에 대한 제한이 존재한다. 그렇기 때문에 다 구현하기 전에 사전에 계산을 통해 실패하는 것을 방지할 수 있다.

 

시간복잡도

입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계를 의미한다. 구현한 코드가 동작하는 시간을 구하기 위해서 빅오 표기법(O(n), O(1))을 사용한다.

 

문제 1

// sol.1 O(n)
function func1(number) {
  let answer = 0;
  
  for(let i=0; i<=number; i++) {
    if(i % 3 === 0 || i % 5 === 0) answer += i;
  }
  
  return answer;
}

// sol.2 O(1)
// 모르겠소..

// 결과
func1(16) // 60
func1(34567) // 278812814
func1(27639) // 178254968

 

문제 2

// sol.1 O(n^2)
function func2(arr, len) {

  for(let i=0; i<len; i++) {
    for(let j=i+1; j<len; j++) {
      if(arr[i]+arr[j] === 100) return 1;
    }
  }
  
  return 0;
}

// sol.2 O(n)
// 모르겠소..

// 결과
func2([1,52,48],3) // 1
func2([50,42],2) // 0
func2([4,13,63,87],4) // 1

 

문제 3

// sol.1 O(n)
function func3(num) {
  for(let i=0; i<=num; i++) {
    if(i*i === num) return 1; // 조건문에 i**2, Math.pow(i,2)로 대체 가능하다
  }
  
  return 0;
}

// sol.1 O(Math.sqrt(n))
function func3(num) {
  // 루트를 씌운 수 이상은 의미가 없기 때문
  // i*i < num과 같은 의미이다
  for(let i=0; i<=Math.sqrt(num); i++) {
    if(i*i === num) return 1;
  }
  
  return 0;
}

// sol.3 O(1)
function func3(num) {
  // Number.isInteger()가 생각나지 않는 경우
  // Math.sqrt(num) - Math.floor(Math.sqrt(num)) === 0
  // 으로도 대체할 수 있다.
  return Number.isInteger(Math.sqrt(num)) ? 1 : 0;
}

// 결과
func3(9) // 1
func3(693953651) // 0
func3(756580036) // 1

 

문제 4

// sol.1 O(log(2)n)
function func4(num) {
  let i = 0;
  while(Math.pow(2,i) <= num) {
    i++;
  }
  
  return Math.pow(2,i-1);
}

// 결과
func4(5) // 4
func4(97615282) // 67108864
func4(1024) // 1024

 

공간복잡도

간단하게 "512MB는 int 변수가 1.2억 개까지 가능하다"라는 사실 정도만 알면 된다고 한다.

 

정수(int, long long)

크기는 각각 4 byte(= 32 bit), 8byte로 정수를 담을 수 있는 크기가 정해져 있기 때문에, 크기를 벗어나는 수를 입력하면 overflow 발생해 원하는 결과와 다른 결과가 나올 수 있습니다.

 

실수(float, double)

크기 각각 4byte, 8byte이다. 소수를 사용할 때에는 IEEE-754 소수표현법을 사용하며, 2진수이기에 오차가 발생할 수 있다. 예를 들어 0.1 + 0.2 == 0.3의 결과가 false로 나오는 경우처럼 말이다.

# JS에서는?

C언어에서와 달리 숫자가 Number라는 타입으로 모두 묶여서 사용된다. 하지만 IEEE-754의 규정을 사용하는 것은 같기 때문에 표현할 수 있는 수의 범위와 방법은 같다. 숫자가 Number로 묶여 있지만 정수와 실수를 구분할 수 있는 Number.isInteger()이 존재한다.

특이한 점으로는 Infinity라는 무한대 값이 존재한다는 사실이다. 양의 무한대와 음의 무한대가 모두 있기 때문에 대소 비교할 때 초기값으로 활용하기 좋다. 자세한 내용은 더 공부하면서 추가로 작성하겠다.

 

 

출처 & 참고

개인적으로 정리한 부분이기 때문에 문제가 궁금하신 경우 BaaaaaaaarkingDog님의 블로그를 봐주세요^.^

오리엔테이션, BaaaaaaaarkingDog, 2024.03.25

기초코드작성요령 1, BaaaaaaaarkingDog, 2024.03.25