![]()
다이나믹 프로그래밍(Dynamic Programming) (= 동적 계획법) 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 문제 해설 앞부터 점차 늘려가며 경우의 수를 구하면 됨 * 풀이 아이디어 : 점화식 (이전까지의 경우의 수) * (끝에 한 칸 남음) → 이전까지의 경우의 수 그대로 (이전까지의 경우의 수) * (끝에 두 칸 남음) → 이전까지의 경우의 수 두배 풀이 # 정수 N을 입력받기 n = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 1001 # 다이나믹 프로그래밍 진행(보텀업) # 계수 1부터 시작(인덱스) d[1] = 1 d[..
![]()
다이나믹 프로그래밍(Dynamic Programming) (= 동적 계획법) 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 문제 해설 문제의 점화식 (i - 1)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 X (i - 2)번째 식량창고를 털기로 결정한 경우 현재의 식량창고를 털 수 O * 왼쪽부터 (i - 3)번째 이하의 식량창고는 고려할 필요 X → 한 칸 이상 떨어진 식량창고는 항상 털 수 있음 즉, 왼쪽부터 순차적으로 최댓값을 업데이트 해오면, d[끝]에 다다랐을 때 해당 창고까지의 최댓값으로 업데이트 되어 있음 * 점화식에서는 첫째항을 잘 신경 써 주자 풀이 # 정수 N을..
![]()
다이나믹 프로그래밍(Dynamic Programming) (= 동적 계획법) 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 문제 해설 최소값을 구하기 위해서는 다 빼보고 나눠봐야 함!!! 근데 비효율을 방지하기 위해서 다이나믹 프로그래밍으로 구현 문제에서 요구하는 내용을 점화식으로 표현하면 위와 같다 이전까지의 최소값을 구한 후에 그 함수를 호출하는 횟수 +1을 하면 된다 풀이 # 정수 x를 입력받기 x = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 30001 # 다이나믹 프로그래밍 진행(보텀업) for i in range(2, x + 1)..
![]()
다이나믹 프로그래밍(Dynamic Programming) (= 동적 계획법) 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 2가지 방식 : 탑다운과 보텀업 + 메모리제이션 기법 다이나믹 : '프로그램이 실행되는 도중에' 피보나치 수열 이전 두 항의 합을 현재 항으로 설정하는 특징이 있는 수열 점화식 표현 - n번째 피보나치 수 = (n - 1)번째 피보나치 수 + (n - 2)번째 피보나치 수 - 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 4번째 피보나치 수 f(4)를 구하기 위해, 함수 f를 반복해서 호출 f(2)와 f(1)은 항상 1이기 때문에, f(1)과 f(2)를 만났을 때는 ..
![]()
문제 해설 전형적인 이진 탐색 & 파라메트릭 서치(Parametric Search) 유형의 문제 절단기 높이(탐색 범위)는 1부터 10억까지 정수 → 이진 탐색(순차 탐색은 시간 초과) * 파라메트릭 서치(Parametric Search) 최적화 문제를 결정 문제(yes or no)로 바꾸어 해결하는 기법 '원하는 조건을 만족하는 가장 알맞은 값 찾는 문제'에 주로 사용 ex) 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제 → 이진 탐색으로 결정 문제 해결하며 범위 좁힘 * 풀이 아이디어 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정 '현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인 조건의 만족 여부(yes or no)에 따라서 탐색 범위 좁혀서 해결 이진 탐색..
![]()
이진 탐색(Binary Search) 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 데이터 찾는 방법 탐색 범위를 절반씩 좁혀가며 데이터 탐색 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터 찾을 수 있음 위치 변수 3개(시작점, 중간점, 끝점) 사용 한 번 확인할 때마다 원소의 개수 절반씩 줄어듦 → 시간 복잡도 O(logN) (단계마다 2로 나누는 것과 동일) 문제 해설 여러 방법으로 해결할 수 있는 문제, 이진 탐색 알고리즘으로 풀이 매장 내 N개의 부품을 번호를 기준으로 정렬, M개의 찾고자 하는 부품이 매장에 존재하는지 검사 시간 복잡도 계산 - 부품을 찾는 과정 : 최악의 경우 O(M x logN)의 연산 - N개 부품 정렬 : 시간 복잡..
