416. Partition Equal Subset Sum
합이 같아지게 배열을 둘로 나눌 수 있는지 판단하는 문제. 처음엔 투포인터로 하다가 2, 2, 1, 1같은 케이스를 보고 dp로 풀었다. 핵심 아이디어는 합이 같아지게 나눈다는 것은 합이 배열의 전체 합의 절반이 되도록 만들 수 있는가를 판단하는 문제가 된다는 것이다. 이 아이디어로부터 배열의 각 원소를 더해보면서 합이 전체 합 / 2가 되는지 보면 된다.…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 162
181 180 878. Nth Magical Number
a 또는 b로 나누어 지는 수를 magical number라 할 때, n번째 magical number를 구하는 문제 일단 n이 크니까 탐색 범위를 줄여보자 LCM을 쓰면 a, b에 동시에 나누어지는 수를 구할 수 있고 이를 이용해 자르면 된다. 자른 다음 나머지 n에 대해 하나씩 a, b를 더해가면서 n번째 수를 구할 수 있다. 솔루션을 보면 이진 탐색으…
179 790. Domino and Tromino Tiling
2 * n 칸을 도미노와 트로미노 타일로 채울 수 있는 경우의 수를 구하는 문제. 전형적인 타일링 DP 문제. 1차원으로 되는 것 같은데 더 직관적인 2차원 배열로 풀었다. 그림으로 나타내면 이런 느낌이다. 그렇다면 점화식을 세울 수 있는데 dp[i][0] = dp[i - 2][0] + dp[i - 1][0] + dp[i - 1][1] dp[i][1] = …
178 1306. Jump Game III
배열의 인덱스 i에서 i + arr[i], i - arr[i]로 점프를 할 수 있을 때 0인 곳으로 갈 수 있는지 출력하는 문제. DFS / BFS로 돌려주면 되는데 BFS로 돌렸다.
177 563. Binary Tree Tilt
이진트리에서 모든 노드의 tilt 값의 합을 구하는 문제. tilt는 자신 왼쪽 서브트리의 합과 오른쪽 서브트리의 합의 절대값 차이다. 그냥 재귀적으로 tilt를 계속 구해주면 된다. 노드의 합 + 노드의 tilt 해서 2개를 배열로 관리해주며 돌려준다.
176 337. House Robber III
이진 트리 상에서 연속하지 않은 노드의 합 중 최댓값을 구하는 문제. 딱 보니 간단한 DP이다. 현재 노드에서 훔치면 다음 자식 노드에서는 훔치면 안되고 현재 노드에서 훔치지 않았으면 자식 노드에서는 훔치거나 훔치지 않거나 2가지를 탐색하면 된다. 연속되지 않아야 하므로 이전의 상태가 필요하고 이도 같이 메모이제이션 해주면 된다. 파이썬은 간단하게 lru_…
175 174 85. Maximal Rectangle
2차원 배열에서 1로만 이루어진 가장 큰 직사각형의 넓이를 구하는 문제. 정사각형의 경우 간단한 DP로 가능한데 직사각형이므로 DP 풀이는 약간 복잡하다. 예전에 로이형 유튜브에서 보긴 해서 그 풀이로 가보기로 하자. 이전 문제인 84. Largest Rectangle in Histogram 문제를 응용하면 된다. 각 칸을 히스토그램의 칸이라 생각하고 아래…
173 224. Basic Calculator
괄호, +, - 가 있는 간단한 계산기를 만드는 문제. 스택으로 하면 될 것 같다. 기본 기호 (+, -) 가 나오면 스택에 집어넣고, 괄호가 나오면 새로 스택을 쌓아주고 괄호가 닫히면 스택에서 하나를 더 빼주는 식으로 구현했다. 약간 코드가 지저분하지만 기본 흐름은 스택을 쓰는 것이다.
172 149. Max Points on a Line
같은 직선에 있는 점의 최대 개수를 구하는 문제. 인풋 범위가 300개로 매우 작아서 그냥 다 돌려보면 된다. 심지어 x, y 범위도 작아서 (-10000 ~ 10000) 단순 기울기로만 카운트를 해주면 된다. 단, x, y 범위가 크다면 부동소수점 오차로 인해 gcd를 이용해서 기울기가 같은 점을 더해줘야 한다.