짱아의 개발 기록장

backtracking을 연습하기에 매우 좋은, 지저분하지 않고 간단 명료한 문제! ()와 같은 열고 닫는 괄호를 통해 굉장히 많은 문제가 출제될 수 있는데, 대표적인 것이 이 문제와 같이 열고닫는 괄호(올바른 괄호)의 조합을 찾는 문제, 올바른 괄호인지 아닌 지의 여부를 묻는 문제, 괄호의 쌍을 묻는 문제 등등.... [메인 로직] open, close와 같은 변수로 현재 문자열에 몇개의 여는 괄호와 닫는 괄호가 있는 지 표시해주었고 open

정말 Greedy에 약하다......ㅜ 정답 코드를 보면 아~~~맞네 이런 리액션이 나올 정도로 코드는 간결하고 간단하다. 간단하게, 발생할 수 있는 예시는 다음과 같다. 1. 지속적으로 증가하는 구간이 없고 올라갔다 내려갔다 들쑥날쑥한 그래프( [7, 1, 4, 3, 5, 2, 4] ) 이 경우는, 위에 그림에서 표시한 A+B>C이다. 따라서, 지속적으로 증가하는 부분이 없는 경우에는 1->5로 바로 점프를 하는 것보다는 각각 1->4, 3->5로 주식을 사고 파는 것이 훨씬 이득이다. 2. 지속적으로 증가하는 구간이 있는 그래프( [1, 7, 2, 3, 5, 7, 2] ) 위 그림에서는 A+B+C = D이다. 따라서, 지속적으로 증가하는 부분의 경우에는 2->7로 바로 점프를 하는 것이 2->3, 3..

은근히 코드는 쉬운데,,,, 나는 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

기존 코드 건드리지 않고 새 기능 추가하기 (실습을 통해 진행했다.) 1. 첫 번째 실습 CashPerf가 프록시의 역할을 한다. + Store라는 클라이언트 side에서 CashPerf를 사용했기 때문에 성능 측정이 가능하다. (만약, Store에서 Store strore = new Store(Cash())를 했다면.... 성능측정은 불가능하다.) 새로운 코드인 CashPer.java를 추가하긴 했지만 기존의 코드를 건들이지 않고 새로운 기능(성능측정)을 추가했다. 이런 일들이 Spring AOP에서는 대부분 자동으로 이루어진다. 굉장히 복잡한 내부적인 로직으로 돌아간다. 따라서, Spring에서는 우리가 비즈니스 로직 개발에만 집중을 할 수 있게끔 이러한 복잡한 작업들을 대신 해준다.

앞서 풀었던 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..