이번 포스팅에서는 재귀 알고리즘 기초에 대해서 알아보겠습니다. 1. 재귀 알고리즘 기초. 재귀 (Recursion) 함수란 특정 함수 내에서 자기 자신을 다시 호출하여 문제를 해결해나가는 함수입니다. 문제를 해결하기 위해 원래 범위의 문제에서 더 작은 범위의 하위 문제를 먼저 해결함으로써 원래 문제를 해결해 나가는 방식입니다. 일반 반복문을 통해 구현 가능한 기능은 재귀 함수를 통해 구현이 가능하며 반대로 재귀 함수로 구현 한 기능을 반복문으로 구현이 가능합니다. 재귀 함수는 함수 내에서 자기 자신을 계속 호출하는 방식이기 때문에 함수 안에 반드시 종료 구간이 되는 Base Case를 생각하며 코드를 구현해야 합니다. 아래 샘플 예제를 한 번 보겠습니다. public class Recursion_Test..

힙 정렬 (Heap Sort) ▶힙 정렬은 힙 자료구조를 기반으로 원소들을 정렬하는 방식을 의미합니다. 힙에 대한 기본 지식은http://lktprogrammer.tistory.com/69 에서 확인 할 수 있습니다. ■ 정렬 과정 ▶ 이번 게시글에서는 최대힙을 기준으로 설명을 하겠습니다. 힙의 기본은 완전 이진 트리의 형태이면서 부모 노드가 자식 노드보다 큰 값을 가지는 힙 성질을 만족하는 트리를 의미합니다. 따라서 최상위 노드인 루트 노드는 전체 원소 중에서 항상 최대값을 가지게 됩니다. 1. 배열에 저장 된 원소들을 최대힙으로 구성 2. 루트 노드에 존재하는 값을 가지고 오고, 가장 말단에 있는 노드를 루트 노드에 위치 시킵니다. 새로 자리 잡은 루트 노드에 대하여 다시 힙 성질에 맞게끔 배열을 조..

기수정렬 (Radix Sort) 기수정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘입니다. 기수정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요합니다. ■ 정렬 방식 1. 0~9 까지의 Bucket(Queue 자료구조의)을 준비한다. 2. 모든 데이터에 대하여 가장 낮은 자리수에 해당하는 Bucket에 차례대로 데이터를 둔다. 3. 0부터 차례대로 버킷에서 데이터를 다시 가져온다. 4. 가장 높은 자리수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복한다. 아래의 8개 데이터에 대하여 기수 정렬을 시도해 보겠습니다. 위의 그림과 같이 각 숫자에 해당하는 Queue공간을 할당하고 진행합니다. 먼저..

병합 정렬 (Merge Sort) 전체 원소를 하나의 단위로 분할한 후에 분할한 원소를 다시 병합하며 정렬해 나가는 방식입니다. ■ 정렬 방식 1. 정렬하고자 하는 데이터 집합을 반으로 나눈다. 2. 반으로 나누어진 하위 데이터의 개수가 2이상이면 1의 과정을 반복한다. 3. 같은 집합에서 나온 하위 데이터 둘을 정렬을 시도하면서 다시 병합합니다. 4. 원래의 데이터 집합이 될때까지 3의 과정을 반복합니다. - 분할과정 전체 데이터 크기(n=8)에서 반으로(n=4) 나눕니다. 이 과정에 대해서 데이터 집합의 크기가 1이 될 때까지 반복합니다. -병합과정 같은 집합에서 나온 하위 데이터집합 두개를 정렬과 동시에 병합을 시도합니다. 주목해야 할 점은 병합이 이루어진 데이터 집합에 대해서는 정렬이 이루어졌습니..

퀵 정렬 (Quick Sort) 기준이 되는 원소를 기준으로 하여 기준 원소보다 작거나 같은 값을 지닌 자료는 앞으로 큰 값을 진ㄴ 자료는 뒤로 가도록 하여 기준 원소를 중심으로 분할해가며 정렬을 진행하는 방식입니다. ■ 정렬방식 1. 기준이 되는 원소를 정합니다. 배열의 시작 원소를 pivot으로 설정합니다. 2. 좌우 인덱스를 지정합니다. 해당 인덱스는 다음을 의미합니다. - left : pivot 보다 큰 값을 찾으러 다니는 index - right : pivot 보다 작은 값을 찾으러 다니는 index - left_hold : pivot을 제외하고 정렬 대상의 시작점 - right_hold : pivot을 제외하고 정렬 대상의 끝점 3. left를 pivot보다 큰 값을 찾을 때 까지 이동합니다...

