본문 바로가기

비트마스크2

[알고리즘 이론] 8. 비트마스킹 비트 마스크 알고리즘이 아닌 하나의 기법이다. 정수를 이진수로 표현하고, 비트 연산으로 다양한 문제를 해결해나가는 방법이다. 예시 열쇠가 a, b, c, d, e, f로 6개가 있다고 가정하고, 가지고 있는 열쇠가 a, c, e 일 때 // 가지고 있는 열쇠를 1, 아닌 것을 0으로 표시한다. // -> 열쇠말고 다양한 곳에서 사용 가능하다. // 1 (true), 0 (false) 로도 가능 a b c d e f 1 0 1 0 1 0 비트 연산자 1. AND // & : 대응되는 비트가 모두 1이면 1을 반환한다. 00001111 & 00010101 = 00000101 2. OR // | : 대응되는 비트 중에서 하나라도 1이면 1을 반환한다. 00001111 | 00010101 = 00011111 3.. 2023. 5. 9.
[알고리즘 이론] 6. 완전탐색 완전탐색 모든 경우의 수를 시도하여 정답을 찾는 방법이다. 무식하게 푼다는 의미로 Brute Force 라고도 한다. 상대적으로 간단하지만 경우의 수가 많아지면 시간이 길어지는 단점이 있다. 1. 단순 Brute-Force 특별한 기법 없이 for문과 if문으로 모든 경우의 수를 체크하여 답을 구함 이 방법으로 풀 수 있는 문제는 많지 않음 2. 비트마스크 각 원소를 두 가지 상태로 분류할 수 있을 때 사용 모든 경우의 수에서 각각의 원소가 포함되거나 포함되지 않는 경우 포함되면 1, 포함되지 않으면 0으로 구분한다 -> 2진수 EX) 원소 n개인 집합의 부분집합 구하기 자세한 건 아래 게시글 https://hoozy.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC.. 2023. 5. 9.

티스토리툴바