본문 바로가기

전체 글185

[프로그래머스 LV2] 호텔 대실 JS https://school.programmers.co.kr/learn/courses/30/lessons/155651 문제요점 10분청소 후 다음 사용가능 필요한 최소객실수는? 풀이 분으로 변환 시작시각 오름차순 각 방마다 입실 가능한 시각을 저장하는 배열 canEnterTimes을 시각 오름차순정리 첫번째방 추가 (이때 10분의 청소시간도 플러스) 다음 방부터 순회를 돌며 들어 갈 수 있는 방이 없는 경우 (현재 예약의 입실 시각 < 가장 빠른 입실 가능한 시각) 방추가 현재 입실하는 방의 다음 입실 가능시각 canEnterTimes에 추가 (+ 10 청소시간) canEnterTimes 가장 빨리 입실 가능한 시각 오름차순으로 갱신 들어 갈 수 있는 방이 있는 경우 canEnterTimes에서 첫번째 제.. 2023. 10. 4.
[크루스칼] 섬 연결하기 크루스칼 알고리즘이란 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 최소비용신장 트리를 만들기 위한 대표적 알고리즘으로 그래프에서 모든 노드를 연결할때 적용된다. 1. 우선 비용 오름차순으로 정렬한다. 2. 작은 비용의 선부터 연결하면서 Union find를 통해 신장트리가 되는지 확인한다 이때 이미 연결된 노드는 연결하지 않고 스킵한다 3. 모든 노드의 부모가 통일되면 최소비용신장트리가 완성된다. https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. pro.. 2023. 9. 25.
MST 최소비용신장트리, Union find 개념과 JS코드 신장트리란 모든 노드가 연결되있고 사이클이 없는 그래프이다. n개의 노드를 n-1개의 선으로 연결한다. 그래프의 최소연결 그래프이다 보통 네트워크 구축에 많이 사용된다 최소비용신장트리란 MST (Minimum Spanning Tree) 간 선에 비용을 붙여 최소의 비용이 드는 신장트리다 조건은 비용 최소 반드시 n-1개의 선만 사용 사이클이 없다 MST를 구하는데 주로 크루스칼, 프림알고리즘이 사용된다 먼저 크루스칼 알고리즘의 베이스인 union find를 알아보자. Union-Find란 여러개의 노드가 존재할 때 선택한 두 개의 노드가 같은 그래프에 있는지를 판별하는 알고리즘이다. 먼저 기본적으로 자기자신을 부모로 가지는 배열을 만들고 서로 다른 부모를 합칠 때 더 작은 쪽으로 합친다. 3과 1이 연결.. 2023. 9. 25.
[dfs, union find] 네트워크 https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 첫 풀이 처음에 단순히 섬의 개수를 구하는 문제와 비슷하다고 생각해서 땅을 찾으면 땅을 파고들어갔는데 문제를 잘 못 이해한거 였다 function solution(n, computers) { var answer = 0; const direction = [ [-1, 0], [0, 1], [1, 0], [0, -1], ]; function dfs(r, c) { for (const [dx, dy] of.. 2023. 9. 25.
색종이 만들기 (dfs) https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 여러줄 입력 split('\n') map(e => Number(e)) === map(Number) 0항 0열부터 돌면서 isUnion을 검사한다 isUnion이거나 더이상 자를 수 없는 조각이면 왼쪽상단모서리가 1일떈 blue++, 0일땐 white++ !isUnion이면 한 변이 n/2크기로 잘라서 다시 isUnion검사를 한다 const input = require(.. 2023. 9. 23.
[그리디] 체육복 https://school.programmers.co.kr/learn/courses/30/lessons/42862?language=javascript# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 function solution(n, lost, reserve) { var answer = 0; for (let i = 1; i r !== i); } // 왼쪽 사람이 여분있음 else if (reserve.includes(i-1)) { // 여분있는사람이 도난당함 if (lost.includes(i-1)) { continue; } else { answe.. 2023. 9. 20.

티스토리툴바