honey_pot

# 500원, 100원 ,50원 ,10원으로 거스름돈 N원을 줄 때, 거슬러줘야 할 동전의 최소 개수를 구하기 n = int(input()) count = 0 # 큰 단위의 화폐부터 차례대로 확인 coins = [500, 100, 50, 10] for coin in coins: count += n//coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기 n %= coin print(count) 화폐의 종류만큼 반복을 수행한다. 화폐의 종류가 K개라고 할 때 시간 복잡도는 O(K) 거스름돈 문제가 그리디 알고리즘으로 해결되는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. => 가장 큰 단위의 화폐부터 가장 작은..

이 문제에서 큰 수의 법칙이란 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만든다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 특징이다. 예를 들어 순서대로 2,4,5,4,6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정한다. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과 6+ 6+6+5+6+6+6+5인 46이 된다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 예를 들어 순서대로 3,4,3,4,3으로 이루어진 배열이 있을 때 M이 7이고, K가 2이라고 가정하자. 이 경우 두 번째 원소에 해당하는 4와 네 번째 ..

정렬 알고리즘 정렬 알고리즘 평균 시간 복잡도 공간 복잡도 특징 선택 정렬 O(N^2) O(N) 아이디어가 매우 간단 삽입 정렬 O(N^2) O(N) 데이터가 거의 정렬되어 있을 때는 가장 빠름 퀵 정렬 O(NlogN) O(N) 대부분의 경우에 가장 적합하며, 충분히 빠름 계수 정렬 O(N+K) (K는 데이터 중에서 가장 큰 양수) O(N+K) (K는 데이터 중에서 가장 큰 양수) 데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만, 매우 빠르게 동작 정렬 알고리즘 핵심 아이디어 선택 정렬 가장 작은 데이터를 '선택'해서 정렬되지 않은 데이터 중에서 가장 앞쪽에 있는 데이터와 위치를 바꾸는 방법 삽입 정렬 데이터를 앞에서부터 하나씩 확인하며 데이터를 적절한 위치에 '삽입'하는 방법 퀵 정렬 기준 데..