[알고리즘] 완전 탐색

1.완전 탐색이란??

• 그냥 다 해보겠다!(무식하게 한다는 의미로 Brute Force라고도 한다네요,,ㅎㅎ)
• 그만큼 직관적인 알고리즘이며 정확한 결과를 얻을 수 있다.
  • 예) 4자리 자물쇠 풀 때 0000~9999까지 다 해보는 거(최대 만 번의 시도로 해결 가능)
• 따라서 효율적으로 동작할 수 있는지 문제를 잘 파악하고 써야 한다!(보통 N의 크기가 작을 때 이용하겠죠?! 보통 시간 복잡도가 지수승이거나 팩토리얼꼴로 나올 때 많이 이용한다고 하네요)
• 모든 경우의 수를 확인하고 있는지 확인하면 된다.

---

2. 완전 탐색 기법들

• 완전 탐색 자체가 알고리즘인 것은 아니기 때문에 완전 탐색 방법을 쓰기 위해 여러 알고리즘 기법들을 사용한다.

1. 단순 Brute-Force

• 특별한 기법 사용 없이 for, if문 등 반복문과 조건문으로 모든 경우를 만들어서 답을 구한다.
• 아주 기초적인 문제에서 주로 이용하거나 풀이의 일부에서 이용.

2. 비트 마스크(Bitmask)

• 2진수를 이용하는 컴퓨터의 연산을 이용
• 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우 유용
  • ex) '원소가 5개인 집합의 모든 부분 집합'을 구한다면, 각 원소가 포함되는지 포함되지 않는지를 0, 1로 구분하여 배열에 저장

---

2. 완전 탐색 기법들

• 완전 탐색 자체가 알고리즘인 것은 아니기 때문에 완전 탐색 방법을 쓰기 위해 여러 알고리즘 기법들을 사용한다.

1. 단순 Brute-Force

• 특별한 기법 사용 없이 for, if문 등 반복문과 조건문으로 모든 경우를 만들어서 답을 구한다.
• 아주 기초적인 문제에서 주로 이용하거나 풀이의 일부에서 이용.

2. 비트 마스크(Bitmask)

• 2진수를 이용하는 컴퓨터의 연산을 이용
• 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우 유용
  • ex) '원소가 5개인 집합의 모든 부분 집합'을 구한다면, 각 원소가 포함되는지 포함되지 않는지를 0, 1로 구분하여 배열에 저장

 

 

• 장점
  • 더 빠른 수행시간: 비트마스크 연산은  O(1)에 구현되는 것이 많기 때문에 적절히 사용하면 다른 자료구조를 사용하는 것보다 훨씬 빨리 동작한다. 비트마스크를 사용할 수 있다는 뜻은 원소의 수가 적다는 뜻이지만, 연산을 굉장히 많이 수행해야 할 경우에는 속도를 크게 향상할 수 있다.
  • 더 작은 메모리 사용량: 배열을 사용하면 여러 개의 정수로 표현하지만 비트마스크를 사용하면 단 하나의 정수로 표현할 수 있다.

💡 예를 들어 그래프에 정점 0, 1, 2, 3 있다고 해보자.
이 그래프를 탐색할 때 DFS로 순회하든, BFS로 순회하든 보통 visited 배열을 둬서 방문한 노드인지 아닌지 확인한다.
정점 0을 방문했다면 배열 [1, 0, 0, 0]로 표현할 수 있다.
이때 배열 대신 비트마스크를 사용할 수도 있다. 비트마스크를 사용하면 정점 0을 방문한 것을 0001로 표현할 수 있다.
2와 3을 추가적으로 방문하게 된다면 1101로 표현할 수 있을 것이다.

• 더 간결한 코드: 집합에 대한 연산을 처리할 때 비트마스크를 사용하면 굉장히 짧은 코드로 작성할 수 있다. 이때 배열 대신 비트마스크를 사용할 수도 있다. 비트마스크를 사용하면 정점 0을 방문한 것을 0001로 표현할 수 있다. 2와 3을 추가적으로 방문하게 된다면 1101로 표현할 수 있을 것이다.
• 비트 연산자 사용
  • 비트마스크는 비트 연산자를 사용해 조작
  • AND 연산 : 두 비트마스크의 각 비트를 비교하면서 해당 비트가 둘 다 켜져 있다면 결과의 비트를 켠다.
    • 1(01)과 3(11)을 AND 연산하면 1 & 3 = 1(01)
  • OR 연산 : 해당 비트 중 하나라도 켜져 있으면 해당 비트를 켠다.
    • 1 | 3 = 3(11)
  • XOR 연산 : 해당 비트 중 하나만 켜져 있으면 해당 비트를 켠다.
    • 1 ^ 3 = 2(10)
  • NOT 연산 : 각 비트를 반전시킨다.
    • !2(10) = 1(01)
  • Shift 연산 : 비트들을 왼쪽으로 밀거나 오른쪽으로 민다. 움직이고 나서 빈자리는 0으로 채워진다.
    • 3(11) << 1 = 6(110), 3(11) >> 1 = 1(01)

⚠️ 자바스크립에서 비트마스크를 사용할 때 주의해야할 점이 있는데, 바로 비트연산의 피연산자가 32비트 정수로 변환된다는 것이다. 따라서 원소 개수가 32개 보다 많다면 표현할 수 없다.

❣️비트마스크 예제 - 외판원 순회 문제

