백준 알고리즘 기초 - 브루트 포스 (예제 + N과 M)

엄청 머리 아팠다..

재귀 쪽에 감이 없는 건지, 잘 이해가 안 돼서 여러번 풀어봤다..

정리하다보면 이해도가 더 높아지리라 기대하면서

정리 시작!

-

* 건너 뛰며 해보기 : 아무리 브루트 포스라도 경우의 수가 너무 많으면 다 해볼 수는 없다. 이때 규칙을 찾아서 건너 뛰면서 경우를 확인해주는 방법이다. 바로 예제 문제를 풀어보자.

 

* 카잉 달력 (mid) : 전에 풀었던 달력 문제와 유사한데, 이번엔 제시된 날짜가 몇번째 해인지 구하는 문제다.

6064번: 카잉 달력

 - 최소공배수를 이용해서 풀면 되겠다는 감을 잡고 디테일을 잡아갔다.

#include <iostream>
#include <algorithm>

using namespace std;

long long gcd(int a, int b) {
	while (b != 0) {
		int r = a%b;
		a = b; b = r;
	}
	return a;
}

int main() {

	int t;
	cin >> t;

	while (t--) {
		int m, n, x, y;
		cin >> m >> n >> x >> y;

		long long lim = m*n / gcd(m, n);

		int k = x;
		while (k <= lim) {
			int tmp = k%n;
			if (!tmp) tmp = n;
			if (tmp == y) break;
			k += m;
		}

		if (k > lim) k = -1;

		cout << k << '\n';
	}

	return 0;
}

 - 최소공배수는 달력의 마지막 값이 된다. 따라서 조건에서 가능한 최댓값으로 지정해 활용한다.

 - m, n 중 하나를 기준으로 삼고, 나머지 값이 동일하게 나오도록 반복해서 더해준다. 나는 m을 기준으로 잡고 x부터 시작해 m을 더해가며 값을 조사했다. 그 값을 k로 뒀다.

 - k 값을 n으로 나눈 나머지값이 y가 되는지 확인한다. 이때 나머지값이 0이 나오면 예외 처리를 해준다. 처리된 값이 y가 된다면 반복문을 나온다. 그 값이 구하고자 하는 답이다.  반복문을 다 돌았는데도 만족하는 조건이 없다면 k에 -1을 넣어준다.

-최소공배수 활용 없이 구하는 백준님 코드도 가져와봤다.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {

	int t;
	cin >> t;

	while (t--) {
		int m, n, x, y;
		cin >> m >> n >> x >> y;

		bool okay = false;
		x -= 1; y -= 1;
		for (int k = x; k < m*n; k += m) {
			if (k%m == x && k%n == y) {
				cout << k + 1 << '\n';
				okay = true;
				break;
			}
		}

		if (!okay) cout << -1 << '\n';
	}

	return 0;
}

 - 훨씬 심플하게 짠 것 같다. x, y에 -1씩 빼줘서 예외 처리할 필요 없이 계산을 편하게 하고 반복문을 돌려준다.

 

* 수 이어쓰기 (mid) : n까지의 수를 쭉 이어쓴 값의 자리 수를 구하는 문제다.

1748번: 수 이어 쓰기 1

#include <iostream>
#include <algorithm>

using namespace std;

int main() {

	int n;
	cin >> n;

	if (n < 10) {
		cout << n << '\n';
		return 0;
	}

	int tmp = 10, len = 2, ans = 9;

	while (n >= tmp*10) {
		ans += 9 * tmp * len;
		tmp *= 10; len += 1;
	}

	ans += (n - tmp + 1) * len;

	cout << ans << '\n';

	return 0;
}

 - 10보다 작으면 그 값을 길이로 출력하고 종료한다.

 - 100, 1000, 10000보다 클 때, 더해질 수 밖에 없는 자리수를 반복해서 더해준다.

 - 반복문이 끝나면 나머지 값의 자리수를 더해준다.

 

* N과 M (mid ~ high): 여기서 한참을 싸웠다.. 1부터 N까지 자연수 중에서 M개를 고르는 수열을 출력하는 문제인데, 여러 조건이 붙을 수 있다. 문제가 12개나 있다. 차근차근 한번 해보자.

 - 1: 중복 없이 선택 (기본)

