짱아의 개발 기록장

Stack을 사용하여 유효한 여부를 판단하기만 하면 된다. [메인 로직] 닫는 괄호가 나오면, Stack의 top에 같은 종류의 여는 괄호가 나오지 않으면 invalid하다. 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 42 43 44 class Solution { public: stack S; bool check = true; bool isValid(string s) { for(int i=0; i

전형적인 조합 문제!!! 기본적인 조합의 코드를 익히지 좋은 문제이다. 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 class Solution { public: vector ans; int N; void dfs(int open, int close, string s){ if(open==N){ for(int i=0; i0){ dfs(open, close-1, s+')'); } } vector generateParenthesis(int n) { N = n; dfs(0, 0, ""); return ans; } }; Colored by Color Scripter cs

전형적인 순열을 사용하는 문제이지만, 중요한 점은 중복된 숫자가 있는 것이다! 따라서, 중복되는 결과를 만들어내지 않기 위한 조치가 필요하다. 1. 순열을 만들어내고 마지막에 ans에 있는 벡터들을 탐색하며 같은 배열이 없는 지 확인 시간 매우 많이 소요....(당연한 것,,) faster than 5.08%인가??ㅋㅋㅋ 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 42 43 44 45 46 47 48 49 class Solution { public: int n; vector v; int visited[10] = {0, }; vector ans; ..

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