• 동적계획법(DP)에 비트마스크를 접목한 방식

💡 문제
1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

⇒ 모든 도시를 한번만 방문하면서 다시 시작점으로 돌아오는 최소 거리 비용을 구하는 문제

• 현재 도시가 current 이고, 방문한 도시들의 집합이 visited 일 때, 나머지 도시들을 순회한 최소 비용이라 하면, visited 를 배열로 관리하는 것이 어렵기에, 비트마스크를 활용
• 부분적으로 문제를 나누어 해결
  • 모든 도시를 방문한 경우. (모든 비트의 값이 1 인지 판단)
  • 이미 방문한 도시 여부. (i번째 비트의 값이 1 인지 판단)
  • 다음 도시를 방문했을 경우. (i번째 비트의 값을 1로 변경)

3. 재귀 함수

• 재귀 함수를 통해서 문제를 만족하는 경우들을 만들어가는 방식
• 비트마스크와 마찬가지로 각 원소가 두 가지 선택지를 가질 때 유용
  • 포함이 되면 해당 원소를 넣어 함수를 호출하고, 포함되지 않으면 그 상태에서 함수를 호출하는 등의 식
• 비트마스크에서의 집합 문제 예시를 들자면
  • 부분집합 = s( s ={} )
  • 각 원소에 대해서 해당 원소가 포함이 되면 s에 넣고 재귀 돌려주기
  • 포함되지 않으면 s를 그대로 재귀 함수에 넣어주는 방식

4. 순열 (Permutation)

• 완전 탐색에서 대표적인 유형
• 서로 다른 N개를 일렬로 나열하는 순열의 경우의 수는 N!이므로 완전 탐색을 이용하기 위해서는 N이 한자리 수 정도는 되어야한다.
• 순열에 원소 하나씩 채워가는 방식
• 시간복잡도 O(N!)

5. BFS/DFS

• 난이도 있는 문제로 완전 탐색 + BFS/DFS 문제가 많이 출제됨
• 예시) 길 찾기
  • 주어진 도로에 장애물을 설치하거나 목적지를 추가하는 등의 추가적인 작업이 필요한 경우에 이를 완전 탐색으로 해결하고 나서, BFS/DFS를 이용하는 방식

---

🕹️ 이번 주 문제

1. 프로그래머스 - 모의고사📝(https://school.programmers.co.kr/learn/courses/30/lessons/42840)

문제 설명

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...

2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...

3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예

answers return

[1,2,3,4,5]	[1]
[1,3,2,4,2]	[1,2,3]

입출력 예 설명

입출력 예 #1

• 수포자 1은 모든 문제를 맞혔습니다.
• 수포자 2는 모든 문제를 틀렸습니다.
• 수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

입출력 예 #2

• 모든 사람이 2문제씩을 맞췄습니다.
• 정답 풀이 1

let answers = [1, 3, 2, 4, 2, 1, 3, 2, 4, 2, 1, 3, 2, 4, 2, 1, 3, 2, 4, 2];

function solution(answers) {

    let answer = [];
    // supo : 수포자 찍는 방식
    let supo = [
        [1, 2, 3, 4, 5],
        [2, 1, 2, 3, 2, 4, 2, 5],
        [3, 3, 1, 1, 2, 2, 4, 4, 5, 5],
    ];

    let score = [];
    for (let i = 0; i < supo.length; i++) {
        // ex) answers = [1,3,2,4,2,1,3,2,4,2 ...] / supo[i] = [1,2,3,4,5,1,2,3,4,5 ...]
        // 각 인덱스의 값 비교해서 일치하는 값(정답)만을 가진 배열을 반환
        // 정답 수 : filter 된 배열의 길이
        score[i] = answers.filter(
            (element, index) => element === supo[i][index % supo[i].length],
        ).length;
    }

    let max = Math.max(...score);

    if (score[0] === max) answer.push(1);
    if (score[1] === max) answer.push(2);
    if (score[2] === max) answer.push(3);

    return answer;
}

console.log(solution(answers));

• 정답 풀이 2

function solution(answers) {
  const one = [1, 2, 3, 4, 5];
  const two = [2, 1, 2, 3, 2, 4, 2, 5];
  const three = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];
  const result = [0, 0, 0];
  const length = answers.length;
  for (let i = 0; i < length; i++) {
    if (one[i % 5] === answers[i]) result[0]++;
    if (two[i % 8] === answers[i]) result[1]++;
    if (three[i % 10] === answers[i]) result[2]++;
  }
  const answer = [];
  const maxValue = Math.max(...result);
  let index = 0;
  for (let i = 0; i < 3; i++) {
    if (maxValue === result[i]) {
      answer[index] = i + 1;
      index++;
    }
  }
  return result;
}

2. 최소 직사각형(https://school.programmers.co.kr/learn/courses/30/lessons/86491)

---

📚 참고자료

완전 탐색 관련 자료

https://hongjw1938.tistory.com/78

https://velog.io/@hhhminme/자바스크립트로-알아보는-완전탐색

https://velog.io/@hyehyes/알고리즘-완전탐색

모의고사 정답 참고

https://velog.io/@livelikemovies/모의고사

비트 마스크 관련 자료

https://woong-jae.com/algorithm/220511-bitmask

(외판원 예제 관련 자세한 설명 보고 싶으면 여기 보면 됩니다!) https://mygumi.tistory.com/361