이벤트 스케쥴러 생성 save_ptr_pmp테이블에서 30일 전 테이터는 날려버려 그리고 2023-03-25 12:22:32 부터 시작하고 하루마다 실행시켜줘 끝나면 이 테이블은 없애줘

• x: 데이터들
• y: 실제값(들)
• batch_size: 모델 한번 돌 때 사용할 샘플 수
• epochs: 학습횟수
• verbose: 출력정보 컨트롤 0: 출력 X 1: 진행 바(Progress bar) 표시 2: 에포크마다 한 줄의 로그 표시
• callbacks: 학습 중에 호출될 콜백 목록, 예를 들면, 모델 저장이나 Early Stopping 등의 기능을 제공하는 객체들
• validation_split: 0과 1 사이의 부동소수점 값. 학습 데이터의 일부를 검증 데이터로 자동 분할하기 위해 사용
• validation_data: 검증을 위한 데이터(tuple 또는 tf.data 데이터셋)
• shuffle: 각 에포크마다 데이터를 섞을지 여부를 지정
• class_weight: 클래스별 가중치를 설정할 딕셔너리
• sample_weight: 샘플별 가중치를 포함하는 numpy 배열
• initial_epoch: 학습 시작 시 시작할 에포크 번호, 이전에 중단된 학습을 재개할 때 유용
• steps_per_epoch: 한 에포크에 사용될 학습 단계 수, 주로 tf.data 데이터셋을 사용할 때 설정
• validation_steps: 검증을 실행할 때 사용될 단계의 수
• validation_batch_size: 검증할 때 "한 번에" 사용할 샘플 수
• validation_freq: 검증을 몇 에포크마다 수행할지 결정
• max_queue_size: 생성자(generator)를 사용할 때 최대 큐 크기
• workers: 생성자를 사용할 때 동시에 실행할 작업자(worker)의 수
• use_multiprocessing: 생성자를 사용할 때 멀티 프로세싱을 사용할지 여부를 지정

b에 a를 덮어씌우기

a >> b

b에 a를 이어붙이기

tac a

a파일 뒤집어서 보기

cat > 새로운 파일이름

간단하게 내용작성할 때 vi 대신 쓰면 유용

ctr + d 저장

cal | tee -a a5

cal 실행결과를 보여주고 a5파일에 이어붙이기

nl a

a파일 넘버링

nl -w10 a (너비 10)

nl -i2 a (행번호 2씩 증가)

nl -i10 -v10 a (시작번호 10, 행번호 10씩 증가)

head -n (+)5 파일명

첫줄부터 5개 가져와

head -n -5 파일명

맨뒤에서 5개 잘라내고 나머지 가져와

tail -n (-)5 파일명

뒤에서부터 5개

tail -n +5 파일명

앞에서 5개 잘라내고 가져와

구문

Object.getOwnPropertyDescriptor(obj, prop)

설명

obj객체의 prop 속성에 대한 설명자를 반환해요

예제

const case1 = Object.defineProperties({},{
    'name' : {
                value : '홍길동',
                writable : true,
                enumerable : true,
             },
    'age' : {
                value : 100,
                writable : false,
                enumerable : false
            }
})

//case1 객체의 name 속성을 찍어보자
console.log(Object.getOwnPropertyDescriptor(case1, 'name'))
configurable : false 
enumerable : true
value : "홍길동"
writable : true

//case1 객체의 age 속성을 찍어보자
console.log(Object.getOwnPropertyDescriptor(case1, 'age'))
configurable : false
enumerable : false
value : 100
writable : false

참고로 defineProperties()메서드를 사용하여 속성을 정의할 경우 configurable, enumerable, writable 기본값은 false입니다.

Object.getOwnPropertyDescriptors()

구문

Object.getOwnPropertyDescriptors(obj)

설명

매개변수로 들어온 obj객체의 모든 속성들의 설명자를 반환해요

예제

const case1 = Object.defineProperties({},{
    'name' : {
                value : '홍길동',
                writable : true,
                enumerable : true,
             },
    'age' : {
                value : 100,
                writable : false,
                enumerable : false
            }
})

// case1 객체의 설명자가 궁금해요
console.log(Object.getOwnPropertyDescriptors(case1))

age : 
    configurable : false
    enumerable : false
    value : 100
    writable : false

name : 
    configurable : false
    enumerable : true
    value : "홍길동"
    writable : true

Object.getOwnPropertyNames()

구문

Object.getOwnPropertyNames(obj)

설명

매개변수의 속성들을 배열에 담아 반환시켜줍니다.

예제

//case1를 만들어볼께요
const case1 = { a : 1, b : 2, c : 3}
//객체에 어떤 속성이 있는지 궁금해요
console.log(Object.getOwnPropertyNames(case1))

결과값 => [ 'a', 'b', 'c' ]

//case2를 만들어 볼께요
const case2 = { name : '홍길동', age : 100 }
//콘솔찍어 볼께요
console.log(Object.getOwnPropertyNames(case2))

결과값 => [ 'name', 'age' ]

Object.getPrototypeOf()

구문

Object.getPrototypeOf(obj)

설명

매개변수의 프로토타입(상속받은 객체)을 반환해요.

예제

//객체를 하나 만들어 볼께요
let obj1 = { name : '홀깅돌' , age : 100 };

//obj1을 상속받는 객체를 하나 만들어 볼께요
let obj2 = Object.create(obj)

// Object.getPrototypeOf(obj2) === obj1

결과값 => true

Object.keys()

구문

Object.keys(obj)

설명

주어진 객체의 속성 이름들을 배열에 담아 반환해줘요

예제

//객체를 하나 만들어 볼께요
const object1 = {
  a: 'something',
  b: 100,
  c: 'kim'
};
//Object.keys()를 사용해볼께요
console.log(Object.keys(object1))// [ 'a', 'b', 'c' ]


//이번엔 defineProperties()메서드를 사용해서 원하는 key들만 반환시켜볼께요
const object2 = Object.defineProperties({},{
    a : {
             value : 'somestring',
              enumerable : true
        },
      b : {
              value : 42,
              enumerable : false
          },
      c : {
            value : 'kim',
              enumerable : true
          }
})

// b만 enumerable(순회할 때 출력을 결정할 수 있는 옵션)을 false로 설정했어요
// 어떻게 나올지 콘솔찍어볼께요

console.log(Object.keys(object2));//[ 'a' , 'c' ] 
// b 키만 출력되지 않았어요

Object.seal(), Object.preventExtensions(),

구문

Object.preventExtensions(obj) Object.seal(obj)

설명

매개변수로 받아온 객체를 밀봉하여 객체의 확장을 막아요(새 속성 추가 X) 하지만 기존 속성의 값을 변경할 수있다는 점에서 Object.freeze()메서드와 차이점이 존재해요.

예제

//age속성을 갖는 객체를 하나 만들어볼께요.
const object1 = {
  age : 100,
};
//만들객체를 밀봉시켜볼께요
Object.seal(object1);

//1. name 속성을 추가 시켜볼께요
object1.name = '홍길동';
//콘솔을 찍어봐요
console.log(object1.name);
// 결과값 => undefined

//2. 기존에 있던 age 속성을 지워볼께요
'use strict'
delete object1.age
//Uncaught TypeError: Cannot delete property 'age'

//3. age값을 변경시켜볼께요
object1.age = 200;
//콘솔찍어봐요
console.log(object1.age);
//결과값 => 200

Object.preventExtensions() 메서드도 동일하게 작동하기 때문에 예제에 포함시키지 않았고 만약 속성의 값을 변경시켜 주기 싫다 하시면 Object.freeze() 또는 Object.defineProperties() 사용할 수 있어요

mdn 문서를 참고하여 정리한 내용이며, 부가적인 옵션은 추후에 업데이트 할 예정입니다.

Object.assign(target, ...source)

짧은 설명 : source 객체들을 복사해 target에 붙여넣는다.

const target = { a : 1, b : 2 }
const source = { b : 3, c : 4 }

const returnTarget = Object.assign(tartget, source);

console.log(returnTarget)//{ a : 1, b : 3, c : 4 }
console.log(returnTarget === target)// true;

assign 메서드는 불변성을 가지고 있지 않아 target객체와 returnTarget객체는 모두 같은 주소값을 가졌으며 같은 객체를 바라보고 있다.

Object.defineProperties()

짧은 설명 : 객체에 새로운 속성을 부여하거나 기존의 속성을 수정하고 그 객체를 반환

//객체 생성
const obj = {};

//
Object.defineProperties(obj, {
  //name 속성을 부여하였으며 값은 10 할당, 수정 불가능
  name: {
    value : 'kim',
    writable: false
  },

  //age 속성을 부여하였으며 수정가능
  age : {
      value : 20 ,
    writable : true
  }
});

console.log(obj.name);//kim
console.log(obj.age);//20

//obj의 name 속성을 park으로, age 속성을 30으로 수정
obj.name = 'park';
obj.age = 30;

console.log(obj.name);//kim
console.log(obj.age);//30

//name속성은 수정이 안되는것을 확인할 수 있다. writable을 false로 사용하여 객체 내부의 값을 함부로 수정하지 못하게 막았기 때문이다. 

