난쟁이 개발자

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 = [..

개념문제DFS를 구현하는 대표적인 두 가지 방법은 재귀 호출을 이용하는 것과 명시적인 스택(Stack) 자료구조를 사용하는 것입니다. 각 구현 방식의 장단점을 비교 설명해주세요.더보기1. 재귀재귀 함수를 호출할 때마다 호출한 함수는 시스템 스택이라는 곳에 쌓이므로 DFS에 적용하여 구현하게 된다. 장점 : 코드의 간결함, (호출 스택이 DFS의 진행 과정을 자연스럽게 관리)단점 : 스택오버플로우 발생 가능성이 높다, (함수 호출 오버헤드로 인한 성능 저하).직접 문제를 풀면서 느꼈던 재귀 함수와 DFS의 장단점은 코드가 간결한 만큼, 스택오버플로우(시간초과, 메모리초과) 발생 확률이 타 문제들보다 많았다는 점이다. 메모리초과가 나지 않으면 시간초과로 이어지는 경우가 많았다. 괄호 내 내용은 각종 AI툴들..

[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문제 링크성능 요약메모리: 115600 KB, 시간: 232 ms분류너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2025년 2월 3일 18:31:45문제 설명남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 있는 도로들을 새로 만드는 계획이다. 도로 정비 계획은 두 도시에 대한 정보가 주어지는데, 도로를 정비하는 일은 매우 큰 일이기에 계획을 순서대로 하나씩 시행해 나갈 것이다.Zych는 차후 도로 정비 계획에 참고하기 위하여, 각 도시들이 수도에 방문하는데 최소 몇 개의 도시들을 방문해야 하는지 조사하기로 하였다.남규나라의 초기 도시상태가 주어지고 도로 정비계획이 주어질 때, 한 도로가 정비될 때마다 각 도시별로 ..

[Gold II] 트리의 지름 - 1167문제 링크성능 요약메모리: 146100 KB, 시간: 280 ms분류깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리제출 일자2024년 9월 3일 18:48:46문제 설명트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.입력트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. ..

[Gold IV] 트리의 지름 - 1967문제 링크성능 요약메모리: 112624 KB, 시간: 124 ms분류깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리제출 일자2024년 11월 27일 19:29:08문제 설명트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다.이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다.입력으로 루트가 있는 트리를 ..