중간에서 만나기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

에라토스테네스의 체 변형 segmented sieve 배우기

https://deepdata.tistory.com/393 소수를 빠르게 구하는 에라토스테네스의 체 알고리즘1. 소수를 구하는 방법 컴퓨터가 주어진 수 n이 소수인지 판단할려면 어떻게 해야할까? 1부터 n까지 n에 나눠보면서 n의 약수인지 아닌지 판단해보면 된다. n의 약수가 1과 n만 있어야 n이 소수이다deepdata.tistory.com 에라토스테네스의 체의 문제는 수행하는 연산의 수가 아니라 메모리 요구량에 있다. n이 매우 큰 경우, 소수의 범위가 메모리에 모두 담기지 않을 수 있다. 더 나쁜 것은, n이 그리 크지 않은 경우에도 캐시 사용이 매우 비효율적이라는 점이다. 이 알고리즘은 배열 A 전체를 순차적으로 탐색하며, 참조 지역성이 거의 없다. 이러한 문제에 대한 해결책으로 분할 체(se..

• format_list_bulleted 정수론
• · 2025. 6. 30.
• textsms

persistent linked list이용한 문자열 변화 추적하기

1. persistent linked list “퍼시스턴트(Persistent) 연결 리스트”는 한 번 만든 리스트를 “불변(immutable)”으로 유지하면서도, 수정할 때마다 과거 버전까지 그대로 보존할 수 있게 해 주는 연결 리스트입니다. 1) 왜 ‘퍼시스턴트’인가?일반 연결 리스트는 노드 값을 바꾸거나 추가·삭제하면 기존 상태가 없던 일처럼 사라집니다.반면 퍼시스턴트 리스트는 “이전 상태”를 그대로 남겨 두고, 수정 후 새 리스트 버전을 만들어 줍니다.즉, 여러 시점(version)의 리스트를 동시에 관리할 수 있죠. 2) 어떻게 불변성을 지키나?노드는 절대 수정하지 않는다.새로운 내용만 새 노드로 생성하고,변경되지 않은 구간은 **기존 노드를 그대로 재사용(공유)**한다.각 버전은 “헤드 포인터..

• format_list_bulleted 알고리즘/고급 자료구조
• · 2025. 6. 23.
• textsms

체력 제한이 있어 끝까지 갈 수 없는 기묘한 다이나믹 프로그래밍(O(NHM)을 O(NM)으로 줄이는 트릭?)

E - Battles in a Row E - Battles in a RowAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp n마리의 몬스터와 차례대로 싸우고자 하는데, 현재 체력 h 마력 m이 있다. i번째 몬스터와 싸울때 두가지 중 하나를 선택할 수 있다. 1) 현재 체력이 A[i]이상일때, A[i]만큼 체력을 감소시키고 몬스터를 처치 2) 현재 마력이 B[i]이상일때, B[i]만큼 마력을 감소시키고 몬스터를 처치 n마리의 몬스터를 모두 쓰러뜨리거나, 어떤 행동도 취할 수 없으면 게임 종료 게임이 끝날때까지 몬스터를 쓰러..

• format_list_bulleted 알고리즘/다이나믹 프로그래밍
• · 2025. 6. 19.
• textsms

vertex multiplexing을 이용한 가중치의 bitwise xor이 최소가 되는 경로

https://atcoder.jp/contests/abc410/tasks/abc410_d D - XOR Shortest WalkAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 방향 그래프가 주어지는데, A에서 B로 가는 간선의 가중치가 W이다. 이때, 1번부터 N번 정점까지 경로의 가중치들의 bitwise xor이 최소가 되는 경로에 대해 그 최솟값을 구하면? 여기서 1번부터 N번 정점까지 경로는, 동일한 간선이나 동일한 정점을 여러번 방문하더라도, 처음 시작점이 1번이고 마지막 종점이 N번인 경로이다. ----------..

• format_list_bulleted 알고리즘/그래프 이론 정복기
• · 2025. 6. 18.
• textsms