본문 바로가기

알고리즘106

[알고리즘] 이분 탐색 (Binary Search) 목차 이분 탐색이란? 이분 탐색 혹은 이진 탐색 (Binary Search)는 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 이 알고리즘은 자료가 순서에 따라 정렬된 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다. 따라서, 탐색할 때마다 검사 범위가 절반으로 줄어든다. 이분 탐색 의 진행 단계 이분 탐색에서는 내가 찾고자 하는 값이 정렬된 배열의 중간 값보다 크면 중간값을 포함한 하위 값들은 탐색 대상에서 제외하고, 반대로 찾고자 하는 값이 배열의 중간 값보다 작으면 중간 값을 .. 2023. 8. 7.
[알고리즘] 계수 정렬 (Counting Sort) 목차 계수 정렬이란? 계수 정렬은 데이터 값을 직접 비교하지 않고, 단순하게 각 숫자가 몇 개 있는지 개수를 세어 저장한 후에 정렬하는 알고리즘이다. 기존의 정렬 알고리즘들은 위치를 바꾸며 정렬을 했는데, 계수 정렬에서는 크기를 기준으로 개수만 세면 되기 때문에 위치를 변경할 필요가 없다. 계수 정렬의 큰 특징은 값 비교가 일어나지 않기 때문에 속도가 빠르다는 것이다. 하지만, 개수를 저장하는 배열을 사용해야 하기 때문에 추가 공간이 필요하다. 그래서, 정렬해야 할 수의 범위가 작을 때에만 유리하다. 이 이유는 예를 보면서 설명하겠다. EX) 0, 100, 2, 10, 10000 오름차순으로 정렬하기 예를 들어서 정렬해야 할 수가 0, 100, 2, 10, 10000이면 고작 5개의 수를 정렬하는데 0부.. 2022. 7. 29.
[알고리즘] 병합 정렬 (Merge Sort) 목차 병합 정렬이란? 병합 정렬은 분할 정복 (Divide and Conquer) 방식을 이용해서 하나의 리스트를 두 개의 리스트로 분할한 다음 각각의 분할된 리스트를 정렬한 후에 합해서 정렬된 하나의 리스트로 만드는 정렬 알고리즘이다. 추가로 병합 정렬은 퀵 정렬과 달리 정렬을 할 때 데이터 크기만큼의 추가 공간이 필요하므로 제자리 정렬 (in-place sort)이 될 수는 없다. 병합 정렬은 분할 정복의 다음과 같은 과정을 거친다. 분할(Divide) : 리스트를 두 개의 리스트로 분할한다 정복(Conquer) : 분할된 리스트를 정렬한다. 결합(Combine): 정렬된 두 개의 리스트를 하나의 정렬된 리스트로 결합한다. 이제 병합 정렬의 예시를 한번 살펴보겠다. 병합 정렬 병합 과정 분할된 리스트.. 2022. 7. 28.
[알고리즘] 퀵 정렬 (Quick Sort) 목차 퀵 정렬이란? 퀵 정렬은 분할 정복 (Divide and Conquer)과 재귀 방식을 이용한 정렬 알고리즘이다. 분할 정복이란 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 방식이다. 퀵 정렬에서는 pivot이라는 기준을 하나 정하고, 왼쪽은 기준보다 작은 값, 그리고 더 큰 값은 기준 오른쪽으로 옮기면서 배열을 둘로 분할한 후 정렬한다. 보통 pivot은 맨 앞이나 맨 뒤, 혹은 중간에 위치한 값을 선택한다. 퀵 정렬 과정 배열 맨 앞에 있는 수를 pivot으로 설정한다. 그리고 배열의 길이가 n일 때, 배열의 시작점은 0이 되고 도착점은 n - 1이 된다. pivot 값을 기준으로 시작점에서부터 검사해서 큰 값을, 도착점에서부터 작은 값을 찾는다.. 2022. 7. 25.
반응형

티스토리툴바