알고리즘
-
[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] 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] 큐(Que) 사용하기 - deque프로그래밍/파이썬 기초 2022. 9. 16. 09:07
1. 라이브러리 Import que는 collections에서 제공하는 deque를 통해 사용할 수 있다. from collections import deque 2. 코드 예시 # 큐 생성 que = deque([]) print(que) #==> deque([]) # 값 추가 que.append(1) print(que) #==> deque([1]) que.append(3) print(que) #==> deque([1, 3]) que.append(3) print(que) #==> deque([1, 3, 3]) # 좌측에 값 추가 que.appendleft(9) print(que) #==> deque([9, 1, 3, 3]) # 특정 값의 개수 반환 print(que.count(1)) #==> 1 # 큐 복..