[코딩 테스트 준비 - 기초] 3. 브루트 포스 - 그냥 다 해보기

1. 브루트 포스

• 브루트 포스는 모든 경우의 수를 다 해보는 것이다.
• 가능한 경우의 수의 시간복잡도를 계산해보고 제한 시간 내에 풀 수 있는 지 확인한다.
• 대부분 O(경우의 수 * 방법 1개를 시도해보는데 걸리는 시간)이 걸린다.

 

참고) 제한 시간이 1초인 경우

• N <= 10 -> N!
• N <= 20 -> 2^N

 

2. 그냥 다 해보기

for문 사용

 

[백준 3085 사탕 게임]

• string vector로 입력을 받는다. (처음에는 char로 받을 생각만 했는데..!)
• algorithm 헤더의 swap을 사용한다.

	vector<string> box(n);
	for(int i=0; i<n; i++) cin>>box[i];

 

[백준 1476 날짜 계산]

• 모든 가능한 경우의 수는 15 x 28 X 19 = 7980 로 다 해보면 답을 찾을 수 있음을 알 수 있다.

 

[백준 1107 리모컨]

• 숫자 버튼을 눌러 이동할 ch를 정한다. (max가 1,000,000)
• ch로 이동이 가능한지 확인한다. (고장난 버튼 있는지 확인)
• 고장난 버튼이 없다면 채널의 자릿수(len)만큼 숫자를 누르고, n까지 누를 +/- 버튼 횟수(press)를 계산한다. 
• cf. 이동할 채널을 string으로 변환해 계산했는데 제공된 코드보다 시간이 더 오래 걸리는 느낌이다.. string 계산이 오래 걸리는 듯..?

#include <iostream>
using namespace std;

bool isBroken[10];

int main(){
	int n, m;
	cin>>n>>m;

	int x;
	for(int i=0; i<m; i++){
		cin>>x;
		isBroken[x] = true;
	}

	// + or - 버튼만으로 이동하는 경우를 정답의 초기값으로 설정
	int ans = n - 100;
	if(ans < 0) ans = -ans;

	for(int i=0; i<=1000000; i++){
		string ch = to_string(i);
		int len = ch.length();

		bool isPossible = true;
		for(int j=0; j<len; j++){
			int idx = ch[j] - '0'; //char to int
			if(isBroken[idx]){
				isPossible = false;
				break;
			}
		}

		if(isPossible){
			int press = stoi(ch) - n; //+ or - 누르는 횟수
			if(press < 0) press = -press;

			int tmp = len + press;
			ans = min(ans, tmp);
		}
	}

	cout<<ans<<'\n';

	return 0;
}

 

[백준 14500 테트로미노]

• 모든 가능한 모양은 19개임을 우선 파악해야 한다.
• 각 모양에 대해 기준을 설정하고 4개의 칸의 합을 구하는 과정에서 약간의 노가다(?)가 필요하다.
• 전역으로 미리 block을 설정해 두는 것도 방법이다!

 

건너 뛰며 해보기

가능한 모든 경우의 수를 탐색하지 않고, 기준을 정하고 필요한 부분만 탐색하는 것이다.

 

[백준 6064 카잉달력]

• x와 y를 1씩 감소시키면, 각각 M과 N으로 나눈 나머지임을 알 수 있다.
• x를 기준으로 잡고, 이에 대응하는 가능한 모든 y를 탐색한다.
• 답을 출력할 때는 1을 더해야 한다. (처음에 x와 y에서 -1을 한 뒤 시작했으니까)

 

[백준 1748 수 이어 쓰기1]

• 자리수별로 나눠 계산한다.
• if로 분기해서 각각 계산했는데, 주어진 코드가 더 간결하고 자리수가 더 커질 경우 유용하다. (확인하기)

 

[백준 9095 1,2,3 더하기]

• 10중 for문을 돌려 구할 수 있다.
• 하지만 이렇게 많은 for문을 사용하는 일은 거의 없고 대부분 재귀를 이용한다.
• (지금까지 경험상 3중 for문을 넘어가는 일은 거의 없는듯..?하다)
• cf) dp(bottom-up) 코드

  #include <iostream>
  using namespace std;
  
  int f[11];
  
  void dp(){
  	f[1] = 1;
  	f[2] = 2;
  	f[3] = 4;
  	for(int i=4; i<11; i++)
  		f[i] = f[i-1] + f[i-2] + f[i-3];
  }
  
  int main(){
  	int t, n;
  	cin>>t;
  
  	dp();
  
  	for(int i=0; i<t; i++){
  		cin>>n;
  		cout<<f[n]<<'\n';
  	}
  
  	return 0;
  }​