(25.03.24) n개에서 k 고르기 : 재귀 백트래킹 VS 비트마스크

OO 사 코딩 테스트를 진행하면서, 기억에 남는 문제를 복기를 해서 알고리즘을 확인했다.

최대한 많은 조합을 만드는 문제는 많은 알고리즘에서 발생을 했지만,

만약 그 조합 중에 K개 만큼 특정 갯수가 변수로 주어진 경우에는, 불필요하게 모든 조합을 구하고, 그리고 거기서 k개의 요소를 가진 경우의 수를 모두 고르는 방식은 굉장히 비효율 적이다.

 

따라서 재귀 트백트래킹을 사용할 수 있지만, 이 보다 효율적인 메모리를 사용해서 재귀를 사용하지도 않고도, 순서 -> 비트로 사용하는 비트마스크 방식을 찾아 이를 적용하고 학습했다.

---

[음료수 맛 조합 문제]
여러 종류의 음료수가 주어집니다. 각 음료수는 여러 가지 맛을 가지고 있습니다. 4가지 맛이 있을 경우 음료수의 맛은 이진수(1101, 1000, etc) 로 주어집니다. 주어진 음료수들 중에서 k개의 음료수를 골라서 그 음료수들을 섞었을 때 만들 수 있는 새로운 맛의 개수가 최대 몇 개인지를 구하시오.
- 1101 과 1000 음료수를 섞는다면 1101 맛으로 나옴 - 음료수들을 섞는 방식은 각 음료수의 맛을 비트 OR 연산을 통해 결합하는 방식
- 음료수 중 `k`개를 선택해서 그들의 비트 OR 연산 결과로 만들어질 수 있는 새로운 맛의 최대 개수

재귀 백트래킹

import java.util.*;

public class DrinkFlavor {

    static Set<Integer> resultFlavors = new HashSet<>();
    
    public static int maxFlavors(List<Integer> drinks, int k) {
        // 음료수의 개수
        resultFlavors.clear();  // 결과 집합 초기화
        
        // 백트래킹을 통해 k개의 음료수 조합을 구하고 맛 계산
        findCombinations(drinks, k, 0, 0, 0);
        
        return resultFlavors.size(); // 가능한 맛의 개수 반환
    }

    // 음료수와 k개의 조합을 구하는 재귀하는 메서드
    public static void findCombinations(List<Integer> drinks, int k, int start, int current, int count) {
      
        if (count == k) {
            resultFlavors.add(current);
            return;
        }
        
        for (int i = start; i < drinks.size(); i++) {
            // 비트 OR 연산
            findCombinations(drinks, k, i + 1, current | drinks.get(i), count + 1);
        }
        
    }

		// 예시
    public static void main(String[] args) {
        List<Integer> drinks = Arrays.asList(101, 110, 111, 100, 101);
        int k = 2;
        
        int result = maxFlavors(drinks, k);
        System.out.println("최대 가능한 맛의 개수: " + result);
    }
}

• n개중 k 를 고르기 위해 재귀와 백트래킹 : 이미 선택된 경우 다시 돌아가기 를 통해서 최대 조합수를 구하는 알고리즘(가장 기본적인)
• 주어진 값들이 이미 이진법 형태를 띄고 있기 때문에 , findCombinations 내에서 비트 OR 연산 을 진행
  • 주어진 값이 이진법이 아니라면 그냥 내가 임의로 비교하는 어떤 Method를 활용할 수 있음

비트연산자

&	대응되는 비트가 모두 1이면 1을 반환함. (비트 AND 연산)
**	**
^	대응되는 비트가 서로 다르면 1을 반환함. (비트 XOR 연산)
~	비트를 1이면 0으로, 0이면 1로 반전 시킴. (비트 NOT 연산, 1의 보수)
<<	명시된 수만큼 비트들을 전부 왼쪽으로 이동시킴. (left shift 연산)
>>	부호를 유지하면서 지정한 수만큼 비트를 전부 오른쪽으로 이동시킴. (right shift 연산)
>>>	지정한 수만큼 비트를 전부 오른쪽으로 이동 시키며, 새로운 비트는 전부 0이 됨.

• 비트 OR 연산을 활용해서 구할 수 있음

비트연산자로 쓸 수 없는 n개 값 중 k개를 고르는 모든 조합 구하기

import java.util.*;

public class Combination {

    // 조합 리스트를 저장할 리스트
    static List<List<Integer>> result = new ArrayList<>();

    // 조합을 구하는 메서드
    public static void findCombinations(List<Integer> arr, int k, int start, List<Integer> current) {
        //  K개가 되면 결과에 추가
        if (current.size() == k) {
            result.add(new ArrayList<>(current)); 
            return;
        }

        // 재귀적으로 원소를 하나씩 선택
        for (int i = start; i < arr.size(); i++) {
            current.add(arr.get(i));  
            findCombinations(arr, k, i + 1, current); 
            // 여기서 백트래킹 사이즈 줄이고 그 사이에 다른거 넣기
            current.remove(current.size() - 1); 
        }
    }
		
		// 예시
    public static void main(String[] args) {
        List<Integer> arr = Arrays.asList(1, 2, 3, 4, 5);  
        int k = 3;
        
        findCombinations(arr, k, 0, new ArrayList<>());
        
        System.out.println("모든 조합: " + result);
        // 모든 조합: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

    }
}

비트 마스크 활용

• 전체적인 플로우는 k개를 골라야 할 때, 1 << n 를 사용을 해서 이진법으로 n 자리 11111… 를 만들기 → 1의 갯수가 k개인 것 찾기 → 해당 값의 1인 부분 (1 << i) 를 활용해서 그 i번째 값을 리스트에 넣기 → 모든 리스트를 최종 리스트에 담아서 반환

