leebaek

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. 남은 작업 시간..

문제요청한 방 번호가 이미 배정되어 있을 때,지나갈 수 있는 다음 빈 방 번호를 찾아 배정해야 하는 문제 생각처음엔 '그냥 현재 방이 차 있으면 +1 탐색하면 되지 않나?'라고 생각하였다.하지만 요청이 수십만 번 들어오는 상황에서이미 배정된 방을 하나씩 순회하면서 찾는다면 최악 O(N) 이 되고,요청 개수가 N이면 O(N²) 가까운 시간이 걸려 효율성 전부 시간초과가 난다. 따라서 이 문제는특정 번호 이후의 ‘다음 빈 방의 번호’를 매우 빠르게 찾아야 한다.즉, find → parent 갱신 구조를 사용하는Union-Find(Disjoint Set) 방식으로 해결해야 한다. 문제 풀이방 번호를 포인터처럼 연결해주면서,각 방이 ‘다음 가능한 빈 방 번호(next)’ 를 가리키도록 만든다. 예를 들어 1번 ..

문제지나갈 수 있는 최소 거리의 최댓값을 구하는 문제 생각거리의 최솟값을 이분 탐색으로 조절하며가능한지 체크하는 방식으로 풀어야 한다. 단순히 양끝부터 하나씩 지우거나,정렬된 간격만 보고 제거하는 방식으로는 최적해가 보장되지 않는다. 예를 들어 아래와 같은 경우를 생각해보자.distance = 25rocks = [2, 11, 14, 17, 21]n = 2 최소 간격을 어느 정도로 잡아야 가장 좋은가?한 번 mid를 잡고, 이 mid 이상을 유지할 수 있는지를 검증하는 방식으로 풀어야 한다. 문제풀이 mid = 최소 거리라고 가정했을 때,그 mid를 만족하도록 돌을 제거했을 때제거 횟수가 n 이하인지? 이 검증을 통해 mid가 가능한 값인지 판단한다. mid 검증 방법stones를 정렬한 뒤 다음을 반복..

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, ..

https://school.programmers.co.kr/learn/courses/30/lessons/1843 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제정수와 +, - 연산자가 번갈아 들어 있는 배열이 주어졌을 때,괄호를 적절히 배치하여 만들 수 있는 계산 결과 중 최댓값을 구하는 문제 생각단순히 왼쪽부터 순차 계산하면 괄호의 효과를 전혀 반영할 수 없다.특히 − 연산은 결합법칙이 성립하지 않기 때문에중간에 어떤 값을 먼저 계산하느냐에 따라 결과가 크게 달라진다.그래서 구간별로 만들 수 있는 최댓값과 최솟값을 모두 관리하는 DP가 필요하다고 생각했다. 문제풀이테이블을 정의해보자.Max[i][j] : i..

문제정수 삼각형이 주어졌을 때꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾는 문제 생각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)이다. 이 외에도 더 효율적..