Object.entries()

짧은 설명 : 매개변수로 받은 obj의 enumerable속성을 [key, value] 쌍을 배열로 반환합니다.

const case1 = { a : 1, b : 2, c : 3 }
console.log(Object.entries(case1)) // [ ['a',1], ['b',2], ['c',3] ]

const case2 = { 100: 'a', 2: 'b', 7: 'c' };
console.log(Object.entries(case2)); // [ ['2', 'b'], ['7', 'c'], ['100', 'a'] ]

Object.fromEntries()

짧은 설명 : 매개변수로 전달받은 키-값쌍 목록을 객체로 반환해준다. 쉽게말해 Object.entries()의 반대되는 메서드임.

const case1 = [ ['a',1], ['b',2], ['c',3] ];
console.log(Object.fromEntries(case1))//{a: 1, b: 2, c: 3}

//배열을 객체로 만들어서 반환


const case2 = [ ['2', 'b'], ['7', 'c'], ['100', 'a'] ];
console.log(Object.fromEntries(case2))//{2: 'b', 7: 'c', 100: 'a'}

//배열을 객체로 만들어서 반환

Object.freeze()

짧은 설명 : 객체를 동결시켜 속성값을 추가하거나 변경하거나 제거를 방지함

//배열생성
const case1 = [1,2,3];
//case1를 동결시켜볼께요
Object.freeze(case1)
//배열에 2를 추가해볼께요
case1.push(1);//error
case1.pop()//error
case1[0] = 10;//error를 발생시키지 않고 조용히 넘어감 대신 변경은 안됨!!
console.log(case1[0])// 1
//case1이 동결인지 아닌지 확인해볼께요
Object.isFrozen(case1);//true

//객체생성
const case2 = { name : 'kim' }

//동결시켜보자
Object.freeze(case2)

//age속성을 추가시킨후에 case2를 출력시켜보면
case2.age = 100
console.log(case2)//{name: 'kim'}

//name속성을 삭제시킨후 콘솔을 찍어보면
delete case2.name
console.log(case2)//{name: 'kim'}

//name속성 값을 변경시킨 후 콘솔을 찍어보면
case2.name = 'park'
console.log(case2)//{name: 'kim'}


Object.defineProperties()메서드는 각 속성을 수정할지 안할지 결정할 수 있었지만 
Ojbect.freeze()메서드는 모든 것을 막는다.

1. toSorted

   const originSorted = [1,2,3,4,5];
   const newSorted = originSorted.sort((a,b)=> b-a);
   console.log(originSorted);//[5,4,3,2,1]
   console.log(newSorted);//[5,4,3,2,1]
   console.log(originSorted === newSorted);//true

   기존의 sort메서드는 원본을 참조하여 변수에 원본 주소값을 넘겨주기에 불변성을 유지하지 못하였지만

const originToSorted = [1,2,3,4,5];
const newToSorted = originToSorted.toSorted((a,b)=> b-a);
console.log(originToSorted);//[5,4,3,2,1]
console.log(newToSorted);//[5,4,3,2,1]
console.log(originToSorted === newToSorted);//true

toSorted를 사용해주면 원본은 그대로 유지하되 newToSorted 변수에 새로운 배열을 반환해준다.

2. toReverse()

const originReverse = [1,2,3,4,5];
const newReverse = originReverse.reverse();
console.log(originReverse);//[5,4,3,2,1];
console.log(newReverse);//[5,4,3,2,1]
console.log(originReverse === newReverse);//true

const originReverse = [1,2,3,4,5];
const newReverse = originReverse.toReverse();
console.log(originReverse);//[1,2,3,4,5]
console.log(newReverse);//[5,4,3,2,1]
console.log(originReverse === newReverse);//false

reverse()를 사용하면 원본 배열의 주소값을 반환하였지만 toReverse()메서드는 새로운 배열을 만들어 반환시켜주기에 기존 배열의 불변성을 유지할 수 있다.

3. with(index, value)

const originWith = [1,2,3,4,5];
const newWith = originWith.with(3,100);
console.log(originWith);//[1,2,3,4,5]
console.log(newWith);//[1,2,3,100,5]
console.log(originWith === newWith);//false

with()메서드는 첫번째 인자값으로 인덱스를 받고 두번째 인자값으로 대체할 값을 받는다. with(3,10)을 해석하자면 배열의 3번째 인덱스 값을 100으로 바꿔줘! 라는 뜻이다. 기존에는 slice를 사용하여 코드가독성이 떨어지는 측면이 있었는데 이를 해결해 준 느낌이다.

ex) [...array.slice(0,3), 바꿔줄 값, ...array.slice(4)]

4. findLast()

const find = [1,2,3,4,5];
find.find((el) => console.log(el));//1,2,3,4,5

const findLast = [1,2,3,4,5];
findLast.findLast((el) => console.log(el))//5,4,3,2,1

기존의 find()는 배열 탐색 시 첫번째 인자부터 검색했지만 findLast()는 가장 마지막 인자부터 탐색을 시작한다. 비록 시간복잡도 측면에서는 비슷하지만 맨 뒤부터 검색해보고 싶다면 위 메서드를 사용할 수 있을것같다.

5. findLastIndx()

const findIndex = [1,2,3,4,5];
findIndex.findIndex((_,idx) => console.log(idx))//0,1,2,3,4

const findLastIndex = [1,2,3,4,5];
findLastIndex.findLastIndex((_,idx) => console.log(idx))//4,3,2,1,0

findIndex()메서드는 배열 첫번째 인덱스부터 탐색을 시작하고, findLastIndex()는 배열 마지막 인덱스부터 탐색을 시작한다. 이 메서드도 배열 가장 마지막 인덱스부터 탐색을 하고 싶다면 사용해보길 바란다.

문제발생!! 로드뷰 버튼 만들어서 클릭하면 현재 지도 중심의 위도, 경도를 구해와 바로 화면에 보여준다는 점 사용자가 원하는 위치를 클릭하여 로드뷰를 볼 수 있도록 구현해줘야 사용자입장에서 훨씬 편하다.

