대략 문제를 풀 때, 하는 수 없이 모든 경우의 수를 뒤져야 하는 경우가 있다.

이런 경우 반복문 또는 재귀(recursion)를 통해 모든 경우의 수를 체크해야 한다.

요런 문제로써, 

줄 세우기, n 개 중 m 개 뽑기, 모든 부분 집합 찾기, 트리 탐방 .... 등의 케이스가 있다.

부분 집합 찾기는 다음 페이지를 참고 하시고 ~

부분집합 출력하기 (C/C++)

다음 코드는 0~n-1 사이의 숫자 중에 m 개를 고르는 모든 수를 출력하는 코드이다. (combination)

요것은 부분집합  중에 원소 개수가 m 인 것만 출력하는 것과 같은 문제이다.

이번에는 0~n-1 사이의 숫자 중에 m 개를 골라서 순서를 세워 출력하는 코드이다. (순열, permutation)

집합 S = {0, 1, ..., n} 이 있을 때, 모든 부분집합 P(S) 를 출력하는 코드

가장 간단히는 비트 플래그를 이용하는 방법이 있다.

단, 집합 원소 크기가 31로 한정되는 단점이 있다 (아래 코드에서는)

아래 코드에서 MAX_VALUE 의 타입을 변경하면 64 개까지 가능하다.

다른 방법으로는 아래와 같이 재귀 호출을 통해 출력하는 방법이다.

이것은 set[] 에 원소를 추가 또는 추가하지 않는 호출을 반복하는 것이다.

이해가 안 되면 그림을 그려 보시라 ~

references :

보통 피보나치 수열의 일반항은 a0 부터 차례대로 구하는 방법이 있다.

이 방법은 time complexcity O(n) 이다.

하지만, 피보나치 수열의 일반항[1]을 이용하면 time complexity 를 O(log n) 으로 계산 할 수 있다.[2]

물론, float point 의 곱셈 계산이 필요하므로, n 이 작으면 위 방법에 비해 시간이 더 많이 소요될 수 있다.

(아마 보통은 아래 방법이 더 오래 걸릴 것이다.)

게다가 double 형 타입의 계산 오차로 인해 n 이 충분히 크다면 대략 오차가 발생한다.

(테스트 해 보니 n=75 까지 잘 계산 되고, n=76 에서 1 오차가 발생함.)

결론적으론 첫 번째 방법이 더 좋다 ㅡㅡ;

references :

[1] http://en.wikipedia.org/wiki/Fibonacci_number

[2] http://stackoverflow.com/questions/5231096/time-complexity-of-power