3장: 설계 기법(1) - 전체 탐색

3장 설계 기법(1) - 전체 탐색

선형 탐색법: 선택지를 순서대로 조사하는 방법.

조합 전체 탐색: 선택지 중 몇 가지를 조합하여 W가 될 수 있는지 판별하는 문제에 사용된다.
부분 집합의 개수를 모두 구하고 이를 탐색한다.

• N = 8 이라고 가정 할 때, 집합 {a0, a1, a2, a3, a4, a5, a6, a7}을 각 자리 수마다 부분 집합을 이진법에 대응시켜 표현 할 수 있다. 
  가령 부분 집합 {a0, a2, a3, a6}를 표현하면, 01001101로 표현 할 수 있다.

• 따라서, Bit로 나타낸 부분 집합에 i번째 요소가 포함되었는지는 
  if (bit & (1 << i)로 판단 할 수 있다.

연습 문제
3.5 N개의 양의 정수 a0 …. an-1 이 주어졌을 때, N개의 정수가 모두 짝수라면 2로 나눈 값으로 치환하는 작업을 더 이상 할 수 없을 때까지 반복한다. 이런 작업을 몇 번 해야 하는지 구하는 알고리즘을 설계하라.

            int maxEvenNum = 0;

            // 모두 순회 - 복잡도 O(N)
            foreach (int num in numContainer)
            {
                // 짝수이며 최대 숫자면 저장
                if (num % 2 == 0 && num > maxEvenNum)
                {
                    maxEvenNum = num;
                }
            }

            int count = 0;
            while (maxEvenNum > 0)
            {
                maxEvenNum = maxEvenNum / 2;
                count++;
            }

            // 결과 출력
            Console.WriteLine(count);
            return count;

3.6 두 개의 양의 정수 K, N이 주어졌을 때, 0 <= X, Y, Z <= K 를 만족하는 정수 (X, Y, Z) 조합에서 X + Y + Z = N 을 만족하는 경우가 얼마나 존재하는지 구하는 O(N^2) 복잡도 알고리즘을 설계하라.

            int count = 0;
            for (int X = 0; X <= K; X++)
            {
                for (int Y = 0; Y <= K; Y++) // O(N^2)
                {
                    if (X + Y <= N)
                    {
                        int Z = N - X - Y;
                        if (Z <= K)
                        {
                            // 출력용
                            while (X + Y + Z <= N)
                            {
                                Console.WriteLine("X: " + X + " Y: " + Y + " Z: " + Z);
                                Z++;
                            }

                            count++;
                        }
                    }
                }
            }

3.7 "1927359" 처럼 모든 글자가 1 이상 9 이하의 숫자로 된 길이가 N인 문자열 S가 주어졌을 때 문자 사이사이에 "+"를 넣을 수 있다고 하자. +는 0개 이상 가능하나, 연속한 +는 넣을 수 없다. 이런 조건으로 만들 수 있는 모든 문자열을 산술식으로 보고 총합을 계산하는 O(N^2) 복잡도 알고리즘을 설계하라.

예: S = "125"라면 만들 수 있는 문자열은 125, 1+25(26), 12+5(17), 1+2+5(8) 이며, 이걸 보두 더한 176이 답이다.