수정 후 로드뷰 누르면 그림처럼 내가 원하는 위치의 로드뷰를 설정하여 볼 수 있다. ![] (https://velog.velcdn.com/images/hyuntae_/post/2b4d4e79-fa07-461d-9106-6427fc56ace1/image.png)

휴.. 사이트 주소 : https://happyhouse.vercel.app/apart

react도 충분히 좋은 도구이지만 왜 next를 사용할까?

react... 단점이 뭐지

바로 SEO(검색엔진)과 Pre-render이라고 생각한다. 인터넷 사용자들은 무언가 찾고싶을 때 네이버나 구글 혹은 다른 브라우저를 이용하여 검색창에 검색을 하고 원하는 데이터를 얻는다. 이 과정에서 브라우저검색엔진이 작동을 하고 사용자들에게 원하는 데이터를 찾아서 보여줍니다.

여기서 검색엔진의 중요성이 나오는데요,

react를 생성하고 index.html보시면 아무것도 없고 body에 달랑 div태그 하나만 있습니다. 브라우저 검색엔진은 html 파일을 뒤져서 필요한 내용이 있다면 가져오는 방식으로 작동을 하는데 이때 react는 아무것도 제공해주질 못해서 검색엔진에 약점이 존재하기에 이를 보완하기 위해서 Next.js의 Pre-rendering을 사용합니다.

Pre-rendering?

Pre-rendering이란 사용자가 페이지를 보기 전에 서버에서 미리 html파일을 생성하여 요청이 오면 보내주고 사용자는 즉각 화면에 어떠한 데이터를 볼 수 있습니다.

위 그림을 보시면 사용자가 사이트에 접속을 하면 미리 렌더링된 HTML을 볼 수가 있고 그리고 나서 동작기능을 사용하기 위해서 js파일을 요청하고 html과 js가 하나로 합쳐지는 hydration 과정이 끝난 후에 사용자는 모든 기능을 사용할 수 있습니다.

SSG와 SSR

그렇다면 Pre-rendering의 종류에는 어떠한 것이 있는지 알아봅시다

먼저 SSG(이하 ssg)입니다. static site generation의 약자로 정적페이지생성을 뜻합니다. 말 그대로 정적, 데이터가 변하지 않고 항상 똑같은 데이터를 가지고 똑같은 화면을 보여주는 경우에 사용할 수 있습니다. 그렇기에 next공식문서에도 추천하고 있습니다✅ ssg는 프로젝트 빌드시 한번 실행되어 html파일로 만들어지고 CDN에 캐싱되어 다음 요청시부터 재사용가능합니다.

어? 저는 데이터가 그때그때 마다 달라서 ssg를 사용하면 안되는데요?

이를 위해서 SSR이 존재합니다. SSR(이하 ssr)은 Server-side Rendering의 약자로 ssg와의 가장 큰 차이점이자 장점은 항상 최신내용을 가지고 있다는 것입니다. 물론 재사용/재활용을 하지 않기에 ssg와 ssr을 잘 생각해서 필요한 곳에 적절히 써야됩니다.

결론

ssr과 ssg를 사용하여 미리 렌더링할 수 있어 검색엔진에 있어서 장점이 있지만, 유저보드처럼 seo의 필요성이 적다면 굳이 사용하지 않아도 된다.

당신은 표 편집 프로그램을 작성하고 있습니다. 표의 크기는 50 × 50으로 고정되어있고 초기에 모든 셀은 비어 있습니다. 각 셀은 문자열 값을 가질 수 있고, 다른 셀과 병합될 수 있습니다.

위에서 r번째, 왼쪽에서 c번째 위치를 (r, c)라고 표현할 때, 당신은 다음 명령어들에 대한 기능을 구현하려고 합니다.

1. "UPDATE r c value" (r, c) 위치의 셀을 선택합니다. 선택한 셀의 값을 value로 바꿉니다.

2. "UPDATE value1 value2" value1을 값으로 가지고 있는 모든 셀을 선택합니다. 선택한 셀의 값을 value2로 바꿉니다.

3. "MERGE r1 c1 r2 c2" (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀을 선택하여 병합합니다. 선택한 두 위치의 셀이 같은 셀일 경우 무시합니다. 선택한 두 셀은 서로 인접하지 않을 수도 있습니다. 이 경우 (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀만 영향을 받으며, 그 사이에 위치한 셀들은 영향을 받지 않습니다. 두 셀 중 한 셀이 값을 가지고 있을 경우 병합된 셀은 그 값을 가지게 됩니다. 두 셀 모두 값을 가지고 있을 경우 병합된 셀은 (r1, c1) 위치의 셀 값을 가지게 됩니다. 이후 (r1, c1) 와 (r2, c2) 중 어느 위치를 선택하여도 병합된 셀로 접근합니다.

4. "UNMERGE r c" (r, c) 위치의 셀을 선택하여 해당 셀의 모든 병합을 해제합니다. 선택한 셀이 포함하고 있던 모든 셀은 프로그램 실행 초기의 상태로 돌아갑니다. 병합을 해제하기 전 셀이 값을 가지고 있었을 경우 (r, c) 위치의 셀이 그 값을 가지게 됩니다.

5. "PRINT r c" (r, c) 위치의 셀을 선택하여 셀의 값을 출력합니다. 선택한 셀이 비어있을 경우 "EMPTY"를 출력합니다.

아래는 UPDATE 명령어를 실행하여 빈 셀에 값을 입력하는 예시입니다.

UPDATE 1 1 menu (1,1)에 "menu" 입력 UPDATE 1 2 category (1,2)에 "category" 입력 UPDATE 2 1 bibimbap (2,1)에 "bibimbap" 입력 UPDATE 2 2 korean (2,2)에 "korean" 입력 UPDATE 2 3 rice (2,3)에 "rice" 입력 UPDATE 3 1 ramyeon (3,1)에 "ramyeon" 입력 UPDATE 3 2 korean (3,2)에 "korean" 입력 UPDATE 3 3 noodle (3,3)에 "noodle" 입력 UPDATE 3 4 instant (3,4)에 "instant" 입력 UPDATE 4 1 pasta (4,1)에 "pasta" 입력 UPDATE 4 2 italian (4,2)에 "italian" 입력 UPDATE 4 3 noodle (4,3)에 "noodle" 입력 위 명령어를 실행하면 아래 그림과 같은 상태가 됩니다.

아래는 MERGE 명령어를 실행하여 셀을 병합하는 예시입니다.

MERGE 1 2 1 3 (1,2)와 (1,3) 병합 MERGE 1 3 1 4 (1,3)과 (1,4) 병합 위 명령어를 실행하면 아래와 같은 상태가 됩니다.

병합한 셀은 "category" 값을 가지게 되며 (1,2), (1,3), (1,4) 중 어느 위치를 선택하더라도 접근할 수 있습니다.

아래는 UPDATE 명령어를 실행하여 셀의 값을 변경하는 예시입니다.

UPDATE korean hansik "korean"을 "hansik"으로 변경 UPDATE 1 3 group (1,3) 위치의 셀 값을 "group"으로 변경 위 명령어를 실행하면 아래와 같은 상태가 됩니다.

아래는 UNMERGE 명령어를 실행하여 셀의 병합을 해제하는 예시입니다.

UNMERGE 1 4 셀 병합 해제 후 원래 값은 (1,4)가 가짐 위 명령어를 실행하면 아래와 같은 상태가 됩니다.

실행할 명령어들이 담긴 1차원 문자열 배열 commands가 매개변수로 주어집니다. commands의 명령어들을 순서대로 실행하였을 때, "PRINT r c" 명령어에 대한 실행결과를 순서대로 1차원 문자열 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ commands의 길이 ≤ 1,000 commands의 각 원소는 아래 5가지 형태 중 하나입니다.

"UPDATE r c value" r, c는 선택할 셀의 위치를 나타내며, 150 사이의 정수입니다. value는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 110 사이인 문자열입니다.

"UPDATE value1 value2" value1은 선택할 셀의 값, value2는 셀에 입력할 내용을 나타내며, 알파벳 소문자와 숫자로 구성된 길이 1~10 사이인 문자열입니다.

"MERGE r1 c1 r2 c2" r1, c1, r2, c2는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.

"UNMERGE r c" r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다.

"PRINT r c" r, c는 선택할 셀의 위치를 나타내며, 1~50 사이의 정수입니다. commands는 1개 이상의 "PRINT r c" 명령어를 포함하고 있습니다.

입출력 예

입력1

"UPDATE 1 1 menu", "UPDATE 1 2 category", "UPDATE 2 1 bibimbap", "UPDATE 2 2 korean", "UPDATE 2 3 rice", "UPDATE 3 1 ramyeon", "UPDATE 3 2 korean", "UPDATE 3 3 noodle", "UPDATE 3 4 instant", "UPDATE 4 1 pasta", "UPDATE 4 2 italian", "UPDATE 4 3 noodle", "MERGE 1 2 1 3", "MERGE 1 3 1 4", "UPDATE korean hansik", "UPDATE 1 3 group", "UNMERGE 1 4", "PRINT 1 3", "PRINT 1 4"

출력1

(1,3) 위치의 셀은 비어있고 (1,4) 위치의 셀 값은 "group"입니다. 따라서 ["EMPTY", "group"]을 return 해야 합니다.

풀이

문제를 처음 읽고 든 생각은 각 명령어 마다 함수를 생성해주고 각각 요구사항에 맞게 풀면 되겠다 생각했는지만 호락호락하지 않았다(역시 카카오 ㄷㄷ😭) 핵심구현이라고 생각한것은 MERGE 명령어였다.

예들 들어 위 그림과 같이 두 집합 A,B가 있다고 가정해보자(초기화된 상태보다는 병합된 상태가 핵심이기에 미리 병합된 집합을 예시로 들었어요)

MERGE 1 1 2 2

위 command가 있다고 하면 1,1은 A집합 2,2는 B집합에 속해있는 상태다. 여기서 MERGE를 하면 또 다른 집합 C가 생성되고 이 집합의 인자는 (1,1),(1,2),(2,2),(2,3) 총 4개를 가진다. 이 과정에 탐색과 집합 A,B 인자의 모든 위치에 새로운 배열 C를 넣어줘야하기에 메모리 초과가 발생하여 에러를 일으킨다. 그림으로 표현하면 아래와 같다.

이를 해결하기 위해 union 알고리즘을 사용하였다. union알고리즘은 두 집합을 합칠 때 공통인자를 가진 값을 넣어 두 집합이 하나라는 표시를 해주는 것이다. 그림을 살펴보자

위 그림처럼 각각의 좌표에는 고유의 값이 존재한다. 다음으로 MERGE 1 1 1 2 와 MERGE 2 2 2 3 을 실행해 보면 다음과 같다.

(1,1),(1,2)의 값을 동일하므로 같은 집합, 마찬가지로 (2,2),(2,3)의 값이 같으므로 같은 집합으로 생각하면 되요. 다음으로 MERGE 1 1 2 2를 실행한 결과를 보면 다음과 같다.

(1,1)의 고유값은 1이고, (2,2)의 고유값은 7입니다. 여기서 로직은 7값을 가진 모든 좌표를 찾아 1로 바꿔주면 되고 시간복잡도는 50 x 50= 2500번입니다.

지금까지 MERGE를 살펴보았고 제가 생각하기로 MERGE를 잘 구현할 수 있다면 위 문제를 스무스?하게 풀 수 있을거라 생각합니다.

const map = Array.from({ length : 51} , () => new Array(51).fill(null));
const parents = Array.from({ length : 51 } , () => new Array(51).fill(0));

for(let i=1; i<=50; i++){
    for(let j=1; j<=50; j++){
        parents[i][j] = i * 50 + j;
    }
}

const update1 = (r,c,value) => {
    //todo
    //r,c와 병합된 다른 셀들의 값도 바꿔줘야함. 
    const p = parents[r][c];

    for(let i=1; i<=50; i++){
        for(let j=1; j<=50; j++){
            if (parents[i][j] === p){
                map[i][j] = value;
            }
        }
    }
}

const update2 = (value1, value2) => {
    for(let i=1; i<=50; i++){
        for(let j=1; j<=50; j++){
            if (map[i][j] === value1) map[i][j] = value2;
        }
    }
}

const merge = (r1, c1, r2, c2) => {
    if (r1 === r2 && c1 === c2) return;
    //두 셀의 최상위 조상의 셀이 같은지 확인
    const aP = parents[r1][c1];
    const bP = parents[r2][c2];
    //최상위 조상이 같을 경우 패스
    if (aP === bP) return;
    //최상위 조상이 다를 경우
    if ((map[r1][c1] !== null && map[r2][c2] !== null) || (map[r1][c1] !== null && map[r2][c2] === null)){

        //(r2,c2)의  조상노드를 가지고 있는 모든 노드를 찾아 (r1,c1)값으로 변환
        for(let i=1; i<=50; i++){
            for(let j=1; j<=50; j++){
                if (parents[i][j] === bP){
                    parents[i][j] = aP;
                    map[i][j] = map[r1][c1];
                }
            }
        }
    } else if (map[r1][c1] === null && map[r2][c2] !== null){
        //(r1,c1)의 조상노드를 가지고 있는 모든 노드를 찾아 (r2,c2)값으로 변환
        for(let i=1; i<=50; i++){
            for(let j=1; j<=50; j++){
                if (parents[i][j] === aP){
                    parents[i][j] = bP;
                    map[i][j] = map[r2][c2];
                }
            }
        }
    } else if (map[r1][c1] === null && map[r2][c2] === null){
        for(let i=1; i<=50; i++){
            for(let j=1; j<=50; j++){
                if (parents[i][j] === aP){
                    parents[i][j] = bP;
                }
            }
        }
    }
}

const unmerge = (r,c) => {
    //todo
    const data = map[r][c];
    //(r,c)의 최상위 조상을 찾는다 
    const p = parents[r][c];
    //이 조상과 같은 모든 노드들의 조상값을 초기화시키고 null값으로 초기화
    for(let i=1; i<=50; i++){
        for(let j=1; j<=50; j++){
            if (parents[i][j] === p){
                parents[i][j] = 50 * i + j;
                map[i][j] = null;
            }
        }
    }
    //(r,c)만 해체 전 셀 값을 가지고 있음
    map[r][c] = data;
}

const print = (r,c) => {    
    if (map[r][c] === null) return "EMPTY";
    return map[r][c];
}

function solution(commands) {

    const answer = [];
    for(let command of commands){
        const splitCommand = command.split(' ');
        const order = splitCommand[0];

        if (order === 'UPDATE'){
            const len = splitCommand.length;
            //1. UPDATE r c value  => update1
            if (len === 4){
                update1(Number(splitCommand[1]), Number(splitCommand[2]), splitCommand[3]);
            } 
            //2. UPDATE value1 value2 => update2
            else if (len === 3){
                update2(splitCommand[1],splitCommand[2]);
            }
        } 
        //3. MERGE r1 c1 r2 c2
        else if(order === 'MERGE'){
            const r1 = Number(splitCommand[1]);
            const c1 = Number(splitCommand[2]);
            const r2 = Number(splitCommand[3]);
            const c2 = Number(splitCommand[4]);
            merge(r1,c1,r2,c2);
        } 
        //4. UNMERGE r c
        else if (order === 'UNMERGE'){
            const r = Number(splitCommand[1]);
            const c = Number(splitCommand[2]);
            unmerge(r,c);
        }
        //5. PRINT r c 
        else if (order === 'PRINT'){
            const r = Number(splitCommand[1]);
            const c = Number(splitCommand[2]);
            answer.push(print(r,c));
        }
    }

    return answer;
}

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '')을 설치해서 방향을 90도 회전시킬 수 있다.

아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

7 . . . . . . . 7 . . . . . . . 6 . . . . . . C 6 . . . . . /-C 5 . . . . . . * 5 . . . . . | * 4 * * * * * . * 4 * * * * * | * 3 . . . . * . . 3 . . . . * | . 2 . . . . * . . 2 . . . . * | . 1 . C . . * . . 1 . C . . * | . 0 . . . . . . . 0 . -------/ . 0 1 2 3 4 5 6 0 1 2 3 4 5 6

입력

첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)

둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

.: 빈 칸 *: 벽 C: 레이저로 연결해야 하는 칸 'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

출력

첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

예제

예제 입력 1

7 8

.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

예제 출력 1

3

풀이

bfs문제이지만 고려해야할 조건이 있다. 흔히 bfs는 어떤 두 점 사이의 최소거리 값을 구하는 문제이지만 이번의 경우에는 조금 다르게 두 'C' 사이의 거리에 놓인 거울개수의 최소값을 구하는 것이다. 즉, 'C'에서 다른 'C'로 이동하여 갈 때 이미 방문했는지 안했는지가 중요한게 아니라 거울개수가 최소인지가 중요한것이다. 또한 어느 한 점으로 들어오는 빛은 방향성을 가지기 때문에 동,서,남,북으로 진행하는 빛은 본인이 진행하는 방향의 빛을 제외하고는 거울이 필요하다는 것이다.

풀이 로직

1. 큐를 먼저 구현한다.
2. 시작점 'C'에서 출발하는 네 가지 방향의 빛을 초기값을 세팅한다.
3. 큐에서 하나 꺼낸다. 3-1. 진행중인 빛의 방향과 다르다면 거울의 개수를 +1 3-2. 진행중인 빛의 방향과 같다면 거울의 개수는 그대로 둔다.
4. 다음 점의 거울개수보다 작거나 같다면 큐에 삽입한다.
5. 큐에 남은게 없을 때까지 3~4를 반복한다.

const [[W, H], ...map] = require('fs')
  .readFileSync('./dev/stdin')
  .toString()
  .trim()
  .split("\n")
  .map((el, idx) => (idx ? el.split("") : el.split(" ").map(Number)));

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.rear = null;
    this.length = 0;
  }

  isEmpty() {
    if (this.length === 0) return true;
    return false;
  }

  enqueue(data) {
    const node = new Node(data);

    if (!this.head) {
      this.head = node;
    } else {
      this.rear.next = node;
    }
    this.rear = node;
    this.length++;
  }

  dequeue() {
    if (!this.head) return false;

    const answer = this.head.data;
    this.head = this.head.next;
    this.length--;

    return answer;
  }
}

