Algorithm, 비트연산자, 쉬프트 연산자, 카카오-후보키
비트 연산자
- 정수형 기본형 데이터 타입의 각 비트를 개별적으로 조작
- 양쪽 피연산자의 대응되는 각 비트별로 부울 연산을 한다
비트 연산자 종류 및 예제
- & : AND, 양쪽 모두 1일때만 1
- ex) 4&5 -> 4 (4=100, 5=101)
-
| __ |
__ : OR, 양쪽 모두 0일 때만 0 |
- ^ : XOR, 양쪽 비트가 서로 다를때1, 같으면 0
- ~ : NOT, 모든 비트값을 반대로 만든다.
-ex) ~5 -> -6 (101 -> 11111111111111111111111111111010)
쉬프트 연산자
- 자바의 기본정수 타입은 반드시 부호(sign)가 있는 정수 값을 가짐
- 부호는 제일 왼쪽 한 비트에 표시, 이 비트를 MSB(Most Significant Bit: 최상위 비트) 양수:0, 음수:1
- 비트 단위 연산 수행, 기본 정수 타입인 byte, short, char, int, long에만 사용 할 수 있다.
쉬프트 연산자 종류
- « : 왼편의 피연산자 비트 값을 오른편에 지정한 수만큼 왼쪽으로 이동, 오른쪽 남는 비트는 0으로 채운다
- » : 왼편의 피연산자 비트 값을 오른편에 지정한 수만큼 오른쪽으로 이동, 비어있는 왼쪽 비트는 부호와 같은 값으로 채운다.
- »> : unsigned 우측 쉬프트 연산자는 왼편의 남는 비트를 부호와는 무관하게 0으로 채운다.
후보키
package org.programmers;
import java.util.ArrayList;
import java.util.HashSet;
public class kakao_42890 {
public static int solution(String[][] relation) {
ArrayList<Integer> candidateKey = new ArrayList<>();
int rowLen = relation.length;
int colLen = relation[0].length;
for (int set = 1; set < (1 << colLen); set++) {
// 최소성 검사
if (!isMinimal(set, candidateKey))
continue;
// 유일성 검사
if (isUnique(set, rowLen, colLen, candidateKey, relation)) {
System.out.println(Integer.toBinaryString(set));
candidateKey.add(set);
}
}
return candidateKey.size();
}
private static boolean isUnique(int set, int rowLen, int colLen, ArrayList<Integer> candidateKey,
String[][] relation) {
HashSet<String> map = new HashSet<>();
for (int row = 0; row < rowLen; ++row) {
String dataByKeySet = "";
// 한 row당 해당 컬럼의 값을 뽑아 dataByKeySet을 만들어준다.
// ex. set=6 이면 0110, 이므로 th값이 1, 2일때 가능하므로,
// relation[0][1]=ryan, relation[0][2]=music ==> dataByKeySet=ryanmusic이 될수있다.
for(int th=0; th<colLen; ++th) {
System.out.println("set="+set + " th="+th+ " set & (1<<th)="+ (set & (1<<th)));
if((set & (1<<th)) != 0) {
System.out.println("relation["+row+"]["+th+"]="+ relation[row][th]);
dataByKeySet += relation[row][th];
}
}
System.out.println("dataByKeySet="+dataByKeySet);
// 모든 경우가 독립적인지 확인한다.
if(map.contains(dataByKeySet)) return false;
else map.add(dataByKeySet);
}
return true;
}
private static boolean isMinimal(int set, ArrayList<Integer> candidateKey) {
// 이미 후보키로 선정된 조합이 들어있는 경우에 속성이 추가되면
// 그 속성을 없앴을때 유일성을 만족하므로, 최소성을 만족하지 않는다.
// 따라서 , 이미 후보키로 선정된 조합에 set이 포함되면 안된다!!
for (int key : candidateKey) {
if ((key & set) == key)
return false;
}
return true;
}
}
집합-boj
import java.util.Scanner;
public class test11723 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
int bitSet = 0;
StringBuilder answer = new StringBuilder();
for (int i=0; i<t; i++) {
String command = scanner.next();
if ("add".equals(command)) {
int n = scanner.nextInt();
bitSet = bitSet | (1 << n);
} else if ("remove".equals(command)) {
int n = scanner.nextInt();
bitSet = bitSet & ~(1 << n);
} else if ("check".equals(command)) {
int n = scanner.nextInt();
int result = (bitSet & (1 << n));
if (result > 0 ) {
answer.append("1\n");
System.out.println(1);
} else if (result == 0) {
answer.append("0\n");
System.out.println(0);
}
} else if ("toggle".equals(command)) {
int n = scanner.nextInt();
bitSet = bitSet ^ (1<<n);
} else if ("all".equals(command)) {
bitSet = (1 << 21) - 1;
bitSet = bitSet & ~(1);
} else if ("empty".equals(command)) {
bitSet = 0;
}
}
System.out.println(answer);
}
}
참고
