C++로 배열에서 주어진 합과 일치하는 삼중항(Triplet) 찾는 방법

이 튜토리얼에서는 배열 안에서 세 원소의 합이 주어진 숫자와 일치하는 삼중항(triplet)을 찾는 프로그램을 작성하는 방법을 알아보겠습니다.

문제 해결 접근 방식

가장 기본적인 방법은 브루트 포스(Brute Force) 탐색입니다. 세 개의 중첩 반복문을 사용하여 배열의 모든 세 원소 조합을 확인하는 방식입니다. 단계별로 살펴보겠습니다.

• 테스트용 더미 데이터로 배열을 생성합니다.

• 세 원소를 가리키기 위해 세 개의 중첩 반복문을 작성하고, 각 반복문은 배열 끝까지 순회합니다.

  • 세 원소의 합을 계산합니다.

  • 계산된 합을 주어진 목표 값과 비교합니다.

  • 두 값이 일치하면 해당 원소들을 출력하고 모든 반복문을 종료합니다.

이 방법의 시간 복잡도는 O(n³)으로, 배열의 크기가 클 경우 비효율적일 수 있습니다. 하지만 문제의 동작 원리를 이해하기에는 가장 직관적인 접근 방식입니다.

예제 코드

실제 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;

bool findTriplet(int arr[], int arr_size, int sum) {
    for (int i = 0; i < arr_size - 2; i++) {
        for (int j = i + 1; j < arr_size - 1; j++) {
            for (int k = j + 1; k < arr_size; k++) {
                if (arr[i] + arr[j] + arr[k] == sum) {
                    cout << arr[i] << " " << arr[j] << " " << arr[k] << endl;
                    return true;
                }
            }
        }
    }
    return false;
}

int main() {
    int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
    findTriplet(arr, 7, 12);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

1 4 7

배열 {1, 2, 3, 4, 5, 6, 7}에서 처음으로 발견된 합이 12가 되는 조합은 1 + 4 + 7 = 12입니다. 함수가 조합을 찾는 즉시 true를 반환하며 종료되므로, 이후에 존재할 수 있는 다른 조합들(예: 2 + 3 + 7)은 출력되지 않습니다.

마무리

이 튜토리얼에서는 단순한 삼중 반복문을 활용해 주어진 합과 일치하는 삼중항을 찾는 방법을 배웠습니다. 성능을 개선하려면 정렬 후 투 포인터(two-pointer) 기법을 사용하여 O(n²)까지 최적화할 수 있습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.