학교 강의26 [Chapter5] 동적 계획 알고리즘 Dynamic Programming(DP) 알고리즘: 입력 크기가 작은 부분 문제들 해결 -> 그 해들을 이용해 보다 큰 크기의 부분 문제들 해결 -> 최종적으로 원래 주어진 입력의 문제 해결 - 최적성의 원리: 큰 문제를 해결하기 위해서는 작은 문제들이 해결되어야 한다.- 최적화 구조: 그런 구조를 가짐 그리디와 DP는 모두 최적성 원리&최적화 구조 가지고 있음그리디 알고리즘과 DP는 모두 최적해를 구하는 것이 목적그리디는 0-1의 경우 최적해 보장이 안 되지만, DP는 항상 최적해를 보장해준다. 그리디 알고리즘DP목적최적해 구하기(최적성 원리 & 최적화 구조)최적해 항상 보장?X(0-1의 경우 안 됨)O 분할 정복 알고리즘DP 알고리즘해 구하는 과정해 중복 가능 여부부분 문제의 해 중복 x부분 문.. 2025. 4. 28. [Chapter4] 그리디 알고리즘(2) 부분 배낭 문제 n개의 물건이 각각 1개씩 있고,각 물건은 무게와 가치를 가지고 있으며,배낭이 한정된 무게의 물건들을 담을 수 있을 때최대의 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제(단위 무게당 가치가 높은 물건을 담는 것이 유리하다.) 물건을 부분적으로 담는 것 허용(쪼개어 담는 것 허용)그리디 알고리즘으로 해결 따라서 주된 아이디어는1. 단위무게 당 가장 값나가는 물건부터 넣음2. 통째로 배낭에 넣을 수 없다면 배낭에 넣을 수 있을 만큼만 물건을 부분적으로 배낭에 담음 알고리즘FractionalKnapsack입력: n개의 물건, 각 물건의 무게와 가치, 배낭의 용량 c출력: 배낭에 담은 물건 리스트 L과 배낭 속의 물건 가치의 합 v1. 각 물건에 대해 단위 무게 당 가치를 계산2. 물건들을 .. 2025. 4. 27. [Chapter4] 그리디 알고리즘(1) - 그리디 알고리즘은 최적화 문제를 해결하는 알고리즘* 최적화 문제: 가능한 해들 중에서 가장 좋은 해(최소 비용, 최대 이익 등..)를 찾는 문제 - 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림 - 근시안적 선택: 입력 데이터 간 관계 고려x 수행 과정에서 순간순간 최솟값 또는 최댓값 가진 데이터 선택 - 일단 한 번 선택하면 -> 절대로 번복하지 x=> 대부분의 그리디 알고리즘들은 매우 단순, 제한적인 문제만이 그리디 알고리즘으로 해결 가능 동전 거스름돈 문제 남은 액수를 초과하지 않는 조건 하에 욕심내어 가장 큰 액면의 동전을 취하는 것 CoinChange입력: 거스름돈 액수 W출력: 거스름동 액수에 대한 최소 동전 수change=W, n500=n100=n50=n10=n1=0while(.. 2025. 4. 26. 선택 문제 n개의 숫자들 중 k번째로 작은 숫자 찾기 1. 최소 숫자를 k번 찾는다.: O(kn) 2. 숫자들을 정렬한 후, k번째 숫자를 찾는다.: O(nlogn) 이진 탐색: 입력을 1/2로 나눈 두 부분 중에 한 부분만을 검색 선택 문제 : 입력 숫자들 중 피봇 선택하여 분할(마치 퀵 정렬)- small group: 피봇보다 작은 숫자 그룹=> k번째 작은 숫자를 small group에서 찾기- large group: 피봇보다 큰 숫자그룹=> (k=|Small group|-1)번째로 작은 숫자를 large group에서 찾기* 피봇 = 1개이므로 Selection알고리즘은 분할 정복 알고리즘이기도 하지만 랜덤 알고리즘이기도 하다.=> 피봇을 랜덤하게 정하기 때문 피봇이 입력을 너무 한쪽으로 치우치게 분할하면=.. 2025. 4. 24. 이전 1 2 3 4 ··· 7 다음
