멋진 개발자가 되고 싶다

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 해설: 아... 가지치기하다가 숨 막혀 죽을 뻔.. 이 문제는 BFS..

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) # 그래프 ..

모든 부분 집합을 리턴하라. Example: Input: nums = [1,2,3] Output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]] 1. 내가 직접 푼 코드(itertools 짱짱맨) 1 2 3 4 5 6 7 8 class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: result = [] for i in range(len(nums)+1): result += list(itertools.combinations(nums,i)) return result Colored by Color Scripter cs 해설: 어떻게 풀지 고민하다가 itertools가 떠올랐다! 속도는 상위 5퍼센트 ..

숫자 집합 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..

문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추 근처에 서식하며 해충을 잡아먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추 흰 지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇..