Study Log

정의상호 배타적 집합(서로소 집합)(Disjoint-Set)을 표현할 때 사용하는 그래프 알고리즘Disjoint-set은 공통 원소가 없는 상호 배타적인 부분집합들로 나눠진 원소들에 대한 정보를 표현하는 자료구조집합을 합치는 Union 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어짐Union(합치기): 두 원소가 속한 집합을 하나로 합친다.Find(찾기): 해당 원소가 속한 집합을 반환한다.핵심은 각각의 집합을 하나의 트리로 나타내는 것Union-Find를 사용하면 특정 노드가 어느 집단에 속해 있는지 알 수 있다.트리의 구조를 사용해서 시간복잡도가 평균적으로 O(log N)이지만, 편향될 경우 O(N)이 될 수 있다.경로 압축(Path Compression), Rank기반 연산을 통해 최적화..

정의트리는 list, queue 등과 달리 한 노드가 여러 노드를 가리킬 수 있는 비선형적 자료구조최상위 노드가 존재하는 계층적인 형태단방향 그래프시작 노드에서 출발해서 다시 돌아올 수 없는 사이클이 없는 연결 그래프 용어노드(Node): 트리를 구성하는 데이터 원소간선(Edge): 노드와 노드를 연결하는 선 (노드의 개수 n, 간선의 수 n-1)루트 노드(Root Node): 부모 노드가 없는 트리의 가장 최상단에 있는 노드. 트리에 1개 존재부모 노드(Parent Node): 연결된 두 노드 중 위에 있는 노드자식 노드(Child Node): 부모 노드의 하위 노드형제 노드(Sibling Node): 같은 부모를 갖는 노드조상 노드(Ancestor Node) / 자손 노드(Descedent Node)..

https://leetcode.com/problems/network-delay-time/description/ 문제 문제 분석- 네트워크 중에서 모든 노드를 탐색하는 것이기 때문에 다익스트라로 검색 후, 가장 먼 거리에 떨어져있는 노드와의 거리를 반환하면 됩니다. (모든 노드를 탐지하는데 걸리는 총 시간이 아닙니다. 네트워크이기에 동시에 퍼져나간다는 가정 후, 가장 먼 노드까지 다 도달하는데 총 얼마나 걸리는가를 묻고 있는 것입니다.)- 초기 노드에서 출발 시 도착못하는 경우 -1를 반환하면 됩니다. 풀이#include #include #include #include using namespace std;class Solution {public: int networkDelayTime(vector>& ..

https://leetcode.com/problems/course-schedule/description/ 문제 문제 분석- 순환(cycle)이 있는지 탐색하는 문제입니다. 사이클이 존재하면 false를 반환하고, 존재하지 않으면 true를 반환하여야 합니다.- 현재 경로 중에서 중복되는 요소가 나온다면 false를 반환하면 됩니다. 이를 위해 set을 사용하였습니다.- traced의 경우 탐색이 끝나고 제거를 해주어야 [0,1], [0,2], [1,2]와 같이 cycle이 아닌 경우를 제대로 판별할 수 있습니다. 0 -> 1 -> 2 경로 탐색 후 제거하지 않는다면 1 -> 2 탐색할 때 2를 이미 탐색한 노드로 판별하여 false를 반환하게 될 것 입니다.- visited는 경로 탐색이 모두 끝난 요소..

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