본문 바로가기

전체 글67

[MST][백준] 1197 최소 스패닝 트리 JS 풀이 💡 접근법 1. 모든 간선들을 비용순으로 오름차순으로 정렬 2. 비용이 작은 간선부터 선택해서 노드들을 같은 그래프로 합쳐줌. 만약 두 노드가 같은 그래프에 포함되어 있다면 넘어감. 3. 트리의 간선의 개수가 정점의 개수-1이면 반복문 break const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt'; // 입력값이 첫 번째 줄에는 입력 값의 길이(n), n개의 줄에 걸쳐서 한 줄에 하나의 입력값이 주어질 때 const [n, ...input] = require('fs') .readFileSync(filePath) .toString() .trim() .split('\n'); function solution(V, E, Lis.. 2023. 12. 28.
MST 크루스칼 알고리즘 설명 크루스칼 알고리즘은 최소 신장 트리를 찾기 위한 알고리즘입니다. 신장 트리란? : 무방향 그래프의 부분 그래프 중 모든 정점을 포함하는 트리 최소 신장 트리란? : 간선의 합이 최소인 신장 트리 Union & Find 알고리즘 : 두 정점이 같은 그래프에 속하는지 판별하는 알고리즘 https://blog.naver.com/ndb796/221230967614 크루스칼 알고리즘 1. 간선의 크기대로 오름차순 정렬하고 제일 낮은 비용의 간선을 선택 2. 현재 선택한 간선이 정점 u,v를 연결하는 간선이라고 할 때 1. 만약 u와 v가 같은 그룹이라면 아무 것도 하지 않고 넘어간다 2.만약 u와 v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장 트리에 추가한다(union&find 알고리즘.. 2023. 12. 28.
[백준] 7569 토마토 js 풀이 💡 접근법 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라 최소 일수를 구해야 하고, 익은 토마토 인접 토마토부터 순차적으로 익으니까 => BFS 1. 익은 토마토를 모두 큐에 넣어준다 2. 익은 토마토와 인접하고 아직 익지 않은 토마토는 큐에 넣어준다 2-1. 박스 위아래 확인 2-2. 같은 박스에서 상하좌우 확인 3. 큐가 빌 때까지 반복 class Node { constructor(val) { this.val = val; this.next = null; } } class Queue { constructor() { this.start = null; this.end = null; this.size = 0; } enqueue(val) { const newNode = ne.. 2023. 12. 28.
[자바스크립트] 비동기 처리와 이벤트루프 비동기 프로그래밍 vs 동기 프로그래밍 무슨 차이일까? 동기 처리 : 현재 실행 중인 태스크가 종료할 때까지 다음 태스크가 대기하는 방식 -> 실행 순서가 보장되지만 실행 중인 태스크가 종료될 때까지 이후 태스크들은 블로킹 됩니다. 비동기 처리 : 현재 실행 중인 태스크가 종료되지 않더라도 다음 태스크를 실행하는 방식 -> 블로킹이 발생하지 않지만 실행 순서는 보장되지 않습니다. 자바스크립트 비동기 코드 예시 function a(){ console.log('a'); } function b(){ setTimeout(a, 300); console.log('b'); } b(); //실행결과 //'b' //'a' 자바스크립트가 비동기 처리를 지원하지 않는다면 a함수가 실행된 후에 b함수가 실행되어야 합니다. 이.. 2023. 12. 27.
[자바스크립트] 클로저 클로저를 이해하기 위한 개념 렉시컬 환경 해당 개념을 모르신다면 실행 컨텍스트 포스팅을 먼저 읽는 것을 추천드립니다! 클로저 외부 함수보다 오래 유지되어 생명 주기가 끝난 외부 함수의 변수를 참조하고 있는 중첩 함수 예제 function coffeeMachine() { let coffeeBeans = 10; const makeCoffee = () => { if (coffeeBeans { console.log(`현재 남아 있는 원두는 ${coffeeBeans}g 입니다.`); }; .. 2023. 12. 27.
[자바스크립트] 실행컨텍스트 📌 실행 컨텍스트(Execution Context) 식별자와 스코프, 코드 실행 순서를 관리하기 위해 구현한 내부 메커니즘 식별자와 스코프는 실행 컨텍스트의 렉시컬 환경으로 관리하고, 코드 실행 순서는 실행 컨텍스트 스택으로 관리합니다. 실행 컨텍스트 스택 실행 컨텍스트는 스택 자료구조로 관리됩니다. 코드가 실행되면 해당 코드의 실행 컨텍스트가 생성되어 스택에 push되고, 실행이 종료되면 pop 됩니다. 렉시컬 환경 식별자와 스코프를 관리하는 자료구조입니다. 환경레코드와 외부 렉시컬 환경에 대한 참조로 구성되어 있습니다. 환경레코드 스코프에 대한 식별자와 바인딩된 값을 관리합니다. 외부 렉시컬 환경에 대한 참조 상위 스코프를 가리킵니다 스코프 체인 = 외부 렉시컬 환경에 대한 참조를 통해 단방향 링크드.. 2023. 12. 27.

티스토리툴바