279. Perfect Squares
1부터 10000까지의 수가 주어질 때 더해서 만들 수 있는 최소 제곱수의 개수를 구하는 문제. 딱 보니 전형적인 DP 문제이다. (medium 난이도는 대부분이 DP 같다...) dp[i] = 최소 제곱수의 개수로 정의하고 j를 제곱수라고 했을 때 시간 복잡도는 i에 대해 한번, j에 대해 한번 돌게 되므로 O (n ^ 1.5) 가 된다. (제곱수는 n …
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
medium 79
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는 오른쪽 노드로 간 경로와 왼쪽 노드로 간 경로를 비교한 다음 오른쪽에서 본 것처럼 덮어 씌우는 방식으로 구현하였다. (문제 설명 그대로 오른쪽에서 보는 방식이다. 이런 문제 풀때 그닥 좋지는 않지만 직관적인 …
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 배열을 둬서 다음 값이 더 크다면 방문을 스킵하는 방식으로 동작한다.