모카의 촉촉한 개발 로그

정수 X가 주어질 때 아래와 같은 4가지 연산을 사용할 수 있다. 첫번째, 5로 나누어 떨어지면 5로 나눈다 두번째, 3으로 나누어 떨어지면 5로 나눈다. 세번째, 2로 나누어 떨어지면 2로 나눈다. 네번째, x에서 1을 뺸다. 위 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 구하라. 입력예시) 26 출력예시) 1 나의 코드 못품.. 꽤나 많은 시간 그림과 함께 이것저것 생각해 보았지만 구현 실패...으악 정답 코드 X=int(input()) dp=[0]*(X+1) for i in range(2,X+1): dp[i]=dp[i-1]+1 if i%2==0: dp[i]=min(dp[i],dp[i//2]+1) if i%3==0: dp[i]=min(dp[i],dp[i//3]+..

중복되는 연산을 줄이자 컴퓨터를 사용하여 해결하기 어려운 문제들 중에는 최적의 해를 찾는 데 많은 시간이 필요하거나 많은 메모리 공간이 필요한 문제들이 있다. 컴퓨터는 계산 속도와 메모리 공간을 제한하고 있기 때문에 이러한 문제들을 해결하는 데에는 제약이 많이 있다. 그래서 우리는 속도와 메모리 공간을 최대화할 수 있는 효율적인 알고리즘을 작성해야 한다. 그러나 일부 문제의 경우에는 약간의 메모리 공간을 더 사용하여 계산 속도를 현저하게 높일 수 있는 방법이 있다. 대표적인 방법 중 하나는 이 장에서 다루는 동적 프로그래밍이다. 먼저 동적 프로그래밍의 기본 아이디어를 소개하고, 그 다음 동적 프로그래밍의 두 가지 방법 (탑다운과 바텀업)을 알아보자. 특히, 동적 프로그래밍에서 자주 사용되는 메모이제이션 ..

N개의 떡이 있을때 길이가 H인 절단기로 잘랐을 때 남은 떡 길이의 합이 적어도 M이 되게 하는 최대의 H를 찾아라. 입력 예시) 4 6 19 15 10 17 나의 코드 n,m=map(int,input().split()) arr=list(map(int,input().split())) MM=0 left=0 right=max(arr) while left0: temp+=(x-mid) if temp>=m : left=mid+1 MM=mid elif temp

N개의 물건 중에 M개의 물건들이 있는지 확인을 하라. (1

순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 보통 정렬되어있지 않은 리스트에서 데이터를 찾아야 할때 사용 시간복잡도는 O(N)이다. 이진 탐색 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 시작점,끝점,중간점으로 범위를 나누어 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 데이터를 찾는다 STEP 1 시작점과 끝점을 확인한 다음 둘 사이 중간점을 시작점과 끝점을 더한 값을 2로 나눈 값으로 한다. 다음으로 중간점[4]의 데이터와 8과 찾으려는 데이터 4를 비교한다. 중간점의 데이터 8이 더 크므로 중간저 이후의 값은 확인 할 필요가 없다. 그래서 끝점을 [4]의 이전인 [3]으로 변경 STEP 2 1과 ..

N개의 원소를 가진 서로다른 배열 A,B가 있을 때 K번 교환하여 A의 원소의 총합을 최대로 하라. 입력 예시) 5 3 1 2 5 4 3 5 5 6 6 5 출력 예시) 26 나의코드 n,k=map(int,input().split()) arrA=list(map(int,input().split())) arrB=list(map(int,input().split())) arrA.sort() arrB.sort(reverse=True) for i in range(k): arrA[i],arrB[i]=arrB[i],arrA[i] print(sum(arrA)) 각각의 배열을 입력 받은뒤 A배열은 오른차순으로 B배열은 내림차순으로 정렬한다. 그 후 k번 만큼 0번 인덱스 부터 스와프 해준다. 정답 코드 n, k = map(..

N명의 학생정보가 이름과 성적으로 입력이 될때 성적이 낮은 순서대로 학생의 이름을 출력하라. 입력예시) 2 홍길동 95 이순신 77 출력 예시) 이순신 홍길동 나의 코드 N=int(input()) arr=[] for i in range(N): arr.append(list(map(str,input().split()))) arr[i][1]=int(arr[i][1]) arr.sort(key=lambda x:x[1]) for i in range(N): print(arr[i][0], end=' ') 빈 배열에 str타입의 리스트로 입력을 받은 값들을 추가 하며 1번 인덱스인 성적을 다시 정수화 한다. 그 후 sort 함수의 key에 람다함수를 적용해 1번 인덱스를 기준으로 정렬한다. 정답코드 # N 입력 받기 n..

수열을 내림차순으로 정렬하는 프로그램을 만드시오. 입력 예시) 3 15 27 12 출력예시 ) 27 15 12 나의 코드 n=int(input()) arr=[] for _ in range(n): arr.append(int(input())) arr.sort(reverse=True) print(arr) 처음 수열의 크기를 입력 받은 뒤 그 크기 만큼 반복문을 돌며 리스트에 추가한다. 그후 한번에 sort함수로 reverse옵션으로 정렬을 한다. 정답 코드 # N 입력 받기 n = int(input()) # N개의 정수를 입력 받아 리스트에 저장 array = [] for i in range(n): array.append(int(input())) # 파이썬 정렬 라이브러리를 이용하여 내림차순 정렬 수행 arr..

계수정렬 - 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다 - 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다 - 모든 데이터가 양의 정수인 상황을 가정했을때, 데이터의 개수가 N개고 데이터 중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를 보장한다 - 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용가능하다 - 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야 하기 때문에, 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 계수 정렬을 사용할 수 없다 - 앞서 다룬 알고리즘과 달리 직접 데이터의 값을 비교한 뒤 위치를 변경하며 정렬하는 비교 기반의 정렬 알고리즘이 아니다 - 계..

퀵정렬 - 병합 알고리즘과 더불어 대부분의 라이브러리의 근간이 되는 가장 많이 사용되는 알고리즘이다. - 기준(피벗(Pivot))을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다 - 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러가지 방식으로 퀵 정렬을 구분하는데, 가장 대표적인 분할 방식인 호어 분할(Hoare Partition) 방식(리스트의 첫 데이터를 피벗으로 설정)을 기준으로 퀵 정렬을 이해해 보자. 피벗을 설정한 후 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환한다 ==> 위 과정을 반복하면 피벗에 대하여 정렬이 수행 이해의 편의를 위해 크게 3개의 파트로 나..