suyeonme

1. 퀵 정렬(Quick Sort)이란? 찰스 엔터니 리처드 호어(C. A. R. Hoare)가 개발한 알고리즘으로, 일반적으로 폭넓게 사용되고 있는 빠른 정렬 알고리즘이다. 퀵 정렬은 대표적인 분할 정복을 사용한 알고리즘으로, 각 그룹에 대해 피벗(pivot) 설정과 그룹 나눔을 반복하여 정렬을 한다. 평균 시간 복잡도는 O(n log n)이다. 이미 정렬이 된 배열의 경우, 최악 시간 복잡도는 O(n ^2)이다. (이 경우 삽입 정렬 사용) 2. 동작 방식 퀵 정렬을 사용하여 배열을 정렬한다면 아래와 같이 동작한다. 배열은 { 5, 7, 1, 4, 6, 2, 3, 9, 8 }이다. 배열의 첫번째 원소를 피벗(pivot)으로 선택하여 배열을 나눈다. 왼쪽에서 오른쪽으로 스캔하며 피벗보다 큰 값을 선택한..

1. 셸 정렬(Shell Sort)이란? 도날드 셸(D.L.Shell)이 고안한 알고리즘으로, 삽입 정렬(Insert Sort)의 장점을 살리고 단점을 보완하여 좀더 빠르게 정렬한다. 일정한 간격으로 서로 떨어져있는 두 요소를 그룹으로 묶어 대략 정렬을 수행하고 간격을 좁혀 그룹의 수를 줄이면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법이다. 즉 그룹 별로 미리 몇차례 정렬을 하고 삽입 정렬을 실시하여 삽입 정렬의 장점을 이용한다. 셸 정렬 과정에서 수행하는 각각의 정렬을 h-정렬이라고 한다. 멀리 떨어져있는 요소를 교환하므로 안정적이지 않다. 시간 복잡도는 O(n1.25)로 O(n^2)보다 빠르다. 1.1 동작 방법 배열이 { 8, 1, 4, 2, 7, 6, 3, 5 }라고 가정하고 셸 정렬을 수..

헤드 퍼스트 디자인 패턴을 읽고 정리한 내용입니다. 1. 문제 상황 1. 유명 커피 전문점은 주문 시스템을 개선하려고 한다. 2. 고객은 커피를 주문할 때 우유, 두유, 모카등을 추가할 수 있다. 각각을 추가할 때 마다 커피의 가격은 변한다. 3. 첨가물은 추가되거나 제거되는등 변경될 수 있다. 2. 데코레이터 패턴으로 문제 해결 2.1 데코레이터 패턴(Decorator Pattern)이란? 객체에 추가 요소를 동적으로 더할 수 있는 디자인 패턴이다. 데코레이터를 사용하면 서브 클래스를 만들 때보다 훨씬 유연하게 기능을 확장할 수 있다. 데코레이터를 적용하는 방법은 아래와 같다. (고객이 Dark Roast에 모카와 휘핑크림을 주문했다고 가정) 1. DarkRoast 객체를 생성한다. 2. Mocha 객..

1. 선택 정렬(Selection Sort)이란? 가장 작은 요소를 맨 앞으로 이동하고, 두번째 작은 요소는 맨 앞에서 두번째로 이동하는등의 작업을 반복하는 알고리즘이다. 시간 복잡도는 O(n^2)으로 효율이 좋지 않다. (버블 정렬 < 선택 정렬) 서로 떨어져있는 요소를 교환하므로 안정적이지 않다. 즉 중복된 요소가 존재할 경우, 정렬한 후 두 요소의 순서가 뒤바뀐다. 1.1 선택 정렬 구현 public void selectionSort(int[] arr, int n) { for(int i = 0; i < n - 1; i++) { int min = i; // 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스 for(int j = i + 1; j < n; j++) { if(arr[j] < arr[mi..

1. 버블 정렬이란? 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘으로 단순 교환 정렬(straight exchange sort)라고도 한다. 시간 복잡도는 O(n^2)로 효율이 좋지 않다. 정렬 과정 1. 배열의 끝에 있는 두 요소부터 비교를 시작한다. 2. 이웃한 두개의 요소를 비교하고 왼쪽 요소가 오른쪽 요소보다 작으면 위치를 교환한다. 3. 위의 과정을 첫번째 요소까지 반복한다. (이 과정을 패스, pass 라고 한다) 2. 버블 정렬 구현 public void swap(int[] arr, int idx1, int idx2) { int t = arr[idx1]; arr[idx1] = idx2; arr[idx2] = t; } public void bubbleSort(i..

1. 재귀란? 어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적(recursive)이라고 한다. 1.1 재귀 관련 용어 직접 재귀(direct recursion): 자신과 동일한 메서드를 호출하는 구조 간접 재귀(indirect recursion): 메서드 a가 메서드 b를 호출하고 다시 메서드 b가 메서드 a를 호출하는 구조 순수(genuinely) 재귀: 재귀 호출을 여러번 실행하는 메서드 꼬리 재귀(tail recursion): 재귀의 호출이 끝난 후 현재 함수에서 추가적인 연산을 요구하지 않도록 구현한 재귀 1.2 재귀 사용시 유의 사항 재귀 함수는 반복적으로 호출된다. 하나의 함수의 실행이 끝나지 않았음에도 함수를 연속적으로 호출하기때문에 각각의 ..

헤드 퍼스트 디자인 패턴을 읽고 정리한 내용입니다. 1. 문제 상황 1. WeatherData 객체는 물리 기상 스테이션과 통신해서 갱신된 기상 데이터를 가져온다. 2. 복수개의 디스플레이는 WeatherData 객체의 기상데이터를 사용한다. 3. 따라서 WeatherData 객체의 기상 데이터가 업데이트될 때마다 디스플레이 장비의 데이터 또한 업데이트해야한다. 2. 문제 해결 시도 가장 간단한 방법으로 아래와 같이 구현할 수 있다. 이 때 각각의 display에서 update()를 호출하는 부분은 구체적인 구현에 맞춰서 코드가 작성되었으므로 프로그램을 고치지 않고서는 다른 디스플레이 항목을 추가하거나 제거할 수 없다. 따라서 해당 부분은 캡슐화가 필요하다. public class WeatherData ..

헤드 퍼스트 디자인 패턴을 읽고 정리한 내용입니다. 1. 문제 상황 1. Duck이라는 슈퍼 클래스가 있고 이 클래스를 확장하여 서로 다른 종류의 오리를 만들었다. 2. 오리가 날 수 있는 기능을 추가해달라는 요건이 들어왔다. 3. Duck 슈퍼 클래스에 fly() 메소드를 추가했다. --> fly 기능을 가지면 안되는 서브 클래스들이 fly()를 상속받았다. 4. fly 기능이 필요없는 서브 클래스에서는 fly()가 아무것도 하지 않도록 오버라이드한다. 5. 추가 요건이 계속 들어온다. (quack, eat, sleep등) --> 일일히 오버라이드할 수 없다. 2. 전략 패턴을 사용하여 해결 3.1 전략 패턴(Strategy Pattern)이란? 알고리즘군을 정의하고 캡슐화해서 각각의 알고리즘을 수정해..