여사건을 이용한 경우의 수1 - 특정 수를 포함하는 부분집합 구하는 법

20214번: Binary Seating (acmicpc.net)  두 강의실 0번과 1번에 n명의 학생이 1/2의 확률로 선택하여 입장할때,  1번 강의실에서 모든 시험이 끝날 때까지 걸리는 시간의 기댓값을 구하는 문제 걸리는 시간을 X라고 한다면...? 예를 들어 학생이 5명이고 각각 t = 1,4,5,2,3 만큼 시험을 보고 떠난다고 할때, 가능한 X = 1,2,3,4,5이다. 그러므로 E(X) = 1*P(X = 1) + 2*P(X = 2) + 3*P(X = 3) + 4*P(X = 4) + 5*P(X = 5) P(X = 1)은 어떻게 구할까? t = 1인 학생이 1번 강의실에 들어간 경우 (1) P(X = 2)는 어떻게 구할까? t = 2인 학생이 1번 강의실에 들어간 경우 (2) t = 1인 학생..

• format_list_bulleted 조합론
• · 2024. 8. 23.
• textsms

다이나믹 프로그래밍을 이용한 partition minimum sum of difference of two subset(합의 차이가 최소가 되는 분할) 문제 해법

1. 문제 배열 A가 주어질때, A를 2개의 부분집합으로 분할하고자 하는데, 각 부분집합의 원소의 합이 X,Y이면 abs(X-Y)가 최소가 되도록 분할하고자 한다 이때, 그 최솟값을 구하거나 X,Y를 구하는 문제 A의 원소의 합이 total = sum(A)라면, 두 부분집합의 원소 합의 차이가 최소가 되는 것은 정확히 절반이 되는 경우이다. 그러니까 최대 target = total//2에 도달하는게 가장 좋다. 1) dp[i] = A의 원소를 일부 골라서 합했을때, i가 될 수 있는가? 만약 i-w를 만들 수 있다면, w를 더하면 i가 될 수 있으므로 dp[i-w] = 1이면 dp[i] = 1이 된다. #dp[i] = 배열 v의 원소를 일부 골라 합해서 i를 만들 수 있는가?target = total//..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 7. 8.
• textsms

모든 부분집합 원소의 곱의 합을 구하는 공식이 있다고?

1. 문제 9375번: 패션왕 신해빈 (acmicpc.net) 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 2. 풀이 경우의 수가 바로 안나오기는 한디... 경우를 나눠서 생각해보면 hat headgear sunglasses eyewear turban headgear headgear에 2가지 있고 eyewear에 1가지 있는데.. headgear에서 1가지를 뽑는 경우의 수 = 2가지 + eyewear에서 1가지 ..

• format_list_bulleted 확률론 알고리즘
• · 2023. 8. 20.
• textsms

포함 배제의 원리를 이용해 매우 큰 범위에서 조건에 맞는 수들만 빠르게 찾는 법 배우기 (+ 부분집합 구하기 재활)

1. 문제 9359번: 서로소 (acmicpc.net) 9359번: 서로소 첫째 줄에 테스트 케이스의 개수 T (0 < T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, A, B, N이 주어진다. (1 ≤ A ≤ B ≤ 1015, 1 ≤ N ≤ 109) www.acmicpc.net 2. 풀이 $10^{15}$이내에서 $N = 10^{9}$과 서로소인 수를 1초안에 찾으라고 한다면.. 보통의 방법으로는 찾기 힘들다 심지어 쿼리로 주어지니 더 어렵다 먼저 약수를 찾는 것보다 배수를 찾는 것이 쉽다는 것을 이해한다. N의 소인수를 모두 찾고, N의 소인수의 배수는 N과 서로소가 아니므로, 이 방법을 이용해 서로소가 아닌 수들을 찾는다. 범위 내에서 N과 서로소인 수와 서로소가 아닌 수로..

• format_list_bulleted 정수론
• · 2023. 7. 9.
• textsms

잊을만하면 순열조합 연습하기 -치킨배달-

1. 문제 15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 어떤 집과 모든 치킨 집 사이 거리의 최솟값을 해당 집의 치킨 거리라고 부르고 모든 집의 치킨 거리의 합이 해당 도시의 치킨 거리이다. 최대 m개의 치킨 집만 선택해서 가능한 도시의 치킨 거리의 최솟값은 2. 풀이 항상.. 문제를 잘 읽어야한다 "어떤 집과 모든 치킨 집 사이 거리의 최솟값을 해당 집의 치킨 거리" 이것부터 제대로 보질 못했는데.. 빨리 봐서 다행이긴해 조합을 구현한..

• format_list_bulleted 브루트포스
• · 2022. 10. 30.
• textsms

경이로운 그리디 알고리즘1 -만들 수 없는 합의 최솟값-

1. 문제 자연수로 이루어진 어떤 수열이 주어질때, 이 수열의 모든 부분수열의 합을 생각해보자 이때 불가능한 합의 최솟값을 구해본다면? 예를 들어 s = [5,1,2]이면, 1,2,3,5,6,7,8은 만들 수 있는데 4를 만들 수가 없다  2. 알고리즘 2-1) 수열을 오름차순으로 정렬한다 2-2) sum = 0로 초기화한다 2-3) 수열을 하나씩 순회해서 그것을 x라고 하자.  sum+1을 만들 수 있는지 확인해본다.  2-4) sum+1 >= x이면 sum+1까지 만들 수 있다. 그러면, sum + x를 sum으로 갱신한다. 2-5) sum+1  이것만 보면 아무리 생각해도 와닿지는 않는다 어떻게 보면 경이롭기까지하다.  진짜 이게 가능한건가? 여러가지 풀이를 보면서 이해해보도록 노력하자  3. 예시..

• format_list_bulleted 그리디 알고리즘
• · 2022. 10. 30.
• textsms