CS STUDY

list(map(int,str(i))) 이 코드를 통해 만약 str(i)='321'이라면 [3,2,1]이 출력된다.

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/ Serialize and Deserialize Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com BFS를 통해서 직렬화를 구현해보자. # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x #..

https://leetcode.com/problems/merge-two-binary-trees/submissions/ Merge Two Binary Trees - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이 문제는 재귀탐색으로 해결할 수 있다. # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = ..

https://leetcode.com/problems/invert-binary-tree/ Invert Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 파이썬 다운 방식 이 문제는 재귀를 통해 파이썬다운 방식으로 정말 쉽게 풀 수 있다. 그러나 막상 설명은 쉽지 않다. class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if root:..

이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라. https://leetcode.com/problems/diameter-of-binary-tree/ Diameter of Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 가장 긴 경로를 찾는 방법은 먼저 가장 말단, 즉 리프 노드까지 탐색한 다음 부모로 거슬러 올라가면서 각각의 거리를 계산해 상태값을 업데이트 하면서 다음과 같이 누적해 나가면 된다. 최종 루트에서 상태값은 2, 거..

https://leetcode.com/problems/maximum-depth-of-binary-tree/ Maximum Depth of Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 깊이는 여러 가지 방법이 있지만 여기서는 BFS로 풀이해 보겠다. DFS는 스택, BFS는 큐를 사용하여 구현한다. 큐 변수에는 현재 깊이 depth에 해당하는 모든 노드가 들어 있고, queue.popleft()로 하나씩 끄집어 내면서 cur_root.h..

트리를 본격적으로 살펴보기에, 앞서 트리 각 부분에 대한 명칭을 살펴보자. 그래프 vs 트리 그래프와 트리의 차이점은 트리는 순환 구조를 갖지 않는 그래프임 이다. 트리는 크게 그래프의 범주에 포함되지만 그래프와 달리 트리는 어떠한 경우에도 한번 연결된 노드가 다시 연결되는 법이 없다. 이외에도 트리는 부모 노드에서 자식 노드를 가리키는 단방향뿐이다. 이진 트리 트리중에서 가장 널리 사용되는 트리 자료구조는 이진 트리와 이진 탐색 트리(Binary Search Tree,BST)이다. 각 노드가 m개 이하의 자식을 갖고 있으면, m-ary 트리(다항 트리, 다진 트리)라고 한다. m=2일 경우, 즉 모든 노드의 차수가 2 이하일 때는 특별히 이진 트리(Binary Tree)라고 구분해서 부른다. 이진 트리..

https://leetcode.com/problems/cheapest-flights-within-k-stops/ Cheapest Flights Within K Stops - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 시작점에서 도착점까지의 가장 저렴한 가격을 계산하되, K개의 경유지 이내에 도착하는 가격을 리턴하라. 경로가 존재하지 않을 경우 -1을 리턴한다. 여기서는 앞에 문제와 비교했을때 한 가지 제약사항이 추가되었는데 K개의 경유지 이내에 도착해야 한다..

그래프의 종류와 특성에 따라 각각 최적화된 다양한 최단 경로 알고리즘이 존재한다. 이 중에서 가장 유명한 것은 다익스트라 알고리즘이다. 다익스트라 알고리즘은 항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디(Greedy)알고리즘 중 하나로, 단순할 뿐만 아니라 실행 속도 또한 빠르다. 다익스트라 알고리즘은 노드 주변을 탐색할 때 BFS를 이용하는 대표적인 알고리즘이기도 하다. 다익스트라 알고리즘은 임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단거리는 계산이 끝났다는 확신을 갖고 더한다. 만일 이후에 더 짧은 경로가 존재한다면 다익스트라 알고리즘의 논리적 기반이 무너진다. https://leetcode.com/problems/network-delay-time/ Network Delay Tim..

https://leetcode.com/problems/combinations/ Combinations - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이번 포스팅에선 저번 순열에 이은 DFS로 조합에 대해 풀이해보겠다. 조합은 순열과 달리 원소의 순서가 달라도 구성되어져있는 원소의 종류가 같으면 같다고 처리해야한다. 예를들어 [1,3] 과 [3,1]은 조합에서 같은 것이다. 순열에서 풀이했던 코드와 상당히 유사하다. def combine(n: int, k: i..