C언어에서 정렬된 배열로 중복 제거하기

정렬된 배열은 중복 데이터를 효율적으로 제거하는 데 유용한 도구입니다. 정렬된 상태에서는 연속된 요소만 비교하여 중복 여부를 확인할 수 있으므로, 탐색 범위를 최소화하면서도 빠른 처리가 가능합니다. 본 기사에서는 C언어를 활용해 정렬된 배열에서 중복을 제거하는 방법을 설명하고, 구현 코드와 다양한 응용 사례를 소개합니다. 이를 통해 효율적인 데이터 처리 기법을 익히고 활용 방안을 탐구할 수 있습니다.

정렬된 배열과 중복 제거의 원리

정렬된 배열은 데이터가 오름차순 또는 내림차순으로 정렬되어 있어, 중복 제거를 간단하게 수행할 수 있는 구조적 장점을 제공합니다.

중복 제거의 핵심 원리

정렬된 배열에서는 연속된 두 요소만 비교하여 중복 여부를 판단할 수 있습니다.

같으면 중복: 두 요소가 동일한 경우, 중복으로 간주하고 하나를 제외합니다.
다르면 고유: 값이 다르면 중복이 아닌 것으로 간주하고 배열에 유지합니다.

효율성의 이유

정렬된 배열은 중복 제거 시 전체 배열을 순차적으로 탐색하는 O(n)의 시간 복잡도를 가집니다. 이는 정렬되지 않은 배열에서 중복을 제거하는 일반적인 방법(예: 해시 테이블 사용, O(n) 또는 O(n log n))보다 단순하고 메모리 사용량이 적습니다.

적용 예

예를 들어, 배열 {1, 1, 2, 3, 3, 4}는 이미 정렬된 상태입니다.

첫 번째와 두 번째 요소(1, 1)를 비교해 중복을 제거합니다.
세 번째와 네 번째 요소(3, 3)를 비교해 중복을 제거합니다.
결과 배열은 {1, 2, 3, 4}가 됩니다.

정렬된 배열을 활용하면 중복 제거 과정이 간단해지고, 대용량 데이터 처리에도 적합합니다.

중복 제거 알고리즘 설계

알고리즘의 핵심 아이디어

정렬된 배열에서 중복을 제거하기 위해, 배열의 연속된 요소를 순차적으로 탐색하며 중복을 확인하고 고유한 값을 유지합니다. 이 과정은 단일 탐색으로 이루어지며, 별도의 메모리 할당 없이 원본 배열을 수정할 수 있습니다.

알고리즘 단계

초기화: 배열의 첫 번째 요소를 기준으로 중복 확인을 시작합니다.
탐색 및 비교: 현재 요소와 이전 요소를 비교합니다.

값이 다르면 고유한 값으로 간주하고 저장 위치를 업데이트합니다.
값이 같으면 중복으로 간주하고 탐색을 계속합니다.

최종 배열 작성: 모든 탐색이 끝나면 중복이 제거된 배열과 새로운 길이를 반환합니다.

의사 코드

function removeDuplicates(array):
    if array is empty:
        return array

    writeIndex = 1  # 고유 값 저장 위치
    for readIndex = 1 to array.length - 1:
        if array[readIndex] != array[readIndex - 1]:
            array[writeIndex] = array[readIndex]
            writeIndex += 1

    return array[:writeIndex]

효율성

시간 복잡도: 배열을 한 번만 순차적으로 탐색하므로 O(n)
공간 복잡도: 추가 메모리를 사용하지 않으므로 O(1)

이 알고리즘은 원본 배열을 수정하는 방식으로 동작하며, 메모리 효율성이 중요한 애플리케이션에 적합합니다.
다음 단계에서는 이를 실제 C언어 코드로 구현해 보겠습니다.

C언어 코드로 구현

아래는 정렬된 배열에서 중복을 제거하는 C언어 구현 예제입니다.

구현 코드

#include <stdio.h>

