목록집합 (1)

PS와 개발을 공부하자

N개의 비트에서 모든 부분집합들의 부분집합 순회하기

시간복잡도가 \(4^N\) 일 것같지만 \(3^N\) 이라고한다. 이유는 잘모르겠음 걍 외우자ㅎ +이유를 깨달았다부분집합(1)의 부분집합(2)이니까부분집합(1) 에 포함되거나 안되거나고, 만약 된다면 부분집합(2)에 포함되거나 안되거나니까 결국1. 부분집합(1)에 포함되지만 부분집합(2)에는 포함되지않거나2. 부분집합(1)에도 포함되고 부분집합(2)에 포함되거나3. 둘다 안포함되거나셋중 하나이기때문에 3^N
Algorithm/Memo &Tips 2017.09.10 22:23
Prev 1 Next