C - [Backjoon 18869] 멀티버스 II (feat. 이분탐색, 좌표압축)

2025.02.03 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 이분 탐색 (Binary Search)

[자료구조 & 알고리즘] 이분 탐색 (Binary Search)

이분 탐색 (Binary Search) 알고리즘이분 탐색(Binary Search)은 정렬된 배열에서 특정 값을 빠르게 찾는 알고리즘입니다. 탐색 범위를 절반으로 줄이기 때문에 시간 복잡도가 O(log⁡N)O(\log N)으로 매우

rnasterofmysea.tistory.com

2025.02.04 - [Computer Science/알고리즘 문제] - C - [백준 18870] 좌표 압축 (feat. 이분탐색, 퀵정렬)

BOJ_18869 멀티버스 I (https://www.acmicpc.net/problem/18869)

N개의 행성과 M개의 우주가 주어집니다. 각 우주는 N개의 행성을 가지고 있으며, 행성의 크기를 나타내는 수들이 주어집니다.
두 우주가 동일한 상대적인 크기 순서를 가지고 있다면, 이 두 우주는 같은 구조를 가진다고 정의합니다.

우주의 쌍 중 같은 구조를 가진 쌍의 개수를 구하는 것이 목표입니다.

입력 형식

첫 번째 줄에 행성의 개수 N과 우주의 개수 M이 주어집니다. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 100)
그다음 줄부터 각 우주에 대해 N개의 정수가 주어지며, 각 숫자는 행성의 크기를 의미합니다.
각 우주 내 숫자는 1,000,000 이하의 자연수입니다.

Checkpoint

코드가 길어지니 전체적인 설계보다 C언어로 설계된 내용을 구현하는 것에 어려움을 겪고 있습니다.

C++만 하더라도 중복 제거, 정렬 등 STL을 활용하고 있으나 이것을 수동으로 구현하려고 하니 에러 발생이 잦고 있고요... 디테일을 신경쓰는 것이 필요하나 부족하다고 또 느낍니다.

전체적인 흐름은 어제 업로드했던 좌표 압축(https://rnasterofmysea.tistory.com/104) 문제를 해결했다면 쉽게 접근할 수 있습니다.

각 우주를 입력받는 동시에 복사본을 생성하고, 각 우주에 대한 행성들을 오름차순으로 복사본에 나열한 후, 본래의 우주를 오름차순으로 정렬된 우주에서 탐색한 후 반환되는 인덱스를 본래의 우주에 저장하면, 우주 안에 행성들의 상대적 위치가 저장되게 됩니다.

즉, 상대적 위치로 본 행성들을 압축하기 위해 설계된 코드입니다. 좌표 압축 문제와 유사하죠?

그 후, 각 우주들을 순회하며 비교하여 행성들의 상대적 위치가 같은 우주를 카운트하면 되는 문제입니다.

문제 접근

각 우주에 있는 행성 크기를 상대적인 크기 순서로 변환하여 비교하면 두 우주가 같은 구조인지 쉽게 판단할 수 있습니다.
좌표 압축과 이진 탐색을 활용하여 각 우주의 상대적 순위를 계산할 수 있습니다.
모든 우주에 대해 상대적 구조가 같은 경우를 세기 위해 우주의 상대적 순위를 배열로 저장하고, 이를 비교하는 방식으로 진행합니다.

구현 단계

입력 처리:
- N과 M을 입력받습니다.
- 각 우주의 행성 크기를 universe 배열에 저장하고, 복사본을 copy_universe 배열에 저장합니다.
좌표 압축 및 이진 탐색:
- 각 우주에 대해 행성 크기를 정렬하여 copy_universe에 저장합니다.
- 정렬된 배열에서 이진 탐색을 사용하여 각 행성의 상대적 순위를 찾고, 이를 원본 배열 universe에 저장합니다.
우주의 구조 비교:
- 두 우주의 상대적 순위를 비교하여 같은 구조를 가진 경우를 확인하고, 같은 구조를 가진 쌍의 개수를 셉니다.

구현 코드

/*
C_BOJ_18869_멀티버스 I 
https://www.acmicpc.net/problem/18869
*/
#include 
#include 
#include 

// 정렬을 위한 비교 함수
int compare(const void *a, const void *b) {
    return (*(int *)a) - (*(int *)b);
}

// 두 배열이 같은 구조인지 확인하는 함수
int is_same_universe(int *u1, int *u2, int N) {
    for (int i = 0; i < N; i++) {
        if (u1[i] != u2[i]) {
            return 0;  // 두 배열이 다름
        }
    }
    return 1;  // 두 배열이 같음
}

int main() {
    int M, N;
    int universe[100][10000];
    int copy_universe[100][10000];

    scanf("%d %d", &M, &N);

    // 입력 받기
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &universe[i][j]);
            copy_universe[i][j] = universe[i][j];
        }
    }

    // 각 우주의 상대적 순위 계산
    for (int i = 0; i < M; i++) {
        qsort(copy_universe[i], N, sizeof(int), compare);

        for (int j = 0; j < N; j++) {
            int target = universe[i][j];
            int start = 0, end = N - 1;

            // 이진 탐색으로 상대적 순위 찾기
            while (start <= end) {
                int mid = start + (end - start) / 2;
                if (copy_universe[i][mid] == target) {
                    universe[i][j] = mid;
                    break;
                } else if (copy_universe[i][mid] < target) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
    }

    // 우주 간 비교 작업
    int count = 0;
    for (int i = 0; i < M; i++) {
        for (int j = i + 1; j < M; j++) {
            if (is_same_universe(universe[i], universe[j], N)) {
                count++;
            }
        }
    }

    // 결과 출력
    printf("%d\n", count);

    return 0;
}

코드 설명

int compare(const void *a, const void *b) {
    return (*(int *)a) - (*(int *)b);
}

qsort 함수에서 사용할 비교 함수입니다.
두 정수를 비교하여 오름차순으로 정렬하기 위해 사용합니다.
- 반환값이 음수면 순서를 유지하고, 양수면 순서를 바꿉니다.

int is_same_universe(int *u1, int *u2, int N) {
    for (int i = 0; i < N; i++) {
        if (u1[i] != u2[i]) {
            return 0;  // 두 배열이 다름
        }
    }
    return 1;  // 두 배열이 같음
}

두 우주의 상대적 순위 배열이 같은지 확인하는 함수입니다.
- 배열 u1과 u2를 순차적으로 비교하여 하나라도 값이 다르면 0을 반환합니다.
- 모든 값이 같으면 1을 반환합니다.

int main() {
    int M, N;
    int universe[100][10000];
    int copy_universe[100][10000];

M: 우주의 개수
N: 행성의 개수
universe: 입력으로 주어지는 각 우주의 행성 크기를 저장하는 배열
copy_universe: universe 배열을 복사하여 정렬된 데이터를 저장하는 배열

    scanf("%d %d", &M, &N);

우주의 개수 M과 행성의 개수 N을 입력받습니다.

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &universe[i][j]);
            copy_universe[i][j] = universe[i][j];
        }
    }

