완전탐색의 정의
-
모든 경우의 수를 전부 찾아서 답을 찾는 알고리즘을 말한다.
-
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;
}
|
cs |
② 재귀함수를 통한 완전탐색 -> 순열, 조합
더보기
조합 문제 - 일곱 난쟁이 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 |
③ 라이브러리를 통한 완전탐색 -> 순열, 조합
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;
}
|
cs |
추천문제
https://www.acmicpc.net/problem/2529 (순열)
https://www.acmicpc.net/problem/10819 (순열)
https://www.acmicpc.net/problem/2309 (조합)
https://www.acmicpc.net/problem/15686 (조합) -> 삼성 코테 기출
'Algorithm' 카테고리의 다른 글
| 지역변수로 크기가 큰 배열 선언 시 문제점 (0) | 2019.09.27 |
|---|---|
| Prim vs Dijkstra (프림 다익스트라 비교) (4) | 2019.09.23 |
| Dijkstra vs Floyd-Warshall (다익스트라 플로이드 비교) (0) | 2019.09.23 |
