본문 바로가기

Algorithm37

[LeetCode] Sort Colors 목차 문제 공간복잡도를 O(1)로 정렬하는 문제입니다. 0,1,2 으로 구성된 array가 있을 때 정렬하는 문제입니다. 대부분의 정렬 예시 Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2] Input: nums = [2,0,1] Output: [0,1,2] 제약사항 n == nums.length 1 2024. 4. 16.
[LeetCode] Pascal's Triangle II 목차 문제 파스칼 삼각형에서 rowIndex 번째의 값을 O(rowIndex)공간만 사용하여 해결하는 문제입니다. 예시 Input: rowIndex = 3 Output: [1,3,3,1] Input: rowIndex = 0 Output: [1] Input: rowIndex = 1 Output: [1,1] 제약사항 0 List[int]: return [math.comb(rowIndex,i) for i in range(rowIndex+1)] 알게 된 내용 이항계수 성질 파스칼 삼각형 출처 https://leetcode.com/explore/learn/card/array-and-string/204/conclusion/1171/ 2024. 4. 15.
[LeetCode] Rotate Array 목차 문제 주어진 배열을 k만큼 rotate 시키는 문제입니다. (단, 추가적인 공간을 생성하지 않고 문제를 해결해야 합니다.) 예시 Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4] Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3.. 2024. 4. 15.
순열, 조합, 중복순열, 중복조합 목차 순열(Permutations) 순열은 주어진 원소들로 만들 수 있는 모든 가능한 순서 있는 배열입니다. (순서가 중요한 경우) 시간복잡도 : O(nPr) 예시 itertools 라이브러리 이용 코드 from itertools import permutations print(list(permutations([1, 2, 3, 4, 5], 3))) 직접구현 코드 def permutations(arr, r): def generate(arr, prefix=[]): if len(prefix) == r: result.append(prefix) return for i in range(len(arr)): generate(arr[:i] + arr[i + 1 :], prefix + [arr[i]]) result = [].. 2024. 4. 10.