글모음

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단계 문제 정도는 풀 수 있는 상태여서 코딩 인터뷰 면접에 대비하기 위한 준비가 필요한 상황이었다. 혼자 공부하기보다는 스터디에 참여하면 좀 더 가독성도 좋고 효율 좋은 코드 작성 방법과 코딩 테스트를 볼 때 특별한 팁 ..

[코드 1] regex 정규 표현식 사용 import re def solution(s): num_dic = {'zero' : '0', 'one' : '1', 'two' : '2','three' : '3', 'four' : '4','five' : '5', 'six' : '6', 'seven' : '7', 'eight' : '8', 'nine' : '9'} ans = '' option = re.compile("zero|one|two|three|four|five|six|seven|eight|nine|\d") nums = option.findall(s) for n in nums: try : n = num_dic[n] ans += n except : ans += n return int(ans) 특정 문자들을 찾아..

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

배열 안 모든 숫자들을 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번)을 계..

[ 코드 ] 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이므로 연산에서 제외하..