백준 5585번 거스름돈 문제 풀이 Python
문제 정의 거스름돈 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 입력: 물건의 가격 출력: 최소 잔돈의 개수 문제 해석 가지고 있는 6종류의 잔돈을 사용하여, 거스름돈의 개수가 가장 적게 하는 해를 구해야 함. 가장 적게 하기 위해서는 큰 단위의 돈을 최대한으로, 작은 단위의 돈을 최소한으로 전달해야 함. 잔돈을 내림차순으로 정렬한 뒤, 거스름돈을 나눈 몫을 잔돈의 개수에 더하고, 나머지를 새로운 거스름돈으로 할당함. ..
2023. 8. 10.
선형 검색, 이진 검색의 시간 복잡도
Big-O 표기법에 따른 결론부터 말하면, 선형 검색은 O(n), 이진 검색은 O(logn)이다. 선형 검색의 시간 복잡도 따져보기 def linear_search(array, elem): for i, e in enumerate(array):#1 if elem == e:#2 return i#3 return -1#4 #1, 시간 복잡도 O(n), 실행 횟수 n/2 (평균적으로 n/2개에 대해 수행, n에 비례하여 시간복잡도가 O(n)이 됨) #2, 시간 복잡도 O(n), 실행 횟수 n/2 #3, 시간 복잡도 O(1), 실행 횟수 1 #4, 시간 복잡도 O(1), 실행 횟수 1 Big-O 표기법은 최댓값을 채택하므로, 선형 검색의 시간복잡도는 O(n)이다. 이진 검색의 시간 복잡도 따져보기 def binar..
2023. 8. 10.