import java.util.*;

public class DrinkFlavor {

    // 주어진 음료수들로 만들 수 있는 최대 맛의 개수를 구하는 메서드
    public static int maxFlavors(List<Integer> drinks, int k) {
    
        Set<Integer> resultFlavors = new HashSet<>();
        int n = drinks.size();
        
        // 가능한 모든 조합을 비트마스크로 계산
        for (int mask = 1; mask < (1 << n); mask++) {
        
			      // 이진법으로 변환했을 때의, 1의 갯수 = 선택한 수 
            int count = Integer.bitCount(mask); 
            
            // k개 음료수가 선택된 경우
            if (count == k) {
            
                int flavor = 0;
                
                for (int i = 0; i < n; i++) {

                    if ((mask & (1 << i)) != 0) {
		                    // 비트 OR 연산 필요에 따라 다른 메서드
                        flavor |= drinks.get(i);
                    }
                }
                resultFlavors.add(flavor);
            }
        }
        
        return resultFlavors.size();
    }

    public static void main(String[] args) {
        List<Integer> drinks = Arrays.asList(101, 110, 111, 100, 101);
        int k = 2;
        
        int result = maxFlavors(drinks, k);
        System.out.println("최대 가능한 맛의 개수: " + result);
    }
}

• mask 라는 비트마스크를 사용해서, 재귀가 아닌 음료수 선택여부를 바로 확인할 수 있음
  • mask < (1 << n) : 왼쪽 쉬프트 연산자(left shift operator) 활용
    • 2^n을 계산 하는 연산 : 즉, n이 3이라면, 0001 부터 쉬프트패서 1000을 한 8이랑 똑같이 사용
    • n개의 음료수 종류에 대해서 선택한다/안한다 두개의 경우의 수를 보기 때문에 사용
    ex) 3개의 음료수에 대해서 101 일 경우 1, 3 두개만 고른다는 의미
• Integer.**bitCount**(mask)
  • mask는 int
  • mask → 이진법으로 바꾸고 → 그 중에 비트 즉 1의 갯수를 반환하는 메서드
• if ((mask & (1 << i)) != 0)
  • AND 연산자를 사용해서, i번째 해당하는 숫자 즉, 두번째는 0100 (1 << i) 과비교
  • 둘다 같은 자리에 1이 있어야 1을 반환하기 때문에 = 그 자리가 1인지 확인 하는 조건 = 해당 순서의 음료수(drinks)가 선택이 되었는지 확인
• flavor |= drinks.get(i);
  • 단순하게 a |= b는 a = a | b 라고 생각하면 편함 a에 덮어 씌우기
  • drinks.get(i) 자체가 이진법이기 때문에 계속 비트를 flavor에 덮어 씌우면서 위의 자리가 1인 값들을 골라서 비교하고 덮는 것을 반복

비트 연산자 쓸수 없는 n개 중 k개의 조합 구하기

import java.util.*;

public class CombinationWithBitmask {

    static List<List<Integer>> result = new ArrayList<>();

    public static void findCombinations(List<Integer> arr, int k) {
        int n = arr.size();

        // 가능한 모든 비트마스크를 확인
        for (int mask = 0; mask < (1 << n); mask++) {
        
            List<Integer> combination = new ArrayList<>();
						
						// 음료수와 똑같이 진행
            int count = Integer.bitCount(mask); 

            // 선택된 비트들에 대해 조합을 구함
            if (count == k) {
                for (int i = 0; i < n; i++) {
                    if ((mask & (1 << i)) != 0) {  // 해당 비트가 1이면 선택된 값
		                    // 여기서 바리에이션 가능
                        combination.add(arr.get(i));
                    }
                }
                result.add(combination);  // 결과에 추가
            }
        }
    }

    public static void main(String[] args) {
        List<Integer> arr = Arrays.asList(1, 2, 3, 4, 5);  
        int k = 3;

        // k개의 조합을 구함
        findCombinations(arr, k);

        System.out.println("모든 조합: " + result);
        // 모든 조합: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

    }
}

• 위와 똑같이 진행할 수 있고, Dynamic Programming 의 Memoization 같지만 전혀 다름
  • 오히려 DP에서 위를 활용할 수 있는 방법으로 접근을 해야함
  • DP는 최적의 값을 찾기 위한 목적이지만 비트마스크는 모든 경우의 수에 초점이 있음
  ex) DP로 부분집합 구해서 저장 → 비트 마스크로 부분집합을 추가로 작업 등
• DFS 와 같은 모든 경우를 확인하지만 개념은 다름
• 어쩔 수 없이 모든 조합을 다 확인해봐야만 하는 경우에 효율적으로 사용할 수 있음
  • 부분집합의 연산을 통해서 그 결과 값이 같은 경우도 고려해야하는 등, 모두 확인이 필요
• 위의 if 조건문을 없애면 모든 부분집합을 구할 수 있음
  • 가능한 모든 경우를 다 확인해야하는 문제에서 매우 유용

---

굉장히 단순하지만, 코딩테스트, 알고리즘에서는 전혀 알 수 없었던 방법을 찾아낸 것이기 때문에, 매우 빠른게 메모리를 효율적으로 사용하면서, 확인할 수 있을 것이다.

 

단, 이러한 알고리즘은 어쩔 수 없이 모든 조합을 다 확인해야하는 경우(중복 값을 고려 하거나, 순서를 상관해야하 하는 등) 에만 쓰일 수 있기 때문에 가급적이면 모든 문제에 적용하지는 않는 것으로 해야할 것이다.