Study Log

https://leetcode.com/problems/reconstruct-itinerary/description/ 문제 문제 분석- 티켓들을 정렬 후 그래프로 구성한 뒤에 DFS 탐색을 하면 됩니다.- 현재 노드를 바로 결과에 추가하는 방식으로 하면 더 이상 갈 수 있는 경로가 없을 때, 올바른 경로가 구성되지 않게 됩니다.ex) tickets = [["JFK", "NRT"], ["JFK", "KUL"], ["NRT", "JFK"]] 의 경우 정렬 후 KUL이 먼저 나오게 되는데 JFK -> KUL로 가면 더 이상 갈 수 있는 경로가 없게 됩니다. 둘 다 가능한 경로라면 KUL이 먼저 나와야하지만, 경로가 가능한 경우에만 해당하기 때문에 가능하지 않은 경로라면 사전 순이 의미가 없게 됩니다.- 따라서 ..

https://leetcode.com/problems/subsets/description/ 문제 문제 분석- 조합을 만드는 문제이지만 result에 탐색하는 동안 나오는 부분집합들을 다 넣어주기만 하면 됩니다. 풀이class Solution {private: vector> result; void dfs(vector& nums, vector& current, int start){ result.push_back(current); for(int i = start; i > subsets(vector& nums) { vector current; dfs(nums, current, 0); return result; }};

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..