// 정렬된 배열에서 중복 제거 함수
int removeDuplicates(int arr[], int size) {
    if (size == 0) {
        return 0; // 빈 배열 처리
    }

    int writeIndex = 1; // 고유 값을 저장할 위치

    // 배열 탐색 및 중복 제거
    for (int readIndex = 1; readIndex < size; readIndex++) {
        if (arr[readIndex] != arr[readIndex - 1]) {
            arr[writeIndex] = arr[readIndex];
            writeIndex++;
        }
    }

    return writeIndex; // 중복 제거 후 배열의 새로운 길이 반환
}

int main() {
    int arr[] = {1, 1, 2, 3, 3, 4, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("원본 배열: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // 중복 제거 실행
    int newSize = removeDuplicates(arr, size);

    printf("중복 제거 후 배열: ");
    for (int i = 0; i < newSize; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

코드 설명

함수 입력: 정렬된 배열 arr와 배열의 크기 size.
빈 배열 처리: 배열의 크기가 0인 경우 0을 반환.
중복 제거 알고리즘: readIndex로 배열 요소를 읽고, 중복되지 않은 경우 writeIndex에 저장.
최종 반환: 중복 제거 후 배열의 새로운 크기를 반환.

실행 예제

입력 배열: {1, 1, 2, 3, 3, 4, 4, 5}
출력 배열: {1, 2, 3, 4, 5}
출력 크기: 5

이 코드는 정렬된 배열에서 효율적으로 중복을 제거하며, 배열 내에서 직접 수정하여 메모리를 절약합니다.

시간 복잡도 분석

중복 제거 알고리즘의 성능을 분석하여 효율성을 평가합니다.

시간 복잡도

정렬된 배열에서 중복 제거 알고리즘은 배열을 한 번 순차적으로 탐색하며, 각 요소에 대해 비교 연산을 수행합니다.

탐색 횟수: 배열의 크기를 n이라 할 때, 최대 n-1번의 비교 연산이 이루어집니다.
총 연산: 요소를 읽고(readIndex), 쓰는(writeIndex) 작업이 한 루프 내에서 이루어집니다.

따라서, 이 알고리즘의 시간 복잡도는 O(n)입니다.

공간 복잡도

이 알고리즘은 원본 배열을 수정하여 중복 제거를 수행하므로, 추가적인 데이터 구조나 메모리를 사용하지 않습니다.

입력 배열 내에서 연산이 이루어지므로 공간 복잡도는 O(1)입니다.

효율성 비교

다른 중복 제거 방법과 비교했을 때, 본 알고리즘은 정렬된 배열의 특성을 활용해 효율적입니다.

정렬되지 않은 배열의 경우:

정렬 작업(예: 병합 정렬)을 추가해야 하므로 시간 복잡도가 O(n log n)로 증가합니다.

해시 테이블을 사용하는 경우:

중복 확인 시 평균적으로 O(n)의 시간 복잡도를 가지지만, 해시 테이블 구축과 메모리 할당이 추가적으로 필요합니다(O(n)의 공간 복잡도).

실행 효율

정렬된 배열에서의 중복 제거는 데이터가 이미 정렬되어 있다는 전제하에 가장 효율적인 접근 방식입니다.

적용 사례: 대규모 데이터 처리, 메모리 사용이 제한된 시스템.

결론

제안된 알고리즘은 정렬된 배열에서 중복 제거를 수행하는 가장 단순하고 효과적인 방법 중 하나로, 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 최적의 성능을 제공합니다.

입력과 출력 예제

제안된 중복 제거 알고리즘의 동작을 입력과 출력 예제를 통해 확인합니다.

예제 1: 기본 사례

입력 배열: {1, 1, 2, 3, 3, 4, 4, 5}

알고리즘 수행 중:
readIndex = 1: 1 == 1 (중복, 저장하지 않음).
readIndex = 2: 2 != 1 (고유값, 저장).
readIndex = 3: 3 != 2 (고유값, 저장).
readIndex = 4: 3 == 3 (중복, 저장하지 않음).
readIndex = 5: 4 != 3 (고유값, 저장).
readIndex = 6: 4 == 4 (중복, 저장하지 않음).
readIndex = 7: 5 != 4 (고유값, 저장).
출력 배열: {1, 2, 3, 4, 5}
출력 크기: 5

예제 2: 중복 없는 배열

입력 배열: {1, 2, 3, 4, 5}

알고리즘 수행 중: 모든 요소가 고유하므로 변경 없이 유지.
출력 배열: {1, 2, 3, 4, 5}
출력 크기: 5

예제 3: 모든 요소가 중복된 배열

입력 배열: {7, 7, 7, 7, 7}

알고리즘 수행 중: 첫 번째 요소만 유지하고 나머지는 중복으로 제거.
출력 배열: {7}
출력 크기: 1

예제 4: 빈 배열

입력 배열: {}

알고리즘 수행 중: 입력이 비어 있으므로 출력도 빈 배열.
출력 배열: {}
출력 크기: 0

예제 실행 결과 요약

입력 배열	출력 배열	출력 크기
`{1, 1, 2, 3, 3, 4, 4, 5}`	`{1, 2, 3, 4, 5}`	`5`
`{1, 2, 3, 4, 5}`	`{1, 2, 3, 4, 5}`	`5`
`{7, 7, 7, 7, 7}`	`{7}`	`1`
`{}`	`{}`	`0`

이와 같은 입력과 출력을 통해, 제안된 알고리즘이 다양한 시나리오에서 정확히 동작함을 확인할 수 있습니다.

실전 응용 사례

정렬된 배열을 활용한 중복 제거는 다양한 분야에서 효율적인 데이터 처리 방식으로 사용됩니다. 여기 몇 가지 주요 사례를 소개합니다.

1. 데이터 정리 및 전처리

중복 제거는 데이터 분석이나 머신러닝에서 필수적인 전처리 단계입니다.

예시: 대규모 고객 데이터베이스에서 중복된 이메일 주소를 제거하여 고유한 사용자 목록을 생성.
장점: 데이터의 정확성을 높이고, 분석 및 학습 모델의 효율성을 개선.

2. 검색 엔진 최적화

검색 엔진은 동일하거나 유사한 데이터를 반복적으로 처리하지 않도록 중복 제거를 수행합니다.

예시: 정렬된 웹 페이지 목록에서 중복된 URL 제거.
장점: 처리 속도 향상 및 불필요한 자원 낭비 방지.

3. 로그 파일 관리

시스템 로그나 애플리케이션 로그에서 중복된 항목을 제거하여 로그 크기를 줄이고 분석을 용이하게 만듭니다.

예시: 서버 로그 파일에서 같은 시간대에 발생한 반복적인 에러 메시지 제거.
장점: 로그 파일 크기 감소와 가독성 향상.

4. 중복 거래 탐지

금융 시스템에서 동일한 거래가 여러 번 발생하는 것을 방지하기 위해 중복 제거를 사용합니다.

예시: 정렬된 거래 기록에서 중복된 거래 ID 제거.
장점: 데이터 무결성을 보장하고, 오류를 줄임.

5. 파일 관리 시스템

중복된 파일이나 데이터 항목을 제거해 저장 공간을 절약하고 관리 효율성을 높입니다.

예시: 클라우드 저장소에서 정렬된 파일 이름 목록에서 중복 파일 제거.
장점: 저장 공간 최적화와 불필요한 데이터 관리 감소.

6. 데이터베이스 최적화

데이터베이스에서 중복된 레코드를 제거하여 효율성을 극대화합니다.

예시: SQL 쿼리 결과로 반환된 정렬된 레코드에서 중복 제거.
장점: 쿼리 성능 향상 및 데이터 정합성 유지.

결론

정렬된 배열을 활용한 중복 제거는 데이터 전처리, 로그 관리, 파일 시스템 등 다양한 분야에서 중요한 역할을 합니다. 간단하면서도 효율적인 이 알고리즘은 실제 프로젝트에서도 폭넓게 사용되며, 정확성과 성능을 보장합니다.

요약

정렬된 배열을 활용한 중복 제거는 간단하면서도 효율적인 알고리즘으로, 시간 복잡도 O(n), 공간 복잡도 O(1)의 성능을 제공합니다. 본 기사에서는 중복 제거의 원리, 알고리즘 설계, C언어 구현, 시간 복잡도 분석, 입력/출력 예제, 그리고 실전 응용 사례를 다루었습니다. 이 방법은 데이터 전처리, 로그 관리, 데이터베이스 최적화 등 다양한 분야에서 활용 가능하며, 효율적인 데이터 처리를 위한 중요한 기법입니다.