SW Expert Academy SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 정수 m의 마지막 n개의 비트가 모두 1인지 확인하는 문제 m이 $10^{8}$이고 테스트 케이스는 10000개이고 제한시간 2초라 단순하게 확인하면 시간초과날 것 같다 가장 쉬운 방법은 0부터 n-1까지 순회해서 각 비트가 1인지 검사하는 것 (1 이다. T = int(input())for test_case in range(1, T + 1): n,m = map(int,input().split()) no = False for i in range(n): if (1 다른..
1. 문제 1311번: 할 일 정하기 1 (acmicpc.net) 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net N명의 사람이 있고, N개의 일이 있는데 각각의 일은 하는데 비용이 든다. 각 사람 1명당 1개의 일만 가능하고 각 일은 1명만이 맡을 수 있다. 이럴 때 최소비용은 얼마인가? 2. 풀이 이런 형태의 문제는 N명의 사람이 1,2,3,4,..,N의 순열대로 배정을 해본후, 각각의 경우에 대해 비용을 전부 조사해서 최솟값을 찾는 방식을 배웠다. 3명이면 (1,2,3), (1,3,2), ..
1. 모든 원소 쌍의 XOR 합 $A_{0}, A_{1}, ... , A_{n-1}$에 대하여 $\sum_{i=0}^{i=n-1} \sum_{j=i+1}^{j=n-1} A_{i} \oplus A_{j}$을 구하는 문제 단순하게 풀면 $O(N^{2})$이지만 조금 더 생각해본다면 $O(N)$에 가깝게 해결할 수 있다. 결국 구하고자 하는 값은 $V = A_{i} \oplus A_{j}$라고 할 때, 이 V들의 합이다. 그런데 V를 2진수로 나타낸다면.. $$V = a_{k}2^{k} + a_{k-1}2^{k-1} + ... + a_{1}*2 + a_{0}$$로 나타낼 수 있다. 여기서 $a_{i} = 0$이거나 $a_{i} = 1$이다. 만약 모든 $V = A_{i} \oplus A_{j}$에 대하여 최대..
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}$이랑 $..
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. 에라토스테..
나머지를 구할때 %로 구하면 되는데.. 효율적으로 구한다는게 도대체 무슨말인가? %연산은 계산 비용이 높아서 비효율적으로 알려져있다. 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비트만 가져오는 것임을..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
