알고리즘 강의 1의 마지막 도전문제는 강의 2 다 듣고 찬찬히 생각하며 풀어보려 한다.
-----------------------------------------------------------------------------------------------------------------------------
-브루트 포스
브루트 포스란 모든 경우의 수를 다 해보는 알고리즘이다. 이 알고리즘은 모든 문제를 풀 수 있는 방법은 아니고 방법의 개수가 많지 않은 경우에만 사용하는 방법이다. 가능한 방법의 수를 모두 구한 후 방법의 수를 모두 했을 때 시간복잡도를 구해서 너무 오래걸리지 않으면 이 방법으로 해결할 수 있다. 여기서 시간복잡도를 구했을 때 1억보다 작으면 작다고 생각하면 된다.
브루트 포스로 문제를 풀기 위해서는 다음처럼 3가지 단계를 생각해 볼 수 있다.
1. 문제의 가능한 경우의 수를 계산해본다.
-> 직접 계산을 통해서 구한다. 대부분 손으로 계산해볼 수 있다.
2. 가능한 모든 방법을 다 만들어 본다.
-> 하나도 빠짐 없이 만들어야 한다.
-> 대표적으로 그냥 다 해보는 방법, for문 사용, 순열 사용, 재귀호출 사용, 비트마스크 사용이 있다.
3. 각각의 방법을 이용해 답을 구해본다.
-> 이 단계는 보통은 어렵지 않다. 문제에 나와있는 대로 답을 계산해 본다.
브루트 포스 문제의 시간 복잡도는 대부분 O(경우의 수 * 방법 1개를 시도해보는데 걸리는 시간 복잡도)가 걸린다. 여기서 경우의 수(방법의 수)가 가장 중요하다.
- 경우의 수
문제의 가능한 경우의 수를 계산하기 위해 몇 가지 경우의 수를 계산하는 방법을 연습해 보자.
- 그냥 다 해보기
브루트 포스의 문제 순서 중 2번째인 가능한 경우의 수를 모두 구해보는 방법 중 첫번째 방법이다.
<2309번 / 일곱 난쟁이>
아홉 명의 난쟁이 중 일곱명의 난쟁이를 찾는 문제이다. 입력으로는 난쟁이의 키가 주어진다. 그러면 9명 중 난쟁이가 아닌 2명을 찾으면 되니까 경우의 수는 9C2이다. 이 문제의 시간 복잡도를 구해보자. 난쟁이 수를 n이라고 하면 두 명을 고르는 경우의 수는 n^2이고 나머지 난쟁이의 키의 합을 고르는 시간 복잡도는 O(n)이다. 따라서 전체 시간복잡도는 O(n^3)이다.
이 문제를 해결할 때 2명을 제외한 키의 합을 계속 구하는 건 효율적이지 않기 때문에 9명의 합을 모두 구한 후 2명의 키를 빼주도록 한다. 오름차순으로 출력해야하니까 입력받고 우선 sort함수로 정렬을 한다. 그리고 합에서 2개를 뺐을때 100이면 i와 j를 제외한 인덱스의 배열을 출력한다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include <iostream> #include <algorithm> using namespace std; int a[9]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int sum = 0; for (int i = 0; i < 9; i++) { cin >> a[i]; sum += a[i]; } sort(a, a + 9); for (int i = 0; i < 9; i++) { for (int j = i + 1; j < 9; j++) { if (sum - a[i] - a[j] == 100) { for (int k = 0; k < 9; k++) { if (i == k || j == k) continue; cout << a[k] << '\n'; } return 0; } } } return 0; } |
cs |
<3085번 / 사탕 게임>
n*n크기의 테이블에 사탕이 있고 인접한 두 칸을 골라 사탕을 교환한다. 그 다음 같은색으로 이루어져 있는 가장 긴 연속 부분 행 또는 열을 고르는 문제이다. 여기서 우선 가능한 경우의 수를 찾으면 인접한 두칸을 고르는데 n^2, 교환하는데 2가지의 경우다. 따라서 n^2*2가지 경우가 가능하다. 행 또는 열을 고르는 문제는 하나의 행을 선택한 후 열을 골라야 한다. 그러면 n가지 행, n가지 열이므로 O(n^2)이다. 따라서 O(n^4)이다. 근데 여기서 사탕 2개가 교환이 되면 바뀌는 행과 열은 총 3가지만 이므로 n^2을 검사하지 않고 3n만 검사하면 됟나. 따라서 시간 복잡도가 O(3n^2)이다. 두가지 방법 모두를 사용해서 구현해보자.
-O(N^4)
이게 원래 시간 복잡도는 O(4n^4)이다. 왜냐면 한칸을 위, 아래, 왼, 오 4가지 방향으로 바꿀 수 있기 때문에 경우의 수가 4n^2인데 빅오에선 상수를 생략한다. 그리고 이것도 줄일 수 있다. 칸이 오른쪽과 아래랑만 바꾼다고 하면 된다. 자세한 건 그림으로 보자.
오른쪽, 아래쪽 바꾸는 경우 나누고, check 함수로 바뀐 행과 열 합 확인하고 swap한거 다시 바꿔준다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
#include <iostream> #include <algorithm> #include <vector> #include <string> 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] == a[i][j - 1]) { cnt += 1; } else { cnt = 1; } if (ans < cnt) ans = cnt; } cnt = 1; for (int j = 1; j < n; j++) { if (a[j][i] == a[j-1][i]) { cnt += 1; } else { cnt = 1; } if (ans < cnt) ans = cnt; } } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<string> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j + 1 < n) { swap(a[i][j], a[i][j + 1]); int temp = check(a); if (ans < temp) ans = temp; swap(a[i][j], a[i][j + 1]); } if (i + 1 < n) { swap(a[i][j], a[i + 1][j]); int temp = check(a); if (ans < temp) ans = temp; swap(a[i][j], a[i + 1][j]); } } } cout << ans << '\n'; return 0; } |
cs |
-O(3N^2)
이 코드는 나중에 다시 생각해보자... 흠
<1476번 / 날짜 계산>
ESM이라는 연도를 사용한다. 이걸로 몇년인지 계산하는 문제이다. 우선 전체 경우의 수는 각 제한인 15*28*19 = 7980이다.
-모든 경우의 수를 구해본다
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <iostream> #include <algorithm> #include <vector> #include <string> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int E, S, M; cin >> E >> S >> M; int e = 1, s = 1, m = 1; for (int i = 1;; i++) { if (e == E && s == S && m == M) { cout << i << '\n'; break; } e++; s++; m++; if (e > 15) e = 1; if (s > 28) s = 1; if (m > 19) m = 1; } return 0; } |
cs |
-나머지 연산을 통해 찾는 방법
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #include <algorithm> #include <vector> #include <string> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int e, s, m; cin >> e >> s >> m; e -= 1; s -= 1; m -= 1; for (int i = 0;; i++) { if (i % 15 == e && i % 28 == s && i % 19 == m) { cout << i + 1 << '\n'; break; } } return 0; } |
cs |
<1107번 / 리모컨>
tv 채널을 리모컨으로 바꾸는 문제. 버튼은 숫자와 +, -가 있고 현재 채널은 100이다. 리모컨 버튼을 누르는 횟수를 최소로 하는 문제이다. 이 문제는 최소값을 구하는 거기 때문에 중요한 것은 의미가 없는것이나, 중복되는 문제는 정답이 될 수 없다. 예를 들어 +나 -를 누르다가 숫자 버튼을 누르면 그 전까지 입력한 것은 의미가 없다. 따라서 숫자 버튼을 누르고, 그 다음에 +나 - 중 하나만 연속해서 눌러야 한다.
이동하려는 채널의 범위가 0<= N <= 500000이니까 숫자버튼을 눌러서 이동하는 채널 C도 0<= C <=1000000이다. 숫자 버튼으로 채널 C로 이동한 후 거기서 +나 -를 몇번 눌러야 하는지 계산을 해본다.
1. 이동할 채널 C를 정한다.
-> C의 범위는 0부터 1000000이므로 반복문으로 설정한다.
2. C에 포함되어 있는 숫자 중에 고장난 버튼이 있는지 확인한다.
-> 수를 문자열로 바꾼 다음, 한글자씩 검사하는 방법
-> 수를 10으로 계속해서 나누면서 하나씩 검사하는 방법
-> 고장난 버튼을 배열에 저장하고 반복문으로 고장난 숫자 버튼이 있는지 찾는다. 여기서 채널이 0인 경우에는 예외처리를 해준다. 고장난 버튼이 있으면 눌러야 하는 버튼의 횟수를 늘려야 한다.
3. 고장난 버튼이 포함되어 있지 않다면 |C-N|을 계산해 +나 -를 몇 번 눌러야 하는지 계산해야 한다.
100과 100번대 채널은 예외처리를 해준다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> #include <algorithm> using namespace std; bool broken[10]; int possible(int c) { if (c == 0) { if (broken[0]) return 0; else return 1; } int len = 0; while (c > 0) { if (broken[c % 10]) return 0; len++; c /= 10; } return len; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; int m; cin >> m; for (int i = 0; i < m; i++) { int x; cin >> x; broken[x] = true; //고장난 버튼 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; } |
cs |
<14500번 / 테트로미노>
폴리오미노는 크기가 1*1인 정사각형을 여러 개 이어 붙여서 만든 도형이다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 총 5가지가 있다. n*m 크기의 종이 위에 테트로미노를 하나 놓아서 놓인 칸에 쓰여 있는 수의 합을 최대로 하는 문제이다. 놓을 수 있는 테트로미노는 5개가 있다. 이 5개를 회전하면서 놓을 수 있는 최대 경우는 19가지이다.
이 문제를 푸는 방법은 어떤 테트로미노를 쓸것인지 결정하고, 어디에 놓을지를 결정하면 된다. 위에 테트로미노 중 주황색을 놓는 경우를 생각하면 n-2까지, m-1까지 놓을 수 있다. 그러면 시간 복잡도는 O(MN)이 된다. 따라서 전체 경우의 수는 19*O(MN)이다. 경우의 수가 그렇게 많지 않으므로 다 해본다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
#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; } |
cs |
이거 알고리즘 똑같이해서 내가 짜니까 틀리고 백준 코드 넣으니까 마자써... 암튼 알고리즘은 이해됐으니까 뭐... 빠잉!
'코딩테스트 > 알고리즘 기초 강의' 카테고리의 다른 글
| 1강 브루트 포스 - N과 M (0) | 2020.08.29 |
|---|---|
| 1강 브루트 포스 - 건너 뛰며 해보기 (0) | 2020.08.28 |
| 4강 다이나믹 프로그래밍 1 - 연습 (0) | 2020.08.25 |
| 4강 다이나믹 프로그래밍 1 - 합분해까지 (0) | 2020.08.24 |
| 4강 다이나믹 프로그래밍 1 - 이친수까지 (0) | 2020.08.22 |
댓글