11000번: 강의실 배정

그리디 "활동 선택 문제" 방식의 문제이다.

먼저 시간복잡도부터 살펴보면 1초의 제한시간에 input 의 길이가 20만이다. 따라서 제곱의 복잡도를 가지게 되면 터진다는 걸 알 수 있다.

이 점에 착안해 각 프로세스를 돌면서 log(n) 의 탐색 복잡도 로직으로 같이 이어서 들을 강의를 체킹하여 문제를 풀기로 하였다.

로직은 다음과 같다.

1. 각 프로세스를 "시간 순 → 짧게 끝나는 순" 으로 정렬한다.
2. 정렬한 프로세스를 하나씩 돌면서 나머지 프로세스 중 바로 시작할 수 있는 프로세스를 이분탐색을 통해 찾는다. (반복)

2. 찾은 프로세스들을 모두 checking 해주고 다시 2번으로 돌아간다.

이에 대한 코드는 다음과 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    int window_size = number.size() - k;

    int max_idx = -1;
    char max_val;
    for(int i=0 ; i< window_size ; i++) {
        max_val = '0';
        for(int j = max_idx + 1 ; j<i+k+1 ; j++) {
            if(max_val < number.at(j)) {
                max_val = number.at(j);
                max_idx = j;
            }
        }
        answer.push_back(max_val);
    }    
    return answer;
}

i번째의 수를 고를 때, k 개를 뽑아야 되니까 최소 i부터 k+1 범위에 있는 수중에서 큰 수만을 고르게 되면 결국 전체적으로 봤을 때 최대 값이 생기게 된다.

그리디한 방법 하에, answer 는 앞자리 수가 크면 클수록 가중치가 크기 때문에 앞에서부터 뽑힐 수 있는 모든 후보군 중에서 큰 값을 뽑게 되면 결국 제일 큰 값이 처리되기 때문에 답이 나온다.

쉽게 설명하자면 각 자리수의 수를 확인할 수 있는 윈도우를 설정하고, 해당 윈도우에서 가장 큰 값을 체킹하고 answer 에 넣어준다. 그렇게 되면 확실하게 k 개를 뺀 개수가 나오게 되고 가장 큰 값이 답으로 나오게 된다.

1028번: 다이아몬드 광산

dp 문제였다.

dp 배열에 문자열을 넣고 drop up 방식으로 단순하게 탐색하는 식으로 문제를 풀 수 있었다.

로직은 다음과 같다.

dp[1] 부터 차례대로 값을 비교하되 하나의 dp 마다 n개의 수를 넣기 전의 dp 값과 비교하여 해당 수를 추가한 뒤 값이 더 큰 값을 dp 값으로 갱신하는 로직.

말이 좀 어려울 수 있겠지만 dp[i - (수의값)] 에서 해당 수를 첨가하여 커지나 안커지나만 확인하면 되는 문제였다.

dp 라 푸는데 좀 오래 걸렸지만.. 다음에는 더 잘 기억하자

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <tuple>
#include <string>
#include <string.h>
#include <stack>
#include <set>
#include <map>


using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef tuple<int, int, string> tii;
string dp[200];

string convert(string a) {
	string res;
	if (a == "") return "";
	for (int i = 0; i < a.size(); i++) {
		if (a.at(i) == '0') continue;
		else {
			res = a.substr(i);
			break;
		}
	}
	if (res == "") return "0";
	else return res;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n, input, money;
	vector<int> v;
	int _min = 50;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> input;
		v.push_back(input);
		_min = min(_min, input);
	}
	cin >> money;

	for (int i = _min; i <= money; i++) {
		for (int j = 0; j < n; j++) {
			if (i - v[j] < 0) continue;
			for (int k = 0; k < dp[i - v[j]].size(); k++) {
				if (dp[i - v[j]][k] - '0' >= j) continue;
				string new_str = convert(dp[i - v[j]].substr(0, k) + to_string(j) + dp[i - v[j]].substr(k + 1));
				// cout << new_str << endl;
				if (dp[i].size() < new_str.size()) {
					dp[i] = new_str;
				}
				else if (dp[i].size() == new_str.size()) {
					dp[i] = max(dp[i], new_str);
				}
			}
			if (dp[i - v[j]].empty() && j == 0)
				continue;

			string t = dp[i - v[j]] + to_string(j);
			if (dp[i].length() < t.length())
				dp[i] = t;
			else if (dp[i].length() == t.length())
				dp[i] = max(dp[i], t);
		}
	}

	if (dp[money].empty()) cout << 0;
	else {
		cout << dp[money];
	}
	return 0;
}

