초코레

아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 열의 '알맞은 위치에 삽입'하는 작업을 n - 1회 반복하여 정렬하는 알고리즘 2번째 요소부터 선택하여 진행한다. 선택한 요소의 왼쪽에 이웃한 요소가 더 크면 그 값을 선택한 요소에 대입하고 앞으로 이동하면서 이 작업을 반복한다. 그러다가 선택한 요소 값 이하의 요소를 만나면 그 보다 앞쪽은 검사할 필요가 없으므로 해당 위치에 선택한 요소 값을 대입한다. 떨어져 있는 요소들이 서로 뒤바뀌지 않아 안정적인 알고리즘이다. 시간 복잡도는 O(n^2) 장점 : 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라진다. 단점 : 삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아진다. 1234567891011//단순 삽입 정렬stat..

가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 서로 떨어져 있는 요소를 교환하는 것이기 때문에 안정적이지 않다. 안정된 정렬이란 같은 값을 가진 요소의 순서가 정렬 전후에도 유지되는 것을 말한다. 안정되지 않은 알고리즘은 정렬 후에 같은 값의 요소의 순서가 바뀔 수도 있다. 시간 복잡도는 O(n^2) 단순 선택 정렬의 교환 과정 아직 정렬하지 않은 부분에서 가장 작은 키의 값(a[min])을 선택한다. a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다. 1 2 3 4 5 6 7 8 9 10 11 // 단순 선택 정렬 static void selectionSort(int[] a, int n) { for (int i = 0; i

이웃한 두 요소의 대소 관계를 비교/교환을 반복하여 최종적으로 배열을 정렬시키는 알고리즘 6 4 3 7 1 9 8 먼저 오른쪽 끝에 있는 두 요소부터 비교/교환한다. 오름차순으로 정렬한다면 왼쪽 요소 값이 오른쪽 요소 값보다 클 때 교환한다. 그 다음 오른쪽에서 2, 3번째 요소를 비교/교환한다. 이 작업을 첫 번째 요소까지 반복한다. 길이가 n인 배열에서 n - 1회 비교/교환을 하면 가장 작은 요소가 왼쪽 끝으로 이동한다. 이런 하나의 사이클을 패스(pass)라고 하며, 첫 번째 패스가 끝나면 두 번째 패스는 왼쪽 끝으로 이동한 요소를 제외한 배열에 대해 비교/교환을 한다. 두 번째 패스의 비교 횟수는 첫 번째 패스보다 정렬한 요소가 하나 줄었기 때문에 1회 적은 n - 2회이다. 모든 정렬이 끝나려..

재귀 알고리즘에 대한 예제로 자주 등장하며 문제는 아래와 같다. 서로 공격하여 잡을 수 없도록 8개의 퀸를 8 x 8 체스판에 놓으세요. (퀸은 서 있는 지점에서 체스판으로 어떤 지점으로든 여덟 방향으로 직선 이동이 가능하다.) 퀸을 배치하기 위해 다음과 같은 규칙을 세울 수 있다. [규칙 1] : 각 열에 퀸을 1개만 배치한다. → 가지 뻗기로 퀸을 배치하는 조합을 나열 [규칙 2] : 각 행에 퀸을 1개만 배치한다. → 분기를 한정하기 필요하지 않은 분기를 없애 불필요한 조합을 줄이는 방법을 한정(bounding) 조작이라고 하고, 가지 뻗기와 한정 조작을 조합하여 문제를 풀어 가는 방법을 분기 한정법(branching and bounding method)이라고 한다. 1 2 3 4 5 6 7 8 9..

문제 해결 방법 중에서 가장 유명한 재귀적 알고리즘 하노이의 탑이나 8퀸 문제처럼 문제를 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법 퀵 정렬(quick sort)이나 병합 정렬(merge sort)도 분할 정복 알고리즘이다. 분할 정복 전략은 다음과 같이 동작한다. 기본 단계를 찾는다. 주어진 문제를 작게 줄여서 기본 단계가 되도록 만드는 법을 찾는다. 재귀로 배열의 합계 구하기 기본단계 : 원소의 개수가 0이면 합계는 0을 반환한다. 재귀단계 : 기본단계가 될 때까지 대상이 되는 배열의 크기를 줄여서 보낸다. 12345678910pydef sum(arr): if len(arr) == 0: return 0 return arr[0] + sum(arr[1:]) def main():..

