-
항해 99 5기 TIL_53항해 99 2022. 3. 4. 01:38
▶ Today I Learned
<알고리즘>
[최대 힙]
소요 시간: 50분 + 30분 (해설 참고)
해결 여부: 해결
백준 11279번
https://www.acmicpc.net/problem/11279
처음 풀이
const input = [0,1,2,0,0,3,2,1,0,0,0,0,0] console.log(input.sort((a,b) => b - a)) let arr = [] let answer = [] for (let v of input) { if (v === 0) { let max = arr.sort((a,b) => b - a).shift() max === undefined ? answer.push(0) : answer.push(max) } else { arr.push(v) } } console.log(answer) // [3, 2, 2, 1, 1, 0, 0, 0] // 정답의 숫자들을 포함하고는 있지만 배열 내 숫자의 순서가 다르다.
그 다음 시도
const input = [0,1,2,0,0,3,2,1,0,0,0,0,0] let arr = [] let answer = [] for (let v of input) { if (v === 0) { let arr2 = arr let max = arr.sort((a,b) => b - a).shift() console.log(arr2.join('')) let first = arr2.join('').substring(0, arr2.indexOf(max)) let last = arr2.join('').substring(arr2.indexOf(max)+1) console.log(fisrt,'1') console.log(last,'2') max === undefined ? answer.push(0) : answer.push(max) } else { arr.push(v) } }
이런 식으로 배열의 순서를 바꾸지 않고 중간의 값들만 쏙쏙 빼기 위해 배열을 문자열로 만든 다음 최댓값이 들어있는 부분만 잘라내고
나눠진 문자열을 합쳐 split('')으로 배열화한 다음 각각의 값을 숫자로 형변환하려 했다.
하지만 중간 중간 고려할 것이 너무 많았고 시간 복잡도가 높을 것 같아 다른 풀이 법을 찾아보게 되었다.
const fs = require('fs'); const [_, ...input] = fs.readFileSync("./dev/stdin").toString().trim().split("\n"); // 이처럼 언더바를 쓰는 것은 변수명을 언더바로 하겠다는 것이다. 언더바로 하는 이유는 내가 이걸 사용하지 않겠다는 것을 명백히 보여주는 것이다. const num = input.map(v => +v); class MaxHeap { constructor() { this.heap = []; } empty() { if (this.heap.length == 0) { return true; } return false; } insert(value) { this.heap.push(value); this.bubbleUp(); } bubbleUp() { let currentIndex = this.heap.length - 1; while (currentIndex > 0) { const parentIndex = Math.floor((currentIndex - 1) / 2); if (this.heap[parentIndex] >= this.heap[currentIndex]) break; [this.heap[currentIndex], this.heap[parentIndex]] = [ this.heap[parentIndex], this.heap[currentIndex], ]; currentIndex = parentIndex; } } extractMax() { if (this.heap.length == 1) { return this.heap.pop(); } const max = this.heap[0]; // 기본적으로 bubble up() 때문에 가장 큰 값이 배열의 앞에 와있음, 가장 앞에 있는 값을 max로 주는 것 this.heap[0] = this.heap.pop(); // max 값을 주었으니 배열에서 값을 하나 빼면서 동시에 그 값을 위에서 뺀 자리에 넣어버림 this.sinkDown(0); // 그 다음 배열의 맨 앞 부터 가장 큰 값이 앞에 오도록 내림차순 나열 return max; } sinkDown(index) { const leftIndex = 2 * index + 1; const rightIndex = 2 * index + 2; const length = this.heap.length; let largestIndex = index; if (leftIndex < length && this.heap[leftIndex] > this.heap[largestIndex]) { largestIndex = leftIndex; } if (rightIndex < length && this.heap[rightIndex] > this.heap[largestIndex]) { largestIndex = rightIndex; } if (largestIndex !== index) { [this.heap[index], this.heap[largestIndex]] = [this.heap[largestIndex], this.heap[index]] [this.heap[index], this.heap[largestIndex]] = [this.heap[largestIndex], this.heap[index]] this.sinkDown(largestIndex); } } } const answer = []; const maxHeap = new MaxHeap(); num.forEach(v => { if (v == 0) { if (maxHeap.empty()) { answer.push(0); // 값이 비었으니 0 집어넣기 } else { answer.push(maxHeap.extractMax()); // 배열 내 값이 들어 있으니 가장 큰 값을 추출 } } else { maxHeap.insert(v); // bubbleUp()으로 최대 힙 순서대로 배열 값 나열하면서 새로운 값 추가 }) console.log(answer.join('\n')); // 답으로 입력된 배열들 예제와 같이 줄바꿈 적용하여 반환
사실상 다른 분께서 작성하신 코드를 그대로 가지고 왔다. 하지만 내 것으로 만들기 위해 코드를 한줄 한줄 읽어내려가며
최대한 이해하려고 했다. 주석은 내가 직접 추가로 달아놓은 설명들이며
요점은 배열을 최대힙 자료구조로 만들어 답을 추출했다는 것이다.
cf) Heap 자료구조란?
쉽게 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리,
(대 힙이면 '큰', 최소 힙이면 '작은' 이다.)자세한 설명은 하단 링크 참조:
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
비슷한 문제
최소힙? https://velog.io/@ywc8851/%EB%B0%B1%EC%A4%80-1927-%EC%B5%9C%EC%86%8C-%ED%9E%99-javascript
<실전 프로젝트>
[socket.io]
function 어떤 함수(event) { event.preventDefault(); const input = room.querySelector("input"); socket.emit("new_message_here", input.value, roomName, () => { addMessage(`You: ${input.value}`); }); input.value = ""; }
여기서 실제로 실행 시 'You:'와 같이 메시지가 없는 것 처럼 보인다. 왜일까?
이는 자바스크립트의 비동기처리 속성 때문이다. socket.emit이 실행되면서 input.value도 동시에실행되어 버렸으니
시작부터 input 값을 비워준 셈이다.
그럼 input.value를 socket.emit이라는 이벤트를 발생시키는 함수 안에 집어넣으면 되지 않는가?
그럼 순서대로 잘 작동하지만 여기도 문제가 있다.
서버에서 해당 익명함수를 실행시키는 것이 늦어질 경우 input란에 값이 바로 비워지지 않을 수 있고
이는 유저 입장에서 렉이 걸린 것 처럼 보일 수 있다.
따라서 다음과 같이 입력하는 것을 권한다.
function 어떤 함수(event) { event.preventDefault(); const input = room.querySelector("input"); const value = input.value; socket.emit("new_message_here", input.value, roomName, () => { addMessage(`You: ${value}`); }); input.value = ""; }
아주 좋다 :)
[익명 id 만들기 - uuid]
비회원 로그인 유저에 대해 다음과 같이 임시 아이디를 발급하기로 했다.
createAnonOrigin: () => { return v4(); }
npm의 공식문서 설명에 따르면 uuid.v4()라는 요소를 통해 랜덤의 Universally Unique Identifier를 만들 수 있다.
참고자료:
https://www.npmjs.com/package/uuid
[Adapter]
사용자가 많아지면 서버를 여러 개 사용하게 된다. 이때 서버 A에서 메시지를 전송한다고 해서 서버 B의 다른 유저들에게 자동적으로 메시지가 보이는 것은 아니다. 서버 간의 연결이 필요한 데, 이를 위해 기본적으로 쓰이는 in-memory adapter가 아닌 다른 adapter로 바꾸어주어야 한다. Adatpter는 서버에 존재하는 일종의 컴포넌트로써 모든 또는 일부의 클라이언트에게 이벤트를 전해주는 (broadcast) 역할을 한다. 자세한 설명은 아래 블로그와 공식문서를 참조해보자.
https://socket.io/docs/v4/adapter/
▶ 느낀 점
알고리즘을 풀 때 점점 난이도가 올라갈 수록 클래스와 객체, 함수를 생성하여 푸는 문제가
많아지는 것 같다. 아직 객체지향 프로그래밍이 익숙한 것은 아니지만 이렇게
점점 연습해 보아야 겠다.
+
오늘도 꽤나 많은 지식을 배웠다. 강의도 빠른 속도로 듣고 알고리즘도 하나하나 뜯어보다 보니 처음엔 머리가 아팠지만
이렇게 또 성장해간다고 생각하니 내심 마음이 뿌듯하기도 하다.
전날 밤을 새다시피 해서 정신이 좀 몽롱하기도 했지만 잘 마무리 짓고
내일도 화이팅 해보아야 겠다.
▶ 공부 시 참고 링크들
https://www.passportjs.org/packages/passport-kakao/
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/switch
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Statements/label
https://ryan-han.com/post/translated/pathvariable_queryparam/
https://ko.javascript.info/map-set
'항해 99' 카테고리의 다른 글
항해 99 5기 TIL_55 (0) 2022.03.06 항해 99 5기 TIL_54 (0) 2022.03.05 항해 99 5기 TIL_52 (0) 2022.03.03 항해 99 5기 TIL_51 (0) 2022.03.02 항해 99 5기 TIL_50 (0) 2022.03.01