프로베니우스의 동전 문제(Frobenius coin problem)와 슈어의 정리(Schur's theorem)

1. 프로베니우스의 동전 문제(Frobenius coin problem) 서로 다른 두 동전 x원, y원이 있을때, 이 두 동전을 각각 적당한 개수를 사용하여, 만들 수 없는 금액중 가장 큰 값은? 이 문제의 정답을 프로베니우스의 수(Frobenius number)라고 부른다. 예를 들어 3원, 5원짜리 동전으로 만들 수 없는 가장 큰 금액은 7원이다. 이 말은 8원 이상의 금액은 무조건 만들 수 있다는 뜻이다. 주의할 점은 7원 밑의 금액 중에서 1,2,4원은 만들 수 없다는 것은 자명하다. 프로베니우스의 수는 x,y가 서로소(최대공약수가 1)일때만 존재한다. 이때, 프로베니우스의 수는 xy - x - y임이 알려져있다. 2. 일반화된 문제 일반적으로는, n개의 동전 $a_{1}, a_{2},...,..

• format_list_bulleted 정수론
• · 2026. 3. 30.
• textsms

모노토닉 스택(monotonic stack)을 이용한 나보다 큰 첫 번째 수 찾기 문제(오큰수,NGE,next greater element)

1. 모노토닉 스택(monotonic stack) 스택 내부의 원소들을 항상 오름차순, 혹은 내림차순 상태를 유지하도록 만드는 자료구조 나보다 크거나, 작은 숫자가 언제 처음 나오는지를 찾는데 유용하다. 알고리즘 문제에서 보통, "배열에서 나보다 크면서 오른쪽에 있는 수 중 첫번째 수는?" 예를 들어, [5,3,1,4,2]가 있다고 하자. 각 숫자에 대해서 "오른쪽에 있는 나보다 큰 첫번째 수"들을 모두 O(N)에 찾으라고 한다면? 스택 []을 두고, 왼쪽부터 오른쪽 차례대로 순회한다. 스택이 비어있으니까 [5] 2번째 3이 들어오는데, 스택의 마지막 수 5가 3보다 더 크므로 그대로 입장 [5,3] 3번째 1이 들어오는데 스택의 마지막 수 3이 1보다 더 크므로 [5,3,1] 4번째 4가 들어오는데 ..

• format_list_bulleted 알고리즘/자료구조(스택,큐,해시맵)
• · 2025. 12. 23.
• textsms

순열 사이클 분할에 대해 알아보기

1. 순열 사이클 1부터 n까지 정수 n개로 이루어진 배열을 순열이라고 부른다. 예를 들어 [3,2,4,5,1]은 길이가 5인 순열이다. 배열의 인덱스를 '현재 위치', 배열의 값을 '다음에 갈 곳'으로 생각하고 인덱스 > 값으로 향하는 방향 그래프를 만들 수 있다. 즉, [3,2,4,5,1]은 1 > 3, 2 > 2, 3 > 4, 4 > 5, 5 > 1로 간선을 이으면 다음과 같이 방향 그래프를 만들 수 있다. 위 그래프는 2개의 사이클 1 > 3 > 4 > 5, 2 > 2가 있다. 이 사이클들을 순열 사이클이라고 부른다. 전체 순열을 여러개의 독립적인 순열 사이클로 분할하는 것을 '순열 사이클 분할'이라고 부른다. 길이 n인 순열에는 반드시 사이클이 생긴다. 왜냐하면 먼저 1부터 n까지 1개씩만 ..

• format_list_bulleted 알고리즘/순열 사이클 분할
• · 2025. 12. 19.
• textsms

O(1)에 스택의 최솟값을 찾는 min stack 기법?

https://www.acmicpc.net/problem/8858 은행원이 현금 보유액 S를 가지고 있다. 고객이 입금을 하러 온다면, 입금 금액을 기록하고 고객이 가져온 현금을 새 봉투에 넣은 다음, 이전 입금 봉투 위에 쌓는다. 입금 봉투는 이처럼 스택 구조로 쌓이게 된다. 고객이 X원을 출금하러 온다면, 봉투 스택이 비어있는 경우 전액을 현금 보유액 S에서 지급 봉투에 든 금액들 중 가장 작은 금액보다 X가 작다면, 전액을 현금 보유액 S에서 지급 그렇지 않다면, 봉투 스택의 맨 위에서부터 하나씩 꺼낸 다음, 필요한 금액을 충당 마지막에 꺼낸 봉투에서 일부 금액만 사용하면, 남은 돈은 현금 보유액 S로 넣는다. 만약 모든 봉투를 다 사용했는데 X를 다 지급하지 못하면 남은 금액은 현금 보유액 S에..

• format_list_bulleted 알고리즘/자료구조(스택,큐,해시맵)
• · 2025. 11. 27.
• textsms

중간에서 만나기3 - 부분집합의 합이 s가 되는 경우의 수를 세는 놀라운 방법

1. 중간에서 만나기(meet in the middle) 중간에서 만나기 알고리즘은, 다익스트라 알고리즘처럼 전형화된 그런 알고리즘은 아니다. 다이나믹 프로그래밍 같은 알고리즘이라고 해야할까 완전탐색의 시간복잡도가 매우 높을 때, 이를 절반으로 줄이는 기법이다. 가능한 경우의 수를 절반씩 나누어 탐색한 뒤 그 결과를 조합하여 정답을 찾는 방식이다. 예를 들어 브루트포스가 $O(2^{N})$으로 매우 높은 경우, $O(2^{N/2})$로 줄일 수 있을때 효과적이다. N = 40인 경우만 해도 아예 불가능한 정도가 $10^{6}$정도로 가능해진다 예를 들어 주어진 수열 A에서 부분집합의 합이 S가 되는 경우의 수는 몇가지일까? 부분집합의 개수는 $2^{N}$이므로, 시간복잡도는 $O(2^{N})$ 1)..

• format_list_bulleted 알고리즘/중간에서 만나기
• · 2025. 7. 4.
• textsms

Prime number Theorem으로 알아보는 구간 내의 소수 개수

1. prime number theorem(소수 정리) 양의 실수 x 이하에 존재하는 소수의 개수를 $\pi(x)$라고 한다면 다음이 성립한다. 양수 x이하의 소수의 개수는 근사적으로 x/logx개라는 소리다. 로그 적분 함수 li(x)는 다음과 같이 정의한다. 그래프가 다음과 같다. 구간 [0,x]가 아닌 [2,x]에서 로그 적분 함수를 Li(x)로 나타내기도 한다 이를 이용해서 다음과 같이 나타내기도 한다. 즉, $\pi(x)$는 Li(x)에 근사할 수 있고, 현대에는 이게 더 정확하다고 알려져있다. 2. 소수의 밀도 직관적으로 큰 숫자에서 소수 사이 간격이 점점 커진다는 것을 알 수 있다. 에라토스테네스의 체로 구해보면 알수 있다 그렇게 차이나지는 않네 흠.. 양수..

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