목록알고리즘 (8)

글모음

[프로그래머스] Python 알고리즘 스터디 - 4주차 Sorting & Dynamic Programming

4주 차 Sorting & Dynamic Programming Trie def solution(departments, budget): departments = sorted(departments) cur_budget, cnt = 0, 0 for department in departments: if cur_budget + department def solution(A,B): A = sorted(A) B = sorted(B) ans = 0 for n1, n2 in zip(A, B[::-1]): ans += (n1 * n2) return ans from functools import cmp_to_key def solution(numbers): nums = list..
알고리즘/프로그래머스 2022. 5. 30. 12:35
[프로그래머스] Python 알고리즘 스터디 - 3주차 Searching

3주 차 Searching 1) backtracking 사용 def find_primes(n): a = [False,False] + [True] * (n -1) primes=[] for i in range(2, n + 1): if a[i]: primes.append(i) for j in range(2 * i, n + 1, i): a[j] = False return primes def solution(n): primes = find_primes(n) cnt = 0 def count_sum(total_sum, level, res, num_cnt): nonlocal cnt if total_sum > n: return if level == len(primes): return if nu..
알고리즘/프로그래머스 2022. 5. 30. 12:34
[프로그래머스] Python 알고리즘 스터디 - 2주차 Stack & Hash

2주 차 Stack, Hash def solution(coordinates): X_set = set() Y_set = set() for coordinate in coordinates: X, Y = coordinate if X not in X_set : X_set.add(X) else: X_set.remove(X) if Y not in Y_set : Y_set.add(Y) else: Y_set.remove(Y) return list(X_set) + list(Y_set) 짝이 되지 않는 좌표가 나머지 한 점이다. 그런 좌표들을 합쳐서 return 해주면 되는 간단한 문제다. def solution(max_weight, specs, names): spec_in..
알고리즘/프로그래머스 2022. 5. 30. 12:31
[프로그래머스] Python 알고리즘 스터디 - 1주차 Queue & Heap

1주 차 Queue & Heap def solution(progresses, speeds): days = [0] * len(progresses) criteria, cnt = 0, 1 ans = [] for i in range(len(progresses)): while progresses[i] criteria: criteria = days[j] if j == 0: continue ans.append(cnt) cnt = 1 else: cnt += 1 if j == len(days)-1: ans.append(cnt) return an..
알고리즘/프로그래머스 2022. 5. 30. 12:30
[Leetcode] 938. Range Sum of BST [Python, easy]

[ 문제 해설 ] Tree를 탐방해서 low와 high 사이에 해당하는 값을 전부 더해서 반환하는 문제다. [ 코드 1. Stack으로 구현 ] class Solution: def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int: if not root: return 0 stack = [root] ans = 0 while stack: c_node = stack.pop() if c_node: if low
카테고리 없음 2021. 6. 12. 17:24
[ 프로그래머스 ] 주식가격 (Level 2)

[ 코드 ] def solution(prices): ans = [] for i in range(len(prices)-1): time = 0 for j in range(i+1,len(prices)): time += 1 if prices[i] > prices[j] : break ans.append(time) return ans + [0] 시간 복잡도 : O(N^2) - 이중 for문 공간 복잡도 : O(N) - ans 리스트 하나 스택이나 큐를 사용한 문제인데 그냥 반복문으로 풀었다. 이중 for문이라 시간 복잡도가 O(N^2)이라 효율성이 좋지는 않는데 스택써도 시간 복잡도는 똑같을거라 최대한 반복을 줄이려고 노력했다. prices의 마지막 요소는 어차피 비교할 것이 없으니 무조건 0이므로 연산에서 제외하..
카테고리 없음 2021. 3. 7. 16:05
1441. Build an Array With Stack Operations [Easy, Python]

1부터 n까지의 숫자들을 list에 넣고, 넣을 때 "Push" 만약 target에 해당하는 숫자가 없다면 제거하면서 "Pop" 기초적인 stack 문제다. [ 코드 1 ] class Solution: def buildArray(self, target: List[int], n: int) -> List[str]: ans, temp = [], [] for i in range(1,n+1): temp.append(i) ans.append("Push") if i not in target: temp.pop() ans.append("Pop") if temp == target: break return ans Push, Pop을 넣어줄 정답 리스트 ans 굳이 추가로 list를 만들어주지 않아도 괜찮지만 숫자들이 Pus..
알고리즘/Leetcode 2021. 3. 6. 10:29
682. Baseball Game [Easy, Python]

[ 정답 1 ] 카테고리: 스택 Runtime: 35.97% Memory Usage: 48.21% 시간 복잡도 : O(n) - for문 하나 공간 복잡도 : O(n) - list 하나 class Solution: def calPoints(self, ops): record = [] for i in range(len(ops)): try: record.append(int(ops[i])) except: if ops[i] == "C": record.pop() elif ops[i] == "D": record.append(2* record[-1]) elif ops[i] == "+": record.append(record[-2] + record[-1]) return sum(record) 1. 값들을 저장할 list 하..
알고리즘/Leetcode 2021. 3. 6. 00:52
Prev 1 Next