알고리즘 (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 - [Algoribblackscene21.tistory.com Go.. [알고리즘 공부] 보이어 무어 알고리즘 Boyer-Moore Algorithm(문자열 검색 알고리즘)(1) Boyer-Moore 알고리즘 또한 앞서 봤던 KMP 알고리즘과 같이 문자열을 검색할 때, 패턴을 둘 이상 이동할 수 있도록 패턴에 대한 사전 처리를 진행합니다. ↓그 전 KMP 알고리즘 관련 글2021.07.23 - [Algorithm/Pattern Searching] - [알고리즘 공부] KMP Algorithm (문자열 검색 알고리즘) 이 알고리즘을 이 두 가지 접근법을 조합한 것입니다.각각의 접근법에 대해 패턴을 처리하고,검색을 수행할 때 두 접근법이 제안하는 값 중 최대값만큼 패턴을 이동합니다.(두 가지 원리 모두 각각 독립적으로 사용해도 문자열 검색이 가능합니다.) 1) Bad Character2) 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 다음
