성덕이의 개발공간

1. 문제 설명 2. 문제 조건 2가지(N)으로 총합 15(M)을 만들기 위해 2원화폐와 3원화폐 3가지(N)으로 총합 4(M)을 만들기 위해 3,5,7원 화폐 3. 문제 해결 아이디어 [Step 0] N = 3, M = 7이고, 각 화폐의 단위가 2, 3, 5인 경우를 확인 초기화 작업 먼저 각 인덱스에 해당하는 값으로 INF(무한)의 값을 설정 INF는 특정 금액을 만들 수 있는 화폐 구성이 가능하지 않다라는 의미 10,001을 사용가능 1~7까지는 만들수 없는 무작위의 값을 설정 인덱스(0) = 0원을 만들기 위한 최소한의 화폐 개수는 0 [Step 1] 첫 번째 화폐 단위인 2를 확인한다. 점화식에 따라서 다음과 같이 리스트가 갱신된다. 인덱스 2원을 만들 수 있는건 1개 인덱스 4원을 만들 수 ..

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 피보나치 수열 문제를 도식화한 것처럼 함수가 호출되는 과정을 그림으로 그리면 이와같다. 최적 부분 구조와 중복되는 부분 문제를 만족 1을 빼는 연산을 제외하고는 해당 수로 나누어떨어질 때에 한해 점화식을 적용할 수 있다. 4. 답안 x = int(input()) d = [0] * 30001 #바텀 업방식 for i in range(2, x + 1): #현재의 수에서 1을 빼는 경우 d[i] = d[i - 1] + 1 #현재의 수가 2로 나누어 떨어지는 경우 if i % 2 == 0: d[i] = min(d[i], d[i // 2] + 1) #현재의 수가 3으로 나누어 떨어지는 경우 if i % 3 == 0: d[i] = min(d[i], d[i /..

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 N = 4일 때, 다음과 같은 경우들이 존재할 수 있다. 식량을 선택할 수 있는 경우의 수는 다음과 같이 8가지이다. 7번째 경우에서 8만큼의 식량을 얻을 수 있으므로 최적의 해는 8이다. i는 인덱스이므로 0부터 시작한다. 창고 0만 있을 때는 a(o) = 1이 최대 값 창고 0,1만 있을 때는 a(1) = 3이 최대 값 창고 0,1,2만 있을 때는 a(2) = 3이 최대 값 모든 창고일때는 창고1, 3 = 8이 최대 값 이렇게 DP 테이블 값을 재정의한다. 왼쪽부터 차례대로 식량창고를 턴다고 했을 때, 특정한 i번째 식량창고에 대해서 털지 안 털지의 여부를 결정 위 2가지 경우 중에서 더 많은 식량을 털 수 있는 경우를 선택하면 된다. 즉, i..

메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록한다. 다이나믹 프로그래밍(동적 계획법)의 구현은 일반적으로 두 가지 방식(탑다운과 바텀업)으로 구성 동적(Dynamic)이란? 자료구조에서 동적 할당(Dynamic Allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법 다이나믹 프로그래밍에서 다이나믹은 별다른 의미가 없다. 1. 다이나믹 프로그래밍의 조건 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 중복되는 부분 문제(Overlapping Subproblem) ..

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 시간 복잡도를 O(logN)으로 동작하는 알고리즘을 요구하므로 선형 탐색이 아닌 이진 탐색을 수행 데이터가 정렬되어 있기 때문에 특정 값이 등장하는 첫 번째 위치와 마지막 위치를 찾아 위치 차이를 계산하여 답을 도출 4. 소스 코드 from bisect import bisect_left, bisect_right # 값이 [left_value, right_balue]인 데이터의 개수를 반환하는 함수 def count_by_range(a, left_value, right_value): right_index = bisect_right(a, right_value) left_index = bisect_left(a, left_value) return righ..

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 적절한 높이를 찾을 때까지 이진 탐색을 수행하여 높이 H를 반복해서 조정 현재 이 높이로 자르면 조건을 만족할 수 있는가?를 확인한 후 탐색 범위를 좁히기 절단기의 높이는 0~10억까지 정수 중 하나 큰 범위는 대부분 이진 탐색 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 나올 동안 중간점의 값을 기록한다. [Step 1] 시작점: 0, 끝점: 19, 중간점: 9(자르고자 하는 높이) 이때 필요한 떡의 크기: M = 6이므로, 결과 저장 탐색 범위는 0~19이다 중간점은 나누면 9가 될 것이다. 잘린 떡의 길이는 모두 25가 나온다. 중간점의 9를 기록하고 중간점을 오른쪽으로 높이면서 또 확인한다. [Step 2] 시작점: 10, 끝점: 19,..

1. 새로 알게된 것 (파이썬 이진 탐색 라이브러리) bisect_left(a, x) 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환 bisect_right(a, x) 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환 a라는 배열에 4가 있는 인덱스의 바로 왼쪽 a라는 배열에 4가 있는 인덱스의 바로 오른쪽 from bisect import bisect_left, bisect_right a = [1,2,4,4,8] x = 4 print(bisect_left(a,x)) print(bisect_right(a,x)) #출력 결과 2 4 2. 값이 특정 범위에 속하는 데이터 개수 구하기 from bisect import bisect_left, bisect_rig..

1. 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 2. 이진 탐색 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정 3. 이진 탐색 동장 예시 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시 [Step 1] 인덱스 시작점 : 0, 끝점 : 9, 중간점 : 4 중간지점은 인덱스 4.5인데 소수점 이하는 제거하므로 4즉, 인덱스 4번째를 중간점으로 선택 중간점과 찾고자하는 값(4)를 비교한다. 오른쪽은 필요가 없을 것이다. [Step 2] 시작점: 0, 끝점: 3, 중간점: 1 끝점은 중간점 바로 앞으로 바뀌고 다시 시작한다. 중간점이 찾고자 하는쪽의 오른쪽에 있..

1. 문제 설명 2. 문제 조건 3. 문제 해결 아이디어 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체 A에 대하여 오름차순 정렬, B에 대하여 내림차순 정렬 각 배열의 첫 번째 인덱스부터 차례로 확인하면서 A원소가 B의 원소보다 작을 때만 교채 최악의 경우 O(NlogN)을 이용 4. 답안 N, K = map(int, input().split()) #N, K 동시에 입력 count = K result = 0 A_array = list(map(int, input().split())) B_array = list(map(int, input().split())) A_array.sort() B_array.sort(reverse = True) for i in range(N): fo..

선택 정렬 알고리즘 특징 키 값을 찾아서 비교한다. 구현이 매우 쉽다. 삽입 정렬 알고리즘 특징 데이터가 거의 정렬되어 있을 때 가장 빠르다. 자신의 위치를 찾아서 계속해서 삽입한다. 퀵 정렬 알고리즘 특징 Pivot 값을 정한 후 계속해서 정렬한다. 충분히 빠른 속도를 가진다. 계수 정렬 알고리즘 특징 데이터의 크기가 한정되어 있는 경우에만 사용한다. 그만큼의 배열, 리스트가 필요하다. 매우 빠른 속도를 가지고 있다.