15649번: N과 M (1)

#include <iostream>

using namespace std;

int a[10]; bool c[10];

void go(int idx, int n, int m) {
	if (idx == m) {
		for (int i = 0; i < m; i++)
			cout << a[i] << ' ';
		cout << '\n';
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (c[i]) continue;
		c[i] = true; a[idx] = i;
		go(idx + 1, n, m);
		c[i] = false;
	}
}

int main()
{
	int n, m;

	cin >> n >> m;

	go(0, n, m);
}

 - a에는 출력할 수열을, c는 사용 여부를 체크한다. 재귀식을 세우는 것이 관건이다. 이를 바탕으로 다양한 조건을 추가해 계산 해본다.

 

- 2 : 중복 없이 선택 + 오름차순

15650번: N과 M (2)

#include <iostream>

using namespace std;

int a[10]; //bool c[10];

void go(int idx, int start, int n, int m) {
	if (idx == m) {
		for (int i = 0; i < m; i++)
			cout << a[i] << ' ';
		cout << '\n';
		return;
	}
	for (int i = start; i <= n; i++) {
		//if (c[i]) continue;
		//c[i] = true; 
		a[idx] = i;
		go(idx + 1, i+1, n, m);
		//c[i] = false;
	}
}

int main()
{
	int n, m;

	cin >> n >> m;

	go(0, 1, n, m);
}

 - 1에서 사용한 c 관련 함수를 모두 제거했다. 이유는 start라는 새로운 인수가 역할을 다하기 때문이다. 그 다음 함수의 반복문이 출력한 값에 1을 더한 수부터 시작되기 때문에, c를 따로 사용할 필요가 없다. 

 - 오름차순 계산은 다른 방식으로도 계산할 수 있다. 백준님이 이 단원에서 가장 중요한 부분이라고 하셨다. 오름차순은 서로 다른 수를 선택해서 크기 순으로 정렬한 것이라고 할 수 있다. 정렬은 이미 되어 있으므로, 정해진 수만큼 선택을 해서 나열하는 것도 하나의 방법이 될 수 있다.

 - 하나의 수가 가질 수 있는 경우의 수는 선택하느냐 마느냐로 총 2가지다. 이를 기반으로 코드를 짜보면 다음과 같다.

#include <iostream>

using namespace std;

int a[10];

void go(int idx, int selected, int n, int m) {
	if (selected == m) {
		for (int i = 0; i < m; i++)
			cout << a[i] << ' ';
		cout << '\n';
		return;
	}

	if (idx > n) return;

	a[selected] = idx;
	go(idx + 1, selected + 1, n, m);
	a[selected] = 0;
	go(idx + 1, selected, n, m);
}

int main()
{
	int n, m;

	cin >> n >> m;

	go(1, 0, n, m);
}

 - selected에는 지금까지 몇 개의 수가 선택됐는지를 나타낸다. selected가 m과 같을 때 출력을 해주면 된다. idx는 이전까지만 해도 a의 인덱스값으로 활용했지만, 여기서는 실제로 a에 들어갈 출력값을 나타낸다. 따라서 idx 값이 n을 넘어가면 함수를 종료한다.

 - 위가 선택하는 경우, 아래가 선택하지 않는 경우다. 선택하지 않는 경우는 selected를 그대로 넘겨주고 있다.

 - 중요한 알고리즘이라고 하니, 잘 기억해두고 넘어가자.

 

 - 3 : 중복 허용해서 선택

15651번: N과 M (3)

 - 따로 코드를 첨부할 필요 없이, 1에서 c와 관련된 라인을 모두 제거하면 된다. c가 중복을 방지하는 역할을 했으므로 c를 지워버리면 중복을 허용하게 된다.

 

 - 4 : 비내림차순으로 선택 ( a1<=a2<= ... <=an)

