JS 알고리즘 공부 2회차 with. BaaaaaaaarkingDog

# 기초 코드 작성 요령 2

표준입출력

프로그래머스 사이트의 경우에는 함수 형식으로 구현하기 때문에 매개변수를 이용하면 해결할 수 있다. 하지만 백준 사이트의 경우 입력을 따로 받아와 읽은 후에 변수로 사용하기 때문에 입력을 읽어드리는 방법을 알 필요가 있다. 이 글에서는 백준을 예시로 들었지만 코딩 사이트마다 조금씩 방법이 다를 수 있기 때문에 찾아보는 것을 추천한다.

 

🍯tip! 코드를 구현할 때 어떻게 구현해야 좋은가에 대해 고민하게 되는다. 코딩 테스트에서 중요한 것은 문제 해결에 집중할 필요가 있다. 실제 개발에서 사용하는 코드는 다른 사람과 공유하기 때문에 변수명이나 함수 이름을 지을 때 조심해야 한다. 하지만 코딩 테스트를 할 때에는 조금 우선순위를 미뤄도 좋다.

 

🍯tip! 코딩 테스트는 다양하게 진행하기 때문에 자주 사용하는 함수 정도는 암기하는 것이 좋다.

# 배열

"메모리 상에 원소를 연속하게 배치한 자료구조"

 

배열의 성질

1. O(1)에 k번째 원소를 확인 및 변경 가능
2. 추가로 소모되는 메모리 양(overhead)이 거의 없다
3. 메모리 상 연속 구간을 잡아야 하기 때문에 할당에 제약이 있다
4. cache hit rate가 높다

시간복잡도

• 특정 위치에 있는 원소 확인 및 변경, 마지막 위치에 요소 추가 및 삭제 → O(1)
• 마지막이 아닌 위치에 요소 추가 및 삭제 → O(n)

+) 특정 위치에 삽입(insert), 삭제(erase) 구현

function insert(index, val, arr) {
  for(let i=arr.length; i > index; i--) {
    arr[i] = arr[i-1];
  }
  arr[index] = val;
  
  console.log(arr);
}

function erase(index, arr) {
  const val = arr[index];
  
  for(let i=index; i < arr.length-1; i++) {
    arr[i] = arr[i+1];
  }
  arr.pop();
  
  console.log(arr);
  
  return val;
}

let a = [1,2,3,4,5]
insert(3,10,a) // [1,2,3,10,4,5]
erase(2,a) // [1,2,10,4,5] 3

사실 JavaScript를 사용하면 해당 함수를 구현해서 사용하는 것보다 존재하는 함수를 사용하는 방법이 있다. Array.splice()를 잘 활용한다면 삽입과 삭제를 폭넓게 사용할 수 있다.

// 삽입
arr.splice(index, 0, val);

// 삭제
arr.splice(index, 1);

 

블로그에서 추천하는 백준는 따로 풀어보는 것으로 한다.

 

OT때 연습문제 중 문제 2은 O(n)으로 구현하는 방법이 있다고 했는데 풀지 못했었다. 이번 장에서 정답을 알려주니 기억하고 넘어가자. 새로운 배열을 만들어 기존 배열에 있는 값을 저장해두어 이전 요소에 접근하는 것을 쉽게 만들어 준다. 원래는 기존 배열을 두번 접근해야 했지만, 새로운 배열을 만들어 값을 저장해서 한번만 접근할 수 있도록 한 것이다.

// 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)
function func2(arr,len) {
  const newArr = Array.from({length:100}, el=>0);
  
  for(let i=0; i<len; i++) {
    const num = arr[i];
    if(newArr[100 - num]) return 1;
    newArr[num] = 1;
  }
  
  return 0;
}

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

 

출처 & 참고

기초코드작성요령 2, BaaaaaaaarkingDog, 2024.03.28

배열, BaaaaaaaarkingDog, 2024.03.28