알고리즘 문제 풀어보기

숫자 변환하기

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

x에 n을 더합니다
x에 2를 곱합니다.
x에 3을 곱합니다.
자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한사항

1 ≤ x ≤ y ≤ 1,000,000
1 ≤ n < y

풀이 코드

function solution(x, y, n) {
    var que = [[y, 0]];
    
    while(que.length) {
        const [num, i] = que.shift();
        
        if(num === x){ 
            return i;
        }
        
        if(num%2 === 0 && num/2 >= x){
            que.push([num/2, i+1]);
        }
        if(num%3 === 0 && num/3 >= x){
            que.push([num/3, i+1]);
        }
        if(num-n >= x){
            que.push([num-n, i+1]);
        }
    }
    return -1;
}

풀이 과정

• 큐(queue)를 이용해 문제를 풀 수 있다.
  • 선입선출(FIFO)의 특징을 가진다.

y값을 기준으로 x값을 도달하기 위해 큐의 초기값을 y, 횟수를 0으로 세팅한다.
큐에 값이 없을 때 까지 반복하는 반복문을 만들어서 먼저 들어온 순으로 값을 가져오고(FIFO, First In, First Out) 조건문을 사용한다.

조건문

• 첫번째 : n값을 빼도 x보다 크거나 같은 경우.
• 두번째 : 2로 나누어 떨어질 때.
• 세번째 : 3으로 나누어 떨어질 때.

위의 조건에 부합한 경우에만 큐에 값을 저장하고, num값이 x와 같다면 i를 return해준다. 만약 반복문 안에서 return되지 않는 값은 x값과 같아질 수 없다는 의미이므로 -1을 return한다.

기술면접 문제 풀어보기

10. Node.js의 이벤트 루프란 무엇이고 왜 필요하며 어떻게 작동하는지 아는 만큼 설명해주세요.

• Node.js는 single-theaded 기반으로 동작하는데, 단일 thread가 가지는 단점을 보완하기 위해 I/O 작업의 처리에 비동기 논-블로킹 방식으로 동작하는 이벤트 루프를 사용합니다. 이벤트 루프는 멀티 쓰레드로 동작하는 시스템 커널에 I/O 작업을 넘겨주고, 작업이 백그라운드에서 처리되어 완료되면 처리 결과가 다시 Node.js로 돌아와 poll queue에 callback의 형태로 추가된 뒤 동기적으로 처리됩니다.

• 이벤트 루프에는 여러 페이즈가 존재합니다. 먼저 Timer 페이즈는 setTimeout과 setInterval로 스케쥴 된 callback 함수를 실행합니다. 다음 pending callbacks 페이즈는 I/O 콜백을 실행하고, idle/prepare 페이즈는 내부적으로 동작하며 이름 그대로 대기상태와 관련된 처리를 합니다. Poll 페이즈는 Timer 및 close 페이즈의 callback을 제외한 다른 모든 callback을 실행하며, setImmediate 를 호출한다면 이 구간에서 block 되고, Check 페이즈에서 실행됩니다. 마지막 close 페이즈에서는 소켓의 close나 database 연결 종료, 서버의 termination 등의 종료 작업이 처리됩니다.

11. Node.js의 libUV 라이브러리에 대해 설명해주세요.

• Libuv 라이브러리는 C언어로 작성된 라이브러리입니다. 핵심이 되는 두 가지 기능으로는 이벤트 루프와 uv_io가 있습니다. 이벤트 루프는 6개의 페이즈로 나뉘어있고, 라운드 로빈 방식으로 각 페이즈를 순회하며 non-blocking 작업을 담당합니다. uv_io는 OS 커널이 지원하는 비동기 함수 호출을 통한 비동기 작업의 처리와, worker thread를 이용하여 커널이 지원하지 않는 작업이나 파일 시스템 관련 작업 및 blocking 작업 처리를 담당합니다. 매 작업 종료 시 작업의 종류에 따라 이벤트 루프의 알맞는 위치에 callback을 등록하기도 합니다.

최종프로젝트

이전에 했던 팀프로젝트와 그 전 기수의 코드를 참고해가며 기본구조를 완성했다. Enter핸들러는 매칭시스템이랑 비슷하다고 생각했었는데 삽질 좀 하다 보니까 매칭시스템보다는 이전 개인프로젝트때 서버에 접속하던 방식과 비슷하다는걸 깨달았다.
내일 할 것 : Enter 마무리, 나머지 맡은 부분 진행.