15652번: N과 M (4)

 - 오름차순을 구했던 2 코드를 이용해서 빠르게 풀 수 있다. a[idx]에 값을 입력하고 다음 재귀로 넘어갈 때, 2에서는 오름차순을 지키기 위해 i+1부터 반복문을 시작했는데, 이를 i부터 시작하는 것으로 바꾸면 된다.

 - 그럼 이것도 다른 방법으로도 풀 수 있겠다. 근데 아까랑은 조금 다르다. 코드를 보고 얘기를 해보자.

#include <iostream>

using namespace std;

int cnt[10];

void go(int idx, int selected, int n, int m) {
	if (selected == m) {
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < cnt[i]; j++) {
				cout << i << ' ';
			}
		}
		cout << '\n';
		return;
	}

	if (idx > n) return;

	for (int i = m - selected; i >= 1; i--) {
		cnt[idx] = i;
		go(idx + 1, selected + i, n, m);
	}

	cnt[idx] = 0;
	go(idx + 1, selected, n, m);
}

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

	go(1, 0, n, m);

	return 0;
}

 - a[i] 대신 cnt[i]를 넣었다. 여기엔 i값이 선택된 개수가 담긴다. 출력도 이에 따라 조금만 생각해서 바꿔주면 된다.

 - 문제는 선택/비선택 조건이다. 비선택 조건은 cnt[idx]에 0을 넣고 2와 같이 해주면 된다. 선택 조건은 지금까지 selected된 수에 따라 달라진다. i값은 m-selected를 시작으로 1까지 점점 감소한다. 이는 1 1 1 1이 1 1 1 2보다 먼저 오는 원리를 생각하면 이해할 수 있다. 더 많은 수를 연속해서 선택하는 것이 사전 순으로 더 먼저 오기 때문이다. 이를 통해 cnt[idx]에는 i만큼의 횟수가 담기고 selected+i가 다음 인자로 들어간다.

 - 감소하는 반복문을 생각하기가 조금 까다로울 수 있다. 이것도 잘 기억 해뒀다가 나중에 써먹자.

 

 - 5 : n개의 수가 주어지고, 중복 없이 선택

15654번: N과 M (5)

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

int a[10], num[10]; bool c[10];

