궁금한게 많은 개발자 노트

해당 문제는 Recursion을 사용하여 재귀적으로 같은 문제를 해결할 수 있는지를 판단하는 문제로 보였습니다. Linked List가 주어졌을 때, 서로 인접한 두개의 노드의 순서가 변경된 결과를 반환하는 문제입니다. ex) 1 -> 2 -> 3 -> 4 2 -> 1 -> 4 -> 3 작은 단위로 쪼개보면 인접한 두개의 노드가 서로 자리를 바꾸는 연산이 반복해서 일어나므로 재귀적으로 해결한다면 다음과 같은 코드로 풀이할 수 있습니다. 첫 번째 노드가 current, 두 번째 노드가 next라고 한다면 결과적으로 next->next는 current를 가리키고, current->next는 다음 두 노드의 변경된 첫 번째 노드를 가리켜야 합니다. 다음 두 노드의 결과는 swapPairs(next->next)..

두 string이 주어졌을 때, 서로 다른 두 위치의 값들을 한번만 바꿔 같은 string이 될 수 있으면 true를 return하고 그렇지 않으면 false를 return하는 문제입니다. 크게 두 가지 갈래로 나눌 수 있습니다. 두 string이 모두 같은 경우와 그렇지 않은 경우가 있습니다. 1. 두 string 같은 경우는 같은 문자가 포함되어 있지 않다면, 두 자리를 변경하면 같아질 수 없습니다. 같은 문자가 포함된 경우를 판단하는 것은 set을 사용하여 기존 문자열과 길이가 달라지는 것으로 판단 가능합니다. 2. 다른 경우는 two point로 양쪽에서 index를 출발하여 같은 자리를 비교하며 같지 않은 index를 각각 저장해두고 그 두 자리를 변경했을 때 같지 않다면 같은 문자열을 만들 수..

Binary Tree가 주어졌을 때, root에서 leaf node까지의 path에 해당하는 값들의 합이 targetSum과 일치하는 경로가 존재하는지 여부를 판단하는 문제입니다. 재귀를 활용하여 left, right 자식들로 들어가면서 leaf node가 되었을 시 targetSum이 0인지 확인하는 방식으로 해결하였습니다. /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(..

조합을 구하는 문제입니다. next_permutation을 활용하여 순열 중에서 원하는 개수만큼 뽑는 방식을 사용하였습니다. 모든 조합의 경우의 수를 출력하므로 출력할 개수를 늘리면서 확인하였습니다. #include #define swap(a,b,t)((t) = (a), (a) = (b), (b) = (t)) class Solution { public: vector subsets(vector& nums) { vector answer; answer.push_back(vector{}); for (int i = 0; i < nums.size(); i++) { vector exist(nums.size(), 0); for (int j = 0; j

start를 기준으로 오름차순으로 정렬된 겹치지 않는 구간 리스트가 주어졌을 때, 한 구간을 리스트에 삽입하는 문제입니다. 만약 삽입하는 과정에서 겹치는 구간이 발생하면 병합하여 하나의 구간을 만들어야 합니다. Binary Search로 삽입할 index를 구하고, 해당 index를 기준으로 좌우로 two pointer로 넓혀가며 겹치는 구간을 찾고, 겹치는 구간이 있다면 삭제 후 병합한 새 구간을 넣어서 해결하였습니다. #include class Solution { public: vector insert(vector& intervals, vector& newInterval) { vector::iterator insert_index = upper_bound(intervals.begin(), interva..