본문 바로가기
반응형

프로그래밍/알고리즘 문제39

[재귀호출] LeetCode 70. Climbing Stairs 1과 2의 합으로 n을 만드는 경우의 수를 구한다. 1. 재귀호출 (브루트포스. 모든 경우의 수를 다 구한다) 예를 들어 1과 2의 합으로 4를 만드는 경우의 수를 봐보자. 1+1+1+1, 1+1+1+2, 1+1+2, 1+2+1, 1+2+2, ... 이런식으로 모든 경우의 수를 다 해보는 것이다. class Solution: def __init__(self): self.cnt = 0 def do(self, result,n): if result == n: self.cnt += 1 return if result > n: return for i in [1,2]: self.do(result+i,n) def climbStairs(self, n: int) -> int: self.do(0,n) return self... 2021. 3. 20.
[리스트] Leet Code 26. Remove Duplicates from Sorted Array 리스트에서 중복값을 제외하고 중복값 제외한 숫자들의 개수를 구한다. class Solution: def removeDuplicates(self, nums: List[int]) -> int: i = 0 while i pop(i) O(N) ([1,1,1,1,1] 인 경우) 공간복잡도 O(1) : 변수 i 공간 1개만 필요 솔루션 보고 개선한 코드 class Solution: def removeDuplicates(self, nums: List[int]) -> int: if len(nums)==0 :.. 2021. 3. 20.
[스택] Leet Code 20. Valid Parentheses 괄호가 제대로 구성되어 있는지 파악하는 문제다. 제대로 구성됐다는 것은 닫는 괄호가 나올 때 제일 최근에 있는 여는 괄호와 매칭된 형태이다. 여는 괄호를 스택에 넣고 닫는 괄호가 나올 때 스택에 있던 값을 pop 하여 괄호가 매칭되는지 확인한다. 괄호가 매칭되지 않는 경우는 1) 닫는 괄호가 여는 괄호가 매칭되지 않거나 "(]" 2) 닫는 괄호는 있지만 여는 괄호가 없거나 "()]" 3) 여는 괄호가 덩그러니 남아있거나 "(()" class Solution: def isValid(self, s: str) -> bool: temp = [] match = {'{':'}', '[':']', '(':')'} # 시간복잡도 O(N) : 하나씩 쭈욱 탐색 O(N) + pop 시간복잡도는 O(1) # 공간복잡도 O(.. 2021. 3. 18.
[재귀호출] 팩토리얼 /피보나치 수열 /순열 시간복잡도 팩토리얼 def factorial(n): if n == 1 || n== 0: return 1 return n * factorial(n - 1) n = 3 print("**팩토리얼") print(factorial(n)) 시간복잡도 O(N) : N번 계산됨 (3*f(2), 2*f(1), 1,*f(0)) 공간복잡도 O(N) : 재귀함수 N번 호출됨 피보나치수열 def fibo(n): if n==1 : return 1 if n==2 : return 1 return fibo(n-1)+fibo(n-2) print("**피보나치수열") print(fibo(n)) 시간복잡도 O(2^N) : 2^N번 연산됨 (f(4)+f(3), f(3)+f(2) f(2)+(1), f(2)+f(1)) 공간복잡도 O(2^N) : 재귀함수 .. 2021. 3. 16.
[Quick Sort] python 퀵정렬 # pivot보다 작은그룹, 큰그룹 분리됨! def partiton(arr,start,end): pivot = arr[(start+end)//2] while start pivot : end -= 1 #pivot보다 큰 값은 건너뛰고 작은 값일 경우 멈춘다. (이따 swap할거야) if start 탐색할 데이터는 반씩 줄어든다 O(logN) 공간복잡도 O(1) 추가 공간이 필요 없다. 아주 깔끔한 설명 영상을 참고했다. 2021. 3. 16.
[이진트리] 순회 & add 정렬되지 않은 이진트리 class Node: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right def __str__(self): return f'' class BinaryTree: def __init__(self,node): self.head = node # 트리모양 그대로 (root -> left 서브트리 -> right 서브트리) def preorder(self): if self.head.val is not None: self.__preorder_traverse(self.head) def __preorder_traverse(self, cur): print(cur.val) if.. 2021. 3. 16.
반응형

티스토리툴바