구간 내 가장 큰 해밍거리를 가지는 두 정수를 구하는 방법

33692번: 해밍 거리 두 정수 a,b의 해밍거리는 a,b를 각각 이진수로 나타내서, 동일한 위치의 비트를 비교하여 서로 다른 비트의 수를 말한다. 예를 들어 9 = 1001 12 = 1100이므로, 2번째 비트와 4번째 비트가 서로 달라 9,12의 해밍거리는 2이다. 두 정수 A,B가 주어질때 A이상 B이하에서 해밍거리가 가장 큰 두 정수 a,b를 아무거나 구한다. -------------------------------------------------------------------------------------------------------------------------------------------------------- A,B를 각각 이진수로 나타내고 이진수의 길이가 서로 다르다면, 앞..

  • format_list_bulleted 애드 혹 알고리즘
  • · 2025. 4. 8.
  • textsms

두 팀중 적어도 한 팀이 소수만큼 점수를 얻을 확률

1344번: 축구  90분간 이루어지는 축구 경기를 5분 간격으로 나눈다. 처음 간격은 처음 5분, 두번째 간격은 그 다음 5분... 각 간격에서 A,B팀이 각각 득점할 확률이 주어진다 각 간격에서 A,B팀은 각각 많아야 한골씩 득점할 수 있다 경기가 끝났을 때 적어도 한 팀이 소수로 득점할 확률은? ------------------------------------------------------------------------------------------------------------------------------------ 5분씩 간격이 나눠지고 전체 경기 시간은 90분이므로 총 18간격씩 이루어진다 각 간격에서 두 팀은 독립적으로 최대 1골씩 넣을 수 있다 dp[i][a][b] = i번째 간..

  • format_list_bulleted 다이나믹 프로그래밍
  • · 2025. 3. 2.
  • textsms

배열의 모든 수의 관계가 약수 배수 관계가 되도록 만드는 다이나믹 프로그래밍

19576번: 약수 주어진 배열의 어떤 수를 양의 정수로 바꿔서 임의의 두 수 x,y를 골랐을 때 x가 y로 나누어 떨어지거나, y가 x로 나누어 떨어지도록 만들고 싶다. 이때 양의 정수로 바꾸는 행위를 최소로 하고자 할 때 최소 몇번 바꿔야하는가? --------------------------------------------------------------------------------------------------------------------------------------------------------------- 어떤 수로 바꾸는가?에 대한 문제는 되지 않는다  1은 모든 수의 약수이기 때문에 그냥 1로 바꾸면 되기 때문이다. 그렇다면 몇번 바꿔야하는지는 어떻게 알아내는가? 주어진 배열..

  • format_list_bulleted 다이나믹 프로그래밍
  • · 2025. 2. 24.
  • textsms

정수의 임의의 거듭제곱들의 합을 바라보는 놀라운 방법

15319번: 동혁이의 생일선물 정수 x의 거듭제곱 x0,x1,x2,...에 대하여 이들의 모든 부분집합 A1, A2, ...을 생각하자 각 부분집합의 원소들의 합을 M1, M2,...라고 할 때 이들을 오름차순으로 정렬하면 수열 a1, a2,...를 얻는다 이때 k번째 원소 ak에 대하여 n개의 x,k가 주어질때 각각 구한 모든 ak의 합을 10^9 + 7로 나눈 나머지를 구한다 --------------------------------------------------------------------------------------------------------------------------------------------------------------- 2,3,4,....

  • format_list_bulleted 정수론
  • · 2025. 2. 11.
  • textsms

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