1416. Restore The Array
문자열과 k 가 주어진다. k까지의 수를 사용해서 문자열을 나눌 수 있는 경우의 수를 구하는 문제. 딱 보니 간단한 DP 같아서 풀었는데 메모리 초과가 많이 났다... modular 연산을 맨 마지막에 했는데 함수에서 리턴할때 넣어주니 돌아간다... 파이썬이 정수 범위가 없다지만 내부적으론 메모리를 더 쓰기 때문에 메모리가 터졌다 암튼 DP는 간단하다. D…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 165
224 223 1671. Minimum Number of Removals to Make Mountain Array
배열에서 최소한의 원소를 제거하여 mountain-array 가 하도록 하는 문제. mountain-array는 순서대로 원소가 커졌다가 작아지는 배열이다. 처음엔 LIS 안 쓰고 무식하게 DP를 돌렸는데 Wrong Answer 몇개 후 MLE 까지 떴다... 아래 discuss 느낌으로 구현했는데 top-down이라 메모리를 많이 먹은 듯.. ! 결국 L…
222 410. Split Array Largest Sum
배열을 m개의 부분 배열로 나눌 때 각각 부분 배열의 합의 최대가 최소가 되도록 하는 문제. 처음에 딱 보면 뭔가 어려워 보이는데 잘 생각해보면 이분 탐색으로 꽤 간단히 풀린다. 또는 파라메트릭 서치라고 하는데.. 그냥 이분 탐색이긴 하다. 먼저 이분 탐색으로 타겟을 정한다. 그런 다음 부분 배열의 합이 타겟 값을 넘지 않도록 하면서 배열을 나눠볼 수 있다…
221 124. Binary Tree Maximum Path Sum
이진 트리가 있을 때 트리 상의 경로 중에 합이 가장 큰 경로를 구하는 문제. 어려워 보이지만 subproblem으로 나누면 의외로 간단하다 일단 현재 노드에서의 최대 합을 구한다면 왼쪽 -> 현재 노드 -> 오른쪽 서브트리의 최대가 최대 합이 될 것이다. 그런데 구현할 때 위의 값 그대로 리턴하면 안되는데 경로가 중복될 수 있기 때문이다. 따라서 함수에서…
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차원…