Gopythor

N가지 종류의 화폐가 있습니다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 합니다. 이때 각 화폐는 몇 개라도 사용할 수 있습니다. 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분합니다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수입니다. M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하세요. 효율적인 화폐 구성: 문제조건 효율적인 화폐 구성: 문제 해결 아이디어 ai = 금액 i를 만들 수 있는 최소한의 화폐 개수 k = 각 화폐의 단위 점화식: 각 화폐 단위인 k를 하나씩 확인하며 ai-k를 만드는 방법이 존재하는 경우, ai=min(ai,ai-k+1) ai..

Python/이코테 2022. 6. 25. 23:25

1로 만들기: 문제 설명 정수 X가 주어질때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지입니다. 1) X가 5로 나누어떨어지면, 5로 나눕니다. 2) X가 3으로 나누어 떨어지면, 3으로 나눕니다. 3) X가 2로 나누어 떨어지면, 2로 나눕니다. 4) X에서 1을 뺀다. 정수 X가 주어졌을때, 연산 4개를 적절히 사용해서 1을 만들어야합니다. 이 연산을 사용하는 횟수의 최솟값을 출력하세요. X = 26일 경우 1. 26 - 1 = 25 2. 25 /5 = 5 3. 5 / 5 = 1 1로 만들기: 문제조건 내코드 X = int(input()) count = 0 while X != 1: if X % 5 == 0: X /=5 count +=1 elif X % 5

Python 2022. 6. 25. 17:06

개미 전사: 문제 설명 개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 합니다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있습니다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정입니다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있습니다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 합니다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자. {1, 3, 1, 5} 이때 개미 전사는 두 번째 식량창고와 네 번째 식량창고를 선택했을 ..

Python/이코테 2022. 6. 25. 04:23

이미 계산된 결과를 메모리에 저장하면 다음과 같이 색칠된 노드만 처리할 것을 기대할 수 있습니다. 실제로 호출되는 함수에 대해서만 확인해보면 다음과 같이 방문합니다. 피보나치 수열: 메모이제이션 동작 분석 메모이제이션을 이용하는 경우 피보나치 수열 함수의 시간 복잡도는 O(N)입니다. d = [0] * 100 def fibo(x): print('f(' + str(x) + ')', end=' ') if x == 1 or x == 2: return 1 if d[x] != 0: return d[x] d[x] = fibo(x - 1) + fibo(x - 2) return d[x] fibo(6) # f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)

Python/이코테 2022. 6. 24. 03:02

피보나치 수열은 다음과 같은 형태의 수열이며, 다이나믹 프로그래밍으로 효과적으로 계산할 수 있습니다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 점화식이란 인접한 항들 사이의 관계식을 의미합니다. 피보나치 수열을 점화식으로 표현하면 다음과 같습니다. a(n) = a(n-1) + a(n-2) a(1) = 1, a(2) = 1 피보나치 수열이 계산되는 과정은 다음과 같이 표현할 수 있습니다. 프로그래밍에서는 이러한 수열을 배열이나 리스트를 이용해 표현합니다. 피보나치 수열 피보나치 수열이 계산되는 과정은 다음과 같이 표현할 수 있음 n번째 피보나치 수를 f(n)라고 할 때 4번째 피보나치 수 f(4)를 구하는 과정은 다음과 같음 피보나치 수열: 단순 재귀 소스코드 (Pytho..

Python/이코테 2022. 6. 22. 23:53

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1,1,2,2,2,2,3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다. 정렬된 배열에서 특정 수의 개수 구하기: 문제 해결 아이디어 내코드 from bisect import bisect_left, bisect_right N, x = map(int, input().split()) arr = list(map(int,input().split())) def sorted(arr, target): left = bisect_left(a..

Python/이코테 2022. 6. 20. 02:57

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했습니다. 오늘은 떡볶이 떡을 만드는 날입니다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않습니다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰줍니다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단합니다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않습니다. 예를 들어 높이가 19, 14, 10, 17cm 인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것입니다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm입니다. 손님은 6cm만큼의 길이를 가져갑니다. 손님이 왔을 때 요청한 총 길이가 M일 때..

Python/이코테 2022. 6. 20. 01:52

순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해서 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다. O(logN) 이진 탐색의 시간 복잡도 단계마다 탐색범위를 2로 나누는 것과 동일하므로 연산횟수는 log₂N 에 비례합니다. 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개 가량의 데이터만 남습니다. 2단계를 거치면 8개 가량의 데이터만 남습니다. 3단계를 거치면 4개 가량의 데이터만 남습니다. 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장합니다. 이진 탐색 소스코드: 재귀적..

Python/이코테 2022. 6. 19. 22:04