DFS5 course schedule Course Schedule prerequisite : [a,b] = a course를 완료하기 위해 b course를 먼저 완료 해야함 numCourses : 코스 개수, prerequisites 가 주어졌을때 전부 완료가능하면 True 아니면 False Solution1 각 course 를 node 로 prerequisite 를 edge 로 생각하면 directed graph로 표현가능 directed graph에 cycle 이 존재하는 지 판별해서 존재하는 경우 False, 없으면 True dfs를 이용해 한 노드에서 출발하는 경로중에 cycle이 존재하는 지 검사할수 있음(has_cycle) 방문한 노드 기록(visitied) 해당 노드를 출발점으로 하는 어떤 경로에도 cycle이 없다고 결정(f.. 2022. 1. 21. [leetcode] combinations combinations n, k ( n >= k >= 1) 의 정수가 주어질때 n 개의 정수 (1 ~ n) 에서 k 개의 수를 뽑는 조합을 리턴 Solution1 itertools의 combinations 이용 code1 from itertools import combinations class Solution(object): def combine(self, n, k): return list(map(list,combinations(range(1,n+1),k))) Solution2 dfs(selected:list,start:int) selected에 el 이 추가된 경우 다음의 dfs에서 start = el + 1 종료조건 len(selected) == k code2 class Solution(object).. 2022. 1. 13. [leetcode] permutations permutations 서로다른 숫자로 구성된 배열을 입력으로 받는다 가능한 모든 조합의 순열을 리턴 Solution1 itertools의 permutations를 사용 code1 from itertools import permutations class Solution(object): def permute(self, nums): return list(map(list,permutations(nums))) Solution2 next_permutation(nums)메서드 구현 nums[i-1] < nums[i] 인 가장 큰 i 찾기 nums[i:] 범위에서 nums[i-1] < nums[j] 인 가장큰 j 찾기 nums[i-1] 와 nums[j] 를 swap nums[i:] 를 양 끝에서 가운데 방향으로 sw.. 2022. 1. 13. [leetcode] letter combinations of a phone number letter combinations of a phone number "2~9" 의 8가지 숫자의 조합으로 된 문자열을 입력으로 각 숫자는, 문자열 집합의 문자들 중 하나의 문자로 대응될수 있음 숫자열이 주어졌을때 조합가능한 모든 문자열 리턴 Solution 1 itertools의 product 이용 곱집합 code 1 from itertools import product class Solution(object): def letterCombinations(self, digits): """ :type digits: str :rtype: List[str] """ book = { '2':['a','b','c'], '3':['d'.. 2022. 1. 13. 이전 1 2 다음