Study Log

https://leetcode.com/problems/combination-sum/description/ 문제 문제 분석- DFS를 이용해서 합이 target과 같을 때만 결과로 넣으면서 반복하고, target 값을 넘어가면 그 즉시 종료하도록 하면 됩니다. 조합이기 때문에 각 요소의 순서가 바뀐 것은 하나로 보아야 하기 때문에 정렬 후에 자기 자신 이상의 값들만 다음 번 요소로 사용할 수 있도록 해야합니다.- 반대로 sum을 계산하면서 합이 아니라 값을 target에서 감소시키는 방향으로도 풀 수 있을 것입니다. 풀이class Solution {private: vector> result; void dfs(vector& candidates, vector& current, int target, ..

https://leetcode.com/problems/combinations/description/ 문제 문제 분석조합의 경우 순열과 다르게 순서가 달라도 같은 경우로 따지기 때문에 중복되어서 탐색하는 경우가 없게 현재 시점의 이후로만 값을 변경할 수 있도록 해야 합니다. 풀이class Solution {private: vector> result; void dfs(int n, vector&current, int start, int k){ if(current.size() == k){ result.push_back(current); return; } for(int i = start; i > combine(int n, in..

https://leetcode.com/problems/permutations/description/ 문제 문제 분석- DFS를 이용하되 요소를 넣다가 뺐다가 하면서 재귀적으로 반복하여 구현할 수 있습니다.- next_permutation을 사용하여 구현할 수도 있습니다 문제 풀이 1 (DFS)class Solution {private: vector> result; vector nums; vector used;public: void dfs(vector& current){ if (current.size() == nums.size()){ result.push_back(current); return; } for(i..

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/ 문제 문제 분석- DFS 재귀 탐색을 이용해서 가능한 모든 경우의 수를 만들어내면 됩니다.- 각 순서가 유지되기 때문에 단순 DFS로 풀이가 가능합니다. ("23"이면 "32"인 경우랑은 다름) 풀이class Solution {private: std::map> keypad = { {2, {'a', 'b', 'c'}}, {3, {'d', 'e', 'f'}}, {4, {'g', 'h', 'i'}}, {5, {'j', 'k', 'l'}}, {6, {'m', 'n', 'o'}}, {7, {..

https://leetcode.com/problems/number-of-islands/description/ 문제 문제 분석- 입력값을 동서남북이 모두 연결된 그래프로 가정하고 각 방향에 대해서 DFS 재귀를 이용해서 탐색이 끝나면 전체 섬의 개수를 1 증가시키는 방법으로 섬들을 탐지할 수 있습니다.- 방문 여부를 따로 트래킹하거나 '1'을 '0'으로 바꾸는 방법을 사용할 수 있습니다. 풀이 1 (방문 여부 트래킹)class Solution {private: vector> isVisited; vector> *grid; int row; int col; int count;public: void dfs(int i, int j){ if(i = row || j >= c..

https://leetcode.com/problems/design-hashmap/description/ 문제 문제 분석- 개별 체이닝 방식으로 hashMap을 구현하였습니다 풀이class MyHashMap {private: static const int SIZE = 1000; struct Node{ int key; int value; Node* next; Node(int k, int v):key(k), value(v), next(nullptr){} }; vector map;public: MyHashMap() { map.resize(SIZE, nullptr); } void put(int key, in..

https://leetcode.com/problems/merge-k-sorted-lists/ 문제 문제 분석- priority queue를 이용해서 정리한 뒤, 요소를 하나씩 빼서 연결시키면 됩니다.- 어떤 방식으로든지 정렬을 해서 하나씩 뽑아서 넣으면 됩니다. 풀이class Solution {public: ListNode* mergeKLists(vector& lists) { if (lists.empty()){ return nullptr; } auto compare = [](ListNode* a, ListNode* b){ return a->val > b->val; }; std::priority_qu..

https://leetcode.com/problems/daily-temperatures/description/ 문제 문제 분석- 스택을 이용해서 온도와 index를 같이 저장해놓고, stack의 top과 현재 temperature를 비교해서 현재가 더 높은 경우에는 stack에서 제거한 뒤 result에 해당하는 index에 Index - 현재 index를 기록합니다. 현재 temperature가 더 높다면 계속 반복합니다. 풀이class Solution {public: vector dailyTemperatures(vector& temperatures) { vector> stack; vector result(temperatures.size(), 0); stack..

https://leetcode.com/problems/remove-duplicate-letters/description/ 문제 문제 분석사전식 순서라는 것을 잘 이해해야 합니다. string을 구성하는 각 char들을 a,b,c .. 이런 식으로 전부 오름차순하라는 것이 아니라 중복을 제거한 상태에서 나올 수 있는 string 중에서 사전순으로 앞선 string을 반환하라는 것입니다.예를 들면, dacbbc라는 글자가 있을 때 중복 제거시 나올 수 있는 경우는 dacb, dabc가 있습니다. 이때 사전 순으로는 dabc가 dacb보다 앞서 있기때문에 dabc를 반환해야 합니다.d가 a보다 사전순으로 뒤에 있는 것은 맞지만, 각 요소를 사전순으로 배치하라는 것이 아닌 중복을 제거한 문자열 경우의 수 중에서..

https://leetcode.com/problems/valid-parentheses/description/ 문제 문제 분석- 스택을 이용해서 닫는 기호가 나타났을 때, 스택의 가장 최상단에 그와 연결되는 여는 기호가 있어야 유효한 Parenthesis가 될 수 있습니다.  풀이class Solution {private: map match = { {')', '('}, {'}', '{'}, {']','['} };public: bool isValid(string s) { stack stack; for(const auto& c: s){ if(c == '(' || c == '{' || c == '['..