새로운 챕터의 시작이다.
그냥 다 해보면 되는 줄 알았는데 그게 아니었다.
다 하는 방법도 생각을 잘 해야했다..
브루트 포스 정리 시작 해본다!
-
* 브루트 포스 : 모든 경우의 수를 다 해보는 알고리즘. 단, 경우의 수를 다 해보는데 걸리는 시간이 문제의 시간 제한을 넘지 않아야 한다.
- 문제 해결 단계 : 문제의 가능한 경우의 수 계산 -> 다 만들어 보기 -> 각각의 방법을 이용해 정답 구하기
- 시간 복잡도 : 대부분 경우의 수 * 방법 1개를 시도하는데 걸리는 시간으로 계산할 수 있음
예제를 한번 풀어보자.
* 일곱 난쟁이(low) : 아홉 명의 난쟁이 중 키의 합이 100이 되는 일곱 명의 난쟁이를 찾는 문제다.
2309번: 일곱 난쟁이
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
www.acmicpc.net
- 일곱 명을 기준으로 찾는 것보다 포함 되지 않는 2명을 기준으로 하는 것이 더 빠를 것이라는 생각으로 접근했다.
#include <iostream>
#include <algorithm>
using namespace std;
int tall[9];
int main() {
int sum = 0, t1, t2;
for (int i = 0; i < 9; i++) {
cin >> tall[i];
sum += tall[i];
}
sort(tall, tall + 9);
for (int i = 0; i < 9; i++) {
for (int j = i+1; j < 9; j++) {
if (sum - (tall[i] + tall[j]) == 100) {
t1 = tall[i]; t2 = tall[j];
for (int k = 0; k < 9; k++) {
if (tall[k] != t1 && tall[k] != t2)
cout << tall[k] << '\n';
}
return 0;
}
}
}
}- 9명 중 2명의 난쟁이를 골랐을 때, 전체 키의 합에 두 난쟁이 키의 합을 뺀 값이 100이면 그게 답이다. 어렵지 않게 해결할 수 있다.
* 사탕 게임 (high) : 난이도가 확 뛴다.. 색이 다른 인접한 칸을 교환 했을 때, 연속하는 색의 최댓값을 구하는 문제다.
3085번: 사탕 게임
문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고
www.acmicpc.net
- N*N 크기의 N에 들어갈 수 있는 최댓값이 50이다. 인접한 두 칸을 고르고 사탕을 교환하는 경우의 수는 최대 50^2 * 2 경우이므로 모든 경우를 구해도 무방하다.
- 우선 단순히 바뀔 때마다 모든 경우의 최댓값을 구하는 알고리즘이다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int check(vector <string> &a) {
int n = a.size();
int ans = 1;
for (int i = 0; i < n; i++) {
int cnt = 1;
for (int j = 1; j < n; j++) {
if (a[i][j - 1] == a[i][j])
cnt += 1;
else
cnt = 1;
if (cnt > ans) ans = cnt;
}
cnt = 1;
for (int j = 1; j < n; j++) {
if (a[j - 1][i] == a[j][i])
cnt += 1;
else
cnt = 1;
if (cnt > ans) ans = cnt;
}
}
return ans;
}
int main() {
int n;
cin >> n;
vector <string> c(n);
for (int i = 0; i < n; i++) {
cin >> c[i];
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j + 1 < n) {
swap(c[i][j], c[i][j + 1]);
int tmp = check(c);
if (tmp > ans) ans = tmp;
swap(c[i][j], c[i][j + 1]);
}
if (i + 1 < n) {
swap(c[i][j], c[i + 1][j]);
int tmp = check(c);
if (tmp > ans) ans = tmp;
swap(c[i][j], c[i + 1][j]);
}
}
}
cout << ans << '\n';
return 0;
}- 굳이 색깔이 다르다는 조건을 걸지 않고 범위 안의 모든 수를 바꿔서 최댓값을 계산해주는 것 같다. 시간 복잡도는 무려 O(N^4).... 조금 더 간단하게 만들 수 없을까? 생각 해보면 바뀌는 두 수에 연관된 줄만 검사해주면 된다.
- 따라서 swap이 이루어지는 i,j 값을 check의 인수로 전달해서, 그 부분에 연관된 줄에서 최댓값을 갱신해주기만 하면 된다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int check(vector<string>&a, int x, int y) {
int n = a.size();
int ans = 1, cnt = 1;
for (int j = 1; j < n; j++) {
if (a[x][j] == a[x][j - 1])
cnt += 1;
else
cnt = 1;
if (cnt > ans) ans = cnt;
}
cnt = 1;
for (int j = 1; j < n; j++) {
if (a[x+1][j] == a[x+1][j - 1])
cnt += 1;
else
cnt = 1;
if (cnt > ans) ans = cnt;
}
cnt = 1;
for (int j = 1; j < n; j++) {
if (a[j][y] == a[j-1][y])
cnt += 1;
else
cnt = 1;
if (cnt > ans) ans = cnt;
}
return ans;
}
int check2(vector<string>&a, int x, int y) {
int n = a.size();
int ans = 1, cnt = 1;
for (int i = 1; i < n; i++) {
if (a[i][y] == a[i-1][y])
cnt += 1;
else
cnt = 1;
if (cnt > ans) ans = cnt;
}
cnt = 1;
for (int i = 1; i < n; i++) {
if (a[i][y+1] == a[i - 1][y+1])
cnt += 1;
else
cnt = 1;
if (cnt > ans) ans = cnt;
}
cnt = 1;
for (int i = 1; i < n; i++) {
if (a[x][i] == a[x][i - 1])
cnt += 1;
else
cnt = 1;
if (cnt > ans) ans = cnt;
}
return ans;
}
int main() {
int n;
cin >> n;
vector<string> s(n);
for (int i = 0; i < n; i++)
cin >> s[i];
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i + 1 < n) {
swap(s[i][j], s[i + 1][j]);
int tmp = check(s, i, j);
if (tmp > ans) ans = tmp;
swap(s[i][j], s[i + 1][j]);
}
if (j + 1 < n) {
swap(s[i][j], s[i][j+1]);
int tmp = check2(s, i, j);
if (tmp > ans) ans = tmp;
swap(s[i][j], s[i][j+1]);
}
}
}
cout << ans << '\n';
return 0;
} - i, i+1 사이의 swap, j, j+1 사이의 swap를 따로 check 해준다. swap이 이루어지는 위치를 전달함으로써 O(N^3)로 시간 복잡도를 줄였다. 잔실수가 너무 많아서 참 오래도 걸렸다... (응 그게 니 실력이야)
* 날짜 계산 (low) : 특정 연도 체계에 맞는 연도가 주어지면 이를 우리가 알고 있는 연도 체계로 해독하는 문제다.
1476번: 날짜 계산
준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타��
www.acmicpc.net
- 나머지 연산을 사용한다. 나머지가 0이 될 때만 주의해서 계산을 해준다.
#include <iostream>
using namespace std;
int main() {
int e, s, m, n = 1;
int et, st, mt;
cin >> e >> s >> m;
while (1)
{
et = n % 15;
st = n % 28;
mt = n % 19;
if (!et) et = 15;
if (!st) st = 28;
if (!mt) mt = 19;
if (et == e && st == s && mt == m)
break;
n++;
}
cout << n << '\n';
return 0;
}- 예외 처리만 잘 해준다면 큰 어려움 없이 풀 수 있다.
* 리모컨 (high) : 단짠단짠도 아니고 로하로하라니.. 생각해야 할 게 많은 어려운 문제였다.
1107번: 리모컨
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼��
www.acmicpc.net
- 버튼이 0부터 9, +, -가 있다. 고장난 숫자 버튼이 몇 개 주어진다. 현재 채널이 100일 때, 고장난 버튼을 제외하고 채널 N으로 이동하기 위해 버튼을 누르는 최솟값을 구하는 문제다. 최소 채널은 0이고, 0에서 -를 누르면 변화가 없다. 채널은 무한대라고 가정한다.
- 브루트 포스니까 다 구해봐야 된다는 건 알겠는데, 어떤 방식으로 접근해야 할지 감이 잘 안 왔다.
- 일단 확실한 것은, 조건 내에서 버튼을 입력해서 가장 인접한 숫자를 구하고, +, - 를 이용해 N에 접근한다는 사실이다. 또한, 버튼을 누르는 최솟값을 구해야 하므로, +와 -를 교차해서 쓸 수는 없다. 그럼 같은 값을 중복해서 방문하기 때문에 최솟값이라고 할 수 없다.
- N의 최댓값은 500,000인데, 버튼을 입력해서 구할 수 있는 수의 최댓값도 500,000일까? 500,000 미만의 수에서 +로 접근할 수도 있지만, 500,000을 넘는 수에서 -를 눌러 접근하는 것이 최솟값이 될 수도 있다. 따라서 버튼을 입력해 구할 수 있는 수의 최댓값은 1,000,000이라고 볼 수 있다. 그럼 이 범위 내에서 모든 경우의 수를 구해보자.
- 처음 채널은 100이다. 여기서 숫자 버튼을 이용해 1,000,000 이하의 채널로 이동한 다음, + 혹은 -가 얼마나 눌리는지 계산하면 된다. 코드를 보면서 생각을 해보는 게 빠를 것 같다.
#include <iostream>
#include <vector>
using namespace std;
bool b[10];
int possible(int c) {
if (c == 0) {
return b[0] ? 0 : 1;
}
int len = 0;
while (c > 0) {
if (b[c % 10]) return false;
len += 1;
c /= 10;
}
return len;
}
int main() {
int n, m;
cin >> n >> m;
int t;
for (int i = 0; i < m; i++) {
cin >> t;
b[t] = true;
}
int ans = n - 100;
if (ans < 0) {
ans = -ans;
}
for (int i = 0; i <= 1000000; i++) {
int c = i;
int len = possible(c);
if (len > 0) {
int press = c - n;
if (press < 0) {
press = -press;
}
if (ans > len + press) {
ans = len + press;
}
}
}
cout << ans << '\n';
return 0;
}
- 채널의 초기 값은 100이므로 ans 값에서 100을 빼준다. 음수가 되면 부호를 바꿔준다. 아무 숫자도 표현하지 못 할 때 + 혹은 -만 사용해서 표현해야 하는 최댓값이라고 할 수 있다.
- 1000000까지의 경우의 수를 모두 구해주고 최솟값을 구한다.
- possible에서는 고장난 버튼을 누를 때 예외 처리를 해주고, 수를 표현할 수 있다면 버튼을 입력한 횟수를 리턴해 len에 저장한다. 표현이 가능할 때, 구하고자 하는 값과 표현한 수를 뺀 값의 절대값이 + 혹은 -를 사용하는 횟수이다. 이를 press에 저장한다. len과 press의 합이 ans보다 작을 때, 최솟값을 갱신한다.
* 테트로미노 (mid) : 특정 모양의 도형 안에 들어가는 수의 최대합을 구하는 문제다.
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변�
www.acmicpc.net
- 제시된 도형으로 만들 수 있는 경우의 수는 2개 / 1개 / 8개 / 4개 / 4개로 총 19개다. 그냥 다 구하면 된다.
- 단순하게 범위를 설정하고 나누는 문제라서.. 이번엔 소스 코드를 그냥 가져왔다.
#include <iostream>
using namespace std;
int a[500][500];
int main() {
int n, m;
cin >> n >> m;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
cin >> a[i][j];
}
}
int ans = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
// 'ㅡ' 모양
if (j+3 < m) {
int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i][j+3];
if (ans < temp) ans = temp;
}
if (i+3 < n) {
int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+3][j];
if (ans < temp) ans = temp;
}
// 'ㄴ' 모양
if (i+1 < n && j+2 < m) {
int temp = a[i][j] + a[i+1][j] + a[i+1][j+1] + a[i+1][j+2];
if (ans < temp) ans = temp;
}
if (i+2 < n && j+1 < m) {
int temp = a[i][j] + a[i][j+1] + a[i+1][j] + a[i+2][j];
if (ans < temp) ans = temp;
}
if (i+1 < n && j+2 < m) {
int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i+1][j+2];
if (ans < temp) ans = temp;
}
if (i+2 < n && j-1 >= 0) {
int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+2][j-1];
if (ans < temp) ans = temp;
}
if (i-1 >= 0 && j+2 < m) {
int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i-1][j+2];
if (ans < temp) ans = temp;
}
if (i+2 < n && j+1 < m) {
int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+2][j+1];
if (ans < temp) ans = temp;
}
if (i+1 < n && j+2 < m) {
int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i+1][j];
if (ans < temp) ans = temp;
}
if (i+2 < n && j+1 < m) {
int temp = a[i][j] + a[i][j+1] + a[i+1][j+1] + a[i+2][j+1];
if (ans < temp) ans = temp;
}
// 'ㅁ' 모양
if (i+1 < n && j+1 < m) {
int temp = a[i][j] + a[i][j+1] + a[i+1][j] + a[i+1][j+1];
if (ans < temp) ans = temp;
}
// 'ㄹ' 모양
if (i-1 >= 0 && j+2 < m) {
int temp = a[i][j] + a[i][j+1] + a[i-1][j+1] + a[i-1][j+2];
if (ans < temp) ans = temp;
}
if (i+2 < n && j+1 < m) {
int temp = a[i][j] + a[i+1][j] + a[i+1][j+1] + a[i+2][j+1];
if (ans < temp) ans = temp;
}
if (i+1 < n && j+2 < m) {
int temp = a[i][j] + a[i][j+1] + a[i+1][j+1] + a[i+1][j+2];
if (ans < temp) ans = temp;
}
if (i+2 < n && j-1 >= 0) {
int temp = a[i][j] + a[i+1][j] + a[i+1][j-1] + a[i+2][j-1];
if (ans < temp) ans = temp;
}
// 'ㅗ' 모양
if (j+2 < m) {
int temp = a[i][j] + a[i][j+1] + a[i][j+2];
if (i-1 >= 0) {
int temp2 = temp + a[i-1][j+1];
if (ans < temp2) ans = temp2;
}
if (i+1 < n) {
int temp2 = temp + a[i+1][j+1];
if (ans < temp2) ans = temp2;
}
}
if (i+2 < n) {
int temp = a[i][j] + a[i+1][j] + a[i+2][j];
if (j+1 < m) {
int temp2 = temp + a[i+1][j+1];
if (ans < temp2) ans = temp2;
}
if (j-1 >= 0) {
int temp2 = temp + a[i+1][j-1];
if (ans < temp2) ans = temp2;
}
}
}
}
cout << ans << '\n';
return 0;
}- 굳이 직접 다 구현할 필요까지는 없는 것 같다. 어떤 원리인지만 이해하고 넘어가자.
-
모든 경우를 다 구하는 게 때로는 가장 효율적일 수도 있다.
기초 강의에 잘 어울리는 챕터가 아닌가 생각한다.
더 많은 예제를 풀어보면서 감을 익혀 봐야겠다.
정리 끝!
'알고리즘 > 백준 알고리즘 강의' 카테고리의 다른 글
| 백준 알고리즘 기초 - 브루트 포스 (순열) (0) | 2020.07.17 |
|---|---|
| 백준 알고리즘 기초 - 브루트 포스 (예제 + N과 M) (0) | 2020.07.16 |
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 (도전) (0) | 2020.07.12 |
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 (연습) (0) | 2020.07.11 |
| 백준 알고리즘 기초 - 다이나믹 프로그래밍 (예제2) (0) | 2020.07.09 |
