Gopythor

금광: 문제설명 n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요. 금광: 문제조건 금광: 문제 해결 아이디어 금광의 모든 위치에 대해 다음 세가지만 고려하면 됩니다. 왼쪽 위에서 오는 경우 왼쪽 아래에서 오는 경우 왼쪽에서 오는 경우 세 가지 경우 중에서 가장 많은 금을 가지고 있는 경우를 테이블에 갱신해주어 문제를..

Python/이코테 2022. 6. 26. 03:35

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

피보나치 수열은 다음과 같은 형태의 수열이며, 다이나믹 프로그래밍으로 효과적으로 계산할 수 있습니다. 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