본문 바로가기

전체 글

 (172)
[알고리즘] 백준 1904 01타일 / python n = int(input()) _list = [0] * n _list[0] = 1 _list[1] = 2 for i in range(2, n): _list[i] = (_list[i-1] + _list[i-2]) % 15746 print(_list[n-1]) DP문제는 점화식을 세우자 f(n) = f(n-1) + f(n-2)
[알고리즘] 백준 1766 문제집 / 위상정렬, python import heapq n, m = map(int, input().split(' ')) num_list = [ [] for _ in range(n+1) ] indegree = [ 0 for _ in range(n+1) ] heap = [] result = [] for _ in range(m): a, b = map(int, input().split(' ')) num_list[a].append(b) indegree[b] += 1 for i in range(1, n+1): if indegree[i] == 0: heapq.heappush(heap, i) while heap: temp = heapq.heappop(heap) result.append(temp) for i in num_list[temp]: indeg..
[알고리즘] 백준 1715 카드정렬하기 / python import heapq n = int(input()) heap = [] for _ in range(n): num = int(input()) heapq.heappush(heap, num) result = 0 while len(heap) != 1: num1 = heapq.heappop(heap) num2 = heapq.heappop(heap) _sum = num1 + num2 result += _sum heapq.heappush(heap, _sum) print(result) 제일 작은 수끼리 비교할수록 최소가 되므로 최소힙을 이용한다
[알고리즘] 백준 1927 최소힙 / python import heapq import sys n = int(input()) h = [] for _ in range(n): num = int(sys.stdin.readline()) if num == 0: if not h: print(0) else: print(heapq.heappop(h)) else: heapq.heappush(h, num) heapq라이브러리를 이용해 힙을 구현 import heapq heapq.heappush(heap, item) heapq.heappop(heap) 시간초과 당해서 sys.stdin.readline()으로 바꿔씀!
[알고리즘] 백준 1991 트리순회 / python class Node: def __init__(self, data, left_node, right_node): self.data = data self.left_node = left_node self.right_node = right_node def pre_order(node): print(node.data, end='') if node.left_node != '.': pre_order(tree[node.left_node]) if node.right_node != '.': pre_order(tree[node.right_node]) def in_order(node): if node.left_node != '.': in_order(tree[node.left_node]) print(node.data, end=''..
[알고리즘] 백준 1939 중량제한 / python from collections import deque n, m = map(int, input().split(' ')) def bfs(c): queue = deque() queue.append(start) visited = [False] * (n+1) visited[start] = True while queue: x = queue.popleft() for y, weight in adj[x]: if not visited[y] and weight >= c: queue.append(y) visited[y] = True return visited[end] adj = [ [] for _ in range(n+1) ] max_weight = 1 min_weight = 1000000000 for _ in range(m)..
[알고리즘] 이진 탐색 (Binary Search) 이진 탐색 이란? 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 오름차순으로 정렬되어 있어야 한다 파이썬 코드 구현 def binary_search(data, search): print(data) if len(data) == 1 and search == data[0]: return True if len(data) == 1 and search != data[0]: return False if len(data) == 0: return False medium = len(data) // 2 if search == data[medium]: return True else: if search > data[medium]: return binary_search(data[medium+1:], sea..
[알고리즘] 퀵 정렬 (quick sort) 퀵 정렬 이란? 기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right)으로 모으는 함수를 작성 각 왼쪽(left), 오른쪽(right)은 재귀용법으로 다시 동일 함수를 호출하여 반복함 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 return 파이썬 코드 구현 def qsort(data): if len(data) item ] right = [ item for item in data[1:] if pivot
[알고리즘] 병합 정렬 (merge sort) 병합 정렬이란? 재귀용법을 활용한 정렬 알고리즘 리스트를 절반으로 자르고 비슷한 두개의 리스트로 나눈다 (나누고나누고..) 각 부분 리스트를 재귀적으로 합병정렬을 이용해 정렬한다 두 개 리스트를 다시 하나의 정렬된 리스트로 합병한다 ex) data_list = [1, 9, 3, 2] 먼저 [1,9]와 [3,2]로 나눈다 앞부분은 [1]과 [9]로 나눈다 정렬해서 합친다 [1,9] 뒷부분은 [3]과 [2]로 나눈다 정렬해서 합친다 [2,3] 비교하면서 [1,9]와 [2,3]을 합친다 1 2 : [1,2] 9 > 3 : [1,2,3] 9 : [1,2,3,9] 코드 구현 def merge(left, right): merged = list() left_point, right_point ..
[알고리즘] DP (동적계획법) DP(Dynamic Programming) 란? 입력 크기가 작은 부분문제들을 해결하고 난 후, 이것을 활용하여 큰 크기의 부분문제를 해결, 최종적으로 전체문제를 해결 상향식 접근법임 - 가장 최하위 해답을 구한 후, 이를 이용해서 상위 문제를 풀어가는 방식 Memorization 기법을 사용 - 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 해서 전체 실행속도 빠르게 재귀 vs 동적계획법 n을 입력받았을 때 피보나치 수열로 결과값을 출력하시오 #재귀호출 def fibo(num): if num

티스토리툴바