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

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

비둘기집 원리(pigeonhole principle) 기본개념 배우기

1. 비둘기집 원리(pigeonhole principle) "n+1개의 물건을 n개의 상자에 넣을때, 최소한 한 상자에는 적어도 2개 이상의 물건이 반드시 들어있다" n+1개의 물건과 n개의 상자가 있으며, 각 상자당 한개씩의 물건만 존재한다고 가정한다면, 최대 n개의 물건이 존재할 수 있는데, 물건의 숫자는 n+1개이므로 어느 상자에도 들어가지 못한 물건이 하나 남을 수밖에 없으므로 모순이다. 그러므로 각 상자당 한개씩의 물건만 들어가야한다는 가정은 성립할 수 없으며, 적어도 하나의 상자에는 2개 이상의 물건이 존재한다. 너무나도 당연한 이 사실에 "비둘기집 원리(pigeonhole principle)"이라는 거창한 이름이 붙은 이유는 생각보다 많은 수학적 원리를 증명하기 위해 비둘기집 원리가 사용되며..

• format_list_bulleted 알고리즘/비둘기집 원리
• · 2023. 6. 25.
• textsms