티스토리 뷰

반응형

이전 포스트

순열과 조합 : 조합의 구현


헤헤헤. 사실 계획대로라면 dp 문제를 들어가야했지만 

하나를 제대로 하는 것이 중요하다고 생각해요. 그래야 다른 응용문제도 잘 풀 수 있을테니까 말이죠.

우리는 조합을 구현하는데 두 가지 방법을 썼습니다.

1 첫 번째는 비트스트링과 순열을 활용한 조합방법  ( 010101011100)

2 두 번째는 조합 인덱스를 생성해내는 알고리즘   (2,4,6,8,9,10)


이제 나머지 두 방법을 살펴볼건데 

3 DFS를 이용한 조합 경우의 수 찾기 (모든 경우의 수도 가능함)

4 비트마스크를 이용한 조합 경우 찾기 (모든 경우의 수도 가능함)

방법은 알고리즘 문제를 푸는데 자주 사용하는 것입니다.


그치만 너무 귀찮군요. 푸하하...


대신에 문제를 두개 준비해보았습니다.

백문이 불여일견이니까..

백준이 불여일견!...






https://www.acmicpc.net/problem/1182


문제는 어떤 집합이 주어지면, 그 집합의 모든 부분집합 중에서 특정한 값이 나오는 갯수를 세주는 것입니다.

부분집합은 정확히 n 크기의 집합에서 2^n개가 나올 수 있습니다.(공집합 포함)

부분집합을 생성하는 것이라면, 결국엔 모든 경우의 수를 다 해봐야합니다.


따라서, 이 문제도 결국 brute force 입니다. 분명한 것은 nCr을 구하는데 r은 다음을 만족해야하죠. 0<=r<=n. 

그러니까 조합을 구하는데, nCr이긴한데, r이 특정한 값이 아닌 0~n 까지를 탐색해야합니다.


이 때 분명한건, 이번문제도 1번 2번 방법으로 충분히 해결할 수 있습니다.

하지만

앞에서 살펴본 1번 순열 과 비트스트링의 조합을 이용한 문제풀이에서는 0000000001  부터 1111111111 까지의 비트스트링(배열)을 만드는 것도 귀찮고,

2번 풀이처럼 조합알고리즘을 이용하는데에도, 매번 변경되는 배열 인덱스를 초기화 시켜주는것도 귀찮다.! 기억이안난다면여길클릭


그런경우 dfs 또는 bitmask를 이용합니다. 

그렇기에 기초적인 경우의 수 문제에서는 다음것 들을 뺄 수 없습니다.

"permutation and dfs", 또는 "permutation and bitmasks" 또는 "only dfs" 또는 "only bitmask" 

저는 dfs를 선호하는편입니다만, 분명한건 bitmask가 많이 쓰입니다. (둘다 많이 쓰이는듯, bitmask가 더 많을지도)



이번 문제는 dfs로 풀어볼것입니다. 

부분집합은 첫 인덱스 0부터 해당 index를 포함하거나, 포함하지않거나로 완성될 수 있습니다. 그리고 인덱스가 n일때 탐색을 종료하죠.

재귀함수로는 이를 훌륭하게 표현할 수 있습니다.


dfs를 활용한 부분집합의 합 소스보기

https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/1182.c



bitmask를 이용한 모든 경우의수를 해보기는 다음 포스트에서 볼 수 있습니다.



다음 포스트 보기

우아한 경우의 수, dynamic programming


반응형