BFS로 어떤 정수의 0과 1로만 이루어진 배수 찾기

4994번: 배수 찾기 정수 N이 주어질때, N의 배수 중에 0과 1로만 이루어진 배수 M을 찾는다 1보다 큰 M의 길이는 100이 넘지 않아야하고 가능한 경우가 여러가지 있으면 아무거나 찾는다 ---------------------------------------------------------------------------------------------------------------------------------------- 100000000000000000000000000000000 해서 0인거 하나씩 1로 바꿔보고 11000000000000000000000, 101000000000000000000.... 근데 하나만 바꾸는게 아니라 문제는 2개 이상 바꿔야할수도 있잖아 11100000000..

  • format_list_bulleted DFS BFS 정복기
  • · 2025. 1. 28.
  • textsms

나머지 연산과 비둘기집 원리

1323번: 숫자 연결하기 어떤 수 n,k가 주어질때, n을 여러번 붙여써서 k로 나누어지는 경우가 있는지 알고 싶다 예를 들어 10은 1번 쓰면 10 2번 쓰면 1010 3번 쓰면 101010 이때, 최소로 붙여써서 k로 나누어 떨어지게 하고 싶을때 최솟값을 구한다면? ------------------------------------------------------------------------------------------------------------------------------------------------------ n을 여러번 붙여쓴다는 것은 예를 들어 10을 여러번 붙여쓴다면 1번 쓰는 경우 10, 2번 쓰는 경우 1010인데 1010 = 1000 + 10 = 10*10^2 + 1..

  • format_list_bulleted 비둘기집 원리
  • · 2025. 1. 19.
  • textsms

2^30으로 나눈 나머지로 2^5으로 나눈 나머지를 구할 수 있을까

8672번: Drabina (acmicpc.net) 사다리의 맨 끝단 s까지 올라가는데 한걸음 혹은 두걸음씩 올라갈 수 있다 이 때 끝까지 올라가는 방법의 수를 2p로 나눈 나머지를 구해야한다. 이것만 보면 매우 쉬운 문제다 dp[i] = i번째까지 올라가는 방법의 수하면 가능한 경우는 한걸음 혹은 두걸음이므로... dp[i] += dp[i-1]dp[i] += dp[i-2] 인 전형적인 문제 dp = [0]*(s+1)dp[0] = 1mod = 2**pfor i in range(1,s+1): for j in range(1,3): if i >= j: dp[i] += (dp[i-j]) dp[i] %= mod  문제는 최대 ..

  • format_list_bulleted 정수론
  • · 2024. 8. 10.
  • textsms

이진수의 마지막 n개의 비트가 모두 켜져있는지 확인하는 방법

SW Expert Academy SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com  정수 m의 마지막 n개의 비트가 모두 1인지 확인하는 문제 m이 108이고 테스트 케이스는 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   다른..

  • format_list_bulleted 비트마스킹
  • · 2024. 5. 3.
  • textsms
다항식의 곱셈과 나눗셈 기본 컴퓨터 구현 방법 배우기

다항식의 곱셈과 나눗셈 기본 컴퓨터 구현 방법 배우기

1. 다항식의 곱셈 두 다항식의 곱셈은 구현하는 방법이 많이 있지만... 당장은 어려우니 일단 O(k2)으로 naive하게 구현 해보자. 다항식은 각 항의 계수를 배열에 저장하면 되는데 f(x)=2x2+x+1이라고 한다면, a = [1,1,2]로 저장하면 된다. 곱셈하고자 하는 다항식이 g(x)=x+5라고 한다면 b = [5,1]이고 두 다항식의 곱셈은 f(x)g(x)=2x3+11x2+6x+5로 [5,6,11,2]가 나와야한다. f(x)가 len(a)-1차수 다항식이고 g(x)가 len(b)-1차수 다항식이면, f(x)g(x)는 len(a)+len(b)-2차수 다항식이다. 위에서 len(a) = 3, len(b) = 2이고 각각 2차 1..

  • format_list_bulleted 대수학
  • · 2023. 8. 26.
  • textsms
최대공약수 파헤치기1 - N*M 최대공약수 테이블이 만들어내는 아름다운 패턴

최대공약수 파헤치기1 - N*M 최대공약수 테이블이 만들어내는 아름다운 패턴

1. 문제 14860번: GCD 곱 (acmicpc.net) 14860번: GCD 곱 N과 M 이 주어졌을 때, GCD(1, 1) × GCD(1, 2) × ... × GCD(1, M) × GCD(2, 1) × GCD(2, 2) × ... × GCD(2, M) × ... × GCD(N, 1) × GCD(N, 2) × ... × GCD(N, M)을 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 N*M 테이블에서 최대공약수를 구해본다. 예를 들어 N = 10, M = 10이라고 한다면.. 1은 곱해봤자 의미없으니까 2부터 테이블에 몇개나 나타나는지 한번 찾아보면 5*5 = 25개 있다는 것을 알 수 있는데 이는 행과 열에서 2의 배수가 몇개나 있는지를 세면 된다는 것을 볼 수 있다. 길..

  • format_list_bulleted 정수론
  • · 2023. 6. 20.
  • textsms