1987. Number of Unique Good Subsequences
배열의 subsequence에서 leading 0는 빼고 만들 수 있는 수의 개수를 구하는 문제. DP이다. 로 두면 이다. 각각 문자를 이전의 결과 뒤에 붙인다고 생각하면 된다. 0은 leading zero 문제 때문에 여기서 더하진 않고 마지막에 0이 있는지만 체크해서 1 더하면 된다 (0 한글자인 경우는 valid 하다) lee 형님의 솔루션도 참고 …
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 161
230 229 1982. Find Array Given Subset Sums
각 부분집합의 합으로 이루어진 배열이 주어질 때 원래의 배열을 찾는 문제. 어려운 문제. 답이 안 떠올라서 코드도 깔끔하고 설명도 괜찮은 디스커션을 참고했다. 아이디어는 다음과 같다. 집합이 있을 때 여기에서 하나의 원소를 골라 이 원소를 포함하거나(including), 포함하지 않는(excluding) 멱집합을 만들 수 있다. 예를 들면 {x, y, z}…
228 1444. Number of Ways of Cutting a Pizza
사과가 올려져 있는 피자가 있을 때 사과가 1개 이상 올라가 있도록 피자를 k개로 나누는 경우의 수를 구하는 문제. 피자는 행 또는 열로 죽 자를 수 있다. 딱 보니 모듈러도 있고 자른 모양이 DP 할 수 있게 생겼다. 점화식을 간단히 만들면 여기까지는 간단한데 사과 개수가 최소 1개 이상 있어야 한다. 입력 크기가 작아서 무식하게 O(nm) 돌면서 사과 …
227 2193. Minimum Number of Moves to Make Palindrome
주어진 문자열에서 최소한의 swap으로 팰린드롬을 만드는 문제. 이런류는 처음에 딱 보면 안떠오른다. 다시 잘 생각해보니 그리디로 될 것 같다. 앞에서부터 탐색하면서 팰린드롬이 되도록 중간에 있는 문자를 뒤로 옮긴다고 보면 된다. 예를 들면 ab....a...b 이런식이라고 하면 맨 앞의 a가 매치되도록 뒤의 a를 맨 뒤로 옮기면 된다. ab ...... …
226 1307. Verbal Arithmetic Puzzle
문자로 이루어진 방정식이 있을 때 문자에 숫자를 적당히 대입해 식이 성립하는지 판단하는 문제. 처음에 간단한 완전탐색 문제인줄 알고 풀었는데 예시부터 시간 초과가 뜸... 생각보다 꽤 빡센 완전탐색 문제. 일단 전체적인 코드는 아래 디스커션 참고함. 먼저 완전 탐색을 돌릴 문자를 구해야 한다. 여기서 맵(카운터)를 쓸 수 있는데 나중에 계산을 빠르게 하기 …
225 268. Missing Number
배열에서 0부터 n까지 수 중에 빠진 숫자를 구하는 문제. 그냥 배열 원소를 다 더한 후 0-n까지의 합에서 빼주면 된다. Easy 중에서도 쉬운 Easy. 디스커션 보니 XOR로도 풀었던데 그게 더 똑똑한 방법 같다 ()
224 1416. Restore The Array
문자열과 k 가 주어진다. k까지의 수를 사용해서 문자열을 나눌 수 있는 경우의 수를 구하는 문제. 딱 보니 간단한 DP 같아서 풀었는데 메모리 초과가 많이 났다... modular 연산을 맨 마지막에 했는데 함수에서 리턴할때 넣어주니 돌아간다... 파이썬이 정수 범위가 없다지만 내부적으론 메모리를 더 쓰기 때문에 메모리가 터졌다 암튼 DP는 간단하다. D…
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으로 나누면 의외로 간단하다 일단 현재 노드에서의 최대 합을 구한다면 왼쪽 -> 현재 노드 -> 오른쪽 서브트리의 최대가 최대 합이 될 것이다. 그런데 구현할 때 위의 값 그대로 리턴하면 안되는데 경로가 중복될 수 있기 때문이다. 따라서 함수에서…