const visited = Array.from({ length: H }, () => new Array(W).fill(Infinity));
const posC = [];

for (let i = 0; i < H; i++) {
  for (let j = 0; j < W; j++) {
    if (map[i][j] === "C") posC.push([i, j]);
  }
}
const [startR, startC] = posC[0];
const [endR, endC] = posC[1];
visited[startR][startC] = 0;

const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];

const queue = new Queue();
for (let i = 0; i < 4; i++) {
  queue.enqueue([startR, startC, i, 0]);
}

while (!queue.isEmpty()) {
  const [curR, curC, dir, mir] = queue.dequeue();

  for (let i = 0; i < 4; i++) {
    const [nextR, nextC] = [curR + dr[i], curC + dc[i]];
    let nextMir = mir;
    // 주어진 맵 범위를 초과한 경우는 패스
    if (nextR < 0 || nextC < 0 || nextR >= H || nextC >= W) continue;
    // 벽인 경우는 패스
    if (map[nextR][nextC] === "*") continue;
    // 현재 진행중인 방향과 다르다면 거울 +1
    if (dir !== i) nextMir++;
    if (visited[nextR][nextC] >= nextMir) {
      queue.enqueue([nextR, nextC, i, nextMir]);
      visited[nextR][nextC] = nextMir;
    }
  }
}

console.log(visited[endR][endC]);

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

예제

예제 입력 1

6 4 1 0100 1110 1000 0000 0111 0000

예제 출력 1

15

예제 입력 2

6 4 2 0100 1110 1000 0000 0111 0000

예제 출력 2

9

예제 입력 3

4 4 3 0111 1111 1111 1110

예제 출력 3

-1

해결방법

기존의 최단거리 문제는 해당위치에서 동서남북 방향으로 아직 방문하지 않았다면 해당 노드를 방문하고 큐에 넣어 진행하는 방식이지만 이 문제에서는 벽을 깨부수는 경우가 추가되었다.

이 문제를 해결하기 위한 핵심포인트는 벽을 깨부순 상태를 각각 달리하는 것이다. 예를 들어 벽을 0개 부순 상태, 벽을 1개 부순 상태, 벽을 2개 부순 상태는 별개의 인격체를 가진다는 것이다. 즉, 벽의 개수마다 방문처리를 해줘야한다.

그래서 방문처리배열을 기존의 2차원 배열에서 3차원 배열로 변경시켜줘야한다.

하지만 한가지 더 문제가 생겼다. 큐에 다음 노드를 삽입하고 반복문을 돌다보면 메모리초과가 발생한다. 그 이유는 자바스크립트에는 큐가 내장되어있지 않아 일반 배열을 큐 처럼 사용하는데 이때 배열크기를 초과하기때문에 메모리가 초과가 발생했다. 이를 해결해 주기 위해서 클래스를 사용해 직접 큐를 구현해주었다.

