Peak 찾기

Peak란?

[0, 5, 7, 7, 7, 7, 9, 0, 4] 라는 배열을 위처럼 그려본다면, 저 빨간색 동그라미들이 모두 peak이다. 즉, a <= b and b >= c를 만족하는 b가 peak인 것이다. 다만 마지막 4는 오른쪽에 값이 없기 때문에 그냥 그 4가 peak이다.

Peak 찾기

전제

배열 안에 peak가 몇개있다는건 고려하지 않고 단순히 어떤 하나의 peak를 찾는다고 가정한다.

느린 방법 – 왼쪽부터 peak를 찾을때까지 비교

왼쪽값과 오른쪽값을 비교해서 왼쪽이 더 크거나 같으면 해당 배열의 peak중 하나가 그 왼쪽값이 된다.

# -*- coding: utf-8 -*- 

def findSimplePeakSlowly(arr):
  length = len(arr)

  if (length == 0) :
    print("배열에 원소가 없습니다")
    return

  # 값이 하나밖에 없으면 그 값이 peak이다
  if (length == 1) :
    return arr[0]

  # arr[i+1]을 했는데 해당 index가 배열 크기를 오바해서 
  # i+1에 위치한 값이 없을 수도 있기 때문에, length - 1 이렇게 미리 하나를 빼준다.
  # range(3) = [0, 1, 2]
  for i in range(length - 1) :
    // 왼쪽과 오른쪽을 비교
    if (arr[i] >= arr[i+1]) :
      return arr[i]

  # 오른쪽 위로 쭉 뻗어나가는 경우에는 마지막원소가 peak이다.
  return arr[length-1]


testCase1 = [44, 2, 9, 12, 8, 7, 9, 3, 4]
testCase2 = [0, 1, 2, 3, 4, 5, 6, 7, 8]
testCase3 = [0, 1, 2, 3, 4, 5, 20, 7, 8]
testCase4 = [0, 1, 5, 5, 5, 4, 3, 2, 0]
testCase5 = [4, 8, 7, 6, 5, 4, 12, 13, 6]
testCase6 = [4]

print( findSimplePeakSlowly(testCase1) ) # 44
print( findSimplePeakSlowly(testCase2) ) # 8
print( findSimplePeakSlowly(testCase3) ) # 20
print( findSimplePeakSlowly(testCase4) ) # 5
print( findSimplePeakSlowly(testCase5) ) # 8
print( findSimplePeakSlowly(testCase6) ) # 4

빠른 방법 – Divide and Conquer(나누고 정복하라!)

위의 방법대로 왼쪽부터 오른쪽 끝까지 peak를 찾기위해 하나하나 비교하는건 오래걸린다. 만약 맨 오른쪽에 peak가 딱 하나 있다면 전체를 비교해야 할것이다. Divide and Conquer방식을 사용하면 훨씬 빠르게 peak를 찾을 수 있다.

방식은 아래와 같다.

  1. 배열을 반으로 나눈다.

2. 그 반으로 나눈 지점에서 왼쪽 원소와 오른쪽 원소를 비교해서, 작은거나 같은 그 아래로 다 버리고, 반대쪽만 취한다. 어차피 오르막길에는 peak가 무조건 있을 것이기 때문이다.

3. 2번에서 얻은 배열을 또 반으로 나눠서 2번 과정을 반으로 나눈 그 위치에 있는 원소가 오른쪽보다 크거나 같을때 까지 계속한다. peak는 그 반으로 나눈 위치에 있는 원소가 된다.

Frame

좌우를 비교했을때 작은쪽(내리막길)은 버린다고 했는데, 그렇게 되면 배열을 새로 만들어야 한다. 그래서 기존의 들어온 배열을 잘라서 다시 배열을 만들기 보다는 하나의 frame을 만들어 줘서 그 안에서 또 나누는 방식으로 작성하는게 큰 배열이 들어왔을때 더 효율적(메모리, 속도)이라고 판단했다. frame을 만드는 과정은 다음과 같다.

1.맨 처음에는 startIndex = 0이고, lastIndex = 배열의 길이 - 1 의 범위를 가지는 영역을 frame으로 설정한다. 그리고 startIndex와 lastIndex를 바탕으로 middleIndex를 구한다.

