279. Perfect Squares
1부터 10000까지의 수가 주어질 때 더해서 만들 수 있는 최소 제곱수의 개수를 구하는 문제. 딱 보니 전형적인 DP 문제이다. (medium 난이도는 대부분이 DP 같다...) dp[i] = 최소 제곱수의 개수로 정의하고 j를 제곱수라고 했을 때 시간 복잡도는 i에 대해 한번, j에 대해 한번 돌게 되므로 O (n ^ 1.5) 가 된다. (제곱수는 n …
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 165
244 243 983. Minimum Cost For Tickets
1일권, 7일권, 30일권 티켓 가격이 주어지고 각 티켓을 사용해 주어진 날짜를 모두 여행할 수 있는 최소한의 비용을 구하는 문제. 간단한 DP 문제이다. dp[i] = i일부터 여행할 수 있는 최소 비용으로 두면 현재 날짜부터 1일권, 7일권, 30일권을 썼을 때 비용 중 가장 작은 것으로 계속 더해 나가면 된다.
242 799. Champagne Tower
샴페인 잔이 피라미드 형식으로 쌓여있고 맨 위의 잔에 샴페인을 부었을 때 특정 행, 열에 샴페인이 얼마나 차있는지 출력하는 문제. 처음에 테스트로 직접 한번씩 부었는데 당연히 시간초과가 난다. 수학적으로 가능한가 싶었는데 그냥 돌려주면 된다. 단 한번씩 붓는게 아니고 처음에 전부 부어주었다고 가정하면 된다. 넘치는 양을 다음 잔에 부어주면서 죽 돌려주면 된…
241 139. Word Break
스트링과 단어 리스트가 주어질 때 단어들을 이어붙여 스트링을 만들수 있는지 판단하는 문제. 간단한 DP 문제이다. 현재까지 인덱스를 dp로 저장해두고 단어를 이어붙일 수 있다면 계속 이어붙여주면 된다. 점화식을 세우자면 이런 느낌이 된다. s의 길이를 N, 단어의 개수 M, 각 단어 길이를 W라 하면 시간복잡도는 O(N M W)가 된다. 단어를 비교할 때 …
240 2841. Maximum Sum of Almost Unique Subarray
배열과 m, k가 주어질 때 배열의 subarray 중에서 길이가 k이고 중복되지 않는 수가 최소 m개인 개수를 구하는 문제. 딱 보니 간단한 슬라이딩 윈도우 문제이다. 배열의 처음부터 끝까지 죽 돌면서 길이가 k이고 중복되지 않는 수가 m개가 되도록 체크해주면 된다. 중복되는 수 체크는 map (dict)로 간단하게 할 수 있고 right는 개수 증가, …
239 97. Interleaving String
s1과 s2 스트링을 자른 다음 교대로 이어 붙여서 s3 스트링을 만들수 있는지 판단하는 문제. 예시는: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 전형적인 DP 문제이다. 현재까지 고른 s1의 인덱스, s2의 인덱스, 마지막으로 고른 스트링 (s1 / s2) 해서 죽 돌려보았다. DP[i][j][k] = i: s1 …
238 199. Binary Tree Right Side View
이진 트리가 주어질 때 오른쪽에서 볼 때 보이는 노드들을 출력하는 문제. DFS로 조금 지저분하게 풀었는데 BFS가 더 깔끔할거 같긴 하다. DFS는 오른쪽 노드로 간 경로와 왼쪽 노드로 간 경로를 비교한 다음 오른쪽에서 본 것처럼 덮어 씌우는 방식으로 구현하였다. (문제 설명 그대로 오른쪽에서 보는 방식이다. 이런 문제 풀때 그닥 좋지는 않지만 직관적인 …
237 2360. Longest Cycle in a Graph
그래프가 주어질 때 가장 길이가 긴 사이클의 길이를 구하는 문제. 문제 자체는 쉽다. 사이클 중에 가장 긴 길이를 구하면 되는데 직접 구현은 살짝 복잡하긴 하다. 먼저 노드에서 나가는 엣지는 최대 1개이므로 그냥 바로 다음 노드로 건너가면 된다. 다음 노드로 갈 때 level 변수에 1씩 증가하다가 이미 방문한 노드가 있다면 현재 노드와 방문했던 노드의 l…
236 2321. Maximum Score Of Spliced Array
배열 2개가 주어지고, 배열의 일부 구간을 다른 배열과 swap 가능할 때 두 배열의 합 중 최대가 가장 큰 값을 구하는 문제. 딱 보니 DP라서 처음에는 top-down으로 풀었다. 해당 최댓값은 배열 하나에만 계산되므로 배열 2개를 서로 바꿔서 한번 더 돌려주면 된다. 정답이 나오긴 하는데 2792 ms로 하위 5%의 성능.. 결국 bottom-up 으…
235 2172. Maximum AND Sum of Array
슬롯이 있고 숫자를 한 슬롯에 최대 2개까지 집어넣을 수 있다. 이때 슬롯의 번호와 숫자를 AND 연산한 합 중에 최대를 구하는 문제. 비트마스크 DP 이다. 처음에는 슬롯에 2개씩 들어가므로 슬롯의 크기를 2배로 해서 돌려봤는데 시간 초과... 결국 비트마스크를 2개 써서 통과. dp[i][slot1][slot2] = slot1, slot2에 숫자가 있을…