[TIL] 알고리즘 : 조합론

오류가 있다면 말씀해주세엽

Chap 4. 조합론

벌써 일주일이 갔군욥 화이팅!

 

1) 이항 계수

이항계수를 구하는 방법?

1. for 문, 팩토리얼
2. 재귀 (시간 worst)
3. Combination 재귀
4. 팩토리얼 DP
5. 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번: 순열의 순서

 

힝힝 문풀 욕심 그만부리고 설명 더마니 들을걸 .. ㅜㅜ 필기 보니까 넘 요약해서만 써놔서 가물가물스 .. 

무튼 이번주 뿌듯하다!