C++에서 피크 요소란?
이 튜토리얼에서는 주어진 배열에서 피크(peak) 요소를 찾는 프로그램을 C++로 작성해 보겠습니다.
피크 요소란 자신의 양옆에 있는 인접 요소보다 크거나 같은 값을 가지는 요소를 말합니다. 배열에는 피크 요소가 여러 개 존재할 수 있으며, 이 예제에서는 그중 하나를 찾아 반환합니다.
문제 해결 접근 방식
문제를 해결하는 단계는 다음과 같습니다.
- 테스트용 더미 데이터로 배열을 초기화합니다.
- 첫 번째 요소와 마지막 요소가 피크 조건을 만족하는지 먼저 확인합니다.
- 두 번째 요소부터 배열을 순회하면서 다음을 검사합니다.
- 현재 요소가 이전 요소와 다음 요소보다 크거나 같은지 확인합니다.
- 조건을 만족하면 해당 요소를 즉시 반환합니다.
- 결과를 출력합니다.
경계 요소 처리가 중요한 이유
배열의 첫 번째 요소는 왼쪽 이웃이 없고, 마지막 요소는 오른쪽 이웃이 없습니다. 따라서 경계 요소는 존재하는 한쪽 이웃과만 비교하면 되며, 이를 별도로 처리해 두면 반복문에서 배열 범위를 벗어나는 오류를 방지할 수 있습니다.
예제 코드
전체 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
int findPeakElement(int arr[], int n) {
// 배열에 요소가 하나뿐인 경우 그 요소가 피크입니다.
if (n == 1) {
return arr[0];
}
// 첫 번째 요소 확인
if (arr[0] >= arr[1]) {
return arr[0];
}
// 마지막 요소 확인
if (arr[n - 1] >= arr[n - 2]) {
return arr[n - 1];
}
// 나머지 요소 순회하며 피크 검사
for (int i = 1; i < n - 1; i++) {
if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1]) {
return arr[i];
}
}
return arr[0];
}
int main() {
int arr[] = { 1, 2, 5, 4, 7 };
cout << findPeakElement(arr, 5) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
7
코드 동작 설명
예제 배열 {1, 2, 5, 4, 7}에서 첫 번째 요소인 1은 2보다 작고, 마지막 요소인 7은 4보다 크므로 마지막 요소가 피크가 됩니다. 실제로 이 배열에는 5와 7이라는 두 개의 피크가 존재하지만, 알고리즘은 먼저 발견되는 하나만 반환합니다.
이 알고리즘의 시간 복잡도는 O(n)으로, 배열을 한 번 순회하며 피크를 찾습니다. 참고로 이진 탐색을 활용하면 O(log n)으로 최적화할 수도 있습니다.
마무리
이 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요. 도움이 되었기를 바랍니다!