버블정렬 (Bubble Sort) 두 인접한 배열요소를 차례대로 검사를 하여 정렬을 하는 방식 ■ 정렬 방식 1. 배열의 가장 앞에서 인접한 두 개의 요소에 대하여 비교를 한다. (배열의 첫 번째 요소와 두 번째 요소) 2. 배열의 다음 인접한 요소(두 번째와 세번째를 비교를 한다.) 3. 배열의 끝까지 반복을 한다. 한 사이클이 끝나면 배열의 맨 끝에는 정렬된 요소 하나가 정렬이 된 채 자리잡는다. 4. 정렬이 된 마지막 요소를 제외한 나머지에 대하여 1,2,3 번 과정을 반복한다. 정렬이 된 상태 비교 원소 5 4 3 2 1 최초 정렬이 이루어지지 않은 상태의 배열입니다. 5 4 3 2 1 첫 번째 요소와 두 번째 요소를 비교합니다. 4가 더 작으므로 둘의 위치를 교환합니다. 4 5 3 2 1 다음 ..

삽입 정렬 (Insetion Sort) 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 입니다. ■ 정렬 방식 1. 배열의 첫 번째 요소는 정렬 된 상태라고 가정한다. 2. 배열의 두 번째 요소부터 앞에 정렬된 배열을 차례대로 비교하며 교환한다. 3. 최종적으로 자신의 위치에 맞는 위치에 삽입된다. 4. 다음 배열 요소에 대해서 같은 작업을 반복한다. : 정렬이 완료 된 상태 : 비교되는 배열 요소들 5 4 3 2 1 첫 번째 배열요소는 정렬이 완료된 상태라고 가정을 합니다. 5 4 3 2 1 두 번째 요소부터 비교를 시작합니다. 앞에 정렬된 첫 번째 요소와 비교를 하고 4가 더 작으므로 둘의 위치를 바꿔줍니다. 4..

선택 정렬(Selection Sort) 기존 위치에 맞는 원소를 선택하여 교환하는 방식 ■ 정렬 방식 1. 아직 정렬이 안된 리스트 중에 가장 앞에 원소를 최소값으로 설정 2. 가장 앞에 원소를 제외한 나머지 원소를 차례로 비교하고 최소값을 찾아감 3. 리스트 끝까지 비교 후 찾은 최소값을 가장 앞에 원소와 교환 4. 정렬이 안된 원소들을 가지고 반복 ■ 특징 - 최소값을 찾기 위한 비교횟수는 많지만 교환 횟수는 적다. - 데이터의 개수가 적을 때 좋은 성능을 발휘한다. - 시간복잡도 : O(n＾2) ■ 소스코드 (Source Code) public int[] Selection_Sort(int[] data,int num) { int min,tmp; for(int i=0;i

[알고리즘] 분할정복 방법 - 이진 탐색, 퀵 정렬 알고리즘 1. 분할정복(Divide-and-Conquer) 방법 - 대표적인 알고리즘 설계 기법 중 하나 - 대표적인 알고리즘 설계 기법 : 분할정복(divide-and-conquer) 방법, 동적 프로그래밍(dynamic programming) 방법, 욕심쟁이(greedy) 방법 1) 분할정복 방법의 원리 - 순환적(recursive)으로 문제를 푸는 하향식(top-down) 접근 방법 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 순환적으로 분할하고 분할된 작은 문제들을 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식 2) 분할정복 방법의 특징 - 분할된 작은 문제는 원래 문제와 성격이 동일하다. → 입력 크기만 작아짐 - 분할된 문..

[알고리즘] 알고리즘의 설계와 분석 - 시간 복잡도와 점근성능 1. 알고리즘 설계 기법 주어진 문제, 속성, 조건 등에 따라 매우 다양한 알고리즘이 존재할 수 있다. 따라서 일반적이고 범용적인 알고리즘 설계 기법은 존재하지 않지만 그 중 대표적인 설계 기법 세 가지를 꼽으면 다음과 같다. 분할 정복 방법(Divide-and-Conquer) 동적 프로그래밍 방법(Dynamic Programming) 욕심쟁이 방법(Greedy) 따라서 알고리즘을 공부하며 위 세 가지 설계 기법은 꼭 알아둬야 할것이다. 2. 알고리즘의 효율성 분석 알고리즘의 효율성 분석은 알고리즘 수행에 필요한 메모리 양과 수행 시간을 계산하는 것이다. 메모리 양 → 공간 복잡도(Space Complexity) = 정적 공간 + 동적 공간 ..