문제 머쓱이는 태어난 지 6개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음을 최대 한 번씩 사용해 조합한(이어 붙인) 발음밖에 하지 못합니다. 문자열 배열 babbling 이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요. 조건 1. 1 ≤ babbling의 길이 ≤ 100 2. 1 ≤ babbling[i]의 길이 ≤ 15 3. babbling의 각 문자열에서 "aya", "ye", "woo", "ma"는 각각 최대 한 번씩만 등장합니다.즉, 각 문자열의 가능한 모든 부분 문자열 중에서 "aya", "ye", "woo", "ma"가 한 번씩만 등장합니다. 4. 문자열은 알..
문제 N가지 종류의 화폐가 있다. 이 화폐들을 최소한으로 사용해 합이 M원이 되도록 하고자 한다. M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하시오. 조건 입력조건 1. 첫째 줄에 N,M이 주어진다. 2. 이후의 N개 줄에는 각 화폐의 가치가 주어진다. 출력조건 1. 첫째 줄에 최소 화폐 개수를 출력한다. 2. 불가능할 때는 -1을 출력한다. 코드 n,m = list(map(int,input().split())) array=[] for i in range(n): array.append(int(input())) d=[10001]*(m+1) d[0]=0 for i in range(n): for j in range(array[i],m+1): if d[j-array[i]]!=10001: d..
문제 일직선으로 이어져 있는 식량 창고를 공격하여 한다. 각 식량 창고에는 정해진 수의 식량을 저장하고 있으며 선택적으로 약탈하여 식량을 빼앗을 에정이다. 서로 인접한 식량창고는 공격할 수 없다. 조건 입력 조건 1. 첫째 줄에 식량 창고의 개수가 주어진다. 2. 둘째 줄에 공백을 기준으로 각 식량창고에 저장된 식량 개수가 주어진다. 출력 조건 1. 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하라. 코드 n = int(input()) array = list(map(int,input().split())) d=[0]*100 d[0] = array[0] d[1] = max(array[0],array[1]) for i in range(2,n): d[i] = max(d[i-1],d[i-2]+arra..
문제 정수 X가 주어질 때 사용할 수 있는 연산은 다음과 같이 4가지이다. 1. 5로 나누어떨어지면, 5로 나눈다. 2. 3으로 나누어떨어지면, 3으로 나눈다. 3. 2로 나누어떨어지면, 2로 나눈다. 4. X에서 1을 뺀다. 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 이 때 연산을 사용하는 최소 횟수를 출력하시오. 입력 조건 1. 첫째 줄에 정수 X가 주어진다. 출력 조건 1. 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 내 코드 n = int(input()) d=[0]*(n+1) for i in range(2, n + 1): d[i] = d[i - 1] + 1 if i % 2 == 0: d[i] = min(d[i], d[i // 2] + 1) if i % 3 ==..
다이나믹 프로그래밍 컴퓨터를 사용한 문제 해결에 있어서, 일반적으로 효율적인 설계라 함은 연산속도나 메모리 공간을 줄여나가는 것이다. 그러나 본 장에서 배울 다이나믹 프로그램과 같이, 조금의 메모리 공간을 더 할애하여 비약적인 성능을 끌어낼 수 있는 경우도 존재한다. 이를 동적 계획법이라고도 부르며, 프로그래밍에서 사용되는 동적 할당의 의미와는 다르다는 것을 인지할 필요가 있다. 다이나믹 프로그래밍의 대표적인 유형으로는 피보나치 수열이 존재한다. 이전 두 항의 합을 현재 항으로 설정하는 특징을 갖는 수열이다. 수학적인 표현으로 점화식을 사용하지만, 프로그래밍에서는 배열이나 리스트를 사용한다. 파이썬에서는 리스트를 사용한다. 이를 구현하기 위해서는 재귀 함수를 사용하면 된다. 재귀 함수를 이용한 피보나치 ..
문제 절단기에 높이를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 그렇게 높이보다 많이 잘린 떡을 손님이 가져간다. 손님이 길이가 M인 떡을 요청했을 때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오 입력 조건 1. 첫째 줄에 떡의 개수 n과 떡의 길이 m이 주어진다. 2. 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 m 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 출력 조건 1. 적어도 m만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다. 내 코드 #1 탐색을 이용한 풀이 n,m = list(map(int,..
문제 동빈이네 전자 매장에는 부품이 N개 있다. 어느 날 손님이 M개 종류의 부품을 구매하기 위한 견적서를 요청하였다. 손님이 요구한 부품이 매장에 전부 있는지 확인하는 프로그램을 작성해보자. 입력 조건 1. 첫째 줄에 정수 n이 주어진다. 2. 둘째 줄에는 공백으로 구분하여 n개의 정수가 주어진다. (매장 내의 부품코드) 3. 셋째 줄에는 정수 m이 주어진다. 4. 넷째 줄에는 공백으로 구분하여 m개의 정수가 주어진다. (손님이 요구한 부품코드) 출력 조건 1. 첫째 줄에 공백으로 구분하여 각 부품이 존재하면 Yes를, 없으면 No를 출력한다. 내 코드 n = int(input()) a = list(map(int,input().split())) m = int(input()) b = list(map(in..
순차탐색 앞서 공부한 알고리즘을 구현하는 과정에서도 굉장히 빈번하게 사용한 탐색 방법이며, 굉장히 단순하다. 리스트 내의 특정 값을 찾기 위해 맨 앞부터 차례대로 확인하는 방법이다. def sequential_search(n,target,array): for i in range(n): if array[i] == target: return i+1 print("생성할 원소 개수를 입력한 다음 한 칸을 띄고 찾을 문자열을 입력하세요") input_data = input().split() n = int(input_data[0]) target = input_data[1] print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.") array = input().split() p..
1. 위에서 아래로 문제 하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오 입력 조건 1. 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1
선택정렬 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 다음으로 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. 2중 반복문을 사용하기 때문에 O(N**2)의 시간복잡도를 갖고 다른 정렬 알고리즘에 비해 다소 비효율적이다. array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_index = i for j in range(i+1,len(array)): if array[min_index] > array[j]: min_index = j array[i],array[min_index] = array[min_index],array[j] 삽입정렬 데이터를 하나씩 순회하며, 각 데이터를 적절한 위치에 삽입. 선택정렬에 비해 효..
