거누의 개발노트

문제 시작점에서 도착점까지의 가장 저렴한 가격을 계산하되, K개의 경유지 이내에 도착하는 가격을 리턴하라. 경로가 존재하지 않을 경우 -1을 리턴한다. 예제 입력 Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1 예제 출력 Output: 700 작성한 코드 import heapq from typing import List def findCheapestPrice(n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: # 그래프 만들기 adj_list = {i: [] for i in range(n)} for f..

문제 K부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다. times배열안에 값들은 각각 출발지, 도착지, 소요시간 순으로 구성되며, 전체 노드의 개수는 N으로 입력받는다. 예제 입력 Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 예제 출력 Output: 2 작성한 코드 import heapq from typing import List def networkDelayTime(times: List[List[int]], n: int, k: int) -> int: INF = int(1e9) graph = [[] for _ in range(n + 1)] for i in times: a, b, c = map(int, i..

문제 정수 행렬 matrix에서 target 값을 검색하는 효율적인 알고리즘을 작성하십시오. 이 행렬에는 다음과 같은 속성이 있습니다. (m x n -> matrix) 각 행의 정수는 왼쪽에서 오른쪽으로 오름차순으로 정렬됩니다. 예제 입력 matrix = [ [1,4,7,11,15], [2,5,8,12,19], [3,6,9,16,22], [10,13,14,17,24], [18,21,23,26,30] ] , target = 5 예제 출력 Output: true 작성한 코드 class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: for i in range(len(matrix)): j = bisect.bisect..

문제 오름차순으로 정렬된 배열이 주어졌을 때 두 요소의 합이 target과 일치하는 배열의 인덱스를 반환하는 프로그램을 작성 예제 입력 Input: numbers = [2,7,11,15], target = 9 예제 출력 Output: [1,2] 작성한 코드 def twoSum(numbers: List[int], target: int) -> List[int]: x, y = 0, len(numbers)-1 while x target: y -= 1 else: return [x + 1, y + 1] https://leetcode.com/problems/two-sum-ii-input-array..

문제 오름차순으로 정렬된 정수 그룹nums가 있습니다. 함수에 전달하기 전에nums는 알 수 없는 축 인덱스 k (1 int: idx_min = sorted([[i, v] for i,v in enumerate(nums)], key=lambda x:x[1])[0][0] nums = nums[idx_min:] + nums[:idx_min] i = bisect.bisect_left(nums, target) if i < len(nums) and nums[i] == target: return (idx_min + i) % len(nums) else: return -1 https://leetcode.com/problems/search-in-rotated-sorted-array/ Search in Rotated Sor..

문제 정수 배열 nums이 주어지면 배열에서 k번째로 가장 큰 요소를 반환 하는 프로그램을 작성하시오. 입력 Input: nums = [3,2,1,5,6,4], k = 2 출력 Output: 5 작성한 코드1 class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: return heapq.nlargest(k,nums)[-1] https://leetcode.com/problems/kth-largest-element-in-an-array/ Kth Largest Element in an Array - LeetCode Level up your coding skills and quickly land a job. This is the be..

문제 m x n이진 행렬 mat이 제공 되는데, 1의 개수가 가장 적은 k 개의 인덱스를 반환하는 프로그램을 작성하시오. 입력 Input: mat = [[1,1,0,0,0], [1,1,1,1,0], [1,0,0,0,0], [1,1,0,0,0], [1,1,1,1,1]], k = 3 출력 Output: [2,0,3] 작성한 코드1 def kWeakestRows(mat: List[List[int]], k: int) -> List[int]: ans = [] s = collections.defaultdict(int) for i in range(len(mat)): # 1의 개수가 몇 개인지 c = collections.Counter(mat[i]) # 인덱스를 키로 1의 개수 만큼으로 하는 딕셔너리 s[i] = c[..

문제 정수 배열에서 (첫번째 최대값-1)*(두번째 최대값-1)을 해주는 프로그램을 작성. 입력 Input: nums = [3,4,5,2] 출력 Output: 12 # (5-1)*(4-1) 작성한 코드1 def maxProduct(nums: List[int]) -> int: n = sorted(nums, reverse=True) return (n[0]-1)*(n[1]-1) 작성한 코드2 def maxProduct2(nums: List[int]) -> int: h = heapq.nlargest(2, nums) return (h[0] - 1) * (h[1] - 1) list를 sort 할 때 는 시간 복잡도가 O(NlogN) 이고, heapq는 push, pop 할 때 O(logN) 이여서 힙이 빠르다는걸 알..