타겟넘버

이 문제는 dfs 로 풀었을 때보다 bfs 로 풀었을 때 시간 복잡도가 적게 나오는 문제이다.

해당 그림을 봤을 때는 속도가 비슷해 보이지만

기본적으로 재귀 함수 틀의 DFS 는 BFS 보다 검색 속도가 느리기 때문에 동일 방법을 사용해도 될 때 시간 단축을 위해서는 BFS 를 사용하는 것이 좋다.

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <tuple>

using namespace std;
int _count = 0;
void dfs(vector<int> check, vector<int> num, int target, int current, int idx, int _size) {
    if (target == current && _size == num.size()) {
        _count += 1;
        return;
    }

    for (int i = idx; i < num.size(); i++) {
        if (check[i] == 0) {
            check[i] = 1;
            dfs(check, num, target, current + num[i], i+1, _size + 1);
            dfs(check, num, target, current - num[i], i+1, _size + 1);
            check[i] = 0;
        }
    }
}

void bfs(vector<int> check, vector<int> num, int target) {
    queue<tuple<int, int, int>> q; // idx, neg
    q.push(make_tuple(0, 1, num[0]*1));
    q.push(make_tuple(0, -1, num[0] * (-1)));
    check[0] = 1;

    int idx, neg;
    int sum = 0;


    while (!q.empty()) {
        
        idx = get<0>(q.front());
        neg = get<1>(q.front());
        sum = get<2>(q.front());
        q.pop();

        if (target == sum && idx == num.size() - 1) {
            _count += 1;
            continue;
        }
        else if (idx >= num.size() -1) {
            continue;
        }
        else {
            q.push(make_tuple(idx + 1, 1, sum + num[idx + 1] * 1));
            q.push(make_tuple(idx + 1, -1, sum + num[idx + 1] * (-1)));
            continue;
        }
    }
}
int solution(vector<int> numbers, int target) {
    int answer = 0;
    vector<int> check(numbers.size(), 0);
    // dfs(check, numbers, target, 0, 0, 0);
    bfs(check, numbers, target);
    cout << _count << endl;
    return _count;
}

재귀적 호출에 대한 개념을 먼저 잡고 넘어가자. 그 이유는 완전 탐색 시에, 해당 호출 방식을 자주 활용하기 때문이다.

재귀함수의 기본적인 이해

• 재귀함수란: 함수 내에서 자기 자신을 다시 호출하는 함수
• : 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수

• 재귀함수 호출방식

  void RecursiveFunction(void) {     
  	printf("Recursive function example1 \n");     
      RecursiveFunction(); 
  }

※ 기저 사례 (base case)

＃ 완전탐색(exhaustive search)

① 완전탐색이란?

▷ '무식하게 푼다(brute-force)'는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게

을 뜻한다.
▷ 완전 탐색은 컴퓨터의 빠른 계산 속도를 잘 이용하는 방법이다.
▷ (예제) n개의 원소 중 m개를 고르는 모든 조합을 출력하는 코드

// n : 전체 원수의 수 
// picked : 지금까지 고른 원소들의 번호 
// toPick : 더 고를 원소의 수
// 일 때, 앞으로 toPick개의 원소를 고르는 모든 방법을 출력한다. 

void pick(int n, vector<int>& picked, int toPick) {   
	// 기저 사례 : 더 고를 원소가 없을 때 고른 원소들을 출력한다.   
	if(toPick == 0) {
    	printPicked(picked); 
        return; 
    }   
    
    // 고를 수 있는 가장 작은 번호를 계산한다.   
    int smallest = picked.empty() ? 0 : picked.back() + 1;   

    // 이 단계에서 원소 하나를 고른다.   
    for(int next = smallest; next < n; ++next) {
        picked.push_back(next);     
        pick(n, picked, toPick - 1);     
        picked.pop_back();   
    } 
 }

② 완전 탐색 방법

