글모음

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..

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..

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..

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..

프로그래머스 / 임팩트 커리어 코딩 테스트와 실무 역량 모두 잡는 알고리즘 스터디 9기 [ 참여 동기 ] 혼자서 공부를 하면 다른 사람의 방해도 없이 편하게 공부할 수 있는 장점이 있지만 그게 바로 혼자 공부의 큰 단점이라는 생각이 늘 든다. 코딩 테스트를 대비하기 위해 틈틈이 알고리즘 문제를 풀고 있지만 혼자서는 내 코드가 알아보기 쉬운지, 효율성이 좋은지 도통 모를 수밖에 없다. 현재 내 상황은 알고리즘 개념은 어느정도 정리되었고, leetcode의 easy문제나 프로그래머스의 1~2단계 문제 정도는 풀 수 있는 상태여서 코딩 인터뷰 면접에 대비하기 위한 준비가 필요한 상황이었다. 혼자 공부하기보다는 스터디에 참여하면 좀 더 가독성도 좋고 효율 좋은 코드 작성 방법과 코딩 테스트를 볼 때 특별한 팁 ..

https://programmers.co.kr/learn/courses/30/lessons/1845 코딩테스트 연습 - 폰켓몬 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. programmers.co.kr 코드1. counting def solution(nums): kinds = {} limit = len(nums)/2 for n in nums: if n not in kinds: kinds[n] = 1 else: kinds[n] += 1 if len(kinds) >= limit: return limit else: return len(kinds) 코드2. set ..

굳이 왜 original tree랑 cloned tree 두개를 주는지 이해가 가지 않는다. 그냥 original tree를 주고 target 숫자를 탐색하라고 하면 되는거 아닌가?.. Find a Corresponding Node of a Binary Tree in a Clone of That Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com

기준점 상하좌우 탐색해서 같다면 newColor 값으로 바꿔주는 DFS 문제 [ 코드 1. 실패 ] def floodFill(self, image, sr, sc, newColor): limit_x = list(range(len(image)+1)) limit_y = list(range(len(image[0]))) l_color = image[sr][sc] def dfs(x, y): positions = [[x, y-1], [x, y+1], [x-1, y], [x+1, y]] if x in limit_x and y in limit_y: if image[x][y] == l_color: image[x][y] = newColor for i in range(len(positions)): if positions[i]..

배열 안 모든 숫자들을 K 이상으로 만들어주는 횟수를 구하는 문제 숫자들을 K이상으로 만들 수 없다면 -1을 return 한다. def solution(scoville, K): scoville = sorted(scoville) cnt = 0 while scoville[0] < K: scoville[0] = scoville[0] + scoville[1] * 2 scoville.pop(1) scoville = sorted(scoville) cnt += 1 if scoville[0] < K and len(scoville) == 1 : return -1 return cnt 제일 작은 숫자만 K이상이 된다면 끝나는 거라 sort 해주고 앞부분만 살펴보면 되겠다 싶었다. 제일 앞(0번)을 계..

[ 문제 풀이 ] Preorder는 DFS(Depth First Search) 탐색 방법 중 하나이고, DFS는 스택으로 주로 구현한다. Preorder는 3가지의 단계로 탐색을 한다. 1. Visit the Node 2. Traverse left 3. Traverse right [ Root -> Left -> right ] [ 루트 -> 왼쪽 노드 -> 오른쪽 노드 ] 순으로 순회를 한다. 한국어로 Preorder는 전위 순회, 이때 전은 먼저라는 뜻의 '前' 한글로 보면 바로 뭔지 체감이 안 가고 영어 단어를 보면 바로 이해가 간다. 영어로는 Preorder인데 Pre-order인 이유는 먼저 노드 방문부터 하고 그다음에 왼쪽, 오른쪽 탐색을 하기 때문 탐색보다 노드 방문을 먼저로 하기 때문이다. <..