suyeonme

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)이란? 알고리즘군을 정의하고 캡슐화해서 각각의 알고리즘을 수정해..

1. Linear Queue(선형 큐)란? FIFO(First In First Out) en-queue: 큐에 데이터를 넣는 작업 -- O(1) de-queue: 큐에서 데이터를 꺼내는 작업 -- O(n) 데이터가 나오는 쪽은 front, 데이터를 넣는 쪽은 rear라고 한다. 1.1 선형 큐의 단점 큐에 데이터가 꽉 찼다면 데이터를 추가할 수 없다. de-queue시 요소를 하나씩 앞으로 옮겨야 하므로 복잡도가 O(n)이다. 2. Ring Buffer(Circular Queue)란? 원형큐는 배열의 맨 뒤가 맨 앞과 연결되었다고 보며 선형 큐의 문제점을 보완하기 위한 자료구조이다. 선형큐와 다르게 de-queue시, 배열 요소를 앞으로 옮기지 않아도 된다. enqueue시 rear 인덱스에 값을 저장하..

1. 스택(Stack)이란? LIFO(Last In First Out) push: 스택에 데이터를 넣는 작업 pop: 스택에서 데이터를 꺼내는 작업 푸시와 팝이 이루어지는 꼭대기는 top, 스택의 가장 아랫부분은 bottom이라고 한다. 2. 직접 스택 생성하기 static class IntStack { private int[] stack; // 스택 배열 private int capacity; // 스택 용량 private int stackPointer; // 스택에 쌓여있는 데이터 수 // 실행시 예외: 스택이 비어 있는 경우 public class EmptyIntStackException extends RuntimeException { public EmptyIntStackException() {};..

1. 선형 검색(Linear Search) 배열에서 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색한다. 복잡도는 O(n)이다. static int seqSearch(int[] arr, int n, int key) { int i = 0; while(true) { if(i == n) { return -1; } if(arr[i] == key) { return i; } i++; } } 1.1 보초법(Sentinel Method) 위의 선형 검색은 반복할 때마다 종료 조건 1과 2를 모두 판단한다. 보초법을 사용하여 반복문에서 종료 판단 횟수를 2회에서 1회로 줄일 수 있다. 순서) 1. 검색할 값을 보초로 arr[n]에 대입한다. 2. 배열 요소를 순서대로 스캔한다. static int..