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!..
1. 일렬로 앉은 경우 먼저 n명의 사람이 일렬로 앉아있다고 생각해보자. a1, a2, a3, ... , an이 일렬로 앉아있고, 여기서 서로 인접하지 않게 b1,b2,...,bk를 선택한다고 생각해보자. b1,b2,...,bk가 서로 인접하지 않다는 것은 무슨 뜻일까? 먼저 선택한 k명 b1,b2,...,bk 사이의 선택받지 못한 x1,x2,x3,..,xk,xk+1에 대해, x1+x2+...+xk+1 = n-k이다. 왜냐하면 n명중 k명 b1,b2,..,bk를 선택하고 나서 남은 사람은 n-k명이니까 여기서 b1,b2,..,bk가 서로 인접하지 않을려면 그 사이에는 사람이 최소 1명이상 있어야한다. 즉, x2,x3,...,xk는 최소 1 이상이고 x1,xk+1은 0이상이다. 그러므로 구하고자 ..
1. 중복조합 n종류가 있을 때, k개를 선택하는데 종류의 중복을 허용해서 선택하는 방법의 수를 구하고 싶다. 예를 들어 a,b,c 3개의 문자 중 5개를 중복을 허용해서 선택한다면 (a,a,a,a,a) (a,a,a,a,b) (a,a,a,b,c) .... (b,b,b,c,c) 등등이 있다. 이러한 방법의 수를 어떻게 찾을 수 있을까? 5개의 빈칸에 a,b,c를 결정하면 되는데 2개의 칸막이를 이용해서 다음과 같이 구별하는 방법의 수로 이해할 수 있다 x1,x2 2개의 칸막이를 적당히 옮겨서 첫번째 영역에는 a를 전부 넣고, 두번째 영역에는 b를 전부 넣고 세번째 영역에는 c를 전부 넣는다. n종류를 구분할려면 필요한 칸막이의 개수는? n-1개이다. 1개를 놓으면 2 영역이 생기고 2개를 놓으면 3 ..
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명 이..
SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 나이트가 (i,j)에 있을때, (i+1,j+2), (i+2,j+1) 둘 중 하나로만 움직일 수 있다고 하자. x,y가 주어질 때, (0,0)에서 출발하여 (x,y)로 이동할 수 있는 경우의 수는? dp[y][x] += dp[y-1][x-2], dp[y][x] += dp[y-2][x-1]로 구할 수 있을 것 같은데 X,Y가 $10^{6}$까지라서 메모리도 안되고 $O(N^{2})$이라 시간복잡도도 안된다 나이트가 (i,j)에서 이동하는 방법이 (i+1,j+2), (i+2,j+1) 2가지만 있다는 것을 생각한다면... (0,0)에서 (..
1. 문제 10972번: 다음 순열 (acmicpc.net) 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 2. 풀이 1부터 n까지 정수로 구성된 어떤 순열이 주어질때 바로 다음 순열을 찾는 문제 예를 들어 1부터 5까지 구성된 순열 1 2 3 4 5 1 2 3 5 4 1 2 4 3 5 ... 5 4 2 3 1 5 4 3 1 2 5 4 3 2 1 1 2 3 5 4가 주어지면 1 2 4 3 5라고 답해야한다. 단순하게 1부터 n까지 리스트를 만들고 permutations로 순열을 구한다음 현재 순열의 위치를 찾고 다음 순열을 찾아볼 수도 있겠지만.. n이 10000까지라..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
