Baekjoon Training / Algorithm-완전탐색 / #3040

 

 

---

#3040

 

 

 

 

 

#include<iostream>
#include <vector>
using namespace std;

int main() {
	vector<int> dwarfs(9); //난쟁이의 모자에 쓰인 정수
	int sum = 0;//sum of 9 dwarfs
	int out1=0, out2=0; //제외할 난쟁이 index 저장

	//입력 받기
	for (int i = 0;i < 9;i++) {
		cin >> dwarfs[i];
		sum += dwarfs[i];
	}

	//제외할 난쟁이 찾기 
	for (int i = 0;i < 8;i++) {
		for (int j = i + 1;j < 9;j++) {   //i,j가 dwarfs의 index를 동일하게 가르키도록
			if (sum - dwarfs[i] - dwarfs[j] == 100) {  //제외했을 때 100을 만드는 index 저장
				out1 = i;
				out2 = j;
			}
		}
	}

	//난쟁이 출력(out1,out2 제외)
	for (int i = 0;i < 9;i++) {
		if (i == out1 || i == out2) {
			continue;
		}
		else cout << dwarfs[i]<<endl;
	}


}

 

 

 

완전 탐색

 

: 완전탐색이란 모든 경우의 수를 시도하는 방법을 말한다.

  상대적으로 구현이 간단하나, 경우의 수에 실행 시간에 비례하기 때문에 입력 값의 범위가 작은 경우에만 유용하다.

 

 

 

 

완전 탐색 Algorithm

 

- 단순 Brute-Force

 : 단순히 반복문과 조건문으로 모든 경우를 만들어 답을 구하는 방법    //이 방법만 사용하는 문제는 거의 x

 

- Bitmask (비트마스크)

 : 나올 수 있는 모든 경우의 수가 "원소가 포함되거나" , "원소가 포함되지 않거나" 이 두 가지 선택으로 구성되는 경우 유용

   ex) 원소가 n개인 집합의 모든 부분 집합

          -> 각 원소가 포함되는지 포함되는지 포함되지 않는지를 0,1로 구분하여 저장할 수 있음

 

- 재귀함수

 : Bitmask와 마찬가지로 각 원소가 두 가지 선택지를 가질 때 유용

   포함이 되면 해당 원소를 넣어 함수를 호출하고 , 포함되지 않으면 그 상태에서 함수를 호출

   ex) 피보나치 수열

 

- 순열

 : 순열(permutation)은 서로 다른 N개를 일렬로 나열하는 방법(경우의 수)