멋진 개발자가 되고 싶다

K부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다. 입력값 (u, v, w)는 각각 출발지, 도착지, 소요 시간으로 구성되며, 전체 노드의 개수는 N으로 입력받는다. example: Input: times = [[2,1,1], [2,3,1], [3,4,1]], n = 4, k = 2 Output: 2 ** 깔끔한 풀이 1. 다익스트라 알고리즘 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution: def networkDelayTime(self, times, n: int, k: int) -> int: graph = collections.defaultdict(list..

0을 완료하기 위해서는 1을 끝내야 한다는 것을 [0,1] 쌍으로 표현하는 n개의 코스가 있다. 코스 개수 n과 이 쌍들을 입력으로 받았을 때 모든 코스가 완료 가능한지 판별하라. Example: Input: numCourses = 2, prerequisites = [[1,0]] Output: true ** 깔끔한 풀이 ** 1. DFS로 순환 구조 판별 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: graph = collections.defaul..

[from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라. 여러 일정이 있는 경우 사전 어휘 순(Lexical Order)으로 방문한다. example: Input: tickets = [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] Output: ["JFK", "MUC", "LHR", "SFO", "SJC"] ** 깔끔한 풀이 ** 1. DFS로 일정 그래프 구성 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def findItinerary(self, tickets): graph = collections.defaultdict(list) # 그래프 ..

숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라. 각 원소는 중복으로 나열 가능하다. Example: Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3], [7]] 1. 내가 직접 푼 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: output = [] def dfs(stack, hap): if hap == target: output.append(stack) elif hap > target: r..

전체 수 n을 입력받아 k개의 조합을 리턴하라. Example: Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 1. 내가 푼 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution: def combine(self, n: int, k: int) -> List[List[int]]: output = [] nums = [i + 1 for i in range(n)] def dfs(k, stack=None): if stack is None: stack = [] if k == 0: output.append(stack) return if stac..

문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. 아..

2에서 9까지 숫자가 주어졌을 때 전화번호로 조합 가능한 모든 문자를 출력하라. Example: Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"] 꼭 재귀를 return으로만 구성할 필요는 없다. 특히 이번 문제는 for문을 이용해서 조합하는 문제인데 return을 쓰면 중간에 return 때문에 끊긴다. ** 깔끔한 답안 ** 1. 모든 조합 탐색 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution: def letterCombinations(self, digits: str) -> List[str]: def dfs(index, pat..

1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라. (연결되어 있는 1의 덩어리의 개수를 구하라.) Example: Input: grid = [ ["1", "1", "1", "1", "0"], ["1", "1", "0", "1", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "0", "0", "0"] ] Output: 1 ** 깔끔한 답안 ** 1. DFS로 그래프 탐색 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution: def numIslands(self, grid: List[List[str]]) -> int: def dfs(i, j): # 더 ..