오류가 있다면 말씀해주세엽
Chap 4. 조합론
벌써 일주일이 갔군욥 화이팅!
1) 이항 계수
이항계수를 구하는 방법?
- for 문, 팩토리얼
- 재귀 (시간 worst)
- Combination 재귀
- 팩토리얼 DP
- Combination DP
당욘 DP가 굿
그러기에 ..
- 파스칼의 삼각형
코드?
//초기화 ->다 1로 초기화
combi[0][0] = combi[1][0] = combi[1][1] = 1;
//파스칼 삼각형
for (int i = 2; i <=n ; i++) {
for (int j = 0; j <= i; j++) {
if(j==0||j==i)
combi[i][j] = 1;
else {
combi[i][j] = (combi[i - 1][j - 1] + combi[i - 1][j]);
}
}
}
참고 ) DP구현시, 배열을 전역변수로 선언해주자. 점화식에 대한 주석과 함께 !
2 ) 순열과 조합
비교 ?
- 순열 : DFS 기반 완전탐색
- 조합 : DP 기반 메모이제이션
(DFS는 https://lullu-nan-potato-developer.tistory.com/4 참고)
팁)
DFS를 하려면 n<20정도일때야 괜찮지만 .. 다음 문제처럼 n=100이러면 무리무리! n에서 힌트를 얻어서 dp로 넘어가는 습관을 기르잣
팁)
순열 등에서 중복을 어떻게 제거할것인가?
: set 자료구조를 사용하자. insert하면 알아서 중복 비허용해서 구현해줌
근데 map자료구조도 차피 중복제거/조회에 대해 O(1)의 시간복잡도를 갖기에 map도 굳
팁) N번째 순열 찾기
https://www.acmicpc.net/problem/1722
1722번: 순열의 순서
첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N
www.acmicpc.net
힝힝 문풀 욕심 그만부리고 설명 더마니 들을걸 .. ㅜㅜ 필기 보니까 넘 요약해서만 써놔서 가물가물스 ..
무튼 이번주 뿌듯하다!