원

https://www.acmicpc.net/problem/20501 20501번: Facebook 예제에서, 1, 2번 사용자, 1, 3번 사용자, 2, 3번 사용자, 2, 4번 사용자는 서로 친구이다. 이 때, 2번 사용자, 4번 사용자와 동시에 친구인 사용자는 없다. 1번 사용자, 3번 사용자와 동시에 친구인 www.acmicpc.net 문제 "마, 내가 누군지 아나? 저커버그가 내 후임이다." 준원이는 저커버그와 함께 페이스북을 만들던 리즈시절을 회상하곤 한다... 저커버그가 페이스북을 다 만들기 직전, 바로 그 순간 저커버그에게 급똥이 찾아왔다. 그는 마지막 남은 기능 하나를 준원이에게 맡겼고, 그 기능이 바로 '함께 아는 친구' 기능이었다. 페이스북의 사용자는 총 N명이고, 각 사용자는 1번에서..

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

소수 구하기 알고리즘으로 유명한 에라토스테네스의 체는 굉장히 빠르게 동작한다. 그렇기 떄문에 수행 범위를 늘릴 때 부담이 되는 것은 수행 시간이 아닌 메모리이다. 체를 구현할 때는 범위 내의 각 정수가 지워졌는지 여부를 저장해야하는데, 이 부분을 원래는 불린 값 배열을 이용해 표현하는 것이 대부분이다. 32비트 정수가 표현할 수 있는 범위 내의 모든 수에 대해 체를 수행한다고 가정하면 불린 값 배열을 사용하기 위해 4기가바이트의 메모리가 필요하다. 짝수를 제외해 2기가바이트로 줄일 수도 있지만, 여전히 적지 않은 메모리 양이다. 이 때 비트마스크를 사용하면 메모리 사용량을 8분의 1로 다시 줄일 수 있다. MAX_N개의 원소를 갖는 불린 값 배열을 다음과 같은 배열로 대체한다. unsigned char ..