• Brute Force for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법
• 비트마스크: 거두절미 하고 이야기 하면, 비트마스크는 알고리즘 이라기 보단 테크닉에 가깝습니다. 비트는 컴퓨터에서 다루는 최소 단위이며, 정수를 이진수로 표현, 비트 연산을 통해 문제를 해결해 나가는 기술을 비트마스크 라고 한다.
• 순열 순열의 시간 복잡도는 O(N!)으로 백트래킹과 비슷하다. check 배열 하나 두고 들어갔다가 나오고, 들어갔다가 나오는 방식을 구현한다. 예시는 밑에 추가해놨으니 참고해보자.
• 백트래킹(DFS): 백트래킹은 모든 조합의 수를 살펴보는 것인데 단 조건이 만족할 때 만이다. 모든 경우의 수를 모두 찾는 것보다 ‘경우에 따라' 훨씬 빠를 수 있다. 왜냐하면 조건이 만족하는 경우라는 조건이 있기 때문이다.한 컬럼에 Queen을 두었으면 오른쪽 컬럼에 가능한 자리에 Queen을 둔다. 또 다시 오른쪽 컬럼 중에서 가능한 자리에 Queen을 둔다. 이 과정을 반복한다. 만약에 N개의 Queen을 두었다면 카운트를 증가 시킨다. 이제부터가 중요한데, 성공하기 직전으로 상태를 되돌린다(back). 그리고 N번째 컬럼 중 다른 칸들을 시도한다. 만약에 없다면 N-1번째 컬럼에 있는 Queen을 들어서 다음으로 가능한 칸으로 옮긴다. 다시 N번째 컬럼에 Queen을 둘 수 있는 곳을 찾는다. N-1번째 컬럼의 모든 경우를 시도했다면, N-2번째로 되돌아가 다음으로 가능한 위치로 Queen을 옮긴다.
• 구체적인 예를 들어보자. 정렬되어 있지 않은 숫자 리스트 중에 특정 숫자를 찾는 것은 n을 리스트 길이라고 했을 때, O(n) 시간 복잡도를 갖는다. 이 경우에는 백트래킹은 의미가 없다. 한 개씩 모두 살펴볼 수 밖에 없기 때문이다. 반면 N-Queen 문제의 경우는 다르다.

#include<iostream> 
#include<vector>   
#define MAX 5 
using namespace std;   

char Arr[MAX]; 
bool Check[MAX]; 
vector<char> V;
void Permutation(int n, int r) 
{     
	if (n == r) {
    	for (int i = 0; i < V.size(); i++) {
        	cout << V[i] << " ";
        }
        cout << endl;
        return;
    }
    for (int i = 0; i < MAX; i++){
    	if (Check[i] == true) continue;
        Check[i] = true;
        V.push_back(Arr[i]); 
        Permutation(n+1 , r);
        V.pop_back();
        Check[i] = false;
    }
}

int main(void) {
	Arr[0] = 'a';
    Arr[1] = 'b';
    Arr[2] = 'c';
    Arr[3] = 'd';
    Arr[4] = 'e';
    Permutation(0,2);
}

#include<iostream> 
#include<vector>   
#define MAX 5 
using namespace std;
char Arr[MAX]; 
bool Check[MAX];
vector<char> V;  
void combination(int idx, int n, int r) {
  if (n == r){
    for (int i = 0; i < MAX; i++){
      if (Check[i] == true){
        cout << Arr[i] << " "; 		        
      } 	    
   	} 	    
  	cout << endl;
  	return;     
  }
  for (int i = idx; i < MAX; i++) {
  	if (Check[i] == true) continue;
    Check[i] = true;          
    combination(i,n+1,r);         
    Check[i] = false;     
  } 
}

int main(void) {
	Arr[0] = 'a';
   	Arr[1] = 'b'; 
    Arr[2] = 'c'; 
    Arr[3] = 'd'; 
    Arr[4] = 'e';
    combination(0,0,2);
}

위의 5가지 방법을 이용한 완전탐색 방법 모두를 익히는 것이 좋다.

모든 경우의 수를 탐색하는 방법은 문제를 접했을 때 가장 쉬운 방법이지만, 기초라고도 볼 수 있다. 그리고 문제에서 제한조건과 위의 몇 가지 SKILL을 추가하여 푼다면 문제 해결 시간을 크게 향상 시킬 수 있다. 참고로 완전탐색을 완벽하게 하기 위해서는 DFS, BFS 등등 코드를 두루두루 알고 있어야 한다.