Treasure House

접근 방법 (트리) 전체 노드가 N개인데 간선의 숫자는 N-1개만 있기 때문에 사이클이 생길 수 없다. 따라서 등대 간의 연결은 트리로 표현될 수 있고, DFS BFS 등의 트리 순회 방법을 사용할 수 있다. (그리디) 하나의 점을 루트로 삼고, DFS를 실시한다고 가정하자. 리프 노드들을 자식으로 두고 있는 노드가 있다면 해당 노드는 무조건 켜져야 하기 때문에 리프 노드에 도착하면 상위 노드가 무조건 켜져있어야 한다는 시그널을 날려야하기 때문에 1을 반환한다. 리프부터 루트까지 올라가면서 각 노드에서 자식 노드가 하나라도 켜져있지 않다면 무조건 켜줘야하기 때문에 1을 반환한다. 모든 자식 노드가 켜져있다면 효율을 위해서 해당 노드를 꺼야하기 때문에 꺼져있다는 시그널인 0을 반환한다. 코드 import ..

접근 방법 (Subproblem) 문제에서 노드들이 트리 형태로 주어진 다는 것이 주어졌기 때문에 아무 노드를 선택한 뒤 그 노드를 루트로 삼고 그대로 depth가 1인 서브 트리까지 순회한다고 가정하자 (메타포적으로 노드를 하나 잡고 위로 쭉 땡긴다고 생각). 이 서브 트리에서 문제의 부분 정답은 자식 노드들의 모든 값과 부모 노드의 값을 더한 값을 N이라고 할 때, N이 0이면 자식 노드들의 모든 값의 절대값을 모두 더한 것이고 아니라면 -1이다. 왜냐하면 문제에서 나온 연산을 수행하려면 결국 두 개의 노드가 인접해야 하는데 결국 자식 노드끼리 값을 공유하려면 부모 노드를 통해야 하기 때문에 옮길 때 2만큼의 비용이 발생하며, 만약 부모의 값과 연산을 한다면 1만큼의 비용이 발생하기 때문이다. 2 만..

접근 방법 (패턴) n개의 빌딩을 높은 순서대로 문제에 나온 룰을 지키면서 배치를 해본다고 가정을 한다. 첫 빌딩은 연달아서 두개를 놓는 방법 외에는 다른 수가 없기 때문에 경우의 수는 1이 될 수 밖에 없다. 다음 빌딩을 놓을 때는 우리 두 가지의 가능성을 생각할 수 있다. 첫 번째는 원래 있는 배치도에서 제일 앞단에 배치를 해서 은비가 보는 빌딩의 가짓수를 1 만큼 늘리는 것이고, 아니라면 맨 앞에 두지 않도록 배치해서 가짓수를 그대로 두는 방식이다. 다시 다른 빌딩을 놓을 때도 다시 두 가지 방식을 생각할 수 있다. 맨 앞에 놓거나(= 가짓수 늘리기), 아니면 그렇지 않게 배치할 수 있다. 마지막 빌딩까지 반복된다. (DP) 그렇다면 위처럼 배치하면서 k번째 단계에서 count만큼 보이도록 배치하려..

접근 방법 n만큼 그리디하게 works에서 1씩 빼주면 최소 야근 지수를 구할 수 있다. 먼저 들어온 works 배열을 힙 구조로 만들어준 뒤, 가장 큰 works 원소부터 1씩 빼준다. n 만큼 소모하면 0 이하의 값을 제외하고 제곱해서 answer에 추가한다. 코드 from heapq import heapify, heappush, heappop def solution(n, works): repl = [-work for work in works] heapify(repl) for i in range(n): heappush(repl, heappop(repl) + 1) answer = 0 for num in repl: if num > 0: continue answer += num ** 2 return ans..

접근 방법 target 보드 위에 beginning을 덮는다고 생각해보면 (XOR 연산), 어느 돌을 뒤집어야할지 표시하는 것과 비슷한 효과를 보인다. 같은 행 및 열을 두번 뒤집으면 안뒤집은 것과 마찬가지다. 열과 행은 한번씩만 뒤집으면 된다. 각 행을 기준으로 순회를 하며, 그 행과 똑같은 행이면 넘어가고 뒤집은 것과 비슷한 행은 뒤집어주고 뒤집은 갯수를 1을 추가한다. 두 조건 모두 만족하지 못한다면 정답을 찾을 수 없는 경우이기 때문에 바로 -1을 반환해준다. 여기서 해당 행에 1이 있다면 다시 뒤집어야 한다는 것이기 때문에 행을 뒤집은 것 + 행에 있는 1의 갯수를 기준으로 최소 값을 반환하면 정답이다. 코드 def solution(beginning, target): xor = [[0] * le..

접근 방법 (다익스트라) 한 노드에서 특정 노드까지 경로 중 최적의 조건을 만족하는 값을 구하는 문제이기 때문에 다익스트라를 적용할 수 있다 (최적화) 경로의 조건 중 중복 조건 혹은 최소 조건은 없기 때문에, 모든 게이트 노드에서 각 노드에 도달하기 까지의 최대 쉬는 시간은 공유된 것처럼 봐도 무방하다. 그렇기 때문에 모든 게이트 노드에서 동시에 시작하면 연산 시간을 아낄 수 있다. (최적의 조건) 모든 노드의 최대 휴식 시간을 기억하고 있는 weights 배열을 두고, 모든 게이트 노드를 우선순위큐에 넣는다. 큐에서 뺄 때마다 a) 현재까지 가장 긴 휴식시간과 b) 종착지 노드가 나올 텐데, 이 때 a의 값이 weights 배열의 종착지 노드 위치의 값보다 크면 이미 최적 조건 달성을 못하기 때문에 ..

접근 방법 (누적합) Naive하게 i가 0 부터 끝까지 모든 범위의 sum을 구한다면 시간 초과가 날 것은 명백하다. 따라서 logs의 입력을 받을 때, 시청 시작시간과 종료시간만 각각 += 1과 -=1로 마크 해놓은 다음 모든 전처리가 끝나면 마크 해놓은 곳을 0 부터 play_time까지 오른쪽으로 땡겨준다. 그 후엔, 매번 sum을 안구해도 되도록 각 index에 대한 누적합을 미리 계산 해놓는다. (탐색) 우리가 알고 싶은 것은 최대 누적 시간이기 때문에 adv_time만큼의 Sliding Window를 두고 0부터 되는 데까지 이동하면된다. 그 과정에서 특정 구간의 최대 누적 시간은 미리 구해놓은 누적합 배열의 adv_time - i 값에서 i를 뺀 값일 것이다. (구조화) 시간의 String..

접근 방법 이 문제는 총 세 가지의 소문제로 나눠서 생각하면 좋다 입력받은 십진수 문자열을 이진수 문자열로 변환 포화이진트리를 구현하기 위해 왼쪽에 더미 노드를 패딩(LPAD) 처리 마지막으로 문제 조건을 만족 가능한 포화이진트리인지 판단 십진수를 이진수로 변환할 때 쓰는 보편적인 방법으로 2씩 나누면서 나머지를 문자열로 더해주고 그 결과 값을 뒤집어주는 방식을 사용할 수 있지만... 그냥 시간을 아끼기 위해서 내장 함수인 Long.toBinaryString()을 사용해서 실제 이진 문자열 길이 actualStringLength 값을 구한다. 포화이진트리(CBT)의 특성 중 하나는 깊이 N인 CBT의 노드의 갯수는 N ** 2 - 1라는 점이다. 이 부분은 직접 공책에 이진 트리를 그려보면 쉽게 알 수 ..