Computer Science12 분할정복 (Devide and Conque)과 이진검색 분할정복 (Devide and Conque)과 이진검색 분할정복을 이용한 대표적인 정렬알고리즘인 병합정렬과 퀵정렬에 대해 알아볼것이다. 실제 전략 : 분할 => 정복 => 통합과정으로 이루어진다 (1). 병합정렬 정렬된 자료의 집합을 한 개의 정렬된 집합으로 만드는 정렬 알고리즘 ex) 6 2 5 1 => 26 15 => 1256 자료를 최소단위로 나눈후에 차례 소스코드 방법 1. append와 pop을 이용한 방법 # 분할과정 def merge_sort(arr): # 문제를 절반으로 나누는 함수 # print(arr) if len(arr) == 1: print(arr) return arr # 절반으로 나누어서 각각 별도의 정렬실행 mid = len(arr)//2 left = arr[:mid] right.. 2020. 6. 29. 탐욕알고리즘(greedy) 나만의 정리 탐욕알고리즘(greedy) 탐욕 알고리즘은 최적해를 구하는데 사용되는 근시안적인 방법 각 선택 시점에서 이루어지는 결정은 지역적으로는최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다 쉬운예) 지금 선택하면 사탕 10개를 주고, 1분뒤 선택하면 사탕 20개를 준다고할때, 탐욕알고리즘은 지금 선택하지만 이 선택이 최선은 아니다. 1. 탐욕알고리즘 동작과정 해 선택 현재 상태에서 부분 문제의 최적해를 구한뒤, 이를 부분해 집합에 추가한다. 실행 가능성 검사 새로운 부분해 집합이 실행가능한지를 확인한다. 곧, 문제의 제약 조건을 위반하지 않는지를 검색한다. 해 검사: 새로운 부분 해 집합이 문제의 해가 되는지를 확인한다. ex) 2370원을 거슬러주자!( 결.. 2020. 6. 29. 이전 1 2 다음