본문 바로가기

전체 글181

[프로그래머스 lv2] 택배상자 JS https://school.programmers.co.kr/learn/courses/30/lessons/131704 문제요점 1번부터 n번까지 증가하는 순으로 벨트에 놓여있다. 1번부터 순서대로 상자를 내릴 수 있다. 현재 실을 순서가 아니면 보조컨테이너에 보관 => 보조컨테이너는 마지막에 보관한 상자부터 꺼내게 된다 stack 보조를 사용해도 순서대로 싣지 못하면 더이상 상자를 싣지 않는다 실을 수 있는 상자 갯수 리턴 풀이 기존의 상자 순서대로 진행할 때, 다음상자와 보조컨테이너의 마지막 상자를 체크한다 O(nlogn) 상자를 1부터 n개까지 순회하며 현재 실어야하는 순서인지 확인한다 컨테이너벨트에 상자가 있으면 옮기고 보조컨테이너벨트(stack)의 마지막에 상자가 있으면 stack의 마지막 상자를 .. 2023. 10. 6.
[hash, 이진탐색 LV2] 시소 짝꿍 JS https://school.programmers.co.kr/learn/courses/30/lessons/152996 문제요점 4,3,2 축 2,3,4 시소짝꿍: 몸무게*거리가 같으면 몇쌍 짝꿍존재? (보충) 짝꿍끼리의 순서는 상관없다. (시소의 오른쪽, 왼쪽 중 어디에 앉는지는 구별하지 않음) 풀이 2,3,4를 통해 가능한 조합을 만든다 짝꿍끼리의 순서는 상관없으므로 왼쪽무게 중심으로 가능한 오른쪽 무게를 찾고 그 갯수를 더한다 왼쪽 중심으로 가능한 오른쪽무게는 왼쪽무게의 *1, *3/2, *2, *4/3이다 왼쪽이 2, 오른쪽 2일때 => 1:1 => 오른쪽은 왼쪽의 1배 왼쪽이 2, 오른쪽 3일때 => 2:3 => 오른쪽은 왼쪽의 3/2배 왼쪽이 2, 오른쪽 4일때 => 1:2 => 오른쪽은 왼쪽의 .. 2023. 10. 4.
[프로그래머스 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.

티스토리툴바