이번 시간에는 저번 시간(이진 탐색)에 이어서 점프 탐색(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를 찾는 알고리즘입니다. 만약 오름차순으로 정렬 되어 있지 않다면(혹은 내림차순) 반드시 다른 정렬을 사용해야 하는데 이때는 가장 단순하고 무식한 선형 탐색 방식을 사용합니다. 선형 탐색은 그저 배열의 처음 인덱스부터 마지막 인덱스 까지 순회하면서 일치하는 값이 될 때까..

이번 시간에는 해시에 대해 배워보겠습니다.(내용이 상당히 많으니 정말 알찬 포스팅이 될 것 입니다 ^.^) 해시 자체는 어려운 개념이 아니나 이를 구현할 때는 노드와 LinkedList를 이용하여 구현하기 때문에 이전 과정이 복습이 잘 된 상태여야 이해가 더 잘 될 것입니다. LinkedList를 참고하기 위해서는 아래 링크를 참조하세요. [CS 지식/자료구조와 알고리즘(Java)] - [자료구조] LinkedList(연결 리스트) 이론 및 구현 [자료구조] LinkedList(연결 리스트) 이론 및 구현 이번 포스팅은 지난 포스팅에 이어 ArrayList에서 했던 것과 마찬가지로 LinkedList에서의 데이터 삽입, 데이터 삭제, 리스트 검색 등의 기능에 대해서 다뤄보도록 하겠습니다. LinkedLi..

이번 시간에 배워 볼 내용은 Queue(큐)입니다. 1. 큐(Queue)란? queue는 지난시간(링크 참조)에 배운 스택과 달리 선입선출(First-In-First-Out-FIFO)의 구조를 가지고 있습니다. 즉, 가장 먼저 들어간 것이 가장 먼저 나오게 되는 구조인 것입니다. 선입선출(FIFO)의 예로는 순서가 보장된 처리를 가지고 있는 '사용자가 몰리는 서버'와 같은 경우가 있습니다. 대학생이 수강신청을 하러 인터넷에 들어간 경우나 내가 좋아하는 가수의 티켓팅을 하기 위해 인터넷에 들어갔을 때 대기 순서와 같은 것을 본 적이 있을 것입니다. (또한 편의점에서 일을 해 보신 분들도 자주 들어본 용어일 것 입니다.) 이러한 경우 가장 먼저 들어간 사람을 우선순위로 다음 페이지로 연결이 되기 때문에 FI..

이번 시간에는 Stack 자료구조에 대해서 배워 볼 것입니다. 1. 스택(Stack)이란? stack은 후입선출(Last-In-First-Out; LIFO)의 대표적인 선형 자료구조 중의 하나입니다. 후입선출이란 'Last-In-First-Out'이라는 뜻 그대로 '나중에 들어온 데이터가 가장 먼저 나간다' 의 의미를 가지고 있습니다. 그 예로 인터넷 브라우저에서 뒤로 가기 기능같은 경우 그 버튼을 눌렀을 때 가장 최근의 페이지가 나오는데 이 역시 가장나중에 들어간 페이지가 가장 먼저 나오는 것이기 때문에 스택 구조라고 할 수 있습니다. 또한, Ctrl + z 와 같은 실행 취소 기능역시 제일 나중에 했던 동작을 취소하는 것이므로 스택 구조라고 볼 수 있습니다. 위 그림은 스택의 구조를 시각화한 자료입니..

이번 시간에는 LinkedList의 종류 중에서 Double LinkedList에 대해서 알아 보겠습니다. 1. Doubly Linked List(이중 연결 리스트)란? 이전 내용에 있는 LinkedList는 앞에 'Single'이 생략 되어있는 셈이라 생각하면 됩니다. 그럼 무엇이 single이고 무엇이 double일까요? 위 그림은 Double LinkedList의 대략적인 구조를 나타낸 그림입니다. 아래 그림을 보면, LinkedList와는 다르게 한 노드에서 다른 노드를 가리키는 pointer가 양방향으로 있습니다. 즉, 다음 노드를 가리키는 next pointer 말고도 이전노드를 가리키는 prev pointer 하나가 더 추가 된 것입니다. 이것이 LinkedList와는 구분되는 Double ..

이번 포스팅은 지난 포스팅에 이어 ArrayList에서 했던 것과 마찬가지로 LinkedList에서의 데이터 삽입, 데이터 삭제, 리스트 검색 등의 기능에 대해서 다뤄보도록 하겠습니다. 1. 연결리스트(Linked List)란? LinkedList는 Node라는 객체로 이루어져 있는데 Node는 데이터를 저장하는 field와 다음 노드를 가리킬 수 있는 next pointer field로 구성이 되어있습니다. 이말인 즉슨, 이 노드들이 연결된 형태의 자료구조를 바로 LinkedList라고 하는 것입니다. 예를 들어, 학교에서 어느 반의 모든 학생들의 데이터를 저장한다고 했을 때, 학생 한명 한명의 신상정보 자료를 노드로 만들고, 1번 학생의 신상정보 자료에 2번 신상정보 자료가 어디 있는 지 표시를 해 ..