Study Log

파이콘 두 번째날에 대해서 후기를 작성해 보겠습니다.개인적으로는 파이콘 두 번째날은 그닥 만족스럽지는 않았었습니다. 제가 파이콘에서 기대했던 거는 새로운 기술, 지식 이런 쪽이었는데 두번째 세션들은 대부분 경험 공유에 초점이 더 있었던 느낌이었기 때문입니다. 또한 제 관심사는 Backend, 보안 쪽이었는데 이쪽 기술 관련된 내용은 부족했던 것 같습니다.두 번째날 세션은 위와 같이 진행되었었고, 경험 공유는 흥미가 없어서 13:50 세션부터 저는 듣기 시작했었습니다. (처음부터 들으신 팀원분이 있으셨는데 저와 같이 경험 공유를 바라고 온 것은 아니시라서 별로였다고 하시더라고요. 그래서 시간 결정 잘한 느낌이었습니다ㅋㅋ) 첫 세션으로는 공정한 채점을 위한 PyPencil이었습니다. Automates ass..

Pycon2024년 10월 26~27일 수원 컨벤션센터에서 진행된 Pycon에 다녀왔습니다. 인턴을 하고 있는 회사에서 시간되면 팀원들과 함께 다녀오면 좋을 것 같다고 하여 학교 시험이 바로 끝난 바로 다음날 파이콘을 다녀오게되었습니다! 파이콘 진행 일주일 전에 신청 후 시험 때문에 정신이 없어서 어떤 느낌의 행사인지 제대로 알지 못하고 행사 전날 밤에서야 세션을 찾아보게 되었습니다.1일차 세션은 위와 같이 진행되었는데, 오전 세션에는 크게 관심이 없어서 점심 이후에 파이콘에 참가하게 되었습니다. 회사에서 프론트엔드와 백엔드를 담당하고 있고, 백엔드에 FastAPI를 사용하고 있었기에 위 세션들 중에서 FastAPI with Dependency Injector라는 세션이 가장 궁금했고, Django에 관..

정의상호 배타적 집합(서로소 집합)(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..