알고리즘3 Binary Search, 이진탐색 정렬된 배열에서 특정 값의 위치 찾기 아래의 정렬된 배열에서 6을 찾는다고 하자. ---------- 0123456789 지금은 배열 전체가 탐색 범위이다. 여기서 중앙에 있는 값과 목표로 하는 값(6)을 비교해 보자. 중앙에 있는 값은 index가 4인 값이다. floor((0 + 9)/2) = floor(4.5) = 4, arr[4] target 임으로 i.. 2023. 1. 6. Next permutation, 다음 순열 구하기 어떤 순열이 주어져 있을 때 다음 순서의 순열을 구하는 알고리즘이다. 참고로 여기서 말하는 순서는 어떤 요소들로 순열을 만들고 이 순열들을 사전 순서대로 정리하듯 정렬하였을 때를 기준으로 한다. 예를 들어 어떤 1, 2, 3을 가지고 모든 순열을 만들고 이를 사전 순서대로 정리하면 아래와 같다. 123 132 213 231 312 321우리가 하고자 하는 것은 어떤 순열이 주어졌을 때 다음 순열을 구하는 것이다. 예를 들어 231 이 주어졌을 경우 312를 반환하는 것이다. Algorithm 어떤 순열을 arr라고 하자. arr[i] arr[i] 인 j 중 가장 큰 j를 구한다. swap(arr[i],arr[j]).. 2022. 4. 4. Merge Sort (합병 정렬) Merge Sort는 배열의 값을 정렬하는 여러 가지 방법 중에 하나이다. Merge Sort는 정렬이 된 부분 배열들을 합쳐가면서 정렬을 수행한다. 정렬이 된 배열들을 합친다는 것이 Merge Sort의 핵심 아이디어이다. 이 아이디어를 이용하여 어떻게 전체 배열에 대해 정렬을 수행할 수 있을까? Merge Sort (합병 정렬)로 배열을 정렬하는 방법에 대해 알아보자. 참고로 이 글에서는 오름차순으로 정렬할 것이다. Merge 정렬에 대해 생각하기 전에, 정렬이 된 두 배열을 합치는 작업에 대해 생각해보자. 함수 merge가 이 작업을 수행한다고 해보자. merge의 입력으로 들어오는 두 배열은 이미 정렬이 되어 있어야 하고 반환하는 결과물도 정렬이 되어 있어야 한다. 사실, 두 배열이 정렬이 되어있.. 2021. 9. 17. 이전 1 다음
