이번 시간에는 merge sorting에 대해서 배워보도록 하겠습니다. 저번 포스팅에서 설명했던 정렬 방식들(버블 정렬, 삽입 정렬, 선택 정렬) 은 가장 기본적인 수준의 정렬 방식들입니다. 그러나 이것들은 일반적으로 좋은 성능은 낼 수 없기 때문에 실제로 개발 시에는 잘 사용하지 않습니다. 앞으로 배울 Merge / Quick 정렬은 굉장히 중요하기 때문에 자세히 알아보도록 합시다. 1. Merge Sort(합병 정렬) 이란? merge sort와 다음 시간에 배울 quick sort가 정렬 알고리즘의 핵심이라고 할 수 있습니다. 하지만 중요한 만큼 이전에 배웠던 것들과는 다르게 매우 복잡하게 진행이 됩니다. 하나의 리스트를 두 개의 균등한 크기의 리스트로 분할하고 부분 리스트를 합치면서 정렬하여 최종..

이번 시간에는 삽입 정렬(Insertion Sorting)에 대해 배워 보도록 하겠습니다. 1. 삽입 정렬이란? 삽입 정렬은 특정 데이터를 리스트의 앞에서부터 이미 정렬된 서브 리스트의 값들과 비교하여 자신의 위치에 삽입하는 방식입니다. 이때 서브 리스트는 이미 정렬이 되어있기 때문에 서브 리스트 안에서도 자신이 삽입이 되어야 할 위치가 정해져 있을 것입니다. 그 위치에 데이터를 삽입하는 것이 바로 삽입 정렬입니다. 예를 들어, 손안의 카드를 정렬하는 방법과 유사하다고 생각할 수 있습니다. 새로운 카드를 기존의 정렬된 카드 더미(Deque) 속에서 올바른 자리를 찾아 삽입하고 새로 삽입될 카드의 수만큼 계속 반복해 가면서 전체 카드가 정렬되는 것입니다. 그렇다면 이런 의문을 가질 수 있으실 겁니다. 정렬..

이번 시간에는 정렬의 종류 중 버블 정렬에 대해서 배워보도록 하겠습니다. 1. Bubble Sort란? 그렇다면 첫 번째 정렬 방식인 Bubble Sort(버블 정렬)에 대해서 배워보도록 하겠습니다. 버블 정렬을 간략히 말하자면 다음과 같습니다. 서로 인접한 두 원소를 순회하며 검사하여 정렬하는 알고리즘 다음과 같은 예시를 통해 이해를 해 보도록 합시다. 아래에 정렬되지 않은 리스트가 있습니다. 우선 가장 앞에 위치한 두 개의 값을 비교하게 됩니다. 그래서 만약 정렬되어 있지 않다면, 즉 다시 말해서 왼쪽의 값이 오른쪽의 값보다 크다면 두 숫자를 바꿔주게 됩니다. 위 그림에서는 첫 비교가 5와 4이기 때문에 5와 4를 비교했을 때 왼쪽 값이 더 크기 때문에 두 값의 위치를 바꾸어 줍니다. 그 다음 5와 ..

그 동안 배운 자료구조를 통해 데이터를 다루는 방법에 대해 알아 보도록 하겠습니다. 이번 시간에는 정렬이란 무엇인가에 대해서 먼저 설명하겠습니다. 1. 정렬 알고리즘이란? 가장 기본적으로 자료 구조에 정의된 데이터들을 어떻게 정렬할 수 있는지에 대해서 알아봅시다. 정렬 알고리즘은 다양하게 존재하는데 우선 기본적인 종류는 다음과 같습니다. 1) 간단하지만(simple) 느린(slow) 방식 Bubble Sort Selection Sort Insertion Sort 2) 약간 복잡하지만 빠른 방식 Shell Sort Merge Sort Quick Sort Heap Sort 3) 아주 빠르지만 제한적으로만 사용 가능한 방식 Counting Sort Radix Sort Bucket Sort 4) 기타 필요에 따..

