Lecture 1: Introduction and Peak Finding

배우는 것 :

• Efficient procedures for solving problems on large inputs
• Scalability
• Classic data structures and elementary algorithms
• Real implementations in Python

---

Peak Finder (극댓값 찾기) 

 

1차원 배열의 경우: 

만약 어떤 위치에서 해당 수가 오른쪽 값보다 크거나 같고, 왼쪽 값보다도 크거나 같으면, 극대라고 할 수 있다.

 

단도직입적인 접근: 

왼쪽에서 시작해서 순차적으로 오른쪽으로 이동, 해당 값을 왼쪽 오른쪽 값과 비교하며 극대값을 찾는다. 

 

분할 정복 알고리즘:

 

만약 가운데에서 시작한다면? 중간 원소를 선택, 왼쪽 원소, 오른쪽 원소와 중간 원소를 비교한다.

오른쪽이 크다면 오른쪽 절반에서 탐색, 왼쪽이 크다면 왼쪽 절반에서 탐색, 중간 원소가 크면 중간 원소를 극대로 지정. 

같은 규칙으로 한 쪽에서 중간 원소 택하여 반복. 

 

이 때의 시간 복잡도: 

 

2차원 배열의 경우:

 

 

a≥b, a≥d, a≥c, a≥e 일 때 a는 2차원 배열의 극대이다. 

 

 

1차원 분할 정복을 2차원 배열에 적용하기 #1 :

 

• 가운데 열을 고른다
• i,j 에서 극대를 찾는다
• (i, j)를 시작점으로 해당 i 행에서 1차원 배열의 극대를 찾는다. 

 

=> 하지만 이는 우리가 원하는 참 극대값을 찾지 못할 수 있음. 

전체 2차원 배열에서 극대값은 20이지만 우리는 i행의 극대값인 14를 얻게 된다. 

 

1차원 분할 정복을 2차원 배열에 적용하기 #2 :

 

• 가운데 열 j = m/2 를 고른다
• (i, j) 에서 가장 큰 값을 찾는다
• (i, j-1), (i, j), (i, j+1) 을 비교한다
• (i, j) 가 양 옆보다 크거나 작다면 (i, j)는 극대값
• 그렇지 않다면 더 큰 열 부분(오/왼)으로 가서 처음부터 반복한다

 

이 때의 시간 복잡도:

 

 

 

 

* 1차원 배열 극대값 찾기 C++ 코드 구현 *

// A C++ program to find a peak element
#include <bits/stdc++.h>
using namespace std;
 
// Find the peak element in the array
int findPeak(int arr[], int n)
{
    // first or last element is peak element
    if (n == 1)
      return 0;
    if (arr[0] >= arr[1])
        return 0;
    if (arr[n - 1] >= arr[n - 2])
        return n - 1;
 
    // check for every other element
    for (int i = 1; i < n - 1; i++) {
 
        // check if the neighbors are smaller
        if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1])
            return i;
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 3, 20, 4, 1, 0 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Index of a peak point is "
         << findPeak(arr, n);
    return 0;
}
 
// This code is contributed by Arnab Kundu

 

Find a peak element - GeeksforGeeks

Find a peak element - GeeksforGeeks