우노

문제 정수 X가 주어질때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다. 1) X가 5로 나누어떨어지면, 5로 나눈다. 2) X가 3으로 나누어 떨어지면, 3으로 나눈다. 3) X가 2로 나누어 떨어지면, 2로 나눈다. 4) X에서 1을 뺀다. 정수 X가 주어졌을때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 예를 들어, 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다. 26 - 1 = 25 25 / 5 = 5 5 / 5 = 1 입력 조건 첫째 줄에 정수 X이 주어진다. (1

들어가기 앞서, 일반적인 피보나치 재귀 함수 코드는 아래와 같습니다. def fibo(x): if (x == 1 or x==2): return x else: return fibo(x-1) + fibo(x-2) 만약, 위와 같은 피보나치 재귀 함수를 사용해 f(6)을 구한다면, f(3) 몇 번 호출될까요? f(3)은 아래와 같이, 3번 호출됩니다. f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(2) f(1) f(4) f(3) f(2) f(1) f(2) 따라서, 위와 같이 단순히 재귀 함수를 통해 매번 계산하는 방식은, 비효율적입니다. f(n) 에서 n 이 커질수록, 반복해서 호출하는 수가 많아지기 때문입니다. 피보나치 재귀 함수의 시간 복잡도는 O(2^n) 입니다. 따라서, 이..

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

문제 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 경적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N = 5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다. M = 3 [5, 7, 9] 이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다. 입력 조건 첫째 줄에..

문제 이미 정렬된 데이터 중에서 특정 원소가 몇 번째 위치에 존재하는지 출력하시오. 입력 예시 10 7 1 3 5 7 9 11 13 15 17 19 10 7 1 3 5 6 9 11 13 15 17 19 출력 예시 4 원소가 존재하지 않습니다. 풀이 탐색 시작 위치와 탐색 종료 위치를 반복적으로 좁혀가며, 중간값과 탐색값을 비교하면 됩니다. 또한, start 가 end 보다 커졌을때를 탐색 불가능으로 판단하면 됩니다. 예제 코드 # n(원소의 개수)과 search(찾고자 하는 값)를 입력 받기 n, search = map(int,input().split()) # 전체 원소 입력 받기 n_list = list(map(int,input().split())) def binary_search(start, end)..

문제 동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다 동빈이는 최대 K 번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야한다. N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K 번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오. 예를 들어 N = 5, K = 3이고, 배열 A와 B가 다음과 같다고 하자. 배열 A = [1, 2, 5, 4, 3] ..

문제 N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오. 입력 조건 첫 번째 줄에 학생의 수 N이 입력된다. (1

문제 하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오. 입력 조건 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1

선택 정렬 개념 정렬 되지 않은 데이터들 중 가장 작은 데이터를 선택하고, 정렬 되지 않은 데이터들 중 가장 왼쪽에 있는 데이터와 교환하는 알고리즘입니다. 특징 시간복잡도는 현재 데이터의 정렬 상태와 상관이 없습니다. 시간복잡도 항상 O(N^2) 매번, 정렬 되지 않은 데이터들을 비교 연산하며, 가장 작은 수를 찾습니다. N + (N - 1) + (N - 2) + … + 2 = N x (N-1 ) / 2 가장 작은 수를 찾아서 데이터를 교환합니다. N - 1 두 시간 복잡도를 더하면, 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 i..

문제 N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력 조건 첫째 줄에 두 정수 N, M(4 = 0 and ny < m): # 인접한 노드를 방문할 수 있는지 확인 if (check[nx][ny] == 0 and maze[nx][ny] == 1): # 방문할 수 있다면 큐에 삽입 queue.append((nx,ny)) ..