탐색 과정 이진 탐색(Binary Search) 알고리즘은 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 먼저 이 알고리즘은 반드시 정렬을 한 후에 탐색을 시작해야 한다. 탐색할 범위의 시작과 끝이 같은 경우에는 찾지 못한 것으로 본다. 그렇지 않은 경우에는 탐색할 범위의 중간값을 확인하여 찾고자 하는 값보다 크거나 작은지 확인한다. 만약 값이 같다면 검색에 성공하여 위치를 반환하고 탐색을 종료한다. 중앙값이 찾는 값보다 크면 새로운 최댓값으로, 작다면 새로운 최솟값으로 설정하여 다시 탐색을 시작한다. 반드시 정렬을 해야한다는 단점이 있지만, 검색을 반복할 때마다 탐색할 범위가 1/2로 줄어들기 때문에 탐색 속도가 빠른 편이다. 구현 코드 import java.util.Scanner; public c..
정렬 과정 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 분할(divide): 임의의 피벗을 지정하여 피벗보다 큰 원소와 작은거나 같은 원소, 두 부분 리스트로 나눈다. 결합(combine): 작은 리스트 - 피벗 - 큰 리스트로 결합한다. 정복(conquer): 두 부분 리스트를 재귀적으로 퀵 정렬을 이용해 정렬한다. 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다. 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다. 역시나 분할과 정복 방식이다. 구현 코드 package net...
정렬 과정 흔히 쓰이는 하향식 2-way 합병 정렬은 다음과 같이 작동한다. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다. 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다. 이 과정에서 재귀 함수를 활용한다. 분할 후 분할된 2개의 조각에 다시 합병정렬을 실행한다. 분할과 정복. 구현 코드 package net.jetalab.excercise.mergesort..