huiyu's blog

관계기반 알고리즘 설계(1) 탐색기반 알고리즘 설계 : 컴퓨터의 빠른 연산 속도를 이용하여 짧은 시간에 가능한 해의 집합을 탐색하면서 최적의 해를 구하는 기술적인 방법(2) 관계기반 알고리즘 설계 : 해를 구하는 행위를 하나의 함수로 표현하고 이 함수들의 관계를 이용하여 해를 구하는 방법 - 문제의 정의 및 상태를 함수로 정의, 이 함수들 간의 관계를 점화식 혹인 이와 유사한 형태로 표현, 수학적 귀납법/점화식 등의 표현 기반 수학적 귀납법 - 자연수 n에 관한 명제 P(n)이 모든 자연수에 대해서 성립함을 증명하기 위한 수학의 증명법 중 한 방법 - 다음의 두가지 단계로 증명 1) P(1)이 성립함을 보인다. 2) P(k)가 성립한다고 가정하고 P(k+1)이 성립함을 보인다. - 수학적 귀납법을 이용한..

병합정렬은 전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬방식이다. 병합정렬 작동 순서1. 정렬한 데이터 집합을 반으로 나눈다.2. 나누어진 하위 데이터 집합의 크기가 2이상이면 이 하위 데이터 집합에 대해 1을 반복한다.3. 원래 같은 집합에서 나뉘어져 나온 하위 데이터 집합 둘을 병합하여 하나의 데이터 집합으로 만든다. 단 병합할 때 데이터 집합의 원소는 순서에 맞춰서 정렬한다.4. 데이터 집합이 다시 하나가 될 때까지 3을 반복한다. 5, 1, 6, 4, 8, 3, 7, 9, 2의 데이터를 정렬한다고 할 때 다음의 과정을 거쳐서 정렬을 한다.먼저 알고리즘의 1-2 과정을 반복해 데이터 집합을 나눈다.파란색 블록은 중간의 기준점을 의미 분할을 끝낸 뒤에는 '정복'을 수행, 합칠..

분할정복이란?문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나누어진 문제들을 각각 풂으로써 결국 전체 문제의 답을 얻는 알고리즘 분할 정복의 과정 1. 분할(Divide) : 문제가 분할이 가능한 경우, 2개 이상의 하위 문제로 나눕니다. 2. 정복(Conquer) : 하위 문제가 여전히 분할이 가능한 상태라면 하위 집합에 대해 1-을 수행합니다. 그렇지 않다면 하위 문제를 푼다. 3. 결합(Combine) : 2과정에서 정복된 답을 취한다. 분할정복법은 어떤 것에 적용하는가? 1. 문제를 작게 쪼개는 것이 가능한가?(Divide) 2. 쪼개진 문제들을 조합하여 문제의 답을 효율적으로 구할수 있는지(Merge & Conquer)