[범철/week2] 분할정복과 퀵정렬, 병합정렬

분할정복이란

분할정복이란 어떠한 문제를 더이상 나눌 수 없을 때까지 나누고, 그 나눠진 문제들을 각각  풀고 다시 합쳐서 전체적인 문제를 해결하는 알고리즘.

분할정복의 과정

1. 분할 : 문제가 분할이 가능한 경우 2개이상의 문제들로 나눈다.
2. 정복 : 분할한 문제들이 여전히 분할이 가능한 상태이면 계속 분할을 수행하며 분할이 불가능할경우 1에서 분할한 문제들을 푼다.
3. 결합 : 1,2 방법에서 분할한 문제들을 합쳐 원래 문제의 답을 얻는다.

분할정복을 사용하는 이유

한번에 풀기 어려운 문제를 분할함으로써 어려운 문제를 보다 쉬운 방법으로 해결할 수 있기때문.

병합정렬이란

전체의 원소를 더이상 쪼갤 수 없을때 까지 반으로 나눈뒤 병합하면서 정렬하는 방식.

병합정렬 작동방식

1. 정렬되지 않은 리스트를 반으로 나눠 비슷한 크기의 두 부분으로 나눈다.
2. 각 부분 리스트를 재귀적으로 합병정렬을 이용해 정렬한다.
3. 나눠진 리스트들을 다시 하나의 정렬된 리스트로 합병한다. 정렬결과는 입시배열에 저장된다.
4. 임시배열에 저장된결과를 원래배열에 복사한다.
5. 리스트의 길이가 1 이하일경우 이미 정렬된 것으로 본다.

퀵정렬이란

하나의 리스트에 Pivot을 설정하여 그 기준으로 두개의 비균등한 크기로 분할을하며 분할된 부분의 리스트를 정렬한다음 두개의 정렬된 리스트를 합병하여 전체가 정렬되게 만드는 방법이다.

퀵정렬 작동 방식

1. 분할 :입력배열을 Pivot을 기준삼아 비균등하게 두개의 배열로 분할한다.
2. 정복 :분할한 배열을 정렬한다. 배열의 크기가 충분히 작지않으면 순환호출을 이용하여 다시 분할정복방법을 적용한다.
3. 결합: 정렬된 부분의 배열들을 하나의 배열에 합병한다.
4. 순환호출이 한번 진행될 때 마다 최소한 하나의 Pivot은 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다. 

퀵정렬 알고리즘의 특징

장점

1. 속도가 빠르다.( 시간복잡도가 O(nlog2n)을 가지는 다른 정렬알고리즘과 비교했을 때도 가장빠르다.
2. 추가 메모리 공간을 필요로 하지 않는다.

   단점

   정렬된 리스트에 대해서는 퀵정렬의 분균형 분할에 의해 수행시간이 더많이걸린다.

귀류법이란

어떠한 명제를 증명하고자 할때 직접적인 증명이 어려운경우 결론이 아니라고 가정을하여 논리를 전개시켜 결국 모순이 나오는것을 보여 결론을 부정한 처음의 가정이 잘못되었음을 보이는 방법이다.

수학적귀납법과 반복문 불변식

수학적 귀납법

어떠한 결과를 증명하는데 사용되는 유용한 증명방법 중 하나 개별 사실들을 기초로하여 일반 결론을 끌어내는 논증방법이다.

순서

1. 단계나누기 : 증명하고 싶은 내용을 여러 단계로 나눔 
2. 첫 단계 증명 : 첫단계에서 증명하고 싶은 내용이 성립함을 보임
3. 귀납 증명 : 한 단계에서 증명하고 싶은 내용이 성립시 , 다음단계에서도 성립함을 보임.

증명방법 

1. 두 단계의 증명을 차례로 완성한다 ( 귀납기초, 귀납절차 )
2. P(1)이 참 임을 증명
3. 모든 임의 k (k>=1)에 대해, P(k) -> P(k+1)이 참임을 증명         즉, 임의 k에 대해 p(k)가 참이라 가정한뒤, 이 가정하에 P(k+1)도 참임을 보임

반복문 불변식 

반복문의 내용이 한 번 실행될 때마다 중간결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지 명시하는 조건이다.

1. 반복문 집입시에 불변식이 성립함을보임
2. 반복문 내용이 불변식을 깨뜨리지 않음을 보임
3. 반복문 종료시 불변식 성립하면 정답을 구했음을 보임

반복문 불변식 예

while (어떤조건){
    // 반복문 내용의 시작
    ...
    // 반복문 내용의끝
    // 불변식은 여기서도 성립해야한다.
}

• 2019 14