765. Couples Holding Hands
커플이 2n개의 좌석을 서로 붙어 있게 앉기 위한 최소의 스왑 횟수를 구하는 문제. 그리디하게 생각하면 의외로 쉽게 풀린다. 일단 앞에서 순차로 탐색한다고 해보면 짝이 안 맞는 사람이 있을 경우 뒤쪽에서 한 명이랑 스왑을 해줘야 한다. 그리고 이렇게 스왑을 한 경우 이 커플은 더 이상 스왑을 해줄 필요가 없어진다. 이렇게 순차적으로 커플이 되도록 스왑을 쭉…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 165
184 183 546. Remove Boxes
계속해서 연속된 수를 제거할 수 있고 제거한 개수의 제곱의 점수를 얻을 수 있다. 최대로 얻는 점수를 구하는 문제. 하드 중에서도 하드한 문제. 다른 사람의 풀이를 보고 풀긴 하였다. 일단 결론부터 말하면 3차원 DP 문제. 연속된 개수가 중요하므로 3차원으로 해야한다. dp[i][j][k] = i 부터 j 까지의 최대 점수, k는 i와 같은 지금까지의 연…
182 1446. Consecutive Characters
연속된 문자 중 가장 긴 길이를 구하는 문제. 그냥 돌면서 구하면 된다... 이걸 글로 써야 하나 고민했지만 푼 문제니까 그냥 올리기로 결정.
181 416. Partition Equal Subset Sum
합이 같아지게 배열을 둘로 나눌 수 있는지 판단하는 문제. 처음엔 투포인터로 하다가 2, 2, 1, 1같은 케이스를 보고 dp로 풀었다. 핵심 아이디어는 합이 같아지게 나눈다는 것은 합이 배열의 전체 합의 절반이 되도록 만들 수 있는가를 판단하는 문제가 된다는 것이다. 이 아이디어로부터 배열의 각 원소를 더해보면서 합이 전체 합 / 2가 되는지 보면 된다.…
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