Keep calm and carry on

병합 정렬(Merge Sort)은 배열을 재귀적으로 반으로 나누고, 각 부분을 정렬한 다음 다시 병합하여 전체 배열을 정렬하는 알고리즘이다.아래 내용은 배열을 나누고 병합하는 과정을 단계별로 설명한다. 주어진 배열[6, 4, 7, 3, 9, 1, 8] 배열을 반으로 나누기 (Divide)첫 번째 나누기 [6, 4, 7, 3, 9, 1, 8] / \[6, 4, 7, 3] [9, 1, 8]두 번째 나누기 [6, 4, 7, 3] [9, 1, 8] / \ / \ [6, 4] [7, 3] [9, 1] [8] / \ / \ / \[6] [4] [7] [3] [9] [1] [8]  배열을 병합..

quick sort: 정렬 속도가 아주 빠르다는 데서 착안해 붙여진 직관적인 이름이다.퀵정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹이 1개의 요소가 될때까지 반복한다.그룹을 나누는 기준을 피벗(pivot) 이라고 한다. 배열을 두 그룹으로 나누기 피벗 이하의 요소를 배열 왼쪽으로, 피벗 이상의 요소를 배열 오른쪽으로 옮겨야 한다. 아래 배열을 통해 과정을 살펴보자.int[] arr = [5, 7, 1, 4, 6, 2, 3, 9, 8]// pl x pr가운데 인덱스를 피벗 x, 왼쪽 끝 요소를 pl, 오른쪽 끝 요소를 pr 이라 했을 때1. arr[pl] >= x 가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔한다. (pl+..

'재귀 알고리즘의 예시와 분석'의 내용을 살펴봤다. 다음으로 재귀 알고리즘의 비재귀적 표현 방식과 메모화를 확인해본다.재귀 알고리즘의 비재귀적 표현 recur 메서드를 비재귀적으로 구현하는 방법을 살펴본다. 우선 '꼬리' 재귀를 제거 하는 방법이 있다. recur(n - 2)는 인수로 n - 2를 전달하여 recur 메서드를 호출한다.이 호출을 바꾼다. n값을 n - 2로 업데이트하고 메서드의 시작 지점으로 돌아간다. // 수정 이전의 코드if (n > 0) { recur(n - 1); System.out.println(n); recur(n - 2); // 꼬리를 제거, n - 2로 업데이트하고 메서드의 시작 지점으로 돌아가야 한다} // 수정 후의 코드, if 문을 while 문으로 수..

재귀 알고리즘 분석하기 재귀 호출을 여러 번 실행하는 순수(genuinely) 재귀의 예시.package org.study.bohyohshibata;public class Recur { static void recur(int n) { if (n > 0) { recur(n - 1); System.out.println(n); recur(n - 2); } } public static void main(String[] args) { recur(4); }} 출력 결과는 아래와 같다.1231412하향식 분석과 상향식 분석recur(4) 는 아래와 같은 순서대로 실행된다.recur(3)을 실행.4를 ..

자료구조와 함께 배우는 알고리즘 입문 책을 보며 학습한 내용 이진 검색 이 알고리즘은 데이터가 키값으로 이미 정렬(sort)되어있다 전제 조건이 필요하다.이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다. 이진 검색 알아보기아래와 같이 오름차순으로 정렬된 데이터에서 39를 검색하는 예시다.int[] a = {5, 7, 15, 28, 29, 31, 39, 58, 68, 70, 95};먼저 배열의 중앙(10 / 2 == 5)에 위치한 요소인 a[5](값: 31)부터 검색을 시작.검색할 값인 39는 중앙 요소(a[5])보다 큼. 따라서 검색 대상을 뒤쪽의 5개(a[6] ~ a[10])로 좁힘. 그리고 다음 검색 범위의 중앙에 위치한 요소인 a[8](값: 68) 선택한다.검색할 값인 39는 중앙요소 a[..

자료구조와 함께 배우는 알고리즘 입문 책을 보며 학습한 내용 보초법으로 선형 검색 구현하기 선형 검색은 반복할 때마다 종료 조건 1, 2를 모두 판단함.처리할 데이터의 양이 많을수록 종료 조건을 검사하는 비용은 커짐. 보초법은 이 비용을 50%로 낮춤.    배열 요소 a[0] ~ a[6]은 원래의 데이터이다. 맨 끝 요소 a[7]은 검색하기 전에 값을 추가하여 저장한 보초(sentinel)이다.보초법을 사용시 아래의 코드와 같이 조건문 수정 가능함.int i = 0;a[n] = key;while (true) { if (a[i] == key) break; i++;}return i == n ? -1 : i;

자료구조와 함께 배우는 알고리즘 입문 책을 보며 학습한 내용 배열에서 검색하기선형검색: 무작위로 늘어서 있는 데이터 모임에서 검색을 수행함.이진검색: 일정한 규칙으로 늘어서 있는 데이터 모임에서 아주 빠른 검색을 수행함.해시법: 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행함.체인법: 같은 해시값의 데이터를 선형 리스트로 연결하는 방법오픈 주소법: 데이터를 위한 해시값이 충돌할 때 재해시하는 방법 선형 검색 요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색한다.이를 ‘선형 검색(linear search)’ 또는 ‘순차 검색(sequential search)’이라함.선형 검색에서 배열 검색의 종료 조건은 2개이다.검색 ..