오늘은 팀 프로젝트에서 디자인 때문에 하루종일 그림만 그린 관계로 ..
TIL 주제는 아침에 풀었던 알고리즘!
타겟 넘버
문제
주어진 numbers 배열의 원소에 적절하게 + 또는 - 부호를 붙여서 모두 합했을 때 그 합이 target이 되는 경우의 수를 구하는 문제
생각의 흐름
- 음! DFS로 풀면 되겠군!
- 왜?
- numbers의 최대 길이가 20이므로 완전 탐색 가능
- 마이너스 부호를 붙일 숫자를 고르면 될 것 같다!
고른다? -> 부분 집합 -> DFS
시도
- 아침에 머리가 잘 안 돌아가서 DFS로 풀어내지 못했다.
사고방식이 자꾸 이상하게 돌아가서 점점 조건이 추가되고 너무 더럽게 풀어버려서 결국 시간 초과가 나버렸다!!!
정말.. 처참한 코드였고... 이미 지워버려서 보여드릴 순 없지만 예.... 그래요...
해결
- 부분 집합하면 떠오르는 것이 DFS 말고 하나 더 있다!
바로 비트마스킹!
비트마스킹
-
아래와 같은 스위치가 3개 있다고 가정하자!
각 스위치는 ON 또는 OFF로 끄거나 킬 수 있다.
다시 말해서 스위치를 표현할 수 있는 방법이 2가지라는 것
-
표현 방법이 2가지라는 점에서 우리는 "이진법"을 떠올릴 수 있다.
0 또는 1로 표현되기 때문!
그렇다면 각 스위치의 상태를 아래와 같이 표현할 수 있다.
-
그렇다면 3개의 스위치로 만들 수 있는 경우의 수는 어떻게 될까?
다음과 같다!
-
이러한 특성을 이용해서 우리는 비트 연산으로 부분 집합을 쉽고 빠르게 구할 수 있다!
풀이
-
비트마스크 기법의 핵심 연산은 시프트 연산(<<, >>)이다.
- 1 << 2 의 결과는 2진수 100(2) 이 된다
-
위에서 보았던 스위치가 n개 있을 때, 우리는 0부터 1을 n만큼 왼쪽으로 시프트 연산을 한 숫자 - 1 까지 탐색하여 스위치 n개의 부분 집합을 모두 구할 수 있다.
- 스위치가 3개일 경우 1 << 3 == 1000(2) == 8
- 0부터 7 (8 - 1) 까지 순회 -> 이는 결국 위에서 보았던 스위치를 ON/OFF 하는 모든 경우의 수를 이진수로 나타내었을 때, 그 이진수를 십진수로 변환한 것과 같다.
000(2) == 0
001(2) == 1
010(2) == 2
...
111(2) == 7
-
이를 문제에 적용해본다면 스위치가 켜진 경우에 + 부호를, 꺼진 경우에 - 부호를 붙여주면 된다!!!
-
풀이 코드
public class Solution {
public int solution(int[] numbers, int target) {
int answer = 0;
for (int i = 0; i < (1 << numbers.Length); i++)
{
int sum = 0;
for (int j = 0; j < numbers.Length; j++)
{
if ((i & (1 << j)) != 0) sum += numbers[j];
else sum -= numbers[j];
}
if (sum == target) answer++;
}
return answer;
}
}- for (int i = 0; i < (1 << numbers.Length); i++)
- 첫 번째 반복문에서는 스위치가 n개일 때, n개 스위치에 대한 모든 경우의 수를 순회한다.
- for (int j = 0; j < numbers.Length; j++)
- 두 번째 반복문에서는 numbers 배열을 순회하면서 현재 스위치 상태를 기준으로 어떤 스위치가 켜져있는지 index 값으로 확인한다.
- 예를 들어, numbers 배열의 길이가 5이고 i == 8일 때 현재 스위치의 상태는 01000(2) 이다.
- 즉, index 1번째 원소에게 + 부호를 붙여주면 된다.
- i & (1 << j)
- j번째 원소가 현재 켜진 스위치인지 아닌지 확인한다.
켜져있다면 sum에 j번째 원소를 더해주고, 아니라면 빼준다. - 여기서 하나 의문점이 들 수 있는데, 위에서 예시로 들었던 numbers 배열의 길이가 5이고 i == 8 일 때로 돌아가보자.
우리는 index가 1인 원소에게 + 부호를 붙여주기로 했다.
그런데 위의 수식으로 계산해보면 8 & (1 << j) == 1이 되는 j의 값은 3일 것이다.
우리는 index 1인 원소를 찾아야 하는데, j의 값은 3이 나오게 된다. - 1을 왼쪽 시프트 연산으로 밀기 때문에 그렇다!
우리 기준으로는 배열의 맨 뒤부터 1이 밀려오기 때문에 사실 (numbers.Length - 1 - j)의 값이 우리가 원하는 index의 값이다.
그런데 j로 계산을 한 이유는..
앞에서부터 부분 집합을 구하든 뒤에서부터 구하든 어차피 경우의 수는 똑같기 때문
어차피 똑같다면 더 짧게 쓰자 하핫
- j번째 원소가 현재 켜진 스위치인지 아닌지 확인한다.
그럼 디자인 노동하러 20000
끗!
