비트마스킹

문제이해 정수로 이루어진 수열 num과 s가 주어지면, num안의 원소중 더한 값이 s가 되도록 하는 경우의 수를 구하는 문제이다. 계획 먼저 브루스포트로 푸는 경우의 시간복잡도는 2^40으로 1초이내 푸는 것이 불가능하다. 따라서, 시간복잡도를 O(2^N)인 알고리즘을 O(2^(N/2))로 줄일 수 있는 Meet In The Middle 알고리즘을 활용하면 해결할 수 있다. MITM(Meet In The Middle) MITM은 N이 그렇게 크지 않지만 완전 탐색을 진행하기엔 무리가 있다고 판단할 때 주로 사용하는 알고리즘이다. 배열을 완전탐색 한다면 O(2^N)시간복잡도가 나올 걸, 배열을 반으로 나눈 뒤 각각의 조합을 구해 O(2^(N/2)+2^(N/2))=O(2^(N/2)) 경우의 수가 나오게 하..

문제이해 0~9까지의 숫자를 적어도 한 번씩은 거치면서 계단 수를 만들 수 있는 경우의 수를 구하는 문제다. 단, 0으로 시작할 수는 없다. 예를 들어, 10자리의 계단 수를 만들 수 있는 경우는 9876543210 밖에 없으므로 한 가지밖에 없다. 계획 0~9까지의 숫자를 적어도 한번씩 거친다는 조건이 없다고 생각하자. 행이 n, 열이 10인 2차원 배열 t가 있다고 하면, t[0]부터 t[n-1]까지 t[i][ii] (0