작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에 옮기는 문제 모든 원반이 규칙에 맞게 첫 번째 기둥에 쌓여있고 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮겨야 한다. 원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반 위에 쌓을 수 없다. 3개의 기둥을 각각 시작 기둥, 중간 기둥, 목표 기둥이라고 부르고, 가장 큰 원반을 최소의 단계로 목표 기둥으로 옮기려면 가장 먼저 그룹(가장 큰 원반을 제외한 원반들)을 중간 기둥으로 옮겨야 한다. 다시 그룹 중에서 가장 큰 원반을 제외한 원반을 그룹으로 보고 같은 방식으로 옮긴다. 이 방식으로 반복하여 원반이 N개인 하노이의 탑 문제를 해결할 수 있다. 123456789101112131415//하노이의 탑publi..

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다. 재귀는 병합 정렬과 퀵 정렬, 이진검색트리 등에 사용된다. 재귀의 사용 예로 양의 정수의 팩토리얼 (n!)을 들 수 있다. 예를 들어 10의 팩토리얼인 10!은 10 * 9!로 구할 수 있고 그 우변에서 사용되는 식 9!은 9 * 8!로 구할 수 있다. 메서드가 자신을 다시 호출하는 방식을 재귀 호출(recursive call)이라고 한다. 직접 재귀 : 자신과 같은 메서드를 내부에서 다시 호출하는 것 간접 재귀 : 다른 메서드를 통해 자기 자신과 같은 메서드를 호출하는 것 a()에서 b() 호출 → b()에서 a() 호출 → a()에서 b() 호출 1 2 3 4 5 6 7 8 9 10 11 //팩토리얼을 재귀적으..

데이터를 일시적으로 쌓아 두기 위한 자료구조 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out) 큐의 예로는 은행 창구에서 차례를 기다리는 대기열이나 마트에서 계산을 기다리는 대기열이 있다. 데이터를 넣는 작업을 인큐(enqueue)라 하고, 꺼내는 작업을 디큐(dequeue)라고 한다. 데이터를 꺼내는 쪽은 프런트(front)라 하고, 넣는 쪽을 리어(rear)라고 한다. 배열로 큐를 구현할 때 디큐 시 요소를 꺼낸 후 다음 두 번째 이후의 요소를 모두 맨 앞으로 옮기는 구현 방식의 처리 복잡도는 O(n)이다. 링 버퍼(ring buffer, 배열의 처음이 끝과 연결되었다고 보는 자료구조)를 이용한다. 논리적으로 변수 프런트(front)와 리어(rear)의..

데이터를 일시적으로 저장하기 위해 사용하는 자료구조 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out) 스택에 데이터를 넣는 작업을 푸시(push), 꺼내는 작업을 팝(pop)이라고 한다. 푸시와 팝을 하는 위치를 꼭대기(top)라고 하고, 스택의 가장 아랫부분을 바닥(bottom)이라고 한다. JAVA 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용한다. (Call Stack) 메서드를 호출할 때는 푸시하고 메서드가 실행을 종료하고 호출한 원래의 메서드로 돌아갈 때는 종료할 메서드를 팝한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 3..

오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘 이진 검색을 한 단계씩 진행할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n 이다. 알고리즘의 복잡도는 O(log n) 이다. 복잡도의 대소 관계 : 1 < log n < n < n log n < n^2 < n^3 < n^k < 2^n JAVA는 배열에서 이진 검색을 하는 java.util.Arrays 클래스의 binarySearch 메서드로 제공한다. 모든 자료형 배열에서 이진 검색을 할 수 있도록 오버로딩되어 있다. [검색 성공] : 넘긴 값과 일치하는 요소의 인덱스를 반환한다. 일치하는 요소가 여러 개라면 무작위의 인덱스를 반환한다. [검색 실패] : 삽입 포인트를 x라고 할 때 -x - 1을 반환한다. ..