알고리즘(2)
-
[Algorithm] Lower Bound & Upper Bound 정리
Lower Bound & Upper Bound 란? Lower(Upper) Bound는 원하는 값이 처음 나오는 위치를 찾는 알고리즘이다. Lower Bound는 원하는 값 k 이상의 수가 처음으로 나오는 위치를 찾는다면, Upper Bound는 원하는 값 k를 초과하는 수가 처음으로 나오는 위치를 찾는다. 📖 알고리즘 특징 - 이분 탐색 알고리즘(binary search algorithm)에서 파생됐다. - 배열 안의 숫자들이 오름차순으로 정렬되어 있을 때 이용할 수 있다. Lower Bound Lower Bound 알고리즘은 원하는 값 k 이상의 수가 처음으로 나오는 위치를 찾는다. Lower Bound 알고리즘 수행 과정 중간 지점 찾기 → 값 비교 → 확인 파악하고자 하는 구간의 시작 위치를 st..
2022.12.26 -
[Algorithm] 합병 정렬(merge sort) 정리
합병 정렬(merge sort) 이란? 합병 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 📖 안정 정렬 이란? 안정 정렬 알고리즘은 반복되는 요소를 입력 때와 동일한 순서로 정렬시킨다. (참고) 📖 분할 정복 알고리즘(Divide and conquer alogorithm) 이란? 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘이다. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다. 합병 정렬(merge sort) 과정 합병 정렬 4단계 분할(Divide) → 정복(Conquer) → 결합(Combine)→ 복사(Copy) 분할(Divde) 정렬되지 않은 리스트를 절반으로 잘라 리스트를 두 부분으로 나눈다. 정복(Conquer) 부분 배열을 정렬한다. 부분..
2022.12.26