[프로그래머스 Lv3] 야근 지수 - Javascript 풀이
PS/프로그래머스_PS
https://school.programmers.co.kr/learn/courses/30/lessons/12927?language=javascript 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제야근 피로도를 최소화한 값을 구하는 문제 생각가장 큰 수부터 일을 진행해야 한다.작업마다 정렬을 반복해서 큰 값부터 줄여갈 수 있지만, 매번 정렬이 일어나기 때문에 비효율적이다.이 문제는 반복적으로 가장 큰 값을 빠르게 꺼내고 다시 넣는 작업이 필요하므로,정렬보다 Max Priority Queue(최대 힙) 을 사용하는 것이 적절하다고 판단했다. 문제풀이1. 작업 배열을 Max Heap에 넣는다.2. 남은 작업 시간..
[프로그래머스 Lv4] 호텔 방 배정 - Javascript 풀이
PS/프로그래머스_PS
문제요청한 방 번호가 이미 배정되어 있을 때,지나갈 수 있는 다음 빈 방 번호를 찾아 배정해야 하는 문제 생각처음엔 '그냥 현재 방이 차 있으면 +1 탐색하면 되지 않나?'라고 생각하였다.하지만 요청이 수십만 번 들어오는 상황에서이미 배정된 방을 하나씩 순회하면서 찾는다면 최악 O(N) 이 되고,요청 개수가 N이면 O(N²) 가까운 시간이 걸려 효율성 전부 시간초과가 난다. 따라서 이 문제는특정 번호 이후의 ‘다음 빈 방의 번호’를 매우 빠르게 찾아야 한다.즉, find → parent 갱신 구조를 사용하는Union-Find(Disjoint Set) 방식으로 해결해야 한다. 문제 풀이방 번호를 포인터처럼 연결해주면서,각 방이 ‘다음 가능한 빈 방 번호(next)’ 를 가리키도록 만든다. 예를 들어 1번 ..
[프로그래머스 Lv4] 징검다리 - Javascript 풀이
PS/프로그래머스_PS
문제지나갈 수 있는 최소 거리의 최댓값을 구하는 문제 생각거리의 최솟값을 이분 탐색으로 조절하며가능한지 체크하는 방식으로 풀어야 한다. 단순히 양끝부터 하나씩 지우거나,정렬된 간격만 보고 제거하는 방식으로는 최적해가 보장되지 않는다. 예를 들어 아래와 같은 경우를 생각해보자.distance = 25rocks = [2, 11, 14, 17, 21]n = 2 최소 간격을 어느 정도로 잡아야 가장 좋은가?한 번 mid를 잡고, 이 mid 이상을 유지할 수 있는지를 검증하는 방식으로 풀어야 한다. 문제풀이 mid = 최소 거리라고 가정했을 때,그 mid를 만족하도록 돌을 제거했을 때제거 횟수가 n 이하인지? 이 검증을 통해 mid가 가능한 값인지 판단한다. mid 검증 방법stones를 정렬한 뒤 다음을 반복..
[프로그래머스 Lv4] 도둑질 - Javascript 풀이
PS/프로그래머스_PS
https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제훔칠 수 있는 돈의 총합의 최댓값을 구하는 문제 생각일반적인 집 도둑 문제(선형 구조)는i번째 집을 털지 말지 선택하며 최대 금액을 DP로 계산하는 문제이다.점화식도 단순하다:DP[i] = max(DP[i-1], DP[i-2] + money[i]) 하지만 이 문제는 원형 구조라서첫 집을 털면 마지막 집을 털 수 없고,마지막 집을 털면 첫 집을 털 수 없다는 제약이 생긴다. 단순히 짝수/홀수 집만 터는 방식으로는 최적해가 보장되지 않는다.예시로,[2, ..
[프로그래머스 Lv4] 사칙연산 - Javascript 풀이
PS/프로그래머스_PS
문제정수와 +, - 연산자가 번갈아 들어 있는 배열이 주어졌을 때,괄호를 적절히 배치하여 만들 수 있는 계산 결과 중 최댓값을 구하는 문제 생각단순히 왼쪽부터 순차 계산하면 괄호의 효과를 전혀 반영할 수 없다.특히 − 연산은 결합법칙이 성립하지 않기 때문에중간에 어떤 값을 먼저 계산하느냐에 따라 결과가 크게 달라진다.그래서 구간별로 만들 수 있는 최댓값과 최솟값을 모두 관리하는 DP가 필요하다고 생각했다. 문제풀이테이블을 정의해보자.Max[i][j] : i번째 숫자부터 j번째 숫자까지 계산해서 얻을 수 있는 최댓값Min[i][j] : i번째 숫자부터 j번째 숫자까지 계산해서 얻을 수 있는 최솟값 여기서 i, j는 숫자의 인덱스이다.연산자는 숫자 사이에 하나씩 존재하므로,연산자 op[k]는 num[k] 와..
[프로그래머스 Lv3] 정수 삼각형 - Javascript 풀이
PS/프로그래머스_PS
문제정수 삼각형이 주어졌을 때꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾는 문제 생각DP에 각 위치까지 도달했을 때의 최댓값을 저장하고,마지막 줄(바닥)에 도달했을 때 그 중 가장 큰 값이 정답이라고 생각했다. 문제풀이테이블을 정의해보자.D[i][j] : 꼭대기에서 i번째 줄의 j번째 위치까지 도달했을 때 얻을 수 있는 최대 합D[i] = f(D[i-1]) 현재 값 triangle[i][j]을 K라고 하면, 점화식은 다음과 같다.j === 0 인 경우: 오른쪽 부모만 존재j === i 인 경우: 왼쪽 부모만 존재그 외: 왼쪽/오른쪽 부모 모두 존재D[i][j] = K + max(D[i-1][j], D[i-1][j-1]) 시간복잡도는 O(N^2)이다. 이 외에도 더 효율적..
[프로그래머스 Lv3] 숫자 타자 대회 - Javascript 풀이
PS/프로그래머스_PS
https://school.programmers.co.kr/learn/courses/30/lessons/136797 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제숫자 배열 numbers가 주어질 때,왼손과 오른손의 현재 위치를 고려하여 각 숫자를 입력하는 데 드는 최소한의 이동 비용(가중치)을 구하는 문제 생각numbers의 최대 길이는 100,000이므로,각 숫자를 왼손 또는 오른손으로 누르는 모든 경우의 수를 고려하면경우의 수가 2^100,000이 되어 완전 탐색은 불가능하다.그래서 현재 왼손/오른손의 위치에 따라 최소 비용만을 저장해 나가는 DP를 사용하면 되겠다고 생각했다. DP로 풀어야 한다는 점은..
[프로그래머스 Lv3] 합승 택시 요금 - Javascript 풀이
PS/프로그래머스_PS
https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제A, B가 택시를 이용할 때 예상 최저 택시 요금을 구하는 문제 생각문제의 노드 수 n은 200으로 작기 때문에 플로이드–워셜 알고리즘(O(n^3))을 사용해도 된다.하지만 우선순위 큐 기반 다익스트라 구현을 익히기 위해,본인은 다익스트라 알고리즘을 사용하여 문제를 해결했다. 문제풀이일반적인 다익스트라 문제는 하나의 시작점에서 각 목적지까지의 최단 거리만 구하면 충분하다.하지만 이 문제는 A와 B가 합승할 수도 있고, 중간에 갈라져 따로 갈 수도 있기..
프로그래밍 언어
■ 우선순위 큐 - Min-heap■ 코드 안녕하세요 ~오늘은 JS로 우선순위 큐 자료구조를 직접 구현해보려고 합니다. 다익스트라 알고리즘 문제를 풀기 위해 바킹독 선생님의 강의를 보았습니다.우선순위 큐를 사용해 구현하면,시간 복잡도가 O(V²+E) 에서 O(ElogV)로 줄어들어 성능이 크게 향상되더군요 ! 하지만 아쉽게도 JS는 우선순위 큐를 기본 제공하지 않습니다..그렇다면 어떻게 해야할까요?정답은 직접 구현해서 쓰면 됩니다. ㅎㅎ 바로 시작해보겠습니다. ■ 우선순위 큐 - Min-heap일반적인 큐(Queue)는 먼저 들어온 값이 먼저 나가는 FIFO 구조입니다.하지만 우선순위 큐(Priority Queue)는 들어온 순서가 아니라,우선순위가 높은 데이터(혹은 더 작은 값)를 먼저 꺼내는 자료구조..
목차 · ON THIS PAGE