본문 바로가기

DFS

[Leetcode/파이썬] 117. Populating Next Right Pointers in Each Node II Populating Next Right Pointers in Each Node IIGiven a binary treestruct Node { int val; Node *left; Node *right; Node *next;}Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.Initially, all next pointers are set to NULL. Example 1:Input: root = [1,2,3,4,5,null,7]Output: [1,#,2,3,#,4,5,7,#]Explanation: Given the .. 더보기
[Leetcode/파이썬] 130. Surrounded Regions Surrounded RegionsYou are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:Connect: A cell is connected to adjacent cells horizontally or vertically.Region: To form a region connect every 'O' cell.Surround: The region is surrounded with 'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board.T.. 더보기
[Leetcode/파이썬] 129. Sum Root to Leaf Numbers Sum Root to Leaf NumbersYou are given the root of a binary tree containing digits from 0 to 9 only.Each root-to-leaf path in the tree represents a number.For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.A leaf node is a node with no children. Example .. 더보기
[Leetcode/파이썬] 101. Symmetric Tree Symmetric TreeGiven the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center). Example 1:Input: root = [1,2,2,3,4,4,3]Output: trueExample 2:Input: root = [1,2,2,null,3,null,3]Output: false Constraints:The number of nodes in the tree is in the range [1, 1000].-100 Follow up: Could you solve it both recursively and iteratively? # Definition for a binary.. 더보기
[Leetcode/파이썬] 112. Path Sum Path SumGiven the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.A leaf is a node with no children. Example 1:Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22Output: trueExplanation: The root-to-leaf path with the target sum is shown.Example 2:Input: root = [.. 더보기
[코딩 테스트 합격자 되기 파이썬 - 1주차]DFS 개념문제DFS를 구현하는 대표적인 두 가지 방법은 재귀 호출을 이용하는 것과 명시적인 스택(Stack) 자료구조를 사용하는 것입니다. 각 구현 방식의 장단점을 비교 설명해주세요.더보기1. 재귀재귀 함수를 호출할 때마다 호출한 함수는 시스템 스택이라는 곳에 쌓이므로 DFS에 적용하여 구현하게 된다. 장점 : 코드의 간결함, (호출 스택이 DFS의 진행 과정을 자연스럽게 관리)단점 : 스택오버플로우 발생 가능성이 높다, (함수 호출 오버헤드로 인한 성능 저하).직접 문제를 풀면서 느꼈던 재귀 함수와 DFS의 장단점은 코드가 간결한 만큼, 스택오버플로우(시간초과, 메모리초과) 발생 확률이 타 문제들보다 많았다는 점이다. 메모리초과가 나지 않으면 시간초과로 이어지는 경우가 많았다. 괄호 내 내용은 각종 AI툴들.. 더보기
[백준/파이썬][Gold III] 텀 프로젝트 - 9466 [Gold III] 텀 프로젝트 - 9466문제 링크성능 요약메모리: 238560 KB, 시간: 1016 ms분류깊이 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2025년 2월 10일 16:55:40문제 설명이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2.. 더보기
[백준/파이썬][Silver I] 그래프 탐색 2 - 14218 [Silver I] 그래프 탐색 2 - 14218문제 링크성능 요약메모리: 115600 KB, 시간: 232 ms분류너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2025년 2월 3일 18:31:45문제 설명남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 있는 도로들을 새로 만드는 계획이다. 도로 정비 계획은 두 도시에 대한 정보가 주어지는데, 도로를 정비하는 일은 매우 큰 일이기에 계획을 순서대로 하나씩 시행해 나갈 것이다.Zych는 차후 도로 정비 계획에 참고하기 위하여, 각 도시들이 수도에 방문하는데 최소 몇 개의 도시들을 방문해야 하는지 조사하기로 하였다.남규나라의 초기 도시상태가 주어지고 도로 정비계획이 주어질 때, 한 도로가 정비될 때마다 각 도시별로 .. 더보기

티스토리툴바