비트연산 - 코딩테스트 시간단축을 위한 마법

비트연산 코딩테스트에 적용하기

 

 코딩테스트에서 코드 실행시간을 최소화하고 정확하고 효율적인 코드를 작성하는 것은 매우 중요합니다. 비트연산은 코드를 간결하게 만들고 실행 속도를 크게 향상시킬 수 있는 강력한 도구로 사용할 수 있습니다. 이번 포스팅에서는 비트연산을 코딩테스트에 적용하는 방법에 대해 구체적인 예제 코드와 함께 알아보겠습니다. 

---

 

0. 비트연산 기본 개념

비트 연산에 대한 기본적인 개념은 아래 포스팅에 자세히 작성했습니다. 먼저 보고 오시길 추천드립니다.

2024.12.22 - [C 언어] - C언어 비트연산 완벽 정리 - 장점, 원리, 사용 예시, 예제코드

C언어 비트연산 완벽 정리 - 장점, 원리, 사용 예시, 예제코드

 

 

 

1. 왜 비트연산을 코딩테스트에서 사용해야 할까?

1. 연산 속도가 빠릅니다.

 비트연산은 CPU가 가장 기본적으로 수행할 수 있는 연산 중 하나입니다. 다른 연산 (덧셈, 곱셈 등)과 비교해도 속도가 월등히 빠릅니다. 코딩테스트에서는 대규모 입력 데이터와 빠른 실행이 요구되므로 비트연산을 사용하면 유리합니다.

2. 코드가 간결해집니다.

비트연산은 논리적인 문제를 한 줄로 해결할 수 있어 코드의 가독성을 높이고, 작성 시간을 단축합니다. 이는 코딩테스트와 같이 시간 압박이 있는 상황에서 매우 큰 장점입니다.

3. 효율적인 메모리 사용

비트를 직접 조작하면 메모리 공간을 절약할 수 있습니다. 이는 수많은 데이터를 처리해야 하는 문제에서 효과적입니다.

---

 

반응형

2. 코딩테스트에서 유용한 비트연산 예제

특히 자주 사용되는 예시들은 형광팬으로 칠해놨습니다!!

1. 짝수/홀수 판별

비트 AND 연산을 사용하면 숫자가 짝수인지 홀수인지 간단히 확인할 수 있습니다.

#include <stdio.h>

int main() {
    int number = 7;

    if (number & 1) {
        printf("홀수입니다.\n");
    } else {
        printf("짝수입니다.\n");
    }

    return 0;
}

 

설명:

• 숫자와 1의 비트 AND 연산을 수행하면 마지막 비트만 확인합니다.
• 마지막 비트가 1이면 홀수, 0이면 짝수입니다.
• 시간 복잡도는 O(1)입니다.

---

 

2. 집합 문제 해결 (비트마스크 활용)

집합 관련 문제를 해결할 때 비트마스크를 사용하면 효율적입니다. 예를 들어, 특정 원소가 집합에 포함되어 있는지 확인하거나 추가/제거하는 연산을 수행할 수 있습니다.

#include <stdio.h>

int main() {
    int set = 0; // 빈 집합

    // 원소 추가 (3번째 원소 추가)
    set |= (1 << 3);

    // 원소 확인 (3번째 원소 존재 여부)
    if (set & (1 << 3)) {
        printf("3번째 원소가 있습니다.\n");
    }

    // 원소 제거 (3번째 원소 제거)
    set &= ~(1 << 3);

    return 0;
}

 

설명:

• 1 << n은 n번째 비트를 1로 설정합니다.
• OR 연산(|)으로 원소를 추가하고, AND NOT 연산(& ~)으로 원소를 제거합니다.
• n번째 비트가 1이라면 n번째 원소가 존재한다고 판단합니다. 

---

 

3. 두 수의 XOR을 이용한 중복 제거

배열에서 한 번만 등장하는 숫자를 찾는 문제를 해결할 때 XOR 연산을 활용할 수 있습니다.

#include <stdio.h>

int findUnique(int arr[], int size) {
    int result = 0;

    for (int i = 0; i < size; i++) {
        result ^= arr[i];
    }

    return result;
}

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

    printf("한 번만 등장하는 숫자: %d\n", findUnique(arr, size));

    return 0;
}

 

설명:

• XOR 연산은 같은 숫자를 XOR하면 0이 됩니다.
• 모든 숫자를 XOR하면 중복된 숫자는 사라지고, 한 번만 등장하는 숫자만 남습니다.
• 시간 복잡도는 O(n)입니다.

실제 성능 개선 예시:

• 예를 들어, 배열 크기가 1,000,000인 경우 단순히 두 중첩 루프를 사용하면 O(n^2)의 시간이 소요될 수 있지만, XOR 연산을 활용하면 O(n)으로 해결 가능합니다. 실행 시간은 대략 2초에서 0.1초로 단축됩니다.

---

 

4. 비트 시프트를 이용한 빠른 곱셈 및 나눗셈

곱셈과 나눗셈 대신 비트 시프트를 사용하면 계산 속도를 개선할 수 있습니다.

#include <stdio.h>

int main() {
    int a = 4;

    // 곱셈
    int mul = a << 2; // a * 2^2 = 16

    // 나눗셈
    int div = a >> 1; // a / 2 = 2

    printf("곱셈 결과: %d\n", mul);
    printf("나눗셈 결과: %d\n", div);

    return 0;
}

 

설명:

• 왼쪽 시프트(<<)는 2의 거듭제곱 곱셈과 같습니다.
• 오른쪽 시프트(>>)는 2의 거듭제곱 나눗셈과 같습니다.

실제 성능 개선 예시:

• 일반적인 곱셈 연산보다 시프트 연산은 20% 이상 빠르게 실행됩니다. 예를 들어, 10억 개의 숫자를 곱셈해야 하는 경우 기존 방식으로는 3초가 소요되던 작업이 비트 시프트로는 2.4초로 단축될 수 있습니다.

---

 

5. 코딩테스트에서 언제 비트연산을 적용해야할까?

1. 문제에서 집합이나 논리적 조작을 요구할 때 비트마스크를 고려하세요.
2. 짝수/홀수 판별, 특정 비트 확인 등의 간단한 연산은 비트연산으로 대체하세요.
3. XOR 연산을 사용해 중복 문제를 해결하거나 두 숫자의 차이를 구하세요.
4. 시프트 연산을 통해 곱셈/나눗셈의 효율성을 높이세요.

---

 

C언어의 비트연산은 단순한 연산에서 복잡한 문제 해결까지 다양한 활용이 가능합니다. 특히 코딩테스트에서는 실행 시간 단축과 코드 간소화라는 두 마리 토끼를 잡을 수 있는 강력한 도구입니다.