C 프로그램으로 합이 k 이하인 세 원소 조합(트리플렛) 출력하기

여러 개의 요소로 구성된 배열이 주어졌을 때, 정확히 세 개의 요소를 선택하여 그 합이 k보다 작거나 같은 모든 조합(트리플렛)을 찾아내는 것이 이번 글의 목표입니다. 중첩 반복문을 활용한 완전 탐색 방식으로 비교적 간단하게 해결할 수 있습니다.

문제 예시

입력 − arr[] = {1, 2, 3, 8, 5, 4}

출력 − {1, 2, 3} {1, 2, 5} {1, 2, 4} {1, 3, 5} {1, 3, 4} {1, 5, 4} {2, 3, 5} {2, 3, 4}

접근 방법

먼저 sizeof(arr)/sizeof(arr[0]) 연산을 통해 배열의 크기를 계산합니다. 이 크기를 기준으로 첫 번째 반복문(i)은 size-2 미만까지, 두 번째 반복문(j)은 size-1 미만까지, 세 번째 반복문(k)은 size 미만까지 순회하면서 가능한 모든 세 원소 조합을 검사합니다. 각 조합의 합이 k 이하이면 해당 조합을 화면에 출력합니다.

알고리즘

START
Step 1 -> 합의 기준값 k(예: 10)를 저장할 int형 변수 sum과 i, j, k 선언
Step 2 -> sizeof(arr)/sizeof(arr[0])로 배열 크기를 계산하여 size 초기화
Step 3 -> i를 0부터 시작하여 i<size-2 조건으로 반복
    j를 i+1부터 시작하여 j<size-1 조건으로 반복
        k를 j+1부터 시작하여 k<size 조건으로 반복
            IF arr[i]+arr[j]+arr[k] <= sum
                arr[i], arr[j], arr[k] 출력
            End IF
        End Loop for
    End Loop For
Step 4 -> End Loop For
STOP

C 코드 예제

#include <stdio.h>
int main(int argc, char const *argv[]) {
    int arr[] = {1, 2, 3, 8, 5, 4};
    int sum = 10;
    int i, j, k;
    int size = sizeof(arr)/sizeof(arr[0]);
    for (i = 0; i < size-2; i++) {
        for (j = i+1; j < size-1; j++) {
            for (k = j+1; k < size; k++) {
                if (arr[i] + arr[j] + arr[k] <= sum)
                    printf("{%d, %d, %d}\n", arr[i], arr[j], arr[k]);
            }
        }
    }
    return 0;
}

실행 결과

위 프로그램을 실행하면 아래와 같은 출력을 얻을 수 있습니다.

{1, 2, 3}
{1, 2, 5}
{1, 2, 4}
{1, 3, 5}
{1, 3, 4}
{1, 5, 4}
{2, 3, 5}
{2, 3, 4}

시간 복잡도

세 개의 반복문이 서로 중첩되어 있으므로 이 알고리즘의 시간 복잡도는 O(n³)입니다. 따라서 배열의 크기가 커질수록 실행 시간이 빠르게 늘어날 수 있으며, 입력 크기가 큰 경우에는 배열을 정렬한 뒤 투 포인터 기법을 활용하는 방식으로 성능을 개선할 수 있습니다.