pushback

sort함수를 이용하여 가볍게 풀이하였습니다. 

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

int num[1000];

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> num[i];
	sort(num, num + n);

	for (int i = 0; i < n; i++) cout << num[i] << '\n';
	return 0;
}

sort함수는 세 개의 인자를 받습니다. sort(배열의 시작, 배열의 끝, 정렬 방법) 이라고 생각하시면 편합니다. 세번째 인자를 생략하면 자동 오름차순으로 정렬됩니다.

좀 더 정확히 설명해봅시다.

int arr[5] = { 4, 3, 2, 1, 0 };

int형 원소들을 갖고 있는 arr배열을 오름차순으로 정렬하고싶다면,

sort(arr, arr + 5); 

이 코드 한줄로 끝나게 됩니다.

한가지 의문이 듭니다. 왜 배열의 끝이 arr + 4가 아니라 arr + 5일까 ?

밑에 그림을 보겠습니다.

간단하쥬 ? 이 그림이 이해가 안가신다면 포인터 개념을 공부해주시면 됩니다.

이번엔 vector를 이용해봅시다.

vector<int> vec = { 4, 3, 2, 1, 0};

위에 배열과 같은 원소를 갖는 vector를 만들었습니다. 

마찬가지로 오름차순으로 정렬하고 싶습니다. 

sort(vec, vec + 5);

하면 에러입니다. 

vector는 STL에서 제공하는 자료구조이기 때문에 iterator(반복자)를 인자로 넣어주어야 합니다.

sort(vec.begin(), vec.end()); 

이 옳은 방법입니다.

혹시 vector에서 모든 원소 정렬이 아닌 원하는 부분만 정렬하고 싶다면,

sort(vec.begin() + a, vec.begin() + b);

와 같은 방식으로 a부터 b - 1번째 원소들만 정렬할 수 있습니다.

이번엔 세번째 인자에 대해 알아봅시다.

sort함수가 수행될 때, 어떤 기준으로 정렬이 될 지 정해주는 부분입니다.정의하는 방법은 세 가지 정도 있지만, 가볍게 함수로 정의하는 방법만 보겠습니다.

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

bool compare(int& a, int& b){
	// (a보다 b가 더 크면 true, 아니면 false) == 오름차순
	return a < b;
}

int arr[5] = {4, 3, 2, 1, 0};
vector<int> vec = {4, 3, 2, 1, 0};

int main(){
	
	sort(arr, arr + 5, compare);
	sort(vec.begin(), vec.end(), compare);
	
	return 0;
}

보시는 것처럼 간단합니다. 같은 자료형 두 개를 인자로 받고, bool값을 리턴해주는 함수를 작성해주면 비교함수 완성. 

return a > b; 를 하면 당연하게도 내림차순으로 정렬됩니다.

살짝 tip 아닌 tip을 드리자면 STL에서 제공하는 functional 라이브러리 안에 less<자료형>()과 greater<자료형>() 함수가 있습니다. 매번 compare함수를 작성하는게 귀찮으신 분들은 이 두 함수를 이용하셔도 되지만, 단순한 내림차순 오름차순 정렬임을 유의해주셔야합니다. 

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

int arr[5] = {4, 3, 2, 1, 0};

int main(){
	
	sort(arr, arr + 5, less<int>()); // 오름차순
	sort(arr, arr + 5, greater<int>()); // 내림차순
	
	return 0;
}

자신이 개발자를 준비중이라면,

$O(n^2)$ : 버블 정렬, 삽입 정렬, 선택 정렬

$O(nlogn)$ : 힙 정렬(Heap Sort), 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort) 

정도는 스스로 구현할 줄 알아야 한다고 개인적으로 생각합니다. 

하지만, 알고리즘 문제를 해결할 때마다 구현하는 것은 굉장한 시간 낭비일 것입니다. 따라서 저는 algorithm 라이브러리에서 제공하는 sort함수를 사용하여 12단계의 문제들을 해결할 예정입니다.

