C++로 배열에서 합이 0이 되는 모든 삼중항(Triplet) 찾기

이 튜토리얼에서는 배열 내 세 개의 요소(삼중항)를 골라 그 합이 0이 되는 모든 조합을 찾아 출력하는 프로그램을 C++로 작성해 보겠습니다.

가장 기본적인 방법인 브루트 포스(Brute Force) 접근법을 사용하며, 문제 해결 과정은 다음과 같습니다.

문제 해결 단계

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

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

  • 선택한 세 요소의 합을 계산합니다.

  • 계산된 합이 0과 같은지 비교합니다.

  • 합이 0이라면 해당 세 요소를 출력하고, 삼중항을 찾았음을 표시합니다.

• 모든 경우를 확인한 후에도 삼중항을 찾지 못했다면, 존재하지 않는다는 메시지를 출력합니다.

예제 코드

위 알고리즘을 구현한 전체 코드는 다음과 같습니다.

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

void findTripletsWithSumZero(int arr[], int n) {
    bool is_found = false;
    for (int i = 0; i < n-2; i++) {
        for (int j = i+1; j < n-1; j++) {
            for (int k = j+1; k < n; k++) {
                if (arr[i] + arr[j] + arr[k] == 0) {
                    cout << arr[i] << " " << arr[j] << " " << arr[k] << endl;
                    is_found = true;
                }
            }
        }
    }
    if (!is_found) {
        cout << "Triplets doesn't exist" << endl;
    }
}

int main() {
    int arr[] = {0, 1, -1, 2, 2, -4, 3, 4};
    findTripletsWithSumZero(arr, 8);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.

0 1 -1
0 -4 4
1 -4 3
2 2 -4

시간 복잡도 분석

이 방식은 세 개의 중첩 반복문을 사용하기 때문에 시간 복잡도는 O(n³)입니다. 배열의 크기가 작을 때는 충분히 실용적이지만, 크기가 커질수록 성능이 급격히 저하될 수 있습니다.

성능을 개선해야 하는 상황이라면 배열을 먼저 정렬한 뒤 투 포인터(Two Pointer) 기법을 활용하는 방법(O(n²))을 고려해볼 수 있습니다.

마무리

이번 튜토리얼에서는 C++를 이용해 합이 0이 되는 모든 삼중항을 찾는 브루트 포스 방식을 살펴보았습니다. 코드에 대해 궁금한 점이 있다면 댓글로 남겨주세요.