const [[N, M, K], ...map] = `4 4 3
0111
1111
1111
1110`
  .toString()
  .trim()
  .split("\n")
  .map((el, idx) =>
    idx ? el.split("").map(Number) : el.split(" ").map(Number)
  );
//큐 규현
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
class Queue {
  constructor() {
    this.head = null;
    this.rear = null;
    this.length = 0;
  }

  isEmpty() {
    if (this.length === 0) return true;
    return false;
  }

  enqueue(data) {
    const node = new Node(data);

    if (!this.head) {
      this.head = node;
    } else {
      this.rear.next = node;
    }
    this.rear = node;
    this.length++;
  }

  dequeue() {
    if (!this.head) return false;

    const data = this.head.data;
    this.head = this.head.next;
    this.length--;

    return data;
  }
}

const visited = Array.from({ length: N }, () =>
  Array.from({ length: M }, () => new Array(K + 1).fill(0))
);

visited[0][0][0] = 1;
//큐 생성
const queue = new Queue();
queue.enqueue([0, 0, 0, 1]);
let idx = 0;
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];

while (!queue.isEmpty()) {
  const [curRow, curCol, wall, step] = queue.dequeue();

  for (let i = 0; i < 4; i++) {
    const [nextRow, nextCol] = [curRow + dr[i], curCol + dc[i]];

    if (nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= M) continue;

    //벽이고 다음 벽까지 합쳐서 K개 이하이고 방문한 적 없음
    if (
      map[nextRow][nextCol] === 1 &&
      wall + 1 <= K &&
      visited[nextRow][nextCol][wall + 1] === 0
    ) {
      visited[nextRow][nextCol][wall + 1] = step + 1;
      queue.enqueue([nextRow, nextCol, wall + 1, step + 1]);
    }

    //벽이 아니고 방문한 적 없음
    if (map[nextRow][nextCol] === 0 && visited[nextRow][nextCol][wall] === 0) {
      visited[nextRow][nextCol][wall] = step + 1;
      queue.enqueue([nextRow, nextCol, wall, step + 1]);
    }
  }
}

//최소값 반환
let min = Number.MAX_SAFE_INTEGER;
for (let i = 0; i <= K; i++) {
  const step = visited[N - 1][M - 1][i];
  if (step === 0) continue;
  min = Math.min(min, step);
}
min === Number.MAX_SAFE_INTEGER ? console.log(-1) : console.log(min);

리액트를 사용하면서 성능최적화에 대해 궁금해졌고 이를 위해 어떠한 Hook이 있는지 찾아봤다. 대표적으로 useMemo와 useCallback Hook이 존재했고 이에 대해 학습한 내용을 정리해본다.

useMemo

useMemo는 렌더링하는 과정에서 특정 값이 바뀌었을 때만 연산을 실행하고, 원하는 값이 바뀌지 않았다면 이전에 연산했던 결과를 다시 사용하는 방식이다. 바로 실습을 통해 알아보자

import { useState } from 'react'

const getAverage = (numbers) => {
  console.log("평균값 계산중 ...");
  if (numbers.length === 0) return 0;
  const sum = numbers.reduce((a, b) => a + b);
  return sum / numbers.length;
};

const Average = () => {
  const [list, setList] = useState([]);
  const [number, setNumber] = useState("");

  const onChange = (e) => {
    setNumber(e.target.value);
  }

  const onInsert = () => {
    const nextList = list.concat(parseInt(number));
    setList(nextList);
    setNumber("");
  }

  return (
    <div>
      <input value={number} onChange={onChange} />
      <button onClick={onInsert}>등록</button>
      <ul>
        {list.map((value, index) => (
          <li key={index}>{value}</li>
        ))}
      </ul>
      <div>
        <b>평균값 : </b> {getAverage(list)}
      </div>
    </div>
  );
};

export default Average;

위 코드를 복사하여 실행해보면 다음과 같이 실행된다.

input에 값을 생성할 때마다 평균값이 구해지는게 보인다. 하지만 우리는 렌더링마다 평균값 구하기를 원하지 않는다. 즉, 값을 입력하고 등록을 눌렀을 경우메나 평균값 함수를 실행시키고 싶다. 이를 해결하기 위해서 useMemo를 사용한다.

useMemo를 추가한 코드를 살펴보자

import { useMemo, useState } from "react";
const getAverage = (numbers) => {
  console.log("평균값 계산중 ...");
  if (numbers.length === 0) return 0;
  const sum = numbers.reduce((a, b) => a + b);
  return sum / numbers.length;
};

const Average = () => {
  const [list, setList] = useState([]);
  const [number, setNumber] = useState("");

  const onChange = (e) => {
    setNumber(e.target.value);
  };

  const onInsert = () => {
    const nextList = list.concat(parseInt(number));
    setList(nextList);
    setNumber("");
  };

  // useMemo 생성
  const avg = useMemo(() => getAverage(list), [list]);

  return (
    <div>
      <input value={number} onChange={onChange} />
      <button onClick={onInsert}>등록</button>
      <ul>
        {list.map((value, index) => (
          <li key={index}>{value}</li>
        ))}
      </ul>
      <div>
        <b>평균값 : </b> {avg}
      </div>
    </div>
  );
};

export default Average;

useMemo(()=> getAverage(list), [list]); 이와 같은 코드를 추가해줬다. 코드를 해석해보면 두번째 인자로 넘겨준 값이 변할 때만 getAverage함수를 실행시켜줘!!라고 이해하면 된다. 실행을 하면 값을 등록했을 때만 평균값을 구하는 함수가 실행된것을 확인할 수 있다.

import React from 'react'를 사용안해도 되나요??

React v17버젼부터는 React내부적으로 JSX transformer가 JSX를 React 요소로 변환하는 작업을 거치기 때문에 모든 컴포넌트에 import React from 'react'를 작성하지 않아도 된다.

위 코드를 아래 코드처럼 작성하여도 컴파일단계에서 에러가 발생하지 않는다.

또한 React v18부터는 ReactDOM.render() 대신에 ReactDOM.createRoot().render() 사용해야 한다.!!

Tree는 graph의 특수한 경우로서 다음과 같은 특징을 가진다.

트리는 각 노드사이에는 오직 한 개의 간선으로 이루어져 있으며(연결성), 각 노드를 연결했는 때 순환하는 경로가 존재해서는 안된다.(비순환성)

Tree의 용어를 살펴보면 다음과 같다.

• Root : 모든 노드의 조상이자 트리내에서 가장 최상단에 위치하며 오직 1개 존재한다.
• 비단말 : 자식이 존재하는 노드
• 단말 : 자식이 없고 마지막 비단말 노드 아래에 위치한 노드

뿐만아니라 K-ary tree, 즉 K진 트리라고 불리우는 모든 node의 자식이 k개 이하인 tree가 있다.

• k=2 => 이진트리
• k=4 => 4진트리
• k=8 => 8진트리

이진트리의 종류

포화 이진트리

• 말 그래도 포화다.
• 즉, 모든 비단말 노드(단말제외)가 2개의 노드를 가진다.
• 모든 단말노드는 동일한 level 즉, 같은 높이에 있다.

total of nodes N = 2^0 + 2^1 + 2^2 + ... + 2^h = 2^(h+1) - 1
위의 식을 계산하면 아래와 같다.
h = log(N+1) - 1 = log N

완전 이진트리

• 트리의 높이를 h라 가정하였을 때 h-1높이까지는 포화 이진트리이다.
• 즉, h-1높이까지는 모든 노드들이 꽉 채워진다.
• 포화 이진트리와 차이점은 마지막 h높이에는 모든 노드들이 꽉 차있는 것은 아니다.
• 그래서 마지막 레벨이 가질 수 있는 노드의 개수는 1개 이상 2^h - 1개이다.

2^h - 1 < N <= 2^(h+1) - 1

2^h <= N < 2^(h+1)
h <= log N < h+1
h = Math.floor(log N) = log N

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

출력

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다.

예제

예제 입력 1

2 2 0 0 1000 0 1000 1000 2000 1000 2 0 0 1000 0 2000 1000 2000 2000

예제 출력 1

happy sad

해결방안

출발지점에서 도착지점까지 갈 수 있는지 없는지를 구해야 하는데 중요한 것은 도착지점까지 가는 도중에 편의점에 들릴지 말지 결정하는 부분이였다고 생각한다. 그래서 나는 다음과 같은 로직을 토대로 구현해봤다.

1. 처음 시작지점에서 도착지점까지 거리가 1000이하 이면 종료(happy출력)
2. 시작지점에서 각각의 편의점까지 거리가 1000인 편의점을 방문처리하고 큐에 넣는다.
3. 큐에서 편의점을 하나 꺼내고 이 편의점에서 갈 수 있는 다음 편의점이 있다면 방문처리 후 큐에 넣는다. 3-1. 도착지점까지 거리가 1000이하라면 반복문 종료(happy출력)
4. 3번 반복
5. 큐를 탐색하는 동안 도착지점에 도착하지 못했다면 sad출력