제가 올리는 글에선 sort함수 사용방법을 배우시고, 만약 위에 언급된 6개 정렬 중 모르는 것이 있다면 꼭 공부해보시는 것을 추천드립니다.

백준에서 제공하는 일반적인 알고리즘 문제에선 sort 함수로도 충분히 통과가 가능하지만, 삼성 B형 테스트와 같이 메모리와 시간 최적화가 필요한 문제들은 스스로 정렬 알고리즘을 구현할 줄 알아야 하기 때문입니다. 시간이 허락한다면, 저도 제가 구현한 코드를 사용하여 문제들을 해결해보도록 하겠습니다. 감사합니다.

두 가지 방법이 있다.

1. 666부터 1씩 증가시키면서 666이 포함되어있는 수인지 확인하는 방법.

2. 666에 앞뒤로 0~9까지 숫자를 붙여가면서 찾는 방법. (= 내가 생각하는 정해)

첫번째 방법은 666이 포함된 수를 오름차순으로 찾을 수 있기 때문에 편하지만, 666이 포함되었는지 확인하는 방법이 조금은 난감하다.

여기서 다시 두 가지로 나눌 수 있다.

1-1. to_string를 이용하여 숫자를 string으로 변환한 다음, string.find를 이용하여 "666"이란 문자열을 포함하는지 확인하는 방법.

1-2. 나머지 연산으로 1의 자리에서부터 3자리씩 보면서 666인지 확인하는 방법이다.

1-1)코드

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int n;
	cin >> n;

	int cnt = 0, ans = 0;
	for (int i = 666; cnt < n; i++) {
		string str = to_string(i);
		if(str.find("666", 0, 3) != string::npos){
			cnt++;
			ans = i;
		}	
	}

	cout << ans;

	return 0;
}

코드 자체는 간결하지만 string을 사용하기 때문에 cost가 꽤나 크다.

1-2 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX = 10e+8;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;

	int cnt = 0, ans = 0;
	for (int i = 666; cnt < n; i++) {
		
		int num = i;
        // 뒤에서부터 3자리씩 보면서 666을 포함하는지 확인
		while (num) {
			int left = num % 1000;
			if (left == 666) {
				cnt++;
				ans = i;
				break;
			}
			num /= 10;
		}
	}

	cout << ans;

	return 0;
}

연산을 통해 666이 있는지 확인하기 때문에 1-1방법에 비해 비약적으로 속도를 줄일 수 있다.

두번째 방법은 쉽지만 어렵다. 정확히 말하면 개념은 쉽지만 구현이 살짝 어지럽다. WHY ?

666 앞뒤에 0~9까지 숫자를 붙여보자.

앞 0666, 1666, 2666, 3666, 4666, 5666, 6666, 7666, 8666, 9666

뒤 6660, 6661, 6662, 6663, 6664, 6665, 6666, 6667, 6668, 6669

두 개의 문제점을 확인할 수 있다. 

하나) 6666이라는 중복 수가 생긴다. - 이건 의심의 여지가 없는 문제점이다.

둘) int형 변수에 0666은 666으로 저장된다. - 이건 왜 ? 0666을 무시하는 순간 우리는 10666을 평생 만들 수 없다. 

중복 수는 해결하기 쉽지만 두번째 문제는 ... 이게 뭘까싶다. 해결하기위해 우리가 0666을 무시했을 때 만들지 못하는 숫자들을 관찰해보자.

5자리 수 : 10666, 20666, 30666, ... 90666

6자리 수 : 100666, 101666, 102666, ... , 200666, ... 

이런 숫자들이다. (사실 110666도 못만드는 숫자지만, 10666을 만들 수 있다면  110666은 자동적으로 추가되는 숫자라 제외했다.)

자세히 보자.

5자리 수 : 10666, 20666, 30666, ... 90666

6자리 수 : 100666, 101666, 102666, ... , 200666, ... 

