완전탐색

완전탐색의 정의

• 모든 경우의 수를 전부 찾아서 답을 찾는 알고리즘을 말한다.

• Brute Force 알고리즘 이라고도 불린다.

• 모든 경우를 전부 찾기때문에 정확한 답을 찾을 수 있다.

• 모든 경우를 전부 찾기때문에 시간초과에 걸릴 가능성이 높다 -> 이를 해결하기 위해 백트래킹 사용

---

완전탐색의 종류

① for문을 통한 완전탐색

 

합이 10인 순서쌍을 구하는 문제

 

 

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void)
{
    int sum = 10;
    int cnt = 0;
    
    for(int i = 0; i <= 10; i++)
    {
        for(int j = 0; j <= 10; j++)
        {
            if(i + j == sum)
            {
                cnt++;
            }
        }
    }
    
    cout << cnt;
    
    return 0;
}
 

② 재귀함수를 통한 완전탐색 -> 순열, 조합

 

조합 문제 - 일곱 난쟁이 https://www.acmicpc.net/problem/2309

#include <stdio.h>
 
int height[7];
int input[9];
int flag;
 
void combination(int sum, int cnt, int idx)
{        
    if(cnt == 7)
    {        
        if(sum == 100)
        {
            flag = 1;
            return;
        }
        else
        {
            return;
        }
    }
    
    for(int i = idx; i < 9; i++)
    {
        height[cnt] = input[i];
        combination(sum + height[cnt], cnt+1, i+1);
        if(flag == 1)
        {
            return;
        }
    }
}
 
int main(void)
{
//    freopen("B2309_input.txt", "r", stdin);
    
    for(int i = 0; i < 9; i++)
    {
        scanf("%d", &input[i]);
    }
    
    combination(0, 0, 0);
    
    // 버블 정렬 -> 오름차순 출력을 위해 
    for(int i = 6; i > 0; i--)
    {
        for(int j = 0; j < i; j++)
        {
            if(height[j] > height[j+1])
            {
                int temp = height[j];
                height[j] = height[j+1];
                height[j+1] = temp;
            }
        }
    }
    
    for(int i = 0; i < 7; i++)
    {
        printf("%d\n", height[i]);
    }
    
    return 0;
}

③ 라이브러리를 통한 완전탐색 -> 순열, 조합

   C++ :  https://twpower.github.io/90-combination-by-using-next_permutation

 

   PYTHON : https://ghwlchlaks.github.io/permutation-combination-python

---

프로그래머스 완전탐색 문제

숫자 야구 (조합 응용)

#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
int num[3];
int result[3];
int visited[10];
int answer;
 
vector<vector<int>> copy_baseball;
 
int strike()
{
    int strikeCnt = 0;
    
    for(int i = 0; i < 3; i++)
    {            
        if(result[i] == num[i])
        { 
            strikeCnt++;
        }
    }
    
    return strikeCnt;
}
 
int ball()
{
    int ballCnt = 0;
    
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            if(i == j)
            {
                continue;
            }
 
            if(result[i] == num[j])
            {
                ballCnt++;
            }
        }
    }
    
    return ballCnt;
}
 
void DFS(int cnt)
{
    if(cnt == 3)
    {   
        for(int i = 0; i < copy_baseball.size(); i++)
        {
            // 자리수별로 num에 저장
            int temp = copy_baseball[i][0];
            for(int j = 2; j >= 0; j--)
            {
                num[j] = temp % 10;
                temp /= 10;
            }
            
            // 스트라이크
            if(strike() != copy_baseball[i][1])
            {
                return;
            }
            
            // 볼
            if(ball() != copy_baseball[i][2])
            {
                return;
            }    
        }
        
        answer++;   
        
        return;
    }
    
    for(int i = 1; i <= 9; i++)    
    {
        if(visited[i] == 0)
        {
            visited[i] = 1;
            result[cnt] = i;
            DFS(cnt+1);   
            visited[i] = 0;
        }
    }
}
 
int solution(vector<vector<int>> baseball) 
{
    copy_baseball = baseball;
    
    DFS(0);
    
    return answer;
}

---

추천문제

https://www.acmicpc.net/problem/2529 (순열)

 

https://www.acmicpc.net/problem/10819 (순열) 

 

https://www.acmicpc.net/problem/2309 (조합) 

 

https://www.acmicpc.net/problem/15686 (조합) -> 삼성 코테 기출