void go(int idx, int n, int m) {
	if (idx == m) {
		for (int i = 0; i < m; i++)
			cout << a[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = 0; i < n; i++) {
		if (c[i]) continue;
		c[i] = true; a[idx] = num[i];
		go(idx + 1, n, m);
		c[i] = false;
	}
}

int main() {

	int n, m;
	cin >> n >> m;

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

	sort(num, num + n);

	go(0, n, m);

	return 0;
}

 - 순서를 알 수 없으므로 입력 받은 수를 sort하고 재귀함수를 돌려준다.

 - a[idx]에 i가 아닌 입력 받은 수 num[i]를 넣는 것 외에는 1번과 똑같다.

 

- 6 : n개의 수 주어지고, 중복 없이 선택 + 오름차순

15655번: N과 M (6)

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

int a[10], num[10]; //bool c[10];

void go(int idx, int start, int n, int m) {
	if (idx == m) {
		for (int i = 0; i < m; i++)
			cout << a[i] << ' ';
		cout << '\n';
		return;
	}

	for (int i = start; i < n; i++) {
		//if (c[i]) continue;
		//c[i] = true; 
		a[idx] = num[i];
		go(idx + 1, i + 1, n, m);
		//c[i] = false;
	}
}

int main() {

	int n, m;
	cin >> n >> m;

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

	sort(num, num + n);

	go(0, 0, n, m);

	return 0;
}

 - 2와 거의 똑같다. 다른 점은 start 지점이 1에서 0으로 바뀌었고, a[idx]에 들어가는 값이 i에서 num[i]로 바뀐 것이다.

 - 2에서는 1부터 출력이 되지만 여기서는 num[0]부터 출력이 되므로 start가 0부터 시작하는 것이 편하고, a[idx]에는 입력된 값이 들어간다.

 - 똑같은 원리지만 selected를 활용해서도 풀어보자.

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

int a[10], num[10]; //bool c[10];

void go(int idx, int selected, int n, int m) {
	if (selected == m) {
		for (int i = 0; i < m; i++)
			cout << num[a[i]] << ' ';
		cout << '\n';
		return;
	}

	if (idx >= n) return;

	a[selected] = idx;
	go(idx + 1, selected + 1, n, m);
	a[selected] = 0;
	go(idx + 1, selected, n, m);
}

int main() {

	int n, m;
	cin >> n >> m;

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

	sort(num, num + n);

	go(0, 0, n, m);

	return 0;
}

 - 위와 다른 지점은 출력하는 값이 num[a[i]]라는 점, idx>n이 아닌 idx>=n인 부분이다.

 - a[i]에 들어가는 값은 순서라고 할 수 있으므로 출력은 num[a[i]]으로 해야 한다. 또한 idx는 여기서 인덱스 역할을 하므로 n-1까지 밖에 못 들어간다.

 

- 7 : n개의 수 주어지고 중복 허용 선택 + 오름차순

15656번: N과 M (7)

 - 아까처럼 5에서 c와 관련된 라인을 모두 제거하면 된다.

 

 - 8 : n개의 수 주어지고, 비내림차순

15657번: N과 M (8)

 - 이것 또한 아까처럼 7에서 다음 재귀로 넘어가는 start 인수를 i+1가 아닌 i로 넣어주면 된다.

 

 - 9 : n개의 수 주어지고, 중복 없이 선택 (똑같은 수 반복해서 주어질 때 한번만 출력하기)

15663번: N과 M (9)

 - 중복 없이 저장하는 배열 하나, 각 수가 얼마나 중복 됐는지 저장하는 배열 하나, 이렇게 두고 생각해본다,

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

int a[10], num[10], cnt[10];

void go(int idx, int n, int m) {
	if (idx == m) {
		for (int i = 0; i < m; i++) {
			cout << num[a[i]] << ' ';
		}
		cout << '\n';
		return;
	}
	for (int i = 0; i < n; i++) {
		if (cnt[i] > 0) {
			cnt[i] -= 1;
			a[idx] = i;
			go(idx + 1, n, m);
			cnt[i] += 1;
		}
	}
}

int main() {

	int n, m;
	cin >> n >> m;

	int temp[10];
	for (int i = 0; i < n; i++)
		cin >> temp[i];

	sort(temp, temp + n);

	int t = temp[0];
	int c = 1;
	int k = 0;

	for (int i = 1; i < n; i++) {
		if (t == temp[i]) {
			c += 1;
		}
		else {
			num[k] = t;
			cnt[k] = c;
			k += 1;
			t = temp[i];
			c = 1;
		}
	}

	num[k] = t;
	cnt[k] = c;
	n = k + 1;

	go(0, n, m);

	return 0;
}

 - num[i]에 중복을 제거한 수를 차례로 담고, cnt[i]에 그 수가 얼마나 있는지 저장한다. cnt[i] > 0 일 때 a[idx] = i를 넣고 cnt에 1을 빼준 뒤 재귀 함수를 반복한다. 그렇게 하면 cnt에 따라 중복 없이 출력할 수 있다.

 

- 10 : n개의 수 주어지고, 비내림차순 선택 (똑같은 수 반복해서 주어질 때 한번만 출력하기)

15664번: N과 M (10)

 - 같은 패턴이다. 9에서 start 인수를 추가해주면 된다. 비내림차순이니 i+1가 아닌 i로 넘겨준다.

 

- 11 : n개의 수 주어지고, 중복 허용해서 선택 (똑같은 수 반복해서 주어질 때 한번만 출력하기)

15665번: N과 M (11)

 - 9에서 cnt의 증감 부분을 제외해주면 된다. cnt가 0보다 크기만 하다면 중복해서 사용해도 무방하기 때문이다.

 

- 12 : n개의 수 주어지고, 비내림차순 선택 (똑같은 수 반복해서 주어질 때 한번만 출력하기)

15666번: N과 M (12)

 - 11에서 start 인수를 추가해주면 된다.

-

체감상 되게 힘들었던 부분이었다. 그만큼 약한 부분인 것 같다.

아직 브루트 챕터가 좀 남았는데, 남은 강의를 들으면서 더 꼼꼼하게 내 것으로 만들어야겠다.

정리 끝!