관찰 결과 : $n$자리 수를 만들려고 할 때, 이미 만들어진 모든 수에 $1\times {10}^{n-1},...,9\times {10}^{n-1}$를 더해주자.

따라서 666을 포함한 n자리의 수를 만드는 방법은,

1. 이미 만들어진 모든 수에 $1\times {10}^{n-1},...,9\times {10}^{n-1}$를 더한 수

2. 666을 포함한 n - 1자리의 수 앞에 0~9을 추가한 수

3. 666을 포함한 n - 1자리의 수 뒤에 1~9을 추가한 수

4. 중복 수 제거이다.

살짝 최적화를 해본다면, 2번에서 만들어지는 모든 수는 이미 1번에서 만들어져 있기 때문에 1, 3, 4만 진행하면 된다.

최적화를  조금 더 해본다면, set를 쓴다면 중복 수는 자동적으로 무시되기 때문에 1, 3만 진행하면 된다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX = 10e+8;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

// 10,000번째 수까지만 보기 때문에 7자리의 수들까지만 봐도 충분하다.
set<int> num[8]; // num[i]에는 666을 포함한 i자리 수들을 저장하고 있다.

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;
	int cnt = 1;
	num[3].insert(666);
	for (int i = 4; i < 8 && cnt < n; ++i) {
		int pos = (int)pow(10, i - 1);
		// 앞에 추가
		for(int from = 3; from < i; ++from) 
			for (int prev : num[from])
				for (int j = 1; j < 10; ++j) 
					num[i].insert(j * pos + prev);
		
		// 뒤에 추가
		for (int prev : num[i - 1]) for (int j = 0; j < 10; ++j) num[i].insert(prev * 10 + j);
		
		cnt += num[i].size();
	}

	for (int i = 3; i < 8; ++i) {
		if (n > num[i].size()) n -= num[i].size();
		else {
			// set는 index접근이 불가능하기 때문에 iterator를 사용
			set<int>::iterator it = num[i].begin();
			for (int i = 1; i < n; ++i) ++it;

			cout << *it;
			break;
		}
	}

	return 0;
}

set때문에 메모리는 두 배정도 더 사용하지만, 매우 만족스러운 속도가 나왔다.

$N,M$이 최대 50이기 때문에 브루트 포스로 충분히 해결 가능한 문제로 보인다.

맨 왼쪽 위칸이 검은색인 경우와 흰색인 경우의 (8x8)체스판을 미리 준비해놓고, NxM체스판 위를 돌아다니며 미리 준비해둔 8x8 체스판과 몇 칸이 다른지 확인해보자. 가장 적은 칸이 다른 경우가 답이 된다.

이 아이디어가 가능한지 시간 복잡도를 생각해보자.

최악의 경우로 (50x50)크기의 체스판에서 (42x42)개의 (8x8)체스판을 뽑아낼 수 있고, 체스판을 한번 뽑아낼 때마다 2x64번의 비교가 필요하다. 따라서 최대 42x42x2x64(=225,792)번의 연산만 하면 되기 때문에 브루트 포스가 가능하다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX = 10e+8;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

char chess[50][50];
char b[50][50]; // 맨 왼쪽 위 칸이 black인 경우
char w[50][50]; // 맨 왼쪽 위 칸이 white인 경우
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    string s;

    int ans = 987654321;

    for (int i = 0; i < N; i++) {
        cin >> s;
        for (int j = 0; j < M; j++) {
            chess[i][j] = s[j];
            // 미리 b배열과 w배열 채워놓기
            if ((i + j) % 2 == 0) {
                b[i][j] = 'B';
                w[i][j] = 'W';
            }
            else {
                b[i][j] = 'W';
                w[i][j] = 'B';
            }
        }
    }

    // 8x8로 잘라서 비교 
    for (int i = 0; i < N - 7; i++) for (int j = 0; j < M - 7; j++) {
        int tmpB = 0, tmpW = 0;

        for (int x = i; x < i + 8; x++) for (int y = j; y < j + 8; y++) {
            if (chess[x][y] != b[x][y]) tmpB++;
            if (chess[x][y] != w[x][y]) tmpW++;
        }

        ans = min({ ans, tmpB, tmpW }); // min이 자주 수행되는 경우엔 2개씩 비교하는게 더 좋다.
        
    }

    cout << ans << '\n';

    return 0;
}

