Limky 삽질블로그

퀵 정렬(Quick Sort) 정말 간략하게 핵심만 설명하겠습니다... ㅎㅎ 퀵 정렬은 기본적으로 분할정복입니다. 분할정복이기 때문에, 재귀적인 호출을 사용합니다. 우선 Pivot 즉 비교기준이 되는 값을 정하고, Left와 Right 각 2개의 비교대상을 정해서 비교하게 됩니다.Left는 Pivot 보다 작은 경우 더 이상 index가 증가하지 않고 진행을 멈춥니다. 만약 크다면, 계속 index를 증가시키면서 Pivot과 비교해나갑니다.Right는 Pivot보다 큰 경우 더이상 index가 감소하지 않고 진행을 멈춥니다. 만약 작다면, 계속 index를 감소시키면서 Pivot과 비교해나갑니다. 이 2case에 비교가 끝나고, 만약 Left의 index와 Right의 index가 교차하지 않고 Left..

이진탐색(Binary Search) 이진 탐색은 정렬된 상태에서 원하는 값이 어디에 있는지 찾는 탐색 방법 중 하나입니다. 우선 탐색 되지 않은 영역의 중간 값과 원하는 값이 일치하는지 체크하고, 2가지 경우에 따라 분기처리합니다. 우선... 1. 중간 값이 찾고자 하는 값보다 작은 경우 중간 값이 시작 기준이 되고 배열의 끝 값이 끝 기준이 되어 중간 값을 다시 도출합니다. 2. 중간 값이 찾고자 하는 값보다 큰 경우 중간 값이 끝 기준이 되고 배열의 시작 값이 시작 기준이 되어 중간 값을 다시 도출합니다. 위 2가지 경우에 분기 처리가 완료되면, 다시 찾고자 하는 값과 비교를 합니다. 찾고자 하는 값이 계속 도출되는 중간 값과 일치하는 경우 해당 탐색 루프를 벗어납니다. ㅎㅎ package Searc..

이진트리 (Binary Tree) 이번시간은 이진트리 (Binary Tree)에 대해서 알아보겠습니다. 정말 재미있는 녀석입니다. 이진트리가 되기 위해선 몇 가지 특징이 있습니다. 우선 이진트리는 가질 수 있는 자식노드의 최대갯수는 2개입니다. 또한 왼쪽 자식 노드는 부모 노드보다 값이 작고, 오른쪽 자식 노드는 부모 노드보다 값이 큽니다. 또한 이진트리에는 여러 종류가 존재하는데 완전이진트리 라는 것은 이상적으로 모든 노드에 2개씩 자식노드를 가지고 있는 형태입니다. 단 마지막 단계에서는 왼쪽에서부터 채워지는 형태를 취합니다. 포화이진트리는 마지막레벨은 단말노드이면서 나머지는 모두 자식이 2개씩 보유하고 있습니다. 뭐 이렇게 이진트리에 대해서 알아보았고, 이진트리를 순회하는 방법에는 지난시간 배웠던 전..

#단순 연결리스트 이번시간은 연결리스트에 대해서 알아보겠습니다. 먼저 리스트란, 자료구조의 한 종류로써 순차적으로 data를 저장하고 순차적으로 data를 처리하는데 유리합니다. 연결리스트에도 종류는 다양합니다. (단순,원형,이중) 하지만, 저는 연결리스트를 단순 연결리스트로 생각하고 설명하겠습니다. 리스트에는 배열리스트, 연결리스트가 있는데, 배열리스트는 얼마나 리스트가 생기고 줄어드는지 미리 파악할 수 없기에 단순히 미리 크기 값을 할당합니다. 따라서 메모리 누수가 발생할 가능성이 있습니다. 너무 큰 크기로 배열을 잡았다가, 실제 다 사용하지 않는다면 메모리가 낭비되기 때문이죠. 하지만 연결리스트는 필요시에만 메모리를 동적으로 할당하기 때문에 메모리 누수가 발생되지 않고 유연합니다. 또한, 배열리스트..

버블정렬 (Bubble Sort) 버블정렬에 대해서 알아보겠습니다. 버블 정렬은 자기자신 뒤에 오는 요소와 끊임없이 비교하면서, 오름차순일 경우 가장 큰 수가 뒤에서부터 정렬되는 정렬알고리즘입니다. 또한 마지막 Sorting시에는 첫번째 요소를 제외하고 모두 정렬됐기 때문에 자연스럽게 첫번째정렬됩니다. 그림을 보면서 이해해 봅시다. 우선 5와 3을 비교하고 5가 더 크기 때문에 교환합니다.다음 버블인 5와 4를 비교하고 5가 더 크기 때문에 교환합니다. 이제 5와 1을 비교하고 5가 더 크기 때문에 교환한 후 정렬 1회전을 종료합니다. 5가 가장 큰 수였기 때문에 차례대로 진행되는 모든 비교에서 이기고 결국 제일 큰 숫자의 자리인 끝의 자리를 차지하게 됩니다. 다음 2회전을 보겠습니다.3과 4를 비교하고..

선택정렬 (Select Sort) 선택정렬에 알아보겠습니다. 선택정렬은 정렬되지 않은 영역에서 가장 작은 값을 찾고, 정렬 대상 요소와 교환하는 방식이다. 간단히 제일 작은 요소부터 앞에서 부터 차례대로 줄을 서는 것이다. 그림으로 설명해보자. 3회전을 하는 과정이다. 우선 회색으로 칠해져 있는 것은 아직 정렬되지 않은 영역이다.정렬되지 않은 영역 첫번째 부터 차근차근 정렬을 하면 된다. 정렬되지 않은 요소 중 첫번째 요소인 5와 나머지 요소를 비교하여 가장 작은 요소의 index 위치를 찾는다. 찾은 후 교환해주면 된다. 위 원리를 코드로 나타내면 다음과 같다. package Sort; import java.util.Arrays; public class SelectSort { public static ..

삽입정렬(Insert Sort) 삽입정렬은 정렬한 부분과 정렬하지 않은 부분을 나눈 후 정렬할 대상인 대상을 정렬하지 않은 부분에서 차례대로 꺼내 정렬한 부분의 요소들과 차례대로 비교를 하면서 자신이 삽입될 인덱스를 찾는다. 이 과정에서 정렬된 부분의 요소들이 현대 정렬대상보다 클 경우 한칸씩 뒤로 밀리면서 정렬대상이 들어갈 공간을 마련해준다. (오름차순인 경우) 자 말로하니까 어렵다. 한 단계씩 그림으로 설명해보자. 파란색은 이미 정렬된 영역이라고 하자. 빨간영역은 정렬되지 않은 영역이다.삽입정렬은 기본적으로 0번째 요소는 정렬된 것이라 가정하고 시작한다. 우선 1회전 과정을 살펴보자. 0번째 요소는 정렬됐다고 가정했으니, 1번째 요소 값이 정렬할 대상이다. Temp에 1번째 요소 값인 2를 임시저장한..