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

주사위를 던져서 얻은 눈의 수의 합이 n이상이 되기 위해 던져야 하는 횟수의 기댓값

13250번: 주사위 게임 1부터 6까지 6면 주사위를 1번 던져 나온 눈의 수만큼 사탕을 받는다고 하자. 사탕을 적어도 n개 이상 받기 위해 던져야하는 횟수의 기댓값은? n = 1이면 1번만 던져도 사탕을 1개 이상 받으므로 1번 -------------------------------------------------------------------------------------------------------------------------------------- 통계적?으로 접근할려고하면 굉장히 어렵다 확률변수 X를 먼저 정의하고 X = 사탕을 n개 이상 받기 위해 던져야하는 횟수 P(X = 1), P(X = 2), ...을 구한다음 xP(X = x)의 합을 구하면 될텐데 문제는 P(X = 1) ..

• format_list_bulleted 확률론 알고리즘
• · 2025. 1. 18.
• textsms

합과 bitwise or연산이 같게되는 조건

1322번: X와 K  x+y = x | y를 만족하는 k번째로 작은 자연수 y를 구하는 문제 합과 or 연산이 서로 같게되는 조건을 먼저 생각해본다 or연산은 두 bit가 1이면 1이고 두 bit가 0이면 0이고 두 bit가 1,0으로 서로 다르면 1인 연산 두 수를 합하는 것은 어떤 의미인지 생각해본다 x,y를 2진수로 바꿔서 예를 들어 5 = 101이고 12 = 1100인데 이진수끼리 서로 덧셈은 어떻게 하는가? $101 = 0 * 2^{3} + 1 * 2^{2} + 0 * 2^{1} + 1 * 2^{0}$ $1100 = 1*2^{3} + 1 * 2^{2} + 0 * 2^{1} + 0 * 2^{0}$ 우측에 2의 거듭제곱으로 바꾼 것끼리 더한다고 생각해보면,  $(0 + 1)*2^{3} + (1+1..

• format_list_bulleted 비트마스킹
• · 2025. 1. 9.
• textsms

재귀적으로 점화식 세우는 다이나믹 프로그래밍 연습1

6096번: Bulls and Cows 총 n마리의 암소와 황소를 한줄로 세울때, 두 마리의 황소 사이에 최소 k마리의 암소가 있도록 줄을 세운다고 할 때, 그러한 방법의 수를 5000011로 나눈 나머지를 구한다. 이때 각 소는 구분할 수 없어서 서로 다르게 세워진 경우만 다른 경우의 수로 센다 n  2마리 황소 사이에 k마리 암소 세우고.. 어떻게 순열 돌리고 흠... dp[i][j]를 i마리 소 세우는데 마지막에 황소가 오는 경우가 j = 0, 아닌 경우가 j = 1인데  마지막에 황소가 온다고 하더라도 그 전 정보를 알수가 없으니 이건 흠... --------------------------------------------------------------------------------------..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 11. 23.
• textsms

재배열 부등식(rearrangement inequality)을 이용한 내적의 최대 최소

1. 재배열 부등식(rearrangement inequality) 실수 $x_{1}  1,2,..,n의 임의의 순열$\sigma_{1}, \sigma_{2}, ... , \sigma_{n}$으로부터$$x_{1}y_{n} + x_{2}y_{n-1} + ... + x_{n}y_{1}   2. 증명$S1 = x_{1}y_{1} + x_{2}y_{2} + .... + x_{a}y_{a} + .... + x_{b}y_{b} + ... + x_{n}y_{n}$에서$y_{a}  $S2 = x_{1}y_{1} + x_{2}y_{2} + ... + x_{a}y_{b} + ... + x_{b}y_{a} + ... + x_{n}y_{n}$ 둘을 뺴면 $S1 - S2 = x_{a}(y_{a} - y_{b}) + x_{..

• format_list_bulleted 그리디 알고리즘
• · 2024. 11. 22.
• textsms