C++에서 N보다 작은 고유한 숫자 쌍을 찾는 방법

개요

이 튜토리얼에서는 C++를 사용하여 주어진 숫자 n보다 작은 값으로 만들 수 있는 고유한(unique) 숫자 쌍을 모두 찾아 출력하는 방법을 알아봅니다.

예를 들어 n = 5가 주어지면, 1부터 4 사이의 서로 다른 두 숫자로 구성된 쌍인 (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)를 얻을 수 있습니다.

문제 해결 접근 방식

이 문제는 중첩 반복문(nested loop)을 활용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 찾고자 하는 기준이 되는 숫자 n을 초기화합니다.
• 바깥쪽 반복문으로 i를 1부터 n 미만까지 순회합니다.
• 안쪽 반복문으로 j를 i + 1부터 n 미만까지 순회합니다.
• 각 단계에서 (i, j) 쌍을 출력합니다.

j의 시작 값을 i + 1로 설정하면 같은 숫자가 두 번 등장하는 경우(예: (2,2))를 자연스럽게 제외할 수 있고, i가 j보다 항상 작으므로 (1,2)와 (2,1)처럼 순서만 다른 중복 쌍도 발생하지 않습니다.

C++ 구현 예제

위 접근 방식을 코드로 구현하면 다음과 같습니다.

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

void uniquePairs(int n) {
    for (int i = 1; i < n; ++i) {
        for (int j = i + 1; j < n; j++) {
            cout << "(" << i << "," << j << ")" << endl;
        }
    }
}

int main() {
    int n = 5;
    uniquePairs(n);
    return 0;
}

실행 결과

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

(1,2)
(1,3)
(1,4)
(2,3)
(2,4)
(3,4)

시간 복잡도

이 알고리즘은 두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)입니다. n이 크지 않은 경우에는 충분히 효율적이지만, n이 매우 커지면 실행 시간이 급격히 늘어날 수 있다는 점을 유의해야 합니다.

마무리

이번 튜토리얼에서는 C++의 중첩 반복문을 이용해 n보다 작은 고유한 숫자 쌍을 찾는 방법을 살펴보았습니다. 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요!