이 튜토리얼에서는 C++를 사용하여 2차원 배열에서 피크(peak) 요소를 찾는 프로그램을 작성하는 방법을 알아보겠습니다.
피크 요소란 무엇인가?
피크 요소란 상하좌우에 인접한 모든 요소보다 값이 큰 요소를 의미합니다. 즉, 특정 요소의 위, 아래, 왼쪽, 오른쪽 값이 모두 해당 요소보다 작다면 그 요소를 피크 요소라고 부릅니다.
문제 해결 접근 방법
2차원 배열은 모서리, 테두리, 내부 영역에 따라 인접 요소의 개수가 다르기 때문에 위치별로 조건을 나누어 검사해야 합니다. 문제를 해결하는 단계는 다음과 같습니다.
- 더미 데이터로 2차원 배열을 초기화합니다.
- 배열 전체를 이중 반복문으로 순회하며 다음 순서로 검사합니다.
- 먼저 배열의 네 모서리 요소를 확인합니다.
- 다음으로 첫 번째 행과 마지막 행에 속한 요소에 대한 조건을 검사합니다.
- 이어서 첫 번째 열과 마지막 열에 속한 요소를 확인합니다.
- 마지막으로 나머지 내부(중간) 요소들을 검사합니다.
- 각 경우마다 현재 요소를 주변 요소들과 비교합니다. 위치에 따라 비교해야 할 인접 요소의 수와 방향이 달라진다는 점에 유의하세요.
- 피크 요소를 찾는 즉시 해당 값을 반환하고 탐색을 종료합니다.
예제 코드
위에서 설명한 로직을 구현한 전체 코드입니다.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 256;
int findPeakElement(int arr[][MAX], int rows, int columns) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (i == 0 && j == 0) {
if (arr[i][j] > arr[i + 1][j] && arr[i][j] > arr[i][j + 1]) {
return arr[i][j];
}
}
else if (i == 0 && j == columns - 1) {
if (arr[i][j] > arr[i + 1][j] && arr[i][j] > arr[i][j - 1]) {
return arr[i][j];
}
}
else if (i == rows - 1 && j == 0) {
if (arr[i][j] > arr[i - 1][j] && arr[i][j] > arr[i][j + 1]) {
return arr[i][j];
}
}
else if (i == rows - 1 && j == columns - 1) {
if (arr[i][j] > arr[i - 1][j] && arr[i][j] > arr[i][j - 1]) {
return arr[i][j];
}
}
else if (i == 0) {
if (arr[i][j] > arr[i][j - 1] && arr[i][j] > arr[i][j + 1] && arr[i][j] > arr[i + 1][j]) {
return arr[i][j];
}
}
else if (i == rows - 1) {
if (arr[i][j] > arr[i][j - 1] && arr[i][j] > arr[i][j + 1] && arr[i][j] > arr[i - 1][j]) {
return arr[i][j];
}
}
else if (j == 0) {
if (arr[i][j] > arr[i - 1][j] && arr[i][j] > arr[i + 1][j] && arr[i][j] > arr[i][j + 1]) {
return arr[i][j];
}
}
else if (j == columns - 1) {
if (arr[i][j] > arr[i - 1][j] && arr[i][j] > arr[i + 1][j] && arr[i][j] > arr[i][j - 1]) {
return arr[i][j];
}
}
else {
if (arr[i][j] > arr[i][j - 1] && arr[i][j] > arr[i][j + 1] && arr[i][j] > arr[i - 1][j] && arr[i][j] > arr[i + 1][j]) {
return arr[i][j];
}
}
}
}
return -1;
}
int main() {
int arr[][MAX] = {
{ 1, 2, 3, 4 },
{ 2, 3, 4, 5 },
{ 1, 3, 7, 5 },
{ 1, 2, 6, 6 } };
int rows = 4, columns = 4;
cout << findPeakElement(arr, rows, columns) << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
7
예제 배열에서 값 7은 세 번째 행 세 번째 열에 위치하며, 주변의 4, 5, 3, 6보다 모두 크므로 피크 요소임을 확인할 수 있습니다.
시간 복잡도
이 알고리즘은 배열의 모든 요소를 한 번씩 검사하므로 시간 복잡도는 O(rows × columns)입니다. 공간 복잡도는 추가 메모리를 사용하지 않으므로 O(1)입니다.
마무리
지금까지 C++에서 2차원 배열의 피크 요소를 찾는 방법을 살펴보았습니다. 위치별 경계 조건 처리가 핵심이라는 점을 기억하시기 바랍니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.