문제https://leetcode.com/problems/longest-cycle-in-a-graph/난이도: Hard토픽: DFS, Graph, Topological sorting그래프가 주어지면 그래프 내의 사이클중 제일 길이가 긴 사이클 길이를 구하는 문제이다. 접근방법그래프에서 사이클을 감지하는 가장 간단한 알고리즘으로 Floyd의 거북이 & 토끼 알고리즘이 있다. Floyd의 거북이 & 토끼 알고리즘거북이와 토끼를 시작점에 놓고 거북이는 한 번에 1칸 움직이고, 토끼는 한 번에 2칸 움직인다.그래프에 사이클이 있다면 토끼와 거북이는 어느 한 지점에서 반드시 만나게 된다.사이클을 감지하는 건 알겠는데, 어떻게 하면 사이클의 길이를 측정할 수 있을까?위의 그래프에서 거북이와 토끼는 4번 이동하여 노..

문제문제: https://leetcode.com/problems/minimum-size-subarray-sum/description/난이도: Medium토픽: Array, Binary Search, Sliding Window, Prefix Sum모든 요소가 양수인 배열 nums와 양수 target이 입력으로 주어지고, nums의 서브 배열들 중 서브 배열의 모든 요소를 더한 값이 target보다 크거나 같은 가장 작은 길이의 서브배열을 구하는 문제이다.풀이각 구간사이의 합을 구하는 것이므로 누적합을 사용하면 서브 배열마다 매번 덧셈 연산을 해줄 필요가 없다.아래의 예제와 같이 누적합을 구해주면 각 구간사이의 합은 쉽게 구할 수 있다.[2,3,1,2,4,3] # 입력[0,2,5,6,8,12,15] ..

문제트리가 주어지면 이 트리가 정말 Binary Search Tree가 맞는지 판단하는 문제이다.98.Validate Binary Search TreeBinary Search TreeBST는 아래와 같은 조건을 모두 만족하는 트리이다.해당 노드의 왼쪽 서브 트리의 값은 모두 해당 노드의 값보다 작아야한다.해당 노드의 오른쪽 서브 트리의 값은 모두 해당 노드의 값보다 커야한다.왼쪽 서브 트리, 오른쪽 서브 트리 모두 BST이다.접근 방법처음에는 정말 간단하게 생각해서 왼쪽 자식 노드의 값 def is_valid_bst(self, node:TreeNode): if node.left and node.right: return self.is_valid_bst(node.left) a..