다이나믹 프로그래밍으로 구하는 복수순열2 - 주어진 개수의 알파벳들만으로 만들 수 있는 문자열의 개수

E - Alphabet Tiles (atcoder.jp) E - Alphabet TilesAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  대문자 알파벳 A,B,C,..,Z의 개수가 주어질때, 이들로 만들 수 있는 길이 1부터 k까지 모든 문자열의 개수를 구하는 문제 길이가 s일때, 각각 A,B,C,...,Z 문자가 a1,a2,a3,...,a26개 있다고 한다면.. 이들을 일렬로 배열하는 복수순열의 개수와 같으므로,  $$\frac{(a1+a2+a3+...+a26)!}{a1!a2!...a26!} = \frac{s!}{a1!..

• format_list_bulleted 다이나믹 프로그래밍
• · 2024. 6. 20.
• textsms

적어도 1명 이상이 자기 자신 것을 그대로 가져갈 확률은?(교란순열의 수렴)

13531번: Secret Santa (acmicpc.net)  n명의 사람이 모자에 이름을 쓰고, 한번 섞은 다음에 다시 가져가는데 적어도 1명 이상이 자기 자신 것을 그대로 가져갈 확률을 구하는 문제 https://deepdata.tistory.com/946 자기 것을 다시 갖지 않고 나눠주는 경우의 수 교란순열(완전순열) 배우기1. 문제 1947번: 선물 전달 (acmicpc.net) 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net 2. 풀이 PS를 위한 수학 - 교란 순열(완전순열) - 와 이게 에러가deepdata.tistory.com 1 - n명의 사람이 모두 자기 자신 것을 가져가지 않는 확률 = 적어도 1명 이..

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

자기 것을 다시 갖지 않고 나눠주는 경우의 수 교란순열(완전순열) 배우기

1. 문제 1947번: 선물 전달 (acmicpc.net) 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net 2. 풀이 PS를 위한 수학 - 교란 순열(완전순열) - 와 이게 에러가 뜨네 (mjstudio.net) PS를 위한 수학 - 교란 순열(완전순열) 교란 순열 ps.mjstudio.net 비가 오는 날에 n명의 사람이 자기의 우산을 쓰고 한 건물에 모여있다. 모두 동시에 집에 가려고 다시 우산을 쓰고 나가려는데, 자신의 우산을 사용하지 않는 경우의 수는? n개의 물건을 n명의 사람에게 다시 분배하는데, 자기 물건을 다시 갖지 않는 경우의 수를 교란순열(완전순열, derangement)라고 부른다 점화식이 유명한데 (고등..

• format_list_bulleted 조합론
• · 2023. 7. 18.
• textsms

[Java]우선순위 큐 응용 - MN개의 조합에서 조건을 만족하는 k번째 수를 찾는 빠르게 찾는 방법 1편

1. 문제 n개의 숫자로 이루어진 수열과 m개의 숫자로 이루어진 수열이 주어졌을 때, 각 수열에서 정확히 원소를 하나씩만 뽑아 나올 수 있는 모든 쌍들을 모두 구하고, 그 값들을 오름차순이 되도록 나열했을 때의 k번째 쌍의 두 수의 합을 구하는 프로그램을 작성해보세요. n,m은 1이상 10만 이하의 자연수 k는 1이상 min(nm, 10만)이하 2. 풀이 가장 쉽게 생각할 수 있는 방법은 mn개의 모든 조합을 만든 다음에 우선순위 큐에 모두 집어 넣고, k번째 빠지는 수를 출력하면 된다 근데 뭐 당연히 시간초과 + 메모리 초과임 m과 n이 10만인데 시간복잡도가 얼마냐 이거 O(M + N + MNlogMN + KlogMN)인가..? 아무튼 O(MN)으로 생각하는 순간 10만*10만 = 100억으로 오바다..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2023. 3. 21.
• textsms

1차원 convolution 연산을 효율적으로 하는 계산하는 방법은?

1. 문제 22964번: conv1d (acmicpc.net) 22964번: conv1d A = [1, 1], B = [1] : 1 1 A = [1, 1], B = [2] : 2 2 A = [1, 2], B = [1] : 1 2 A = [1, 2], B = [2] : 2 4 A = [2, 1], B = [1] : 2 1 A = [2, 1], B = [2] : 4 2 A = [2, 2], B = [1] : 2 2 A = [2, 2], B = [2] : 4 4 1+2+1+2+2+4+2+4 = 18 1+2+2+4+1+2+2+4 = 18 www.acmicpc.net 입력데이터와 필터가 주어질때, 1차원 convolution 연산을 수행하는 문제 2. 풀이 역시 만만한 문제가 아니다 단순히 곱하는거면 문제가 아닌..

• format_list_bulleted 구현,시뮬레이션
• · 2022. 12. 10.
• 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