1부터 n까지의 최소공배수를 빠르게 구하는 방법

1. 문제 11690번: LCM(1, 2, ..., n) (acmicpc.net) 11690번: LCM(1, 2, ..., n) 첫째 줄에 1보다 크거나 같고, n보다 작거나 같은 모든 자연수의 최소공배수를 출력한다. 정답이 매우 커질 수 있기 때문에, 232로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 두 수 a,b의 최소공배수를 어떻게 구하는지 생각해본다면.. a랑 b를 소인수분해하고... 각각 소인수분해에서.. 소인수의 지수가 큰것끼리 곱하면 그것이 a,b의 최소공배수이다. 예를 들어 18과 24의 최소공배수를 구한다면.. $$18 = 2 * 3^{2}$$ $$24 = 2^{3} * 3$$ 여기서 소인수는 2와 3만 나타나는데.. 각각에서 지수가 큰 경우는 $2^{3}$이랑 $..

• format_list_bulleted 정수론
• · 2023. 5. 4.
• textsms

비트마스크를 이용한 에라토스테네스의 체 배우기

1. 에라토스테네스의 체 기본형태 n이하의 소수를 구하는 알고리즘 n+1개의 1을 가지는 리스트로 초기화하고, 2부터 n의 제곱근까지 순회하여 해당 수의 배수를 모두 지우고 나면 소수만 남는다는 알고리즘이다 n = int(input()) result = [1]*(n+1) for i in range(2,int((n+1)**(1/2))+1): if result[i] == 1: for j in range(i*i,n+1,i): result[j] = 0 prime_list = [i for i in range(2,n+1) if result[i] == 1] 여기서 j의 시작 지점을 i+i로 하는 경우가 많은데, i*i로 해도 된다. 왜냐하면, i+i는 결국 가장 먼저 2의 배수에서 지워지기 때문이다. 2. 에라토스테..

• format_list_bulleted 비트마스킹
• · 2023. 5. 4.
• textsms

정수 n을 2의 거듭제곱으로 나눈 나머지를 효율적으로 구하는 방법

나머지를 구할때 %로 구하면 되는데.. 효율적으로 구한다는게 도대체 무슨말인가? %연산은 계산 비용이 높아서 비효율적으로 알려져있다. n = 98 print(n % 2) #0 print(n % 4) #2 print(n % 8) #2 print(n % 16) #2 print(n % 32) #2 계산비용을 줄이고 싶다면 % 연산자를 사용하지 않고 나머지를 구해야한다. 예를 들어 4로 나눈 나머지를 어떻게 구할 수 있을까? 컴퓨터는 모든 수를 2진수로 인식하기 때문에.. 가장 쉬운 접근은 정수 n을 2진수로 나타내보는 것이다. 위 그림을 보면 어떤 수를 4로 나눈 나머지는 0,1,2,3중 하나인데... n을 2진수로 나타냈을때 4로 나눈 나머지는... n의 2진수 표현에서 오른쪽 끝의 2비트만 가져오는 것임을..

• format_list_bulleted 비트마스킹
• · 2023. 5. 3.
• textsms

비트마스킹 연습하기1(백준 25166,12833)

1. 문제 25166번: 배고픈 아리의 샌드위치 구매하기 (acmicpc.net) 25166번: 배고픈 아리의 샌드위치 구매하기 "두리"라는 나라가 있다. 이 나라에서 사용되는 동전은 1원, 2원, 4원, 8원, 16원, 32원, 64원, 128원, 256원, 512원짜리 이렇게 총 10가지이다. 이 나라의 국민인 아리는 10가지의 동전을 각각 1개씩 총 10 www.acmicpc.net 1,2,4,8,16,32,64,128,256,512원짜리 동전만 사용가능할때, 이들을 하나씩 가지고 있는데, 친구에게 돈을 빌려서라도 샌드위치 가격만큼 내줄 수 있는지 아닌지 알아보는 문제 2. 풀이 브론즈1인데.. 어렵다.. 비트마스킹 이론 공부 했는데 뭔가 응용하기가 어렵다고 해야하나..? 연습좀 많이 해봐야겠지 이..

• format_list_bulleted 비트마스킹
• · 2022. 10. 30.
• textsms

비트마스킹을 위한 비트연산 필수이론 가볍게 정리

1. 비트(bit) 정보를 구분하는 최소 단위로 이진 숫자(binary)를 뜻한다 0,1의 값을 가지며 True/False나 on/off같은 2가지 상태를 나타낼 수 있다 10진수를 2진수로 바꾸면 해당 10진수에 대응하는 하나의 비트열을 얻는다 2. 비트연산 - 비트연산은 비트열의 같은 위치끼리만 연산함 2-1) &(and) 비트 단위로 and연산을 수행 비트가 둘다 1이면 1이고, 하나라도 0이면 0인 연산 & 연산은 위 표에서 특징을 자세히 살펴보면.. 1) 0과 and연산은 무조건 결과가 0이다 0&0 = 0 0&1 = 0 2) 1과 and연산은 나머지 비트를 그대로 가져온다 1&1 = 1 1&0 = 0 2가지 성질을 잘 이용하면.. 3) 어떤 비트열에서, 특정 부분을 0으로 만들고 싶다면.. 나..

• format_list_bulleted 비트마스킹
• · 2022. 10. 23.
• textsms