내가 기억하려고 만든 블로그 내가 기억하려고 만든 블로그

문제 설명, 조건 ● 정수 X가 주어졌을 때, 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지입니다. 1. X가 5로 나누어 떨어지면, 5로 나눕니다. 2. X가 3으로 나누어 떨어지면, 3으로 나눕니다. 3. X가 2로 나누어 떨어지면, 2로 나눕니다. 4. X에서 1을 뺍니다. ● 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 값을 1로 만들고자 합니다. 연산을 사용하는 횟수의 최솟값을 출력하세요. 예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값입니다. 26 -> 25 -> 5 -> 1 ● 입력 조건 첫째 줄에 정수 X가 주어집니다. (1

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

이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성 다음의 조건을 만족할 때 사용할 수 있습니다. 1. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다. 2. 중복되는 부분 문조 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 합니다. 피보나치 수열 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, .... # 피보나치 함수(Fibonacci Function)을 재귀함수로 구현 def fibo(x): if x == 1 or x == 2: return 1 re..

문제 설명, 조건 ● N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟구를 계산하세요. 예를 들어 수열 {1, 1, 2, 2, 2, 2, 3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다. ● 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 시간 초과 판정을 받습니다. ● 입력 조건 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다. (1

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

이진 탐색 라이브러리 bisect_left(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환 bisect_right(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환 값이 특정 범위에 속하는 데이터 개수 구하기 from bisect import bisect_left, bisect_right # 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수 def count_by_range(a, left_value, right_value): right_index = bisect_right(a, right_value) left_index = bisect_left(a, left_value) return right..

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시간 복잡도는 O(logN) 답안 예시 # 이진 탐색 소스코드 구현 (재귀 함수) def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: return binary_search(array, target, start, mid-1) # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 else: return ..

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