짱아의 개발 기록장

모기업 코드페스티벌에 참여했는데,,,, 유일하게 풀지 못했던 문제;;;; ㅂㄷㅂㄷ 팰린드롬인지 아닌지를 판별하는 문제는 쉽게 풀었었는데 만드는 문제는 처음 접해서 당황했다.... 끝나고 백준을 찾아보니 역시나 똑같은 문제가 있었다 ㅋㅋㅋ 그래서 다른 분의 코드를 참조해서 다시 풀어보았다! [메인 로직] 해결방법은 인덱스가 0인 지점부터 차례대로 조사하며 팰린드롬이 되는 최소한의 시작 위치를 찾는 것이다. 어차피 중간에 팰린드롬이 생기는 것은 아무 의미가 없기 때문에특정 인덱스부터 문자열의 맨 마지막까지 팰린드롬이 되는 부분 문자열을 찾으면, (특정인덱스+원래 문자열의 크기)가 최소 팰린드롬의 길이가 되는 것이다. aabcaa인 경우에는 맨 뒤의 aa만 팰린드롬이 가능하다 따라서 aa는 그대로 두고 나머지..

사실 문제 유형은 DP(Dynamic Programming)으로 분류되어 있었지만, 그냥 구현? 문제로 풀었다. 아이디어는 문제의 Discuss 탭에 있는 외국인 분의 코드를 보고 얻었다...ㅎ [메인 로직] 최대 합을 저장하는 변수 ans, 매 번 큰 값을 비교하여 저장하는 변수 sum을 두고 탐색하는 식으로 구현했다. 예를 들어, [-1, 2, 3]의 배열이 있는 경우 idx = 1 => -1+2 2+3 > 3 이기 때문에 계속 더해주는 것이 이득이다. 따라서, sum = 5가 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution..

앞서 풀었던 Combination Sum 과 매우 유사한 문제이다. 하지만, 이 문제는 중복허용이 되지 않는 다는 것! [메인 로직] ex) 10, 1, 2, 7, 6, 1, 5 / target = 8이라면 먼저 오름차순 정렬해준다. 1, 1, 2, 5, 6, 7, 10 으로 정렬된 상태에서 idx = 0부터 target = 8인 조합을 찾아나가면 [1, 2, 5]를 완성할 수 있다. 하지만 idx = 1도 '1'이기 때문에 중복된 결과를 만들게 된다. 따라서, 중복된 값을 만들지 않기 위해!! for문 탐색할 때, if(i>start && candidates[i]==candidates[i-1])이라면 continue를 해서 중복을 막았다. 12345678910111213141516171819202122..

backtracking문제를 너무 오랜만에 풀어서 약간 푸는 데 생각보다? 오래걸렸다. [문제 설명] Input: candidates = [2,3,6,7], target = 7 다음과 같이 배열이 주어지면 그 안에서 합이 target이 될 수 있는 조합을 찾는 문제이다. 위와 같은 input이라면, Output: [[2,2,3],[7]] 이러한 결과가 나올 수 있다. 주의할 점은!! [2, 2, 3] = [2, 3, 2] = [3, 2, 2] 모두 같은 값으로 취급한다는 것! [메인 로직] dfs함수의 인자값으로 지금까지의 값의 합 / 지금까지의 값들을 넣는 벡터 / candidates벡터 / target값 / 다음에 탐색을 시작할 idx값을 넣어주었다. 만약, 다음에 탐색을 시작할 idx값을 넣어주지 ..

마찬가지로, 트리를 기반으로 한 BFS문제이다. [메인 로직] queue를 pair형태로 다음과 같이 자료구조를 짰다. => queue q; second 위치에 dir변수를 두어서 dir==-1일 경우 거꾸로 저장하도록 했다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647class Solution {public: vector zigzagLevelOrder(TreeNode* root) { vector ans; if(root==NULL){ return ans; } vector v; queue q; q.push(make_pair(root, 1)); while(!q.empty()){ int size = q..

BFS를 통해서 간단하게 해결할 수 있는 문제이다. [메인 로직] 간단히 말해서, 같은 level에 있는 값들을 하나의 벡터에 넣어주고 그것을 다시 최종 ans벡터에 넣어주는??? 그런 로직이다. 코드를 보면 더 잘 이해가 될 것이라 생각한다. 1234567891011121314151617181920212223242526272829303132333435class Solution {public: vector levelOrder(TreeNode* root) { vector ans; if(root==NULL){ return ans; } vector v; queue q; q.push(root); while(!q.empty()){ int size = q.size(); for(int i=0; ival); q.pop..

난이도는 easy였지만...생각보다? 이런 문제류를 처음 풀어본 사람이면 충분히 어려웠을 만한 문제였다. 분류로는 BFS로 되어 있었지만,,, 생각보다 간단한 재귀로 풀 수 있다. [메인 로직] 1. 주어진 root 트리를 각각의 다른 트리라고 생각하고 2개의 트리를 비교하는 형식으로 진행한다. 2. 즉, isMirror(root, root) 함수를 돌아서 tree1->left와 tree2->right이 같은지, tree1->right과 tree2->left가 같은지 확인하면 된다! (Symmetric인지 확인한는 것이기 때문에 => 밑의 사진 참고) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public: bool isMirror(TreeNode* tree..

아주 간단하게 재귀 방식을 통해서 풀 수 있는 문제였다. [메인 로직] 기본적으로 재귀를 root->left->right 순서로 PreorderTraversal을 진행했다. 1. 각 트리의 노드가 둘 다 NULL일 경우, true를 반환한다.(루트의 경우 NULL이면 어차피 left, right으로 뻗어가는 가지가 아니기 때문에 같은 형태임을 알 수 있다.) 2. 각 트리의 노드가 둘 중 하나만 NULL이라면, 같은 구조의 트리가 아니므로 false를 반환한다. 3. 각 트리의 노드의 값이 다르다면, 노드의 값이 다르므로 false를 반환한다. 4. 이후, 왼쪽 서브트리, 오른쪽 서브트리로 순환한다. 1 2 3 4 5 6 7 8 9 10 11 class Solution { public: bool isSa..