짱아의 개발 기록장

은근히 코드는 쉬운데,,,, 나는 Greedy문제가 왜 이렇게 어려울까.....?ㅎㅎ 생각만 잘 할 수 있다면 쉽게 구현할 수 있는 Greedy 문제였다. [메인로직] 중요한 부분은! 이 문제는 앞에서부터 해결하려고 하면 복잡해지고 늪에 빠져버린다...(마치 나처럼^^) 뒤에서 부터 접근해보면 생각보다 쉽다! 현재 idx(i)와 현재 갈 수 있는 이동 거리(nums[i])를 더한 값이 반드시 도달해야하는 지점(lastPos)보다 크거나 같다면 현재 내 위치가 다시 lastPos가 되는 것이다. (=> 즉, 내 지점까지만 오면 내가 알아서 마지막 idx까지 도착할 수 있다는 것) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public: b..

이분탐색 문제이다. [메인 로직] low, high값을 잡고 mid가 target과 같을 때, 작을 때, 클 때를 나누어서 구현하면 된다. 같을 때 -> 위, 아래로 같은 값이 나오면 탐색한다. 작을 때 -> 정렬된 상태이기 때문에 low = mid+1; 클 때 - > high = mid-1; 123456789101112131415161718192021222324252627282930313233343536373839404142434445class Solution {public: vector searchRange(vector& nums, int target) { int low = 0; int high = nums.size()-1; int Start = 0, End = 0; vector ans; bool c..

MergeSort(병합정렬)에서 처음에 Array가 쪼개지는 과정만 생략된 버전?이라고 할 수 있다. [메인 로직] 즉, 정렬된 순서대로 2개의 Array를 합치는 과정을 통해 정렬된 하나의 Array를 만들고 합친 Array의 크기가 짝수라면 중간에 있는 2개의 값의 median값을 반환, 홀수라면 그냥 중간의 값을 반환하면 된다. 1234567891011121314151617181920212223242526272829303132333435class Solution {public: double findMedianSortedArrays(vector& nums1, vector& nums2) { double ans = 0; vector v; int i=0, j=0; while(i

앞서 풀었던 3Sum문제와 거의 동일하지만 조금 더 쉽다고 할 수 있다. 3Sum은 각각의 요소들을 직접 출력해야 했지만 이 문제는 그냥 가장 가까운 값의 합만 출력하면 되기 때문! [메인 로직] 풀이는 거의 동일하지만, int diff라는 변수를 INT_MAX로 초기화하고 차이(abs(sum-target))가 더 작은 값들을 발견하면 계속적으로 갱신해주면 된다. 단! diff에 abs(sum-target)값을 넣어주면 나중에 정확히 sum을 구하기 어렵기 때문에 그냥 sum-target을 저장한다. 123456789101112131415161718192021222324252627class Solution {public: int threeSumClosest(vector& nums, int target) ..

Two Pointers 문제이다. [메인 로직] i, low, high값을 잡아서 3개의 값을 더해준 sum과 0을 비교해서 작을 때, 클 때, 같을 때 조건을 통해 구현해주면 된다. 앞에서 sort를 했기 때문에 0보다 작으면 -> low++ 0보다 크면 -> high-- 0과 같으면 바로 ans에 넣어주고 혹여나, 중복되는 vector를 ans에 넣을 수 없기 때문에 ex) [-1, 0, 1] == [-1, 0, 1] low와 high를 같은 값이 아닐때 까지 while문으로 처리해주어야 한다!! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 4..

재귀와 dp를 함께 사용하는 아주 전형적인 문제 중 하나이다! 어느정도 난이도도 있으면서 감을 잡기 좋은? 문제인 것 같다. [메인 로직] dp배열을 -1의 값으로 초기화해놓고 판다가 출발하는 좌표보다 더 많은 대나무를 가지고 있는 영역의 dp값을 가져와서 +1씩 더하는 논리로 구현했다. 가지치기를 할 수 있는 부분이 바로 dp값이 -1이 아닌 경우는 이미 이전에 방문을 해서 그 영역에서 최대 몇 일을 버틸 수 있는지 메모이제이션을 해놓은 것이기 때문에 연산을 하지 않고 return dp[x][y]을 하고 바로 넘어갈 수 있다. (-> 매우 시간 절약!) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ..

1) DP+BFS BFS와 DP를 모두 활용해서 푸는 문제였다. 약간 백준에서 욕심쟁이 판다?와 비슷한 느낌? 하지만 이 문제가 훨~~씬 쉽다. [메인 로직] 일단, dp[y][x] = dp[y-1][x] + dp[y][x-1]이라는 공식은 문제를 읽어보면 쉽게 세울 수 있다. 이것을 응용해서 특정 칸에서 다음 칸으로 이동하게 되면, 다음 칸의 dp값에 현재 칸의 dp값을 무조건 더해주었다. 지나가는 길이기 때문에 경로추가! (dp[ny][nx] += dp[y][x]) 또한!!! 이미 방문한 곳은 큐에 절대로 넣어주지 않았다... 왜냐하면 수가 배가 되기 때문에....dp값은 방문했던 곳이여도 지나가는 길에 도달한 것이기 때문에 항상 더해주었지만, 이미 방문한 점은 다시 큐에 넣어주면 안된다! 1 2 3..

도저히.. 풀이가 생각이 나지 않아 다른 블로그의 아이디어만 참고해서 가닥을 잡을 수 있었다. [메인 로직] 모든 경우의 수 중에서 가장 최악의 시간이 나올 경우를 찾는다. ex) [7, 10], n = 6이면 최악의 시간은 10분이 걸리는 심사관에게 6명 모두가 입국심사를 받는 경우가 될 것이다. 그러면 최악의 시간은 총 60분이다. Start = 1, End = 60으로 하고 이분탐색을 시작하면 된다. mid = (Start+End)/2로 잡고 mid의 시간일 때 총 검사할 수 있는 인원의 수를 구한다. 30/7+30/10 = 7은 n=6의 값보다 크기 때문에 End = mid-1로 이분탐색을 쭉 진행하면 된다. 단! 조심해야하는 부분은 n값과 같은 값이 나왔다고 해서 바로 break로 빠져나오면 오..