배운점

방문처리하는 부분에 대해서 Map 자료구조를 사용했는데 그 이유는 키의 자료형은 string뿐만 다른 자료형도 들어갈 수 있다고 생각해서였다. 하지만 원시타입만 가능할 뿐 참조타입은 안된다는것을 몰랐기에 Map의 키값으로 배열을 넣고 방문처리를 구현할 수 없었다. [1,2] === [1,2] => false

코드

const [TC, ...input] = `4
2
0 0
1000 0
1000 1000
2000 1000
2
0 0
1000 0
2000 1000
2000 2000
0
0 0
500 501
0
0 0
500 499`
  .toString()
  .trim()
  .split("\n");
// console.log(TC, input);
const answer = [];

const distanceBetweenTwoPoints = (x1, y1, x2, y2) => {
  return Math.abs(x1 - x2) + Math.abs(y1 - y2);
};

for (let i = 0; i < input.length; i++) {
  const storeCnt = +input[i++];
  const start = input[i++].split(" ").map(Number);
  const store = [];
  let cnt = 0;
  for (let j = i; j < i + storeCnt; j++) {
    const [x, y] = input[j].split(" ").map(Number);
    store.push([x, y, cnt++]);
  }
  i += storeCnt;
  const end = input[i].split(" ").map(Number);

  //   console.log("편의점 개수 : ", storeCnt);
  //   console.log("출발지점 : ", start);
  //   console.log("편의점 모음 : ", store);
  //   console.log("도착지점 : ", end);

  if (distanceBetweenTwoPoints(start[0], start[1], end[0], end[1]) <= 1000) {
    answer.push("happy");
    continue;
  }

  const visited = new Array(store.length).fill(0);
  const queue = [];
  for (let k = 0; k < store.length; k++) {
    const [storeX, storeY, index] = store[k];

    if (distanceBetweenTwoPoints(start[0], start[1], storeX, storeY) <= 1000) {
      queue.push([storeX, storeY, index]);
      visited[index] = 1;
    }
  }
  //   console.log(queue);
  let idx = 0;
  let flag = 0;
  while (idx < queue.length) {
    const [curR, curC, index] = queue[idx++];

    if (distanceBetweenTwoPoints(curR, curC, end[0], end[1]) <= 1000) {
      answer.push("happy");
      flag = 1;
      break;
    }
    for (let i = 0; i < store.length; i++) {
      const [storeX, storeY, idx] = store[i];

      if (
        distanceBetweenTwoPoints(curR, curC, storeX, storeY) <= 1000 &&
        !visited[idx]
      ) {
        queue.push([storeX, storeY, idx]);
        visited[idx] = 1;
      }
    }
  }
  if (flag) continue;
  answer.push("sad");
}
console.log(answer.join("\n"));

지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.

그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.

그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.

그림 2

그림 3

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

입력

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

출력

첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

예제

예제 입력 1

5 7 0 0 0 0 0 0 0 0 2 4 5 3 0 0 0 3 0 2 5 2 0 0 7 6 2 4 0 0 0 0 0 0 0 0 0

예제 출력 1

2

위 문제는 bfs 또는 dfs로 풀이가 가능한 문제이다. 즉 탐색문제라는 것이다. 그 이유는 1년 마다 모든 빙산의 위,아래,좌,우를 탐색하여 인접 칸이 0이라면 인접 칸의 개수만큼 빙산의 높이를 감소시키고 그 이후에 다시 모든 배열을 탐색하여 빙산의 구역이 2개 이상으로 나눠졌으면 그 때까지 몇 년이 걸리는지 알아보기 때문이다.

그래서 나는 크게 2가지의 로직으로 구현해봤다.(물론 다르게 생각하신 분도 계실거라고 생각하기때문에 참고만해주시면 감사하겠습니다!!)

1. 모든 빙산이 1년 마다 감소되는 높이를 측정하여 큐에 넣어준다.
2. N년이 지나고 N+1년이 되는 해가 시작되는 지점이 왔을 때 모든 배열이 탐색하여 빙산의 구역이 몇 구역으로 나눠지는지 파악한다.

let [[N, M], ...map] = require('fs')
  .readFileSync('./dev/stdin')
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.split(" ").map(Number));

let copyMap = JSON.parse(JSON.stringify(map));
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];
const queue = [];

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (map[i][j] !== 0) queue.push([i, j, map[i][j], 0]);
  }
}
<!-- 빙산이 총 몇 구역인지 탐색>
const checkMap = (param) => {
  const visited = Array.from({ length: N }, () => new Array(M).fill(0));

  const bfs = (row, col) => {
    visited[row][col] = 1;

    const queue = [[row, col]];
    let idx = 0;

    while (idx < queue.length) {
      const [curR, curC] = queue[idx++];

      for (let i = 0; i < 4; i++) {
        const [nextR, nextC] = [curR + dr[i], curC + dc[i]];

        if (
          nextR >= 0 &&
          nextC >= 0 &&
          nextR < N &&
          nextC < M &&
          param[nextR][nextC] !== 0 &&
          !visited[nextR][nextC]
        ) {
          visited[nextR][nextC] = 1;
          queue.push([nextR, nextC]);
        }
      }
    }
  };
  let count = 0;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (param[i][j] !== 0 && !visited[i][j]) {
        count += 1;
        if (count >= 2) return true;
        bfs(i, j);
      }
    }
  }
  return false;
};

let idx = 0;
let year = 0;
while (queue.length) {
  const [curRow, curCol, level, curYear] = queue.shift();
  <!-- 새롭게 해가 바뀌는 구간>
  if (year !== curYear) {
    year = curYear;
    map = JSON.parse(JSON.stringify(copyMap));
    if (checkMap(map)) {
      console.log(year);
      return;
    }
  }
<!-- 모든 빙산의 위,아래,왼쪽,오른쪽을 탐색하여 높이 감소>
  let count = 0;
  for (let i = 0; i < 4; i++) {
    const [nextRow, nextCol] = [curRow + dr[i], curCol + dc[i]];

    if (
      nextRow >= 0 &&
      nextCol >= 0 &&
      nextRow < N &&
      nextCol < M &&
      map[nextRow][nextCol] === 0
    ) {
      count += 1;
    }
  }
  const nextLevel = level - count;
  nextLevel > 0
    ? (copyMap[curRow][curCol] = nextLevel)
    : (copyMap[curRow][curCol] = 0);
  if (copyMap[curRow][curCol] !== 0)
    queue.push([curRow, curCol, copyMap[curRow][curCol], curYear + 1]);
}
console.log(0);

CPU관점에서 간략하게 살펴보자

1. CPU는 메모리에 프로그램이 올라와야 읽고 실행 할 수 있다!
2. 메모리에 올라온 프로그램 -> 프로세스!

• OS는 프로세스를 어떻게 관리하는가? PCB
• 프로세스의 라이프 사이클, 쓰레드, 스케쥴링
• IPC, 그리고 공유자원 문제, 교착상태

메모리 관리

운영체제에 의해 메모리 관리가 필요한 이유

메모리는 공유자원

• 여러 프로세스 사이에 메모리 공유

메모리 보호

• 프로세스의 독립된 메모리 공간 보장
• 다른 프로세스로부터 보호

메모리 용량 한계 극복

• 여러 프로세스의 메모리 합이 설치된 물리 메모리보다 큰 경우 필요

메모리 효율성 증대

• 가능하면 많은 개수의 프로세스를 실행시키기 위해서
• 프로세스당 최소한의 메모리 할당

메모리는 컴퓨터 시스템 곳곳에 계층적으로 존재

• CPU레지스터 - CPU캐시 - 메인메모리 - 보조기억장치
• CPU레지스터에서 보조기억장치로 갈수록
  • 용량 증가, 가격 저렴, 속도 저하
• 메모리 계층 구조의 중심은 메인 메모리

그렇다면 왜 메모리를 계층화 했을까?

바로 CPU가 메모리에 접근하는 시간은 최대한 줄여 프로그램의 실행 속도를 올리기 위해서이다.

메모리 관리는 왜 어려운가?

1. 폰노이만 구조 -> 메모리는 컴퓨터의 유일한 작업공간이라 모든 프로그램은 메모리에 올라온다.

• 일괄처리 시스템 : 한번에 하나의 프로그램만 실행시킴으로 메모리 관리가 단순하다.
• 다중 프로그래밍 : 운영체제를 포함한 모든 응용 프로그램이 메모리에 올라와야 한다.

2. 유일한 작업공간을 같이 쓰다보니..

• 여러 프로세스간 침범이 안되게 하면서
• 그러면서 필요한 공간은 충분히 할당해줘야 하고
• 가능한 많은 프로세스를 동작시켜야 하는데, 메모리는 부족하고...

메모리 관리의 이중성

• 프로세스 : 가능한 많은 메모리를 쓰고 싶어함(메모리 독점)
• OS/관리자 : 가능한 메모리를 적게 주고 싶어함. 가능한 효율적으로..

컴퓨터의 메모리를 어떻게 관리 할 것인가?

-> 메모리 관리자의 작업/정책

