레퍼런스 마이닝

셸 정렬 기본 개념 "Donal L. Shell"이라는 사람이 제안한 방법으로, 삽입 정렬을 보안한 알고리즘이다. 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 빠르다는 것을 착안하였다. 삽입 정렬과 다르게 셸 정렬은 전체의 리스트를 한 번에 정렬하지 않는다. 셸 정렬 구체적인 개념 정렬해야 할 리스트의 각 k번째 요소를 추출해서 부분 리스트를 만든다. 이때 k를 "간격(gap)"이라고 한다. 각 회전마다 간격 k를 절반으로 줄인다. 즉, 각 회전이 반복될 때마다 하나의 부분 리스트에 속한 값들의 개수는 증가한다. 간격의 초기값 : 정렬할 리스트 사이즈 / 2 분할된 리스트의 개수는 gap과 같다. 간격은 홀수로 하는 것이 좋다. 간격을 절반으로 줄일 때 짝수가 나오면 +1을 해서 홀수를 만든다. 간격 ..

선택 정렬 기본 개념 제자리 정렬(in-place sorting) 알고리즘의 하나로, 입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법이다. 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 선택 정렬 구체적인 개념 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세번째 자료부터 마지막 자료까지 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다. 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회차에서는 두 번째 자료를 가지고 비교한다. 선택 정렬 알고리즘 예제 import java...

삽입 정렬 기본 개념 손 안의 카드를 정렬하는 방법과 유사하다. 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분의 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다. 삽입 정렬 구체적인 개념 삽입 정렬은 두 번째 자료부터 시작하여 그 앞의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 2|1, 3|2, 4|3 번째 자료와 비교한 후 삽입할 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다. 처음 Key 자료는 두 번째 자료부터 시작한다. 삽입 정렬 알고리즘 예제 import java.util.Ar..

버블 정렬 기본 개념 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘(인접한 2개의 레코드를 비교하여 크기를 순서에 맞게 서로 교환한다.) 선택 정렬과 기본 개념이 유사하다. 버블 정렬 구체적인 개념 버블 정렬은 1|2, 2|3, 3|4 ... 이런 식으로 마지막(마지막 -1) 번째 자료까지 비교하여 교환한다. 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 2번째 자료는 정렬에서 제외된다. 이런 식으로 정렬을 1회전 수행할 때마다 정렬에서 제외되는 자료가 하나씩 늘어난다. 버블 정렬 알고리즘 예제 import java.util.Arrays; public class BubbleSort { public stat..

알고리즘 문제는 아닐지라도 실타래를 한 올씩 풀어서 답을 찾는 문제를 풀어보자.이 문제를 만든 사람은 "상대성 이론"으로 유명한 앨버트 아인슈타인(Albert Einstein)이라고 알려져 있는데, 확인된 바는 없다. 사물을 기억할 수 있는 두뇌의 메모리 용량이 특별하게 큰 사람이 아니라면 아마 종이와 연필을 이용해서 논리의 흐름을 하나씩 따라가는 것이 필요할 것이다. 전제서로 색이 다른 5채의 집이 있다.각 집에는 출신 나라가 서로 다른 사람이 살고 있다.각 집주인은 5가지 다른 종류의 음료수를 마시고, 상표가 다른 담배를 피우며, 애완동물을 한 마리씩 키운다.음료, 담배, 동물은 일치하지 않는다. 주어진 정보를 토대로 "금붕어"를 기르는 사람은 누구일까? 조건1. 영국 사람은 빨간 집에서 산다.2. ..

프랙탈(fractal) 구조란 전체의 모습이 작은 부분에서 똑같이 반복되고 있는 경우를 뜻한다."재귀"란 동일한 함수에 대한 호출이 반복되는 것이로, 이진 트리의 모습을 가만히 생각해 보면 그것이 동일한 구조가 반복되는 프랙탈(fractal) 구조을 하고 있음을 알 수 있을 것이다.그런데 이진 트리에서 일부분을 따로 보면 그것이 여전히 이진 트리의 모습을 하고 있기 때문에 이진 트리는 프랙탈(fractal) 구조에 해당한다.말하자면 재귀란 프랙탈(fractal) 구조의 알고리즘적 반영이다.