2. middleIndex의 좌 우 값을 비교해서 오르막길이 오른쪽에 있는 경우에는 startIndex를 middleIndex로 설정한다

3. middleIndex의 좌 우 값을 비교해서 오르막길이 왼쪽에 있는 경우에는 lastIndex를 middleIndex로 설정한다

이런식으로 계속 반복해서 Frame을 만들고 그 안의 middleIndex값과 middleIndex-1 그리고 middleIndex+1 값들을 비교해서 peak를 찾으면 된다. peak를 찾는 더 구체적인 과정은 아래 코드에 나와있다.

# -*- coding: utf-8 -*-

import time

def findSimplePeakFastly(arr):
  length = len(arr)

  if (length == 0) :
    print("배열에 원소가 없습니다")
    return

  # 값이 하나밖에 없으면 그 값이 peak이다
  if (length == 1) :
    return arr[0]

  # 처음에 들어온 arr를 자르지 않고 반으로 나눴을때의 index만을 바탕으로 peak를 찾기 위해서는
  # startIndex와 lastIndex가 필요하다. 이게 frame역할을 해서 그 frame안에서 반으로 나누는 것이다.
  startIndex = 0
  lastIndex = length - 1

  while True :

    # frame안에 원소가 2개면 바로 좌우만 비교해서 크거나 같은값이 peak이다
    if (lastIndex - startIndex == 1) :
      return arr[startIndex] if (arr[startIndex] >= arr[lastIndex]) else arr[lastIndex]

    # frame안에 원소가 3개 이상일때는 divide and conquer !
    middleIndex = int((lastIndex - startIndex) / 2) + startIndex

    # 오른쪽으로 오르막길 (or 평지)
    if (arr[middleIndex-1] <= arr[middleIndex+1]) :

      # 오른쪽으로 쭉 오르막길 인줄 알았는데, middleIndex위치에 있는 값이 peak !
      if (arr[middleIndex] >= arr[middleIndex+1]) :
        return arr[middleIndex]

      # 오른쪽으로 쭉 오르막길이 있을 줄 알았는데, 바로 오른쪽이 끝지점 이었다면, lastIndex에 있는 값이 peak !
      if ( middleIndex + 1 == lastIndex ) :
        return arr[lastIndex]

      # frame 재설정
      startIndex = middleIndex
    
    # 왼쪽으로 오르막길
    else :

      # 왼쪽으로 쭉 오르막길 인줄 알았는데, middleIndex위치에 있는 값이 peak !
      if (arr[middleIndex] >= arr[middleIndex-1]) :
        return arr[middleIndex]

      # 왼쪽으로 쭉 오르막길이 있을 줄 알았는데, 바로 왼쪽이 끝지점 이었다면, startIndex에 있는 값이 peak !
      if ( middleIndex - 1 == startIndex ) :
        return arr[startIndex]

      # frame 재설정
      lastIndex = middleIndex


testCase1 = [44, 2, 9, 12, 8, 7, 9, 3, 4]
testCase2 = [0, 1, 2, 3, 4, 5, 6, 7, 8]
testCase3 = [8, 7, 6, 5, 4, 3, 2, 1, 0]
testCase4 = [8, 7, 6, 8, 4, 3, 2, 1, 10]
testCase5 = [0, 1, 2, 3, 4, 5, 20, 7, 8]
testCase6 = [0, 1, 5, 5, 5, 4, 3, 2, 0]
testCase7 = [4, 8, 7, 6, 5, 4, 12, 13, 6]
testCase8 = [4, 8, 7, 6, 7, 14, 5, 6]
testCase9 = [1, 0, 1, 10, 12, 14, 7, 4]
testCase10 = [4]

print(findSimplePeakFastly(testCase1)) # 12
print(findSimplePeakFastly(testCase2)) # 8
print(findSimplePeakFastly(testCase3)) # 8
print(findSimplePeakFastly(testCase4)) # 8
print(findSimplePeakFastly(testCase5)) # 20
print(findSimplePeakFastly(testCase6)) # 5
print(findSimplePeakFastly(testCase7)) # 8
print(findSimplePeakFastly(testCase8)) # 14
print(findSimplePeakFastly(testCase9)) # 14
print(findSimplePeakFastly(testCase10)) # 4

끝.

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다

Up Next:

10진법을 2진법으로 변환

10진법을 2진법으로 변환