1. 적재 정책(Fetch policy)

• 프로세스가 필요로 하는 데이터를 언제 메모리로 가져올지 결정하는 정책
• 요구반입 vs 예상반입

2. 배치 정책(Placement policy)

• 가져온 프로세스를 메모리의 어떤위치에 올려놓을지 결정하는 정책
• 최초 적합 vs 최적 적합 vs 최악 적합

3. 재배치(교체) 정책(Replacement policy)

• 메모리가 꽉 찼을 때 메모리 내에 있는 어떤 프로세스를 내보낼지 결정하는 정책
• 최적 교체, FIFO, LRU(Least Recently Used), LFU(Least Frequently Used)

MMU

Memory Management Unit의 약자로 일반적으로 MMU가 메모리 관리자로 불린다.

위 그림에서 빨간색 점선을 따라가보자

1. 논리주소를 물리주소로 바꾸는 하드웨어 장치

• CPU가 발생시킨 논리 주소는 MMU에 의해 물리 주소로 바뀌어 메모리에 도달한다.

2. 오늘날 MMU는 CPU 안에 내장

• MMU 덕분에 여러 프로세스가 하나의 메모리에서 실행될 수 있다.

메모리 오버레이

프로그램의 크기가 실제 메모리(물리 메모리)보다 클 때 전체 프로그램을 메모리에 가져오는 대신 적당한 크기로 잘라서 가져오는 기법 즉, 프로그램이 실행되면 현재 필요한 부분만 메모리에 올라와 실행 -> 바꿔가면서(swap)

가상메모리 공간

• 각 프로세스는 자신이 모든 메모리를 점유하고 있는 것처럼 생각한다.

swap

• 메모리가 모자라서 쫓겨난 프로세스를 저장장치의 특별한 공간에 모아두는 영역
• 메모리에서 쫓겨났다가 다시 돌아가는 데이터가 머무는 곳이기에 저장장치는 장소만 빌려주고 메모리 관리자가 관리
• 사용자는 실제 메모리의 크기와 스왑 영역의 크기를 합쳐서 전체 메모리로 인식하고 사용

노트북, 스마트폰에서 네이버에 접속하는 과정

1. Network Edge인 스마트폰이나 노트북이
2. Access Network인 와이파이에 접속하여
3. Network core의 기능을 통해 네이버 서버에 패킷을 전송하거나 받아온다.

정리

1. Network edge는 end system 즉, 사용자들의 스마트폰이나 PC, 회사 서버 등 클라이언트나 서버
2. Access Network는 end system들이 인터넷을 사용할 수 있도록 길을 열어주는 것.
3. Network core는 forwarding과 routing을 통해 패킷을 전송

• forwarding이란? 라우터의 Input으로 들어오는 패킷을 올바른 Output으로 보내는 기능(forwarding table을 읽어서)
• routing이란? 패킷이 어디로 가야하는지 판단하는 과정 즉, forwarding table을 만드는 과정.

알고싶은 것들

• 단일 링크로 전송하기 위해서 네트워크 계층 데이터그램을 어떻게 링크 계층 프레임으로 캡슐화하는지
• 통신 경로상에서 링크마다 상이한 링크 계층 프로토콜이 사용되는지
• 브로드캐스트 링크에서의 전송 충돌을 어떻게 해결하는지
• 링크 계층에서 주소체계가 있는지, 있다면 링크 계층 주소체계가 네트워크 계층 주소체계와 어떻게 상호 동작하는지
• 스위치와 라우터의 차이가 정확하게 무엇인지
• 현재 가장 많이 사용하는 유선 랜 기술인 이더넷을 포함한 스위치 랜(switched LAN)과 다중 접속망에 대해..
• 가상(virtual) 랜, 데이터 센터 네트워크(data center network)

링크 계층의 두 가지 종류

브로드 캐스트 채널

• 일반적으로 무선 랜(LAN), 위성 네트워크, HFC(hybrid fiber-coaxial cable) 접속망에서 다수의 호스트를 연결해 준다.
• 다수의 호스트가 연결되기 때문에 프레임 전송을 조정히기 위해 매체 접속 프로토콜(media access protocol)이 있어야 한다.
• 경우에 따라서는 중앙 제어기를 사용해서 전송을 조정할 수도 있다.

점대점(Point-to-Point)통신

• 원거리 링크에 의해 연결된 두 라우터 또는 사용자의 사무실 컴퓨터와 이 컴퓨터에 연결된 근처 이더넷 스위치 사이에서 사용될 수 있다.

다음 시간에는 오류검출 및 정정기술, 다중 접속 링크와 프로토콜에 대해서 알아보자

정수를 표현하는 비트수와 소수를 표현하는 비트수를 미리 정해놓고 해당 비트만큼만 사용해서 숫자를 표현하는 방식이다. 저는 이론을 이해하고 학습하는 것보다 바로 실전을 통해 이론을 학습하는 편이라서 먼저 예시를 통해 빠르게 알아보겠습니다. 예시를 들기위해 임의의 숫자인 263.3을 선택하였고 32비트를 사용하여 부호, 정수부, 소수부를 표현해보겠습니다.

부호의 경우 1비트를 차지하며 양수의 경우에는 0을, 음수의 경우에는 1로 표현합니다.

다음으로 263.3의 정수부를 구하는 과정을 가져보겠습니다. 2진수이기에 2로 나눠주면 다음 과정에서는 몫을 가지고 계속 실행시켜줍니다.

263 % 2 = 1
131 % 2 = 1
65 % 2 = 1
32 % 2 = 0
16 % 2 = 0
8 % 2 = 0
4 % 2 = 0
2 % 2 = 0
1 % 2 = 1

아래에서 위로 올라가면 읽어줍니다 100000111(2) -> 9비트 15비트 - 9비트 = 6비트 6비트를 모두 0으로 채워 정수부를 만들어 주면 000000+100000111 = 000000100000111(2) 이게 정수부입니다.

다음으로 소수부를 구해보는 과정을 해보겠습니다.

0.3 * 2 | 0.6 | 0
0.6 * 2 | 1.2 | 1
0.2 * 2 | 0.4 | 0
0.4 * 2 | 0.8 | 0
0.8 * 2 | 1.6 | 1
0.6 * 2 | 1.2 | 1
0.2 * 2 | 0.4 | 0
0.4 * 2 | 0.8 | 0
        .
        .
        .

0(1001)(1001)(1001)... 처음에 0뒤로는 계속 1001이 반복되는 과정을 거치지만 소수부의 비트는 최대 16비트이므로 16비트만 사용해줍니다.0100110011001100(2)으로 표현할 수 있습니다.

위 결과를 토대로 263.3을 고정소수점으로 나타내면 (0)(000000100000111)(0100110011001100)입니다.

하지만 고정소수점에는 단점이 존재합니다. 정수부의 bit를 늘려 큰 숫자를 표현할 수 있지만 정밀한 숫자를 표현하기 힘들고, 반대로 소수부의 bit를 늘려 정밀한 숫자를 표현할 수 있지만 큰 숫자를 표현하기 힘들다는 단점이 존재합니다. 이를 보완하기 위해서 부동소수점이 나왔습니다.

부동소수점이란?

부동은 영어로 float, 뜻은 떠다니다,유동적인이라는 의미를 나타내고 있습니다. 이는 소수점이 고정되어 있지 않고 좌우로 움직일 수 있다는 뜻입니다.

소수점이 자유롭게 움직인 다는 것은 표현할 수 있는 수의 범위가 매우 넓어진다는 장점을 가지고 있습니다. 바로 263.3을 부동소수점으로 구하는 과정을 구해보자.

고정소수점에서 구한 263.3의 정수부는 100000111(2), 소수부는 0100110011001100였다. 합치면 100000111.0100110011001100이다. 하지만 부동소수점에서는 지수부와 가수부를 사용하기때문에 표준 표기법으로 바꿔준다면 1.000001110100110011001100 * 2^8이 된다. 지수부인 8을 이진법으로 나타내면 100(2)으로 표현할 수 있다. 하지만 여기서 한가지 중요한 것이 있는데 바로 지수부는 양수와 음수를 둘 다 표현하기 위해서 8비트로 표현할 수 있는 숫자 영역을 반으로 나누어 양수와 음수를 표현하는 한다는 점이다.

00000000 ~ 01111110  => -127부터 -1까지인 음수를 표현
01111110 => 0을 표현
10000000 ~ 11111111 => 1부터 128까지를 표현

따라서 8을 표현하기위해서는 00001000에 127(01111111)을 더해야한다. 00001000 + 01111111 => 10000111이 바로 지수부이다.

다시 역으로 정리하면 0 10000111 000001110100110011001100에서 가수부는 000001110100110011001100이니 맨앞에 1하고 소수점을 추가한 1.000001110100110011001100이고 지수부는 8이니 가수부에 적용시키면 100000111.0100110011001100이다. 이를 10진수로 표현하면 263.3이 되는것이다.

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

예제

예제 입력 1

5 6 1 5 1 1 1 2 2 1 3 3 2 3 4 2 4 5 3 4 6

