Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- 개발자 면접
- 가장긴증가하는 부분수열
- 카카오 인턴
- 백준11053
- 카카오 서류전형
- 2228
- 백준12015
- 여름인턴십
- 파이썬
- LIS
- 구간나누기
- 1670
- 최장증가수열
- 알고리즘
- LIS 알고리즘
- Python
- 2482
- 정상회담2
- 2629
- 백준12738
- 기술면접
- 카카오 인턴십
- 인턴십 면접
- DP
- 카카오
- 단어수학
- 백준
- 카카오 면접
- Longest Increasing Subsequence
- 카카오 자기소개서
Archives
- Today
- Total
프로그래밍에 대한 고찰 및 생각
[알고리즘][9][백준_11723][C언어] - 집합 본문
문제이해
이 문제는 집합에서의 기본적인연산 ( 원소의 추가, 삭제, 확인, 반전, 전체 변경, 전체 삭제 등) 을 수행하는 알고리즘을 설계하는 문제이다.
다만 수행해야하는 연산의 수가 최대 3,000,000 이므로 배열연산보다는 비트마스크를 활용해서 문제를 해결해야할것이다.
알고리즘 설계
사실 비트마스크를 사용해본적이 있다면 쉽게 해결할수 있을것이다.
집합의 원소개수가 1부터 20까지 20개 이므로 한개의 int에서 20bit를 사용해서 n번째 원소가 채워져있으면
2^(n-1) 에 해당하는 부분을 1로 아니라면 0으로 채워서 현재 집합의 상태를 표현할수 있다.
#include <stdio.h>
#include <string.h>
int ss = 0;
int bit(char ar[], int k);
int main(){
int n,i,j;
char arr[10] = {};
char ar[10];
int tmp;
int check = 1;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%s",&arr);
scanf("%d",&tmp);
bit(arr,tmp);
}
}
int bit(char ar[], int k){
if(!strcmp(ar,"add")){
if((ss & (1<<k)) == 0){
ss = ss + (1<<k);
}
}
else if(!strcmp(ar,"remove")){
if((ss & (1<<k)) > 0){
ss = ss - (1<<k);
}
}
else if(!strcmp(ar,"check")){
if((ss & (1<<k)) > 0){
printf("1\n");
}
else{
printf("0\n");
}
}
else if(!strcmp(ar,"toggle")){
if((ss & (1<<k)) == 0){
ss = ss + (1<<k);
}
else{
ss = ss - (1<<k);
}
}
else if(!strcmp(ar,"all")){
ss = (1<<21) - 1;
}
else{ // empty
ss = 0;
}
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[알고리즘][11][백준_1029][C언어] - 그림교환 (0) | 2020.03.04 |
---|---|
[알고리즘][10][백준_1126][C언어] - 같은 탑 (0) | 2020.02.29 |
[알고리즘][8][백준_2515][C언어] - 전시장 (0) | 2020.02.24 |
[알고리즘][7][백준_1648][Python3] - 격자판 채우기 (0) | 2020.02.06 |
[알고리즘][6][백준_1670][Python3] - 정상 회담 2 (0) | 2020.02.06 |