# bitset

bformat

이걸 처음에 역추적까지 해야 한다고 생각해서 메모리 초과를 좀 많이 받았었는데 문제 난이도가 루비 V인 시점에서 눈치챘어야 했다;; 문자 $X$가 정확히 하나씩 존재한다는 걸 생각하면 문자열 $A$, $B$ 모두 $X$가 위치하는 부분에서 끊어서 나눌 수 있다. $LCS(A, B)$ = $LCS(A1, B1)+LCS(A2, B2)$로 생각할 수 있기 때문에 Bitset LCS를 두 번 구해주면 된다. $Y$에 대해서는 문자열 입력받을 때 문자 $Y$를 전부 제거해주는 전처리를 수행하면 된다. $N$ 길이의 $LCS$가 존재한다는 것은 $1$~$N$ 사이의 모든 길이 $LCS$가 존재한다는 뜻이므로 소수를 구하는 건 나이브하게 해도 된다. >코드

kimyj1234

[백준 20501] 문제 조건 "마, 내가 누군지 아나? 저커버그가 내 후임이다." 준원이는 저커버그와 함께 페이스북을 만들던 리즈시절을 회상하곤 한다... 저커버그가 페이스북을 다 만들기 직전, 바로 그 순간 저커버그에게 급똥이 찾아왔다. 그는 마지막 남은 기능 하나를 준원이에게 맡겼고, 그 기능이 바로 '함께 아는 친구' 기능이었다. 페이스북의 사용자는 총 N명이고, 각 사용자는 1번에서 N번까지로 번호 붙어 있었다. 준원이는, 사용자의 친구관계에 대한 정보가 모두 주어졌을 때, **"a번 사용자, b번 사용자와 공통적으로 친구 관계인 사용자의 수" ** 를 묻는 Q개의 질문에 차례로 답해야 했다. 준원이는 천

longbright_choi

💡 문제 💬 입출력 예시 📌 풀이(소스코드) 📄 해설 문제의 이름, 문제의 설명대로 중복을 제거한 결과를 출력하는 문제 그러나 일반적인 방법을 수행하기에는 메모리가 굉장히 적은 반면에 수의 크기는 $2^{25}$ 까지이고, 입력의 개수가 1 이상 500만 이하로 굉장히 큰 범위를 가짐 HashSet 을 사용하면 시간초과가 발생함 비트 연산을 처리하기 위한 클래스인 BitSet 을 사용해야 시간초과가 나지 않고 정답을 얻을 수 있음 set 메소드를 사용

apolontes

✅ 문제 분석 첫 줄에 B1 B2 길이를 나타내는 정수 n과 수행할 작업 수 m이 한칸 띄어 입력된다. 다음 줄부터는 위 다섯가지 형태 중 하나로 입력 된다. set에서 1,2는 각각 B1, B2를 의미한다. index의 숫자는 BitSet안의 비트 인덱스를 의미한다. 이진연산 AND OR XOR는 첫번째 피연산자에 두번째 피연산자의 집합을 적용한다. 예를 들어 AND 2 1인 경우 B2에 B1과 B2의 합집합이 들어간다. M0 = AND 1(SET) 2(SET) B1 = B1 ∩ B2 = {0,0,0,0,0} ∩ {0,0,0,0,0} = {0,0,0,0,0} B1 ={0,0,0,0,0}, B2={0,0,0,0,0} 따라서 설정된 비트수가 각각 0이므로 0 0 이 출력됨

pss407

문제 문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 이상 500만 이하이다. 입력 첫째 줄에 A1, A2, ..., AN이 주어진다. 출력 B1, B2, ..., BN’을 출력한다. 예제 입력 1 예제 출력 1 예제 입력 2