각 우주의 행성 크기를 입력받아 universe와 copy_universe 배열에 저장합니다.
copy_universe는 원본 데이터를 복사해 정렬 후 사용할 배열입니다.

    for (int i = 0; i < M; i++) {
        qsort(copy_universe[i], N, sizeof(int), compare);

각 우주에 대해 qsort를 사용하여 행성 크기를 정렬합니다.

        for (int j = 0; j < N; j++) {
            int target = universe[i][j];
            int start = 0, end = N - 1;

            // 이진 탐색으로 상대적 순위 찾기
            while (start <= end) {
                int mid = start + (end - start) / 2;
                if (copy_universe[i][mid] == target) {
                    universe[i][j] = mid;
                    break;
                } else if (copy_universe[i][mid] < target) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
    }

각 행성의 상대적 순위를 이진 탐색으로 찾아서 universe 배열에 저장합니다.
- target: 현재 행성의 크기
- start와 end: 이진 탐색을 위한 시작과 끝 인덱스
- mid: 중간 인덱스
- 이진 탐색을 통해 정렬된 배열에서 target의 위치(=순위)를 찾습니다.

    int count = 0;
    for (int i = 0; i < M; i++) {
        for (int j = i + 1; j < M; j++) {
            if (is_same_universe(universe[i], universe[j], N)) {
                count++;
            }
        }
    }

모든 우주의 쌍을 비교하여 같은 구조를 가진 경우를 확인합니다.
- is_same_universe 함수를 통해 두 우주가 같은 구조인지 비교합니다.
- 같은 구조인 경우 count를 증가시킵니다.

    printf("%d\n", count);

같은 구조를 가진 우주의 쌍의 개수를 출력합니다.

    return 0;
}

프로그램을 종료합니다.

코드 동작 요약

입력으로 주어진 행성 크기를 배열에 저장합니다.
각 우주에 대해 행성 크기를 오름차순으로 정렬하고, 이진 탐색을 통해 상대적 순위를 계산합니다.
모든 우주의 쌍을 비교하여 같은 구조를 가진 경우를 확인하고, 그 개수를 출력합니다.

핵심 로직

좌표 압축:
- 원본 배열의 값을 정렬된 배열에서 이진 탐색하여 상대적 순위로 변환합니다.
구조 비교:
- 두 우주의 상대적 순위 배열을 비교하여 같은 구조인지 판단합니다.

시간 복잡도 분석

입력 크기가 최대 M = 100,N = 10,000입니다.
각 우주에 대해 정렬(qsort)은 O(N \log N)의 시간 복잡도를 가집니다.
상대적 순위 계산을 위한 이진 탐색은 O(N \log N)입니다.
총 시간 복잡도는 O(M \cdot N \log N)로, 문제에서 주어진 입력 크기 내에서 효율적으로 동작합니다.

테스트 케이스

입력

출력

모든 우주가 서로 다른 구조를 가지므로 출력은 0입니다.

문제 해결 팁

이진 탐색을 통해 상대적 순위를 효율적으로 찾습니다.
qsort를 활용하여 각 우주의 데이터를 정렬합니다.
모든 우주 쌍을 비교할 때는 단순히 배열을 순차적으로 비교하는 방식이 가장 효율적입니다.

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.

'Computer Science > 알고리즘 문제' 카테고리의 다른 글

Python - [백준 12789] 도키도키 간식드리미 (feat. 스택) (0)	2025.02.09
C - [백준 18870] 좌표 압축 (feat. 이분탐색, 퀵정렬) (0)	2025.02.07
★ C - [백준 2295] 세 수의 합 (feat. 이분탐색) (0)	2025.02.06
C - [백준 1931] 회의실 배정 (feat. 그리디, 퀵 정렬) (0)	2025.02.05
C - [백준 2217] 로프 (feat. 그리디, 퀵 정렬) (0)	2025.02.04