[C] 백준 11723번 집합

 

안녕하세요 ♪(´▽｀)

오늘은 지난번에 풀었던 14889번 스타트와 링크 문제를 쉽게 풀기 위해,,

비트 마스크 문제를 풀어보았습니다.

.

백준 11723번

www.acmicpc.net/problem/11723

11723번: 집합

.

문제의 조건을 살펴보면 피연산자인 X의 범위는 1 ≤ X ≤ 20으로 작은 편이지만,

M의 범위가 3,000,000 이하로 아주 큰 편입니다.

따라서 시간제한을 넘기지 않는 것이 이 문제의 포인트가 될 것 같습니다.

.

저는 비트 마스크를 활용하여 이 문제를 풀었는데,

아직 비트 마스크에 대해서는 잘 몰라서 아래의 링크로 공부하였습니다.

비트를 켜고, 끄고, toggle 하는 것에 대해 자세히 설명되어 있으니 참고하세요 :-)

dojang.io/mod/page/view.php?id=184

C 언어 코딩 도장: 24.4 비트 연산자로 플래그 처리하기

.

11723번 문제를 비트 마스킹 문제로 바꿔보자면

집합 S를 20비트의 수라고 표현하고, x가 S에 추가된다면 x비트를 켜줍니다.

마찬가지로 x가 S에서 제거된다면 x비트를 꺼주도록 합니다.

예를 들어 add 7을 한다고 가정했을 때 7번째 비트를 1로 만든다고 생각하면 됩니다.

이를 바탕으로 add, remove, check, toggle, all, empty 연산을 아래의 그림과 같이 표현하였습니다.

.

연산자를 수식으로 표현

.

해당 수식들을 코드를 작성하면 아래와 같습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

int add(int flag, int x) {
	return flag |= 1<<x;
}
int remove(int flag, int x) {
	return flag &= ~(1 << x);
}
int check(int flag, int x) {
	return flag &= 1 << x;;
}
int toggle(int flag, int x) {
	return flag ^= 1 << x;;
}
int empty() {
	return 0;
}
int main() {
	int M;
	scanf("%d", &M);
	
	char op[7] = "";
	int operand;
	int flag = 0;
	for (int i = 0; i < M; i++) {
		scanf("%s %d", op, &operand);
		if (strcmp(op, "add") == 0) {
			flag = add(flag, operand);
		}
		else if (strcmp(op, "remove") == 0) {
			flag = remove(flag, operand);
		}
		else if (strcmp(op, "check") == 0) {
			if (check(flag, operand))
				printf("%d\n", 1);
			else
				printf("%d\n", 0);
		}
		else if (strcmp(op, "toggle") == 0) {
			flag = toggle(flag, operand);
		}
		else if (strcmp(op, "all") == 0) {
			for (int i = 1; i <= 20; i++)
				flag = add(flag, i);
		}
		else {
			flag = empty();
		}
	}

	return 0;
}

.

우선 연산을 한 줄씩 입력받고, 해당 연산자가 어떤 연산자인지를 알아낸 후 비트 마스킹을 하였습니다.

주어진 S 집합은 20 비트까지 존재하기 때문에 int 자료형을 사용하여 표현할 수 있었습니다.

(int 자료형 = 4바이트 = 32비트)

비트 마스킹 함수의 경우에는 위에서 언급한 수식을 활용하여 작성하였습니다.

여기서 조심해야 할 점은 저는 처음 문제를 풀 때 x번째 비트(2의 x승)를 표현하기 위해 pow 함수를 사용하였는데,

이렇게 문제를 풀면 시간 초과가 된다는 것입니다. pow 함수 생각보다 시간이 오래 걸리네요 ㅎ..

따라서 shift 연산자로 코드를 수정해주었습니다.

.

pow 함수와 shift 연산자의 속도 차이 계산

.

위의 사진을 보면 pow 함수가 얼마나 느린지 체감할 수 있습니다.

실행시간 측정 코드는 아래의 코드와 같이 작성하였습니다.

.

#include <stdio.h>
#include <time.h>
#include <math.h>

int main() {
	clock_t start_pow, end_pow;
	clock_t start_shift, end_shift;
	float time_pow, time_shift;

	printf("pow 함수 속도: ");
	start_pow = clock();
	for (int i=1; i<=3000000; i++)
		pow(2.0, i);
	end_pow = clock();
	time_pow = (float)(end_pow - start_pow) / CLOCKS_PER_SEC;
	printf("%f\n", time_pow);

	printf("shift 연산자 속도: ");
	start_shift = clock();
	for (int i=1; i<=3000000; i++)
		1 << i;
	end_shift = clock();
	time_shift = (float)(end_shift - start_shift) / CLOCKS_PER_SEC;
	printf("%f\n", time_shift);
	
	printf("속도 차이: 약 %.f배\n", time_pow/time_shift);
	return 0;
}

.

추가로 실수했던 부분은, 처음에 입력받는 연산자 (문자열) 배열의 크기를 6으로 잡았습니다.

이렇게 하니 컴파일 에러가 나더라구요!

연산자 중 길이가 가장 긴 것은 'toggle'로 총 6글자입니다.

문자열을 입력받게 되면 문자열 배열의 마지막에 \0(NULL) 문자열이 들어가기 때문에 7자리로 잡는 것이 맞습니다!

오랜만에 코딩을 하니깐 이런 것도 헷갈리네요 ㅠ_ㅠ.ㅎ

.

이번 문제는 비트 마스크의 기본 원리와 공식?만 알면 쉽게 해결할 수 있는 문제였습니다.

다음번에는 이 비트 마스킹을 활용하여 스타트와 링크 문제를 다시 풀어보겠습니다!