124. Binary Tree Maximum Path Sum
이진 트리가 있을 때 트리 상의 경로 중에 합이 가장 큰 경로를 구하는 문제. 어려워 보이지만 subproblem으로 나누면 의외로 간단하다 일단 현재 노드에서의 최대 합을 구한다면 왼쪽 -> 현재 노드 -> 오른쪽 서브트리의 최대가 최대 합이 될 것이다. 그런데 구현할 때 위의 값 그대로 리턴하면 안되는데 경로가 중복될 수 있기 때문이다. 따라서 함수에서…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 162
221 220 399. Evaluate Division
방정식과 결과 값이 주어질 때 방정식을 받아서 값을 계산하는 문제. 체인 형태로 연결되어 있는 것이 그래프가 생각났다. 위 식이 핵심인데, a - b - c 를 죽 이었을 때 a / c 의 답을 얻을 수 있다. a -> b 의 간선은 a / b 의 값으로, b -> a 의 간선은 1 / (a / b) 로 값을 세팅한 후 쿼리가 오면 경로대로 곱해주면 답이다…
219 785. Is Graph Bipartite?
그래프가 이분 그래프인지 판단하는 문제. 먼저 이분 그래프의 정의를 보자. A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node i…
218 1631. Path With Minimum Effort
경로상의 좌표의 절댓값 차이가 최소가 되도록 경로를 찾는 문제. 딱 보고 pq로 BFS 돌렸는데 시간 초과. 아마 같은 좌표가 여러 번 들어가서 큐가 잔뜩 쌓이지 않았나 싶다. 그래서 다익스트라로 변경. 다익스트라가 pq 기반 BFS와 큰 차이는 없는데 distances 배열을 둬서 다음 값이 더 크다면 방문을 스킵하는 방식으로 동작한다.
217 1202. Smallest String With Swaps
문자열과 스왑이 가능한 인덱스가 주어질 때 스왑을 해서 문자열을 사전 순으로 최소가 되게 만드는 문제. 조금만 생각해보면 Disjoint-set 으로 풀 수 있다. 스왑을 하는 인덱스가 연결이 되어 있다면 얼마든지 스왑을 통해 연결된 인덱스의 최소로 바꿀 수 있다는 점을 이용한 것이다. 예를 들어 [0, 1], [1, 2]가 스왑이 가능하면 여러 번 스왑으…
216 284. Peeking Iterator
일반 이터레이터를 사용해서 peek 연산이 가능한 이터레이터를 만드는 문제. 임시 변수 하나를 두면 쉽게 풀린다. peek 할 경우 peeked 변수에 값을 집어넣고, 이미 변수에 값이 있다면 그대로 리턴하면 된다. next 할 때는 peeked 변수에 값이 있으면 그대로 리턴하면 되고 값이 없으면 next를 호출해서 가져오면 된다. hasnext도 비슷하…
215 2147. Number of Ways to Divide a Long Corridor
의자와 식물이 있을 때 의자를 2개씩 묶을 수 있는 경우의 수를 구하는 문제. 딱 보니 DP 냄새가 나서 탑 다운으로 풀었는데 ... 메모리 초과가 난다. 바텀업으로 고치니 통과! 또, 2차원 DP를 1차원으로 줄이니 더 빨라지고 메모리도 적게 먹는다. 간단하게 설명하자면 로 정의하고 점화식을 만들 수 있다. 그리고 for문을 돌면서 덮어 씌워지므로 1차원…
214 1396. Design Underground System
checkin, checkout을 통해 두 도시간의 평균 시간을 구하는 문제 그냥 간단하다. checkin 할 때는 map으로 id가 들어온 시각을 저장한 후 checkout 할때 해당 구간에 대해 걸린 시간과 카운트를 누적해서 더해주면 평균을 쉽게 구할 수 있다.
213 535. Encode and Decode TinyURL
tinyurl 같은 것을 구현하는 문제. ... medium 치고 너무 쉬운데... 그냥 daily 라서 풀어보았다. 단순히 입력받는 것을 리턴해도 통과가 된다... 하지만 아무 의미가 없으니 간단하게 짜보자. 간단하게 하는 방법으로 id 카운터 값을 놓고 1씩 증가하면서 shorturl을 생성할 수 있다. map으로 관리해주면 매우 간단하게 가능하다.
212 1735. Count Ways to Make Array With Product
n, k 가 입력으로 주어질 때 n개의 수의 곱으로 k를 만들 수 있는 방법의 수를 구하는 문제. 처음에 단순 DP로 하니 시간 초과가 난다... O(NKD) (F: 약수 개수) dicussion을 보니 Stars and bars 개념을 이용해서 풀 수 있다. Stars and bars를 간단하게 설명하면 별을 바로 나눌 수 있는 경우의 수를 구하는 문제이…