알고리즘 오답노트 (~24.6.28)
LeetCode - 3164. Find the Number of Good Pairs II
숫자로 이뤄진 두 배열 nums1, nums2 와 하나의 숫자 k 주어질 때, "nums2[j] * k 로 나눠떨어지는 nums1[i]" 가 성립하는 i, j 쌍의 개수를 찾는 문제.
nums1 을 순회하고 그 속에서 또 nums2 를 순회하면서 (이중for문), 캐싱까지 활용해가며 답을 찾았지만 시간 초과로 실패했다.
알고보니 nums1 만 순회하면서 해당 숫자들을 나눌 수 있는 값들을 찾아서 저장해두고, nums2 를 돌면서 nums2[j] * k 가 저장해둔 값에 있는지만 찾으면 되는 문제였다. 음, 발상이 거기까지 가지 못했다.
풀이 참고
BOJ - 17070. 파이프 옮기기 1
처음에는 큐를 사용해 풀려고 했으나, 시간초과. 이후에 n*2 DP 를 사용해 풀려고 했으나, 풀리지 않음. 풀이를 찾고 보니 n*n*3 DP 로 풀어야 했다. DP 의 길은 멀고도 험하구나.
풀이 참고
LeetCode - 3169. Count Days Without Meetings
미팅 일정이 일단위로 주어질 때, 미팅이 없는 날짜를 찾는 문제. 단순하게도 배열을 만들어서 미팅이 있는 날짜들을 마킹하면 되는 거 아냐? 라고 생각했다가 큰코 다친 문제다.
푸는 방법은 미팅 일정을 시작일 기준으로 정렬한 뒤 순회하면서 미팅 일정을 병합하고, 동시에 빈 날짜를 카운팅하는 것. 이러면 모든 일정을 순회하면서 마킹할 필요가 없이 바로 계산이 가능하다.
풀이 참고
LeetCode - 3180. Maximum Total Reward Using Operations I
리워드 배열에서 원하는 리워드 값을 취할 수 있다. 단 두 번째부터는 현재 내가 취한 리워드의 합보다 큰 리워드만 취할 수 있다. 이런 조건에서, 특정한 리워드 배열이 주어졌을 대 취할 수 있는 가장 큰 리워드 합은 몇인가?
처음에는 우선순위 큐로 되지 않을까 싶어서 시도해봤는데, 우선순위 큐로는 커버되지 않는 케이스가 존재했다.
찾아보니 방법은 두 가지가 있었다.
하나는 브루트포스, 리워드 배열에서 중복되지 않는 값만 뽑아낸 뒤 모든 가능한 합의 조합을 찾아내서, 가장 큰 값을 찾으면 된다. 리워드 배열이 최대 2000개밖에 되지 않아 가능한 것 같다.
다른 하나는 DP, n*4000 DP 로 풀 수 있다. 여기서 뜬금없이 나온 것 같은 4000 은 리워드 값의 최대 값이 2000이기 때문에 추론할 수 있는, 가능한 리워드 총합의 최대값이다 (X + (X-1)). ...이건 혼자서는 절대 못풀었을 것 같다.
풀이 참고
- Sorting and brute force - easy to understand
- Pick or not pick DP
- easy understanding memo solution pick not pick method
BOJ - 1275. 커피숍2
세그먼트 트리 재활을 위해 풀었다. 오랜만에 풀어서 그런가 잘못 넣은 조건 하나 때문에 한참을 고생했다.
풀이 참고
BOJ - 10999. 구간 합 구하기 2
세그먼트 트리를 조금 응용하면 되겠지 하고 풀었다가 큰 코 다쳤다. 레이지lazy 세그먼트 트리를 연습하기 좋은 문제다.
풀이 참고
BOJ - 13334. 철로
선형적인 문제일 것이라고는 예상했지만 각 쌍의 큰 수에 집중해야 한다는 걸 놓쳤고, 자바스크립트는 메모리 초과 에러가 계속 나고... 결국 파이썬으로 풀었다.