반응형 코딩테스트/파이썬68 [프로그래머스] 야근 지수 (level3) (파이썬) 문제 접근 정렬 된 최대 값이 필요하므로 우선순위큐로 표현해야 된다고 생각하였다 가장 빠른 삽입 삭제 시간복잡도 N(데이터) logN을 가진 힙(heap)을 이용하여 문제를 접근 풀이 코드 # 19:10 ~ 19:30 # https://programmers.co.kr/learn/courses/30/lessons/12927?language=python3# import heapq def solution(n, works): answer = 0 h = [] # 우선순위 큐 최대힙으로 저장 for value in works: heapq.heappush(h, -value) while n > 0: # 힙에서 하나 꺼내어 다시 넣음 work = -heapq.heappop(h) if work != 0: heapq.hea.. 2021. 6. 28. [프로그래머스] 더 맵게 (level2) (파이썬) 문제 접근 힙의 특징을 이용하여 문제를 푼다. 문제 해결 # 09:30 ~ 09:55 # https://programmers.co.kr/learn/courses/30/lessons/42626?language=python3 # 정렬 시간 복잡도 NlogN, 삽입 삭제 logN # heapq.heappush() 삽입 # heapq.heappop() 꺼냄 import heapq def solution(scoville, K): # 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우 -1 return answer = -1 count = 0 flag = True h = [] for value in scoville: heapq.heappush(h, value) # pop 하면서 스코빌 지수와 체크 하며 섞을지 .. 2021. 6. 28. [프로그래머스 ] 짝지어 제거하기 (level2) (파이썬) 문제 접근 스택에 쌓으면서 짝이 지어지면 바로바로 제거하는 방식을 선택하였다 풀이 코드 # https://programmers.co.kr/learn/courses/30/lessons/12973?language=python3 # 9:40 ~ 09:52 def solution(s): answer = -1 stack = [] for i in s: if len(stack) != 0: if stack[-1] == i: stack.pop() else: stack.append(i) else: stack.append(i) if len(stack) == 0: answer = 1 else: answer = 0 return answer 2021. 6. 21. [프로그래머스] Summer/Winter Coding(~2018) 소수 만들기 (파이썬) 문제 접근 소수의 판별을 할 줄 알면 풀 수 있던 문제 에라토스테네스의 체를 기억하자 2021.03.08 - [Problem-solved (코딩테스트 문제풀이)/python] - [백준] 소수 구하기 1929 (파이썬) # Summer/Winter Coding(~2018) 소수 만들기 import math from itertools import combinations def solution(nums): # 에라토스테네스의 체를 이용하여 해당 범위의 소수를 판별한다. # 1~1000 사이의 자연수를 3개 고르므로 단순히 합의 최대값을 3000이라고 설정하였다 n = 3000 array = [True for i in range(n+1)] for i in range(2, int(math.sqrt(n) + 1).. 2021. 6. 18. [프로그래머스] 예상 대진표(level 2) (파이썬) 문제 접근 수학 문제 a,b 중 b가 큰것이 보장된다면 둘이 만나는 경우는 b가 2의 지수이면서 b - 1이 a일 때 뿐이다. 코드 # 13:45 ~ 14:10 import math def solution(n,a,b): if a > b: a, b = b, a cnt = 1 while True: if b % 2 == 0 and b - a == 1: break a = math.ceil(a/2) b = math.ceil(b/2) cnt += 1 return cnt 노트 2021. 5. 19. [프로그래머스] 위장(level 2) (파이썬) 접근 경우의 수를 잘 생각해야 하는 문제 최소한 1개의 옷을 입어야 하므로 모두 안입은 경우를 -1 해야 한다. 각각의 경우의 수에서 옷의 종류는 독립변수로 작용한다. # 위장 level2 # 3시 57분 ~ 4시 43분 # 경우의 수 문제 종류가 2인 경우 00, 10, 01, 11 2*2 -1(00) def solution(clothes): answer = 1 hmap = dict() for i in range(len(clothes)): if clothes[i][1] in hmap.keys(): hmap[clothes[i][1]] = hmap[clothes[i][1]] + 1 else: hmap[clothes[i][1]] = 1 value_list = hmap.values() for value in .. 2021. 5. 18. [프로그래머스] 다음 큰 숫자(level 2) (파이썬) 접근 2진수로 변환 하는 함수를 알아야했다 (bin이나 format 방식을 이용한다) 숫자를 하나 씩 늘려가며 일치할 시에 반복문을 빠져나오면 된다. # 다음 큰 숫자 # https://programmers.co.kr/learn/courses/30/lessons/12911 # 3시 8분 - 3시 25분 (17분) def solution(n): b_origin = str(format(n, 'b')) b_count = b_origin.count('1') num = n while True: num += 1 v = str(format(num, 'b')) if v.count('1') == b_count: return num def solution2(n): cnt = format(n, 'b').count('1') .. 2021. 5. 18. [프로그래머스] 기능 개발(level 2) (파이썬) 문제 접근 간단한 문제로 생각했으나 문제를 잘 못 파악한 것이 코드를 잘못작성하는 것으로 이어졌다. 문제파악을 잘하는 것이 중요할 것 같다 # https://programmers.co.kr/learn/courses/30/lessons/42586?language=python3 # 내가 푼 것 (1차) from collections import deque import math from collections import deque import math def solution(progresses, speeds): answer = [] q = deque() time = 0 # 누적된 시간을 나타냄 for i in range(len(speeds)): day = math.ceil((100 - progresses[i].. 2021. 5. 10. [프로그래머스] 주식가격(level 2) (파이썬) 문제접근 스택 큐 유형이며 level2 문제였으나 이중 반복문으로 충분히 풀 수 있을 것 같아 이중반복문으로 구현하였다. 스택 큐 쪽으로는 문제접근 방식이 생각나지 않는다. https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr def solution(prices): answer = [0] * len(prices) for i in range(len(prices)): for j.. 2021. 5. 7. [백준] 01타일 1920 (파이썬) 문제접근 n에 대한 예시가 여러개 주어진 것으로 봐서 규칙이 있을거라 생각하였다. 피보나치 수열과 동일한 규칙을 찾았고 규칙에 맞게 점화식을 풀면 된다. 스케치 코드 # 수 찾기 import sys input = sys.stdin.readline def binary_search(start, end, target, arr): while start 2021. 3. 19. [백준] N과 M (1) 15649 (파이썬) 문제 접근 n 개중에서 m개를 뽑는데 순서를 고려해서 뽑는다 = 순열 문제 파이썬 라이브러리를 사용해서 쉽게 풀었다. 2021.03.15 - [Algorithm & Data structure] - [알고리즘] 순열 (Permutation)과 조합(Combination) (파이썬) [알고리즘] 순열 (Permutation)과 조합(Combination) (파이썬) 순열과 조합 경우의수 한 번의 시행에서 일어날 수 있는 사건의 가지 수 재귀 함수, 반복문을 이용해서 직접 구현 가능하지만 실제 코딩테스트에서 직접 구현하기는 매우 번거롭다 순열 (Permutati seongbindb.tistory.com 코드 # N과 M from itertools import permutations n,m = map(int,i.. 2021. 3. 19. [백준] 수 찻기 1920 (파이썬) 문제접근 어떤 수열에서 특정 값이 있는지 없는지를 찾는데 수가 크다면 이진탐색을 고려해 봐야했다 2021.03.17 - [Algorithm & Data structure] - [알고리즘] 이진탐색 (이분탐색) # 수 찾기 import sys input = sys.stdin.readline def binary_search(start, end, target, arr): while start 2021. 3. 19. [백준] 곱셈 2588 (파이썬) 문제접근 1안: 방식은 음 뭔가 복잡하다 2안: 문제 조건이 3자리 자연수를 입력값으로 준다고 명시돼 있으므로 쉽게 풀 수 있다 # 곱셈 a = int(input()) b = input() b = list(b) b.reverse() zero = '' arr = [] for i in b: c = str(a*int(i)) arr.append(c+zero) zero = zero + '0' print(a*int(i)) total = 0 for j in arr: total = total + int(j) print(total) # 2안 # 문제 조건이 3자리 자연수를 준다고 명시돼 있으므로 조금더 쉽게 풀 수 있다. n = int(input()) m = int(input()) m = str(m) print(n * .. 2021. 3. 18. [백준] [백트래킹] N-Queen 9663 (파이썬) 문제 접근 처음 보는 유형이 었고 공부를 해도 잘 몰라서 유투브 '코드랩' 님의 백트래킹 강의를 참조하였다 백트래킹 기본 개념 2021.03.17 - [Algorithm & Data structure] - [알고리즘] 백트래킹 [알고리즘] 백트래킹 백트래킹 DFS (재귀) + 가지치기 (break or continue) 모든 경우의 수를 탐색하는 DFS의 기본개념과 다르게 DFS이면서 break나 continue등으로 가지치기를 해서 경우의 수를 줄이면 백트래킹이라고 한다. 대 seongbindb.tistory.com 코드 # N - Queen # 참조 코딩랩 import sys input = sys.stdin.readline def queen(row, col): for i in range(row): #.. 2021. 3. 17. [백준] [다익스트라 알고리즘] 최단경로 1753 (파이썬) 문제접근 주어진 V E의 범위가 큰 편이기 때문에 시간 복잡도를 고려했을 때 다익스트라 알고리즘을 적용해서 풀어야 한다고 파악했다. 또한 특정지점 (주어진 시작점)에서 다른 지점으로 까지 가는 최단 경로를 구하기 때문에 모든 정점에 대해 최단 경로를 알 수 있는 플루이드 워셜 알고리즘 시간복잡도와 문제를 보았을 때 적합하지 않았다. 최단 경로 알고리즘에 대해 정리한 글을 참조하면 도움이 될 것 같다 2021.03.17 - [Algorithm & Data structure] - [알고리즘] 최단경로 알고리즘 (다익스트라, 플루이드워셜) [알고리즘] 최단경로 알고리즘 (다익스트라, 플루이드워셜) 최단 경로 알고리즘 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 다익스트라 최단 경로 알고리즘.. 2021. 3. 17. 이전 1 2 3 4 5 다음 반응형