이번 시간에는 저번 시간(이진 탐색)에 이어서 점프 탐색(Jump search)에 대해서 알아보도록 하겠습니다. 1. 점프 탐색이란? Jump Search는 순차적으로 탐색하는 선형 탐색과는 달리 블록 단위로 이동(점프)하면서 탐색하는 알고리즘입니다. 이 역시도 이진 탐색과 마찬가지로 정렬된 배열에서만 사용할 수 있고, 한 칸씩 이동하는 것이 아니기 때문에 선형 탐색보다 적은 요소를 탐색할 수 있어 더 빠르게 탐색할 수 있습니다. 이 알고리즘은 선형 탐색보다는 빠르지만 이진 탐색 보다는 느립니다. 2. 점프 탐색 방식 배열을 블록(block) 단위로 나누어서 탐색을 진행하기 때문에 이 블록 사이즈 m의 크기를 구합니다. m의 최적 값은 다음과 같다. m = √n (n: 요소의 수) 한 블록에서 값을 탐색..

이번 시간에는 보간 탐색(Interpolation Search), 삼진 탐색(Ternary Search), 지수 탐색(Exponential Search)에 대해서 알아 보도록 하겠습니다. 이번 포스팅의 내용은 사실 코딩테스트를 준비하시는 분들이라면 이런게 있구나 하고 쓱 넘어가도 되는 파트입니다. 1. 보간 탐색 보간 탐색(Interpoation search)은 정렬된 리스트에서 범위를 좁혀 가면서 탐색해 나가는 알고리즘입니다. 보간 탐색은 전화부에서 이름(책의 항목이 정렬되는 키 값)을 검색하는 방법과 매우 유사합니다. 동작하는 방식이 이진 탐색과 거의 유사하지만 탐색 위치를 정하는 방식에 있어서 차이점이 존재하게 됩니다. 이진 탐색과 보간 탐색에서 탐색 위치를 정하는 공식은 다음과 같습니다. arr[..

이번 시간에는 이진 탐색(Binary Search)에 대해서 알아보겠습니다. 정렬 알고리즘을 배우기 앞서 이진 탐색 내용이 공부가 되어있으면 편하기 때문에 우선은 이진 탐색 먼저 알아봅시다. 1. Binary Search - 이진 탐색이란? 자료구조 및 알고리즘 강의 초반에 시간 복잡도를 설명하면서 이진 탐색에 대한 내용을 간단히 설명을 했었습니다. 다시 설명하자면 이진 탐색은 오름차순으로 정렬되어 있는 리스트 내에서 특정 값의 index를 찾는 알고리즘입니다. 만약 오름차순으로 정렬 되어 있지 않다면(혹은 내림차순) 반드시 다른 정렬을 사용해야 하는데 이때는 가장 단순하고 무식한 선형 탐색 방식을 사용합니다. 선형 탐색은 그저 배열의 처음 인덱스부터 마지막 인덱스 까지 순회하면서 일치하는 값이 될 때까..

1. Basic Concept 이 Data structure and algorithm에서는 자료구조와 알고리즘의 각 종류와 세세한 이론을 바탕 및 구현으로 한 내용이 주를 이루어 기술하는 카테고리입니다. 2. 시작하기 앞서... 자료구조와 알고리즘은 타 과목에 비해 중도포기하는 사람이 많은 과목이라고 합니다. 막히거나 답답한 부분이 자주 나올 수도 있지만 어려운 것이 정상이고 모두가 다 어려워 하기 때문에 기초부터 차근차근 배워나가면 충분히 소화할 수 있는 과목이기도 합니다. 이 카테고리(자료구조와 알고리즘 with Java) 에서는 모든 코드를 알고리즘 동작방식에 초점을 맞추어 java언어로 짰습니다. 파이썬을 이용한 자료구조와 알고리즘도 따로 포스팅 해 두었으니 파이썬을 이용한 자구알을 원하시는 분들..