1.기본 컨셉 - 정렬되지 않은 배열 중에서 최소값을 찾아 정렬되지 않은 맨 처음 요소와 자리를 바꾼다. - 이제 자리를 바꾼 요소는 정렬된 요소이다. - 하나의 원소만 남을 때까지 위 과정을 반복한다. 아래의 동영상을 살펴보자. https://www.youtube.com/watch?v=Ns4TPTC8whw 2. 정렬 과정 3. 자바 코드 @Test public void selectionSortTest(){ data = new int[] {3,0,1,8,7,2,5,4,9,6}; for(int i=0; i

1. 기본 컨셉 - 앞에서부터 자료를 정렬해가는 방식이다. - 새로운 요소를 이미 정렬된 마지막 요소부터 비교해가며 적절한 자신의 위치에 삽입해 넣는다. 다음 동영상을 보고 전체적인 흐름을 이해해보자. https://www.youtube.com/watch?v=ROalU379l3U 2. 정렬 과정 int [] src = {3,0,1,8,7,2,5,4,9,6}; 3. 자바 코드 @Test public void insertionSortTest() { data = new int[] { 3, 0, 1, 8, 7, 2, 5, 4, 9, 6 }; // 0번째는 볼 필요 없다. int key = 0;// 비교를 시작하는 값 int j = 0;// key가 삽입될 위치 for (int i = 1; i < data.len..

여러 가지 형태의 정렬 방식을 살펴보고 그 동작의 차이점을 고민해보자. 사실 어떤 정렬 알고리즘이 빠른지는 이미 다 나와있기 때문에 쓸데없이 버블 정렬 같은것을 살펴볼 필요가 있을가 싶기도 하겠지만 알고리즘을 공부하면서 아이디어의 정리 차원이라고 생각하면 좋겠다. 여기서 소개하는 모든 정렬들은 기본적으로 오름 차순 정렬을 사용한다. 가장 먼저 살펴볼 알고리즘은 버블 정렬이다. 1. 기본 컨셉 - 버블 정렬은 인접해 있는 두 수를 비교해서 보다 큰 수를 뒤쪽으로 보내는 정렬 방식이다. 버블 정렬을 소개하는 간단한 동영상을 살펴보면 구현 방식을 아주 쉽게 알 수 있다. (50초 부터가 정렬 과정이다.) https://www.youtube.com/watch?v=lyZQPjUT5B4 - 동영상 내용을 보면 알 ..

조합의 정의 조합은 서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 말한다. 앞서 살펴본 순열과의 차이점은 순서를 고려하지 않는다는 점이다. 수학적 증명을 통한 조합 구하기 순열이 nPr = n개에서 r개를 선택한 후 순서대로 나열하는 것인데 여기서 n개에서 r개를 선택하는 것이 순열이고 이 r개를 다시 나열하는 것이 nPr이다. 따라서 nCr은 다음과 같이 구할 수 있다. 위 식을 처리하기 쉬운 재귀 방식으로 변경해보자. 위 식을 잘 살펴보면 nCr은 보다 낮은 단계인 n-1Cr-1과 n-1Cr의 합이다. 여기서 r이 선택할 요소의 개수이다. 즉 n개에서 r개를 뽑는 방법은 어떤 요소 하나를 고려했을 때 그 요소를 뽑았을 때의 조합과 그 요소를 뽑지 않았을 때의 조합의 합이된다. 조합의 과정 ..

다음으로 알아볼 순열 작성 방식은 next permutation을 이용하는 방법이다. next permutation은 말 그대로 사전 순으로 다음의 순열을 찾는 과정이다. 다음 순열이란 만약 요소가 {1,2,3}일 때 이것의 다음은 {1,3,2}, 다시 {1,3,2}의 다음은 {2,1,3} --> {2,3,1} --> {3,1,2} --> {3,2,1}로 전개되는 것을 말한다. 어떻게 이과정이 진행되는지 살펴보자. 진행 과정 next permutation을 찾는 과정은 몇 가지 절차를 거쳐서 이뤄진다. {3, 5, 1, 9, 7}로 이뤄진 배열의 다음 순열을 찾아보자. step 1: src[i]< src[i+1] 즉 다음 요소보다 작은 요소 중 가장 마지막 요소를 찾는다. 다음 그림을 보면 현재 위 조건..

순열은 앞서 살펴봤던 visited를 이용하는 방식이외에도 여러 가지 방식으로 작성이 가능하다. 여기서는 swap 을 이용해서 순열을 구하는 방식에 대해 살펴보자. 기본적인 컨셉은 아래와 같다. - swap: 요소와 요소의 위치를 서로 변경한다. - depth: 선택할 수 있는 요소의 범위를 조절한다. 진행 과정 먼저 최초의 배열 {A, B, C, D}가 있고 depth 0에서 swap 되는 단계는 다음과 같을 것이다. 물론 depth0-1인 BACD는 depth0-0 인 ABCD에 대한 모든 하위 depth가 종료된 후 진행될것이다. 이제 depth0-0의 하위인 depth1의 동작을 살펴보자. 첫 번째 자리는 A로 고정된 상태에서 나머지 요소들이 swap 대상이 된다. 이제 depth1-0이 종료되면..