일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- Easy
- 자바입력
- R
- 카데인 알고리즘
- 수학
- 자바 스레드 실행 순서 제어
- 자바 thread 실행 순서 제어
- input
- Kadane's Algorithm
- scanner
- SpringBoot 2
- heroku
- 사칙연산
- array
- JAVA11
- hash table
- Today
- Total
목록Data Structure, Algorithm (15)
DeFacto-Standard IT
비효율적이지만 간단한 정렬 방법들은 입력 데이터가 많지 않을 때는 사용하기에 부담이 적다. 하지만 입력 데이터가 많으면서 자주 정렬해야 할 필요가 있다면 이 방법들은 적절하지 못하다. 합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 합병 정렬은 분할 정복(divide and conquer)방법에 바탕을 둔다. 분할 정복 방법은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분리된 문제가 아직도 해결하기 어렵다면(충분히 작지 않다면) 분할 정복 방법을 연속하여 다시 적용한다. 분할 정복 방법은 대개 순환 호출을 이용하여..
Donald L. Shell 이라는 사람이 제안한 방법이다. 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 아주 빠르다는 것에 착안하여 고안한 방법이다. 셸 정렬은 삽입정렬의 보다 빠르다. 삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동하는 것이다. 만약, 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야한다. 셸 정렬은 요소들이 멀리 떨어진 위치로도 이동이 가능하다. 삽입 정렬은 전체의 리스트를 한 번에 정렬하는데 비해, 셸 정렬은 그렇지않다. 1. 정렬할 리스트를 일정기준에 따라 분류하여 연속적이지 않은 여러 개의 부분리스트를 만든다. 2. 모든 부분 리스트를 삽입 정렬을 이용하여 정렬 3. 모든 부분 리스트가 정렬되면 다시 전체 리스트를 더 적은..
버블 정렬은 오름차순 기준으로, 인접한 2개의 레코드를 비교하여 정렬되어 있지 않다면 서로 교환하는 비교-교환 과정을 처음부터 끝까지 비교한다. 한 회전에서 2개의 레코드를 계속 비교하기 때문에 각 회전마다 그 리스트의 가장 큰 숫자는 항상 제자리(맨 뒤쪽)로 찾아간다. 1. 리스트의 첫 번째, 두 번째 숫자를 선택 2. 이 둘을 비교, 순서가 맞지 않으면 서로 교환 3. 1회전이 끝나면 가장 큰 숫자는 뒤로 가게 된다. 4. 위 과정을 정렬이 안된 리스트에서 반복 예를 들어 요소의 갯수가 5개이고 3 2 6 1 5 라는 배열이 있다면 1회전 - 2 3 6 1 5 2회전 - 2 3 6 1 5 3회전 - 2 3 1 6 5 4회전 - 2 3 1 5 6 위와 같은 절차가 1번의 스캔이다. 다른 정렬은 1번의 ..
삽입 정렬은 오름차순 기준으로, 정렬이 완료된 기존의 카드 사이에 올바른 자리를 찾아 삽입하는 정렬이다. 1. 정렬되어 있지 않은 리스트의 첫 번째 숫자를 선택 2. 자신을 기준으로 인덱스를 감소시키며(뒤에 부터) 하나 씩 비교해 가며 자신보다 작은 숫자를 찾는다. 3. 자신보다 크다면 그 숫자를 뒤로 한 칸 미룬다. 4. 자신보다 작다면 연산을 멈춘다. 5. 위 과정을 정렬되어 있지 않은 리스트의 마지막 요소까지 반복 주의할 점은, index를 앞에서 부터 비교하는 것이 아니라 뒤에서 부터 비교한다. 즉, (자신의 인덱스-1)번부터 0번까지비교하여 인덱스가 점점 감소한다. 그리고 첫 회전에서 시작은 0번이 아니라 1번부터 시작한다. 예를 들어 요소의 갯수가 5개이고 3 2 6 1 5 라는 배열이 있다면..
선택 정렬은 오름차순 기준으로 1회전 시 마다, 가장 작은 숫자를 선택하여 맨 앞으로 차례대로 정렬하는 기법이다. 입력 배열 외에는 다른 추가 메모리를 요구하지 않는, 즉 한 리스트안에서 교환해여 해결하는 것을 제자리 정렬(in-place sorting)이라고 한다. 1. 입력 배열에서 정렬되지 않은 값 중 최솟값을 검색 2. 이 최솟값을 배열의 1 번째 요소와 교환 3. 1 번째 요소(배열 중 최솟값, 정렬이 완료된 요소)를 제외한 나머지 값 중에서 가장 작은 값을 검색 4. 이 최솟값을 배열의 두 번째 요소와 교환 5. 이 과정을 배열요소갯수-1만큼 되풀이 주의할 점은, index값이 0에서 n-2까지만 변화된다. 만약 A[0]부터 A[n-2]까지 정렬되어 있다면 이미 A[n-1]이 가장 큰 값이기 ..