[TIL, 일일 회고] 2024.12.19 - 바이토닉 수열(Bitonic Sequence)이란❓

 

 

바이토닉 수열(Bitonic Sequence)이란❓

바이토닉 수열(Bitonic Sequence)은 다음과 같은 특징을 가진 수열입니다.

1. 수열이 처음에는 증가하다가 어느 지점을 기준으로 감소하는 형태
2. 즉, 왼쪽에서부터 봤을 때 어느 한 지점까지는 오름차순이었다가, 그 이후부터는 내림차순인 수열

바이토닉 수열의 예시

 

• {1, 3, 5, 7, 6, 4, 2}
  • 7을 기준으로 증가했다가 감소
• {1, 2, 3, 4}
  • 순수하게 증가하는 수열도 바이토닉 수열
• {4, 3, 2, 1}
  • 순수하게 감소하는 수열도 바이토닉 수열
• {1, 2, 2, 3}
  • 바이토닉 수열이 아님 (같은 값이 연속으로 나타남)

바이토닉 수열(Bitonic Sequence)의 특징

 

 

• 반드시 하나의 "peak" 값이 존재
• peak를 기준으로 왼쪽은 오름차순, 오른쪽은 내림차순
• 수열의 값들은 모두 달라야 함 (중복된 값이 있으면 안 됨)

---

 

peak란?

• Peak는 "봉우리" 또는 "정점"이라는 의미로, 수열에서는 다음과 같은 특징을 가진 값을 의미합니다.

수열: [1, 3, 5, 7, 6, 4, 2]
            ↑
           peak
여기서 7이 peak입니다
- 7은 왼쪽 값(5)보다 크고
- 7은 오른쪽 값(6)보다 큽니다

1. 기본 정의
   • 이웃한 값들보다 큰 값
   • 수열에서 가장 높은 지점
2. 구체적인 조건:
   • 왼쪽 값보다 크고 (arr[i] > arr[i-1])
   • 오른쪽 값보다 큰 (arr[i] > arr[i+1])
   • 위치의 값