$N$의 범위가 최대 50이기 때문에, 겁 먹지 말고 브루트 포스로 $O(n^2)$에 해결하자.

문제에서 원하는 대로 구현만 해주면 쉽게 해결 가능하다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX = 10e+8;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int cnt[51] = { 0, }; // 나보다 덩치가 큰 사람의 명수를 담는 배열
pair<int, int> spec[51]; // 나의 키, 몸무게 저장

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	int n;
	cin >> n;
	
	for (int i = 0; i < n; i++) cin >> spec[i].first >> spec[i].second;
	
	for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) {
    	 // i가 j보다 덩치가 큰 경우
		if (spec[i].first > spec[j].first && spec[i].second > spec[j].second) cnt[j]++;
         // i보다 j가 덩치가 큰 경우
		else if (spec[i].first < spec[j].first && spec[i].second < spec[j].second) cnt[i]++;
	}

	for (int i = 0; i < n; i++) cout << cnt[i] + 1 << ' ';

	return 0;
}

최악의 경우로 1부터 1,000,000까지 돌면서 분해합을 구해야 한다고 가정해보자.

어떤 수 x의 분해합을 구하기 위하기 위해선 x의 자리 수만큼의 시간이 필요하다. 

따라서 $(1\times 10)+(2\times 100)+(3\times 1000)+...+(5\times 100000)+(6\times 1)=1,543,210$번의 연산이 필요하고, 이는 문제에서 주어진 2초 안의 충분히 해결할 수 있는 연산량이다. 때문에 브루트 포스로 해결하자 !

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX = 10e+8;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, ans = 0;
	cin >> n;
	// 생성자는 n보다 작을 수 밖에 없다.
	for (int i = 1; i <= n; i++) {
		int cur = i, sum = i;
		// 분해합 구하기
		while (cur) {
			sum += cur % 10;
			cur /= 10;
		}
		// 가장 작은 생성자를 구해야하기 때문에 찾자마자 for문 종료
		if (sum == n) {
			ans = i;
			break;
		}
	}

	cout << ans;

	return 0;
}

카드가 총 백장이므로 완전 탐색을 진행하여도  ${}_{100}{C}_3$개의 경우의 수 밖에 안나온다. 따라서 완탐으로 진행하자.완전 탐색하는 방법은 재귀 함수를 이용하면 되는데, 3개만 뽑으면 되기 때문에 3중 for문도 가능할 것으로 보인다.

1. 재귀 함수

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX = 1e5;
const int MOD = 1e9 + 3;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int n, m;
int cnt = 0, ans = 0;
int card[101];


void sum(int cur, int prev_sum, int cnt) {
	
	if (cnt == 3) {
		if (prev_sum <= m) ans = max(ans, prev_sum);

		return;
	}

	for (int i = cur; i < n; ++i) sum(i + 1, prev_sum + card[i], cnt + 1);

	return;
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n >> m;
	
	for (int i = 0; i < n; i++) cin >> card[i];

	sum(0, 0, 0);
	
    cout << ans;
}

2. 3중 for문

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX = 1e5;
const int MOD = 1e9 + 3;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int card[101];

int solve(int n, int m) {
	int ans = 0;

	for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) for (int k = j + 1; k < n; ++k) {
		if (card[i] + card[j] + card[k] == m) return m;
		else if(card[i] + card[j] + card[k] < m) ans = max(ans, card[i] + card[j] + card[k]);
	}

	return ans;
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; ++i)cin >> card[i];

	cout << solve(n, m);
	return 0;
}