분류 전체보기252 ch12-7(leetcode 332). 일정 재구성 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 332번 ( https://leetcode.com/problems/reconstruct-itinerary/ ) 시도한 방법 풀이에는 실패하였지만 시도한 방법은 기록해 두었다. 전체 코드는 다음과 같다. 더보기 class Solution(object): def findItinerary(self, tickets): def dfs(elem, path): if len(path) >= (len(tickets)+1): result.append(path[:]) return for e in route[elem]: route[elem].remove(e) dfs(e, path + [e]) route[elem].insert(0, e) result .. 2023. 1. 19. ch12-6(leetcode 78). 부분 집합 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 78번 ( https://leetcode.com/problems/subsets/ ) 풀이 1. 원소들의 집합 nums이 매개변수로 주어졌을 때 nums의 원소로 만들 수 있는 모든 부분집합들을 리턴하는 문제이다. 이전에 풀었던 조합 문제에다가 로직을 추가하는 방법으로도 풀 수 있다. dfs(elements, start, k) 이전에 중첩 함수 dfs()를 선언하는 방식으로 배열과 숫자 k가 주어졌을 때 배열에서 k개의 요소를 조합하는 문제를 풀었었다. 조합은 순열처럼 순서를 고려하지 않기 때문에, 앞에 온 원소가 포함되는 조합의 경우를 모두 고려하였다면 나머지 남은 경우에서는 앞의 원소가 포함되지 않는다. (조합의 합 문제와 같.. 2023. 1. 19. ch12-5(leetcode 39). 조합의 합 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 39번 ( https://leetcode.com/problems/combination-sum/ ) 풀이 1. (교재 참고) 중첩 함수(nested function)를 선언하고 그 함수를 재귀적으로 호출하면 풀 수 있다. 주어진 배열 candidates의 각 원소를 횟수 제한 없이 사용해서 정확히 target의 값을 만드는 문제이다. unbounded knapsack 문제와도 유사하다. 예를 들어 candidates = [2, 3, 4], target = 7인 상황에서 맨 처음 2를 선택했다고 해 보자. 이 경우 각 원소를 한 번만 써야하는 것이 아니므로 똑같이 [2, 3, 4]의 값을 사용해서 7-2인 5를 만들어 내면 되는 문.. 2023. 1. 18. ch12-4(leetcode 76). 조합 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 77번 ( https://leetcode.com/problems/combinations/ ) 방법 1. itertools 모듈을 이용한다. itertools.combinations(n, k) 해당 모듈의 메소드는 총 n개의 원소 중 k개를 뽑는 조합의 경우의 수를 리스트로 리턴해 준다. def combine(self, n, k): return itertools.combinations(range(1, n+1), k) 방법 2. 이전에 풀었던 순열 문제와 같은 방법으로, 내부 함수 dfs()를 선언한다. dfs(elements, k)에서는 elements에 포함된 n개의 원소 중 k개를 하나씩 뽑는다. 뽑은 원소는 추가된 원소이므로.. 2023. 1. 18. ch12-3(leetcode 46). 순열 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 46번 ( https://leetcode.com/problems/permutations/ ) 풀이 1. (교재 참고) DFS를 재귀 함수로 사용해서 풀 수 있다. 이때 지금까지 탐색한 경로(노드)를 저장하는 prev_elements와 최종 탐색한 결과만을 저장하는 results 두 개의 변수를 사용한다. dfs() 라는 이 내부 함수는 숫자 리스트를 매개변수로 받는다. 그리고 다음에 탐색할 숫자 리스트를 저장하는 next_elements 변수에다가 매개변수로 받은 리스트 값을 할당한다. 이때 = 를 사용해서 변수를 그대로 할당하면 파이썬에서는 값을 복사하는 것이 아니라 참조하게 되므로, [:]을 통해 할당해 준다. next_el.. 2023. 1. 15. ch12-2(leetcode 17). 전화번호 문자 조합 * 해당 포스트는 공부 후 정리 목적으로 작성되었습니다. * leetcode 17번 ( https://leetcode.com/problems/letter-combinations-of-a-phone-number/ ) 풀이 1. 재귀함수를 이용해서 풀 수 있다. 딕셔너리를 이용해서 각 digits의 자리수를 key로, 해당 자리수의 문자열 리스트를 value로 저장한다. 그리고 내부 함수를 선언하여 재귀함수로 사용한다. digits의 맨 뒤의 자리수에서부터 맞는 문자열을 리스트로 리턴하고, 해당 리스트의 앞에다가 붙여 준다. digits="234"를 예로 들어보자. "3"과 "4"의 관계를 보면, "4"에서는 뒤의 문자열이 더 이상 없어서 딕셔너리에서 "4"에 해당하는 알파벳 리스트인 ["g","h","i".. 2023. 1. 15. 이전 1 ··· 27 28 29 30 31 32 33 ··· 42 다음
