suyeonme

1. 브루트-포스법(Brute force method)이란? 선형 검색을 확장한 단순한 알고리즘이다. 효율이 좋지 않다. 2. 구현하기 public class BruteForceMethod { static int bruteForceMethod(String text, String pattern) { int textIdx = 0; int patternIdx = 0; while(textIdx != text.length() && patternIdx != pattern.length()) { if(text.charAt(textIdx) == pattern.charAt(patternIdx)) { textIdx++; patternIdx++; } else { textIdx = textIdx - patternIdx + 1;..

헤드 퍼스트 디자인 패턴을 읽고 정리한 내용입니다. 1. 간단한 팩토리(Simple Factory) 디자인 패턴이라기 보다는 프로그래밍에서 자주 쓰이는 관용구이다. 객체 생성 작업을 팩토리 클래스로 캡슐화해놓으면 구현을 변경할 때 팩토리 클래스 하나만 고치면 된다. 즉 코드에서 중복되는 내용을 제거할 수 있고, 관리할 때도 한군데만 관리하면 된다. 객체 인스턴스를 만들 때 인터페이스만 있으면 된다. 인터페이스를 바탕으로 하여 유연성과 확장성이 뛰어난 코드를 작성할 수 있다. 팩토리(factory): 객체 생성을 처리하는 클래스 1.1 문제 상황 당신은 피자가게를 운영한다. 따라서 아래의 코드를 작성하였다. 하지만 코드는 몇 가지 문제점이 있다. 피자 종류가 추가, 제거, 변경등이 일어날 때마다 코드를 계..

1. 도수 정렬(Counting Sort)이란? 요소의 대소 관계를 판단하지 않고 (다른 정렬 알고리즘들은 두 요소의 키 값을 비교해야 한다.) 단순하게 크기를 기준으로 세는 알고리즘이다. 데이터를 비교, 교환하는 작업이 없고 다중 for문이 아닌 단순 for문을 사용하고 재귀 호출과 중첩 for문이 없기 때문에 아주 효율적이다. 도수분포표가 필요하기 때문에 데이터의 최솟값과 최댓값을 미리 알고있을 경우, 즉 범위 조건(e.g. 5이하 자연수를 오름차순 정렬)이 있는 경우에만 사용할 수 있다. 각 단계의 for문에서 배열 요소를 건너뛰지 않고 순서대로 스캔하기 때문에 같은 값의 순서가 바뀌는 일이 없다. 따라서 안정적인 정렬 알고리즘이다. 시간 복잡도는 O(n)으로 매우 빠르다. 2. 동작 방식 총 4단..

1. 힙 정렬(Heap Sort)이란? 힙(heap)을 사용하여 가장 큰 값이 루트에 위치 하는 특징을 이용하는 정렬 알고리즘이다. 선택 정렬(selection sort)을 응용한 알고리즘이다. (선택 정렬은 아직 정렬되지 않은 부분의 모든 요소를 대상으로 가장 큰 값을 선택한다.) 시간 복잡도는 O(n log n)이다. 1.1 힙(heap)이란? 부못값이 자식값보다 항상 크다(부못값 >= 자식값)라는 조건을 만족하는 완전 이진 트리이다. (완전: 부모는 자식을 왼쪽부터 추가하는 모양을 유지 + 이진: 부모가 가질 수 있는 자식의 개수는 최대 2개) 트리의 최상단 노드를 루트(root), 트리의 최하단 노드를 리프(leaf), 노드의 상하 관계를 부모(parent)와 자식(child), 자식간의 관계를 ..

1. 병합 정렬(Merge Sort)이란? 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬하는 알고리즘 배열 병합의 시간 복잡도는 O(n)이고, 전체 시간 복잡도는 O(n log n)이다. 서로 떨어져있는 요소를 교환하는 경우가 없으므로 안정적인 정렬 방법이다. 2. 동작 방식 int[] arr = { 5,6,4,8,3,7,9,0 }; // 1. 배열을 앞부분과 뒷부분으로 나눈다. 앞부분(a): { 5,6,4,8 } 뒷부분(b): { 3,7,9,0 } // 2. 앞부분과 뒷부분을 재귀를 사용하여 정렬한다. 앞부분(a): { 4,5,6,8 } 뒷부분(b): { 0,3,7,9 } 정렬된 배열(c): {} // 3. 각 배열의 작업에서 선택한 요소의 인덱스는 pa, pb, p..

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 객..