Algorithm (8) 썸네일형 리스트형 [알고리즘 공부] 최근접 점의 쌍 찾기 알고리즘(Closest Pair of Points) - python 파이썬 ▶ 최근점 점의 쌍을 찾는 문제? 최근접 점의 쌍(Closest Pair)을 찾는 문제는 2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제입니다. 바로 그 문제를 해결하기 위한 방법은 효율적인 분할 정복을 이용하는 것입니다. n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 쌍을 찾고, 2개의 부분 해 중에서 짧은 거리를 가진 점의 쌍을 일단 찾습니다. 여기서 주의할 점! 취합할 때 중간 영역을 고려해야합니다. 이게 무슨 말이냐면, 분할된 왼쪽 점 중에 하나, 오른쪽 점 중에 하나가 최근접점 쌍이 될 수 있습니다. 그래서 중간 영역도 왼쪽 부분과 오른쪽 부분의 최단 거리인 10과 15중에 더 짧은 거리 10이내에 있는 각각 왼쪽과 오른쪽 점들만 거리 .. [ 알고리즘 공부 ] 선택 문제 알고리즘(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번째 숫자를 찾.. [ 알고리즘 공부 ] 퀵정렬 퀵소트(Quick Sort) - 분할 정복 알고리즘(feat. python 파이썬) 퀵 정렬이란? 퀵 정렬도 분할 정복 알고리즘입니다. 2개의 문제로 분할합니다. 합병 정렬(Merge Sort) 같은 경우에는 2개의 문제로 분할할 때, 문제의 크기가 항상 같았지만, 퀵 정렬은 일정하지 않은 형태로 분할합니다. 퀵 정렬은 피봇(pivot)이라 부르는 배열의 원소를 기준으로 피봇보다 작은 값은 왼쪽으로, 피봇보다 큰 값은 오른쪽으로 위치하도록 분할합니다. 이 과정을 통해 분할된 왼쪽 배열과 오른쪽 배열에도 동일한 과정을 수행합니다. 이렇게 반복을 하다 보면 배열은 어느새 정렬이 되어 있을 겁니다. 여기서 주의할 점은 피봇(pivot)은 분할된 왼편이나 오른편 부분에 포함되지 않습니다. 그 이유는 피봇을 기준으로 왼편과 오른편의 분할 과정을 수행했다면, 피봇의 위치는 확정되었기 때문입니다. .. [ 알고리즘 공부 ] 합병 정렬(Merge Sort) 알고리즘 - 분할 정복 알고리즘(python, 파이썬) 합병 정렬(Merge Sort)이란? 입력이 2개의 부분 문제로 분할되고, 부분 문제의 크기가 1/2로 감소하는 분할 정복 알고리즘입니다. 즉, n개의 숫자들을 n/2개씩 2개의 부분문제로 분할하고, 각각의 부분 문제를 순환적으로 합병 정렬한 후, 2개의 정렬된 부분을 합병하여 정렬(정복)합니다. 즉, 합병 과정이 정복하는 것입니다. → 합병이란? 2개의 각각 정렬된 숫자들을 1개의 정렬된 숫자들로 합치는 것입니다. 합병 정렬이 어떻게 정렬하는지 감이 안 잡히실 수도 있는데, 이 그림 한 장이면 어떤 알고리즘이신지 알 수 있습니다. (화살표 옆 숫자는 실행 순서를 의미합니다.) 합병 정렬 수행 과정을 설명해 보도록 하겠습니다. 맨 위에 원소의 개수가 8인 배열이 정렬되지 않은 채 있습니다. 저 배열을 정.. [ 알고리즘 공부 ] 시간 복잡도(빅오Big-Oh, 빅오메가Big-Omega, 세타Theta) 시간 복잡도란? 알고리즘의 효율성은 알고리즘의 수행 시간 또는 알고리즘이 수행하는 동안 사용되는 메모리 공간의 크기로 나타낼 수 있습니다. 이들을 각각 시간복잡도, 공간복잡도로 나타낼 수 있습니다. 시간복잡도는 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 비례한 함수로 표현합니다. 예를 들어, 숫자 카드가 10장이 있고 이 중에서 최대 숫자를 찾는데, 순차 탐색으로 찾는 경우에 숫자 비교가 기본적인 연산이고, 숫자 비교가 9번입니다. 숫자 카드가 만약에 n장이 있다면, 숫자 비교는 n -1 번을 하므로 n -1이 시간복잡도가 됩니다. ▶ 복잡도를 표현하는 방법 - 최악 경우 분석 '어떤 입력이 주어지더라도 알고리즘의 수행시간이 얼마 이상은 넘지 않는다'라는 상한(Upper Bound)의 의미 보.. [알고리즘 공부] 보이어 무어 알고리즘 Boyer-Moore Algorithm(문자열 검색 알고리즘)(2) 앞서 Boyer-Moore 알고리즘에 사용되는 두 원리 중 Bad Character 원리를 살펴 보았다. 이번에는 그 나머지 원리인 Good Suffix 원리를 배워보려고 한다. 2021.07.26 - [Algorithm/Pattern Searching] - [알고리즘 공부] Boyer-Moore Algorithm(문자열 검색 알고리즘)(1) [알고리즘 공부] Boyer-Moore Algorithm(문자열 검색 알고리즘)(1) Boyer-Moore 알고리즘 또한 앞서 봤던 KMP 알고리즘과 같이 문자열을 검색할 때, 패턴을 둘 이상 이동할 수 있도록 패턴에 대한 사전 처리를 진행합니다. ↓그 전 KMP 알고리즘 관련 글 2021.07.23 - [Algori bblackscene21.tistory.com .. [알고리즘 공부] 보이어 무어 알고리즘 Boyer-Moore Algorithm(문자열 검색 알고리즘)(1) Boyer-Moore 알고리즘 또한 앞서 봤던 KMP 알고리즘과 같이 문자열을 검색할 때, 패턴을 둘 이상 이동할 수 있도록 패턴에 대한 사전 처리를 진행합니다. ↓그 전 KMP 알고리즘 관련 글 2021.07.23 - [Algorithm/Pattern Searching] - [알고리즘 공부] KMP Algorithm (문자열 검색 알고리즘) 이 알고리즘을 이 두 가지 접근법을 조합한 것입니다. 각각의 접근법에 대해 패턴을 처리하고, 검색을 수행할 때 두 접근법이 제안하는 값 중 최대값만큼 패턴을 이동합니다. (두 가지 원리 모두 각각 독립적으로 사용해도 문자열 검색이 가능합니다.) 1) Bad Character 2) Good Suffix 이번 글에서는 Bad Character 원리부터 살펴보겠습니다. .. [알고리즘 공부] KMP Algorithm (문자열 검색 알고리즘) 밑에 보이는 예시는 KMP 알고리즘 사용 전인데 효율이 떨어져 보입니다. 텍스트와 패턴이 일치하는지 차례대로 순회하면서 비교해보기 때문에 시간복잡도는 O(문자열 길이 * 패턴 길이) = O(N)으로, 시간이 오래 걸립니다. KMP 알고리즘이란? 패턴과 텍스트의 불일치를 감지할 때마다 그 전에 검사해왔던 텍스트의 문자들이 무엇인지 알고 있습니다(처음 검사할 때 A B A B 로 B에서 불일치가 발생했을 때, 불일치 발생 전 문자들이 A, B, A). KMP 알고리즘은 이를 이용해 불필요한 검사는 스킵합니다. 시간 복잡도는 최악의 경우, O(문자열 길이 * 패턴 길이) 이므로 위와 같이 O(N)입니다. 알고리즘 구성 lps[ ] : 패턴 문자열에서 접두사와 접미사가 일치하는 최대 길이를 저장하는 배열 (밑에.. 이전 1 다음
