프로그래밍/알고리즘
-
[Python] 배송비 절약 문제 동적프로그래밍 구현프로그래밍/알고리즘 2022. 9. 22. 11:09
이번 글에서는 파이썬 언어를 사용하여 배송비 절약 문제를 구현합니다. 이때 동적프로그래밍 기법을 사용합니다. 1. 배송비 절약 문제 물건의 개수, 배송가능한 무게제한, 물건의 무게와 가치가 주어졌을 때, 한번에 배송할 수 있는 최대의 물건 가치가 얼마인지 구하시오. 2. 코드 구현 주어지는 입력 정보 # 물건 개수 item_num = 5 # 배송 제한 무게 limit_weight = 10 # 물건의 무게 w_lst = [2,1,1,4,4] # 물건의 가치 v_lst = [34,686,668,678,560] 배송 가능 최대 물건 가치 저장 리스트 생성 D = [[0]*(limit_weight+1) for _ in range(item_num)] 물건별로 탐색하며 0~배송 제한 무게값 별로 최대 가치를 계산 ..
-
[Python] 최장 증가 부분 수열 구현하기프로그래밍/알고리즘 2022. 9. 22. 09:35
이번 글에서는 파이썬 언어로 최장 증가 부분 수열을 구현한다. 1. 최장 증가 부분 수열 증가 부분 수열이란, 기존의 수열에서 임의의 숫자들을 뽑았을 때 오름차순인 경우를 의미한다. 이때 연속하지 않아도 되며 뽑은 숫자들의 순서를 바꿀 수는 없다. 이렇게 생성될 수 있는 증가 부분 수열중에 가장 긴 길이를 가지는것이 최장 증가 부분 수열이다. 1 -1 2 0 1 1 2 3 -2의 수열이 있다면, 이중에서 -1 0 1 2 3 을 뽑아서 5의 길이를 가지는 최장 증가 부분 수열을 찾을 수 있다. 2. 동적 프로그래밍으로 구현 2.1 코드 예시1 # 제공된는 수열 input_lst = [1,-1,2,0,1,1,2,3,-2] # 동적 프로그래밍을 위한 기록 리스트 T = [0]*len(input_lst) # 첫..
-
[Python] bisect 함수를 통해 이진탐색 구현하기프로그래밍/알고리즘 2022. 9. 21. 22:08
이번 글에서는 파이썬 언어에서 bisect 함수를 통해서 이진탐색을 구현한다. 1. Bisect 함수 리스트 lst와 숫자 x가 있을 경우(lst는 정렬되어 있다고 가정한다), x가 lst의 어느 위치에 들어가야 정렬된 리스트가 유지되는지 반환한다. from bisect import bisect lst = [1,3,5,7,9] x = 7 # lst에 '7'이라는 값이 어디에 들어가야 정렬된 리스트를 유지하는지 bisect(lst,x) # 4라는 인덱스값을 반환함 2. Bisect의 네가지 케이스 2.1 동일한 값이 있을 경우 lst에 동일한 값이 있기 때문에 '7'의 다음 인덱스인 4를 반환한다. lst = [2,3,5,7,9] x = 7 bisect(lst,x) #=> 4 2.2 동일한 값이 없을 경우..
-
[Python] 최소신장트리(Minimum Spanning Trees, MST) 구현하기 by Prim프로그래밍/알고리즘 2022. 9. 21. 10:57
이번 글에서는 파이썬 언어를 사용하여 Prim방식 기반 최소신장트리를 구현한다. 1. 문제 가중치가 있는 무방향성 그래프가 주어졌을 때, 최소 신장 트리(MST, Minimum Spanning Tree)의 가중치의 합을 구하라 2. 파이썬 구현 기본적으로 주어지는 정보 import heapq node_n, edge_n = 4,6 graph_info = [(0,1,6),(0,2,7),(2,3,2),(1,2,5),(1,3,3),(0,3,9)] start_node = 0 # 탐색을 시작할 노드 주어진 그래프로부터 인접 딕셔너리 생성(인접 리스트로 해도 상관없음) 무방향 그래프이기때문에 node_a,node_b의 간선정보를 서로 넣어준다 # 인접 딕셔너리 생성 adj_dic=dict([(n,[])for n in..
-
[Python]이진탐색 재귀함수로 구현해보기(recursion binary search)프로그래밍/알고리즘 2022. 9. 20. 20:24
이번 글에서는 파이썬 언어를 사용하여 재귀함수 기반 이진탐색을 구현합니다. 1. 이진탐색으로 같은 값 찾기 문제 리스트와 목표값이 주어졌을 때 값이 존재한다면 인덱스를 반환하고 없다면 -1을 반환해라. 이때 리스트는 정렬되어 있다. def binary_search(lst,start_p,end_p,target): mid_p = (start_p+end_p)//2 # 중앙 포인트 생성 #전체 탐색후 값이 없다면 -1 반환 if start_p>=end_p: return -1 # 중앙값이 목표값이라면 해당 인덱스 반환 if lst[mid_p] == target: return mid_p # 목표값보다 중앙값이 크다면 시작값부터 중앙값 이전까지 다시 탐색 elif target < lst[mid_p]: return b..
-
[Python]다익스트라 알고리즘 구현(Dijkstra algorithm)프로그래밍/알고리즘 2022. 9. 20. 16:47
이번 글에서는 파이썬 언어를 사용하여 다익스트라 알고리즘을 구현합니다. 1. 다익스트라 알고리즘이란? 노드(node)간에 방향과 가중치를 가지는 간선(edge)으로 연결된 그래프에서, A지점에서 B지점으로 가는 최단거리를 구할 수 있는 알고리즘. 단, 간선의 가중치가 양수일 경우에만 사용 가능하다. 2. 구현 코드 우선순위 큐 준비 import heapq 그래프 인접 리스트 준비 node_n = 6 # (출발노드,도착노드,이동값) arr = [(0,1,7),(1,2,3),(2,0,1),(0,3,4),(2,3,5),(3,2,1),(3,4,8),(4,3,1),(2,4,2),(1,4,4),(4,5,2),(3,5,9)] adj_lst = [[] for x in range(6)] for sp, ep, cost i..
-
[Python]피보나치수열 구현 및 방법 비교: 재귀 함수,동적 프로그래밍 활용(Fibonacci numbers, recursion and dynamic programming)프로그래밍/알고리즘 2022. 9. 20. 16:16
이번 글에서는 파이썬 언어로 피보나치수열을 구현합니다. 이때, 재귀함수 및 동적 프로그래밍 방법을 모두 구현하여 실행시간을 비교합니다. 1. 재귀 함수로 구현(Recursion) def Fibo_recursion(n): if n == 0: return 0 elif n == 1: return 1 else: return Fibo_recursion(n-1) + Fibo_recursion(n-2) 2. 동적 프로그래밍으로 구현(Dynamic programming) def Fibo_dynamic(n): arr = [0]*(n+1) arr[1] = 1 for i in range(2,n+1): arr[i] = arr[i-1] + arr[i-2] return arr[n] 3. 실행시간 비교 # 재귀함수 실행 start..