까만화면

Algorithm [ 알고리즘 공부 ] 시간 복잡도(빅오Big-Oh, 빅오메가Big-Omega, 세타Theta) 더보기

Divide-and-Conquer [알고리즘 공부] 최근접 점의 쌍 찾기 알고리즘(Closest Pair of Points) - python 파이썬 ▶ 최근점 점의 쌍을 찾는 문제? 최근접 점의 쌍(Closest Pair)을 찾는 문제는 2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제입니다. 바로 그 문제를 해결하기 위한 방법은 효율적인 분할 정복을 이용하는 것입니다.n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 쌍을 찾고, 2개의 부분 해 중에서 짧은 거리를 가진 점의 쌍을 일단 찾습니다. 여기서 주의할 점!취합할 때 중간 영역을 고려해야합니다. 이게 무슨 말이냐면, 분할된 왼쪽 점 중에 하나, 오른쪽 점 중에 하나가 최근접점 쌍이 될 수 있습니다. 그래서 중간 영역도 왼쪽 부분과 오른쪽 부분의 최단 거리인 10과 15중에 더 짧은 거리 10이내에 있는 각각 왼쪽과 오른쪽 점들만 거..
Divide-and-Conquer [ 알고리즘 공부 ] 선택 문제 알고리즘(Selection) (feat.python 파이썬) ▶ 선택문제(Selection)란? ※ 선택 정렬(Selection Sort)과는 다른 알고리즘입니다.선택(Selection) 문제는 n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제입니다. 이 문제를 해결하기 위한 단순한 방법은 다음과 같습니다. 1) 최소 숫자를 k번 찾는다.→ 숫자 n개가 들어있는 배열 중에서 최소 숫자를 찾고, 찾을 때마다 입력에서 그 숫자를 제거합니다.시간복잡도는 O(kn), k번째 숫자를 찾을 때까지 반복하는 과정마다 항상 n, n-1, n-2....(최소 숫자는 제거되므로) 개의 숫자들을 탐색하기 때문입니다. 2) 숫자들을 정렬한 후, k번째 숫자를 찾는다.→ 시간복잡도는 O(nlogn), 즉 정렬하는 과정에서 걸리는 시간에 따라 다를 것입니다. (k번째 숫자를 찾..
Divide-and-Conquer [ 알고리즘 공부 ] 퀵정렬 퀵소트(Quick Sort) - 분할 정복 알고리즘(feat. python 파이썬) 퀵 정렬이란? 퀵 정렬도 분할 정복 알고리즘입니다. 2개의 문제로 분할합니다. 합병 정렬(Merge Sort) 같은 경우에는 2개의 문제로 분할할 때, 문제의 크기가 항상 같았지만, 퀵 정렬은 일정하지 않은 형태로 분할합니다. 퀵 정렬은 피봇(pivot)이라 부르는 배열의 원소를 기준으로 피봇보다 작은 값은 왼쪽으로, 피봇보다 큰 값은 오른쪽으로 위치하도록 분할합니다. 이 과정을 통해 분할된 왼쪽 배열과 오른쪽 배열에도 동일한 과정을 수행합니다. 이렇게 반복을 하다 보면 배열은 어느새 정렬이 되어 있을 겁니다. 여기서 주의할 점은 피봇(pivot)은 분할된 왼편이나 오른편 부분에 포함되지 않습니다.그 이유는 피봇을 기준으로 왼편과 오른편의 분할 과정을 수행했다면, 피봇의 위치는 확정되었기 ..

티스토리툴바