예제 출력 1

0 2 3 7 INF

해결

전형적인 다익스트라 알고리즘 문제로 보인다. 내가 참고한 글은 https://yabmoons.tistory.com/364 이다. 다른 글도 많지만 여기 블로그가 그림으로 잘 설명되있다.

위 글을 읽고 이해한 내용을 간략하게 설명해보고자 한다.

다익스트라는 방향과 가중치가 존재하는 그래프로 어느 한 노드에서 다른 노드로 갈 때 최단거리를 찾는 알고리즘이다. 다익스트라를 해결하기 위한 핵심은 그리디 알고리즘과 비슷하다고 느꼈다. 왜냐하면 현재의 노드에서 인접한 노드들이 여러개가 존재하는 상황에서 지금 당장 가야만 하는 노드는 최단거리의 노드라는 점이기 때문이다. 그렇기에 현재노드에서 갈 수 있는 노드의 조건은 다음과 같다.

1. 아직 최단거리를 찾지 못한 노드(= 아직 방문하지 못한 노드)
2. 갈 수 있는 노드들 중에서 가장 최단거리인 노드 위 와 같은 조건을 만족하는 노드를 찾아 그래프를 탐색하여 모든 노드까지의 최단거리를 구할 수 있다.

const distance = new Array(V + 1).fill(Infinity);
const visited = new Array(V + 1).fill(0);
const adjArr = Array.from({ length: V + 1 }, () => new Array());

for (let i = 0; i < E; i++) {
  const [from, to, weight] = input[i];
  adjArr[from].push([to, weight]);
}
distance[start] = 0;
visited[start] = 1;

let next = start;

<!--2번조건인 가장 최단거리인 노드를 찾아 반환한다.-->
const findNextV = () => {
  let min = Infinity;
  let minV = null;

  for (let i = 1; i <= V; i++) {
    if (!visited[i]) {
      if (distance[i] < min) {
        min = distance[i];
        minV = i;
      }
    }
  }

  if (!minV) return -1;
  else return minV;
};

while (1) {
  const cur = next;

  for (let i = 0; i < adjArr[cur].length; i++) {
    const [to, dis] = adjArr[cur][i];
    <!-- 1번 조건을 만족하는 노드들의 최단거리를 갱신해준다. -->
    if (!visited[to]) {
      if (distance[to] > distance[cur] + dis)
        distance[to] = distance[cur] + dis;
    }
  }

  const vaild = findNextV();
  if (vaild === -1) break;
  next = vaild;
  visited[next] = 1;
}

let answer = "";
for (let i = 1; i <= V; i++) {
  if (distance[i] === Infinity) answer += "INF\n";
  else answer += `${distance[i]}\n`;
}
console.log(answer);

위 코드를 작성하여 제출하면 통과는 할 수 있지만 시간복잡도 측면에서는 상당히 비효율적인 것을 확인했다. 그 이유는 다음과 같다.

1. 모든 노드를 탐색한다. O(N)
2. 각 노드마다 다음으로 갈 수 있는 노드를 찾기 위해 모든 노드를 탐색한다. O(N)

1번과 2번을 동시에 진행하기에 시간복잡도는 log(N^2)을 나타낸다. 노드가 100,000개 라면 100억 번의 탐색을 진행해야하기 때문이다. 이러한 비효율적인 시간복잡도를 해결하기 위해최소힙을 사용하여 다음 노드를 탐색하는 과정을 logN으로 줄여 시간복잡도를 O(NlogN)으로 만들 수 있다.

class MinHeap {
  constructor() {
    this.heap = [];
  }
  push(node, weight) {
    this.heap.push({ node, weight });
    if (this.heap.length === 1) return;
    let curIdx = this.heap.length - 1;
    let parentIdx = parseInt((curIdx - 1) / 2);
    while (
      curIdx > 0 &&
      this.heap[parentIdx].weight > this.heap[curIdx].weight
    ) {
      this.swap(curIdx, parentIdx);
      curIdx = parentIdx;
      parentIdx = parseInt((curIdx - 1) / 2);
    }
  }
  pop() {
    if (this.heap.length === 0) return -1;
    if (this.heap.length === 1) return this.heap.pop();
    const answer = this.heap[0];
    this.heap[0] = this.heap.pop();

    let pos = 0;

    while (1) {
      let cur = pos;
      let leftIdx = cur * 2 + 1;
      let rightIdx = cur * 2 + 2;
      if (leftIdx > this.heap.length - 1) break;

      if (this.heap[cur].weight > this.heap[leftIdx].weight) cur = leftIdx;
      if (
        rightIdx < this.heap.length &&
        this.heap[cur].weight > this.heap[rightIdx].weight
      )
        cur = rightIdx;

      if (cur === pos) break;
      this.swap(pos, cur);
      pos = cur;
    }

    return answer;
  }
  swap(a, b) {
    const tmp = this.heap[a];
    this.heap[a] = this.heap[b];
    this.heap[b] = tmp;
  }
}

const heap = new MinHeap();
const visited = new Array(V + 1).fill(0);
const distance = new Array(V + 1).fill(Infinity);
const adjArr = Array.from({ length: V + 1 }, () => new Array());

for (let i = 0; i < E; i++) {
  const [from, to, dis] = input[i];
  adjArr[from].push({ to, dis });
}

distance[start] = 0;
heap.push(start, 0);

while (heap.heap.length) {
  const { node, weight } = heap.pop();
  visited[node] = 1;

  for (let i = 0; i < adjArr[node].length; i++) {
    const { to, dis } = adjArr[node][i];
    if (!visited[to]) {
      if (distance[to] > weight + dis) {
        distance[to] = weight + dis;
        heap.push(to, distance[to]);
      }
    }
  }
}
let answer = "";
for (let i = 1; i <= V; i++) {
  if (distance[i] === Infinity) answer += "INF\n";
  else answer += `${distance[i]}\n`;
}
console.log(answer);

첫번째 풀이는 2616ms, 두번째 풀이는 1112ms로 시간복잡도가 상당히 개선된 것을 확인할 수 있다.

대개 react query를 도입하기 전에는 서버와의 API통신과 비동기 데이터 관리에 redux를 사용했습니다. 비동기 미들웨어인 redux-thunk, redux-saga를 사용하기도 하며 다양한 Custom미들웨어를 만들어 사용하기도 했습니다. 하지만 redux는 비동기 데이터를 관리하기 위한 전문 라이브러리가 아니라, 범용적으로 사용할 수 있는 전역 상태 관리 라이브러리이기에 redux 미들웨어로 비동기 상태를 불러오고 그 값을 보관할 수는 있지만, 내부적인 구현은 모두 개발자가 알아서 해야하기에 팀 구성원들이 많아지고 협업 관계가 복잡하게 구성될 수록 데이터를 관리하는 방식과 방법이 모두 달라지는 점이 발생합니다.

react-query 도입

redux를 사용한 API요청과 비동기 데이터 관리의 불편함을 해소하기 위해 react-query를 사용할 수 있습니다. react-query는 react application에서 서버의 상태를 불러오고, 캐싱하며, 지속적으로 동기화하고 업데이트하는 작업을 도와주는 라이브러리입니다. react-query는 우리에게 친숙한 Hook을 사용하여 react component 내부에서 자연스럽게 서버(또는 비동기적인 요청이 필요한 source)의 데이터를 사용할 수 있는 방법을 가지고 있습니다.

react-query는 API요청을 Query 와 Mutation 이라는 두 가지 유형으로 나누어 생각한다.

query 요청

// 가장 기본적인 형태의 React Query useQuery Hook 사용 예시
const { data } = useQuery(
  queryKey, // 이 Query 요청에 대한 응답 데이터를 캐시할 때 사용할 Unique Key (required)
  fetchFn, // 이 Query 요청을 수행하기 위한 Promise를 Return 하는 함수 (required)
  options, // useQuery에서 사용되는 Option 객체 (optional)
);

react-query의 useQuery Hook은 요청마다(API마다) 구분되는 Unique Key를 필요로 한다. react-query는 이 Unique key로 서버 상태를 로컬에 캐시하고 관리한다.

mutation 요청

// 가장 기본적인 형태의 React Query useMutation Hook 사용 예시
const { mutate } = useMutation(
  mutationFn, // 이 Mutation 요청을 수행하기 위한 Promise를 Return 하는 함수 (required)
  options, // useMutation에서 사용되는 Option 객체 (optional)
);

useMutation Hook으로 수행되는 Mutation 요청은 http method POST,PUT,DELETE 요청과 같이 서버에 Side Effect를 발생시켜 서버의 상태를 변경시킬 때 사용한다. useMutation Hook의 첫번째 파라미터는 이 Mutation 요청을 수행하기 위한 Promise를 Return 하는 함수 이며, useMutation의 return 값 중 mutate함수를 호출하여 서버에 side effect를 발생시킬 수 있다.

참고

• https://velog.io/@jay/10-minute-react-query-concept
• https://velog.io/@jay/5-minute-react-query-essential
• https://tech.kakao.com/2022/06/13/react-query/
• https://tech.kakaopay.com/post/react-query-1/