스터디 - 씨앗
공지 커리큘럼
19-2 씨앗 6회차(11.11)
11월 11일 (강의자: 원승주)
스택, 큐, 덱 자료구조에 대해서 설명하고 관련 문제를 풀어보았습니다.
10828번. 스택 (https://www.acmicpc.net/problem/10828)
9012번. 괄호 (https://www.acmicpc.net/problem/9012)
10845번. 큐 (https://www.acmicpc.net/problem/10845)
2164번. 카드2 (https://www.acmicpc.net/problem/2164)
10866번. 덱 (https://www.acmicpc.net/problem/10866)
10828번. 스택
|
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;
int main()
{
int cmdNum;
cin >> cmdNum;
stack<int> s;
while (cmdNum--) {
string tmp;
cin >> tmp;
if (tmp == "push") {
int val;
cin >> val;
s.push(val);
}
else if (tmp == "pop") {
if (s.empty()) {
cout << -1 << '\n';
continue;
}
else {
cout << s.top() << '\n';
s.pop();
}
}
else if (tmp == "size") {
cout << s.size() << '\n';
}
else if (tmp == "empty") {
if (s.empty())
cout << 1 << '\n';
else
cout << 0 << '\n';
}
else if (tmp == "top") {
if (s.empty())
cout << -1 << '\n';
else
cout << s.top() << '\n';
}
}
return 0;
}
|
cs |
9012번. 괄호
|
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
using namespace std;
int main()
{
int T;
cin >> T;
string str;
while (T--) {
cin >> str;
stack<char> s;
bool pass = true;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '(')
s.push('(');
else // 닫는 괄호였으면.
{
if (s.empty()) {
pass = false;
break;
}
else
s.pop();
}
}
if (pass && s.empty())
cout << "YES\n";
else
cout << "NO\n";
}
return 0;
}
|
cs |
10845번. 큐
|
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
queue<int> q;
while (N--) {
cin.ignore(256, '\n');
string cmd;
cin >> cmd;
if (cmd == "push") {
int tmp;
cin >> tmp;
q.push(tmp);
}
else if (cmd == "pop") {
if (q.empty())
cout << -1 << '\n';
else
{
cout << q.front() << '\n';
q.pop();
}
}
else if (cmd == "size") {
cout << q.size() << '\n';
}
else if (cmd == "front") {
if (q.empty())
cout << -1 << '\n';
else
cout << q.front() << '\n';
}
else if (cmd == "empty") {
cout << (q.empty() ? 1 : 0) << '\n';
}
else if (cmd == "back") {
if (q.empty())
cout << -1 << '\n';
else
cout << q.back() << '\n';
}
}
return 0;
}
|
cs |
2164번. 카드2
|
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
|
#include <iostream>
#include <queue>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
queue<int> q;
int N;
cin >> N;
for (int i = 1; i <= N; ++i) {
q.push(i);
}
int t = 0;
while (q.size() != 1) {
if (t % 2 == 0)
q.pop();
else {
int k = q.front();
q.pop();
q.push(k);
}
++t;
}
cout << q.front();
return 0;
}
|
cs |
10866번. 덱
|
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
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <deque>
using namespace std;
int main() {
int N;
cin >> N;
string cmd;
deque<int> deq;
while (N--) {
getchar();
cin >> cmd;
if (cmd == "push_back") {
int tmp;
cin >> tmp;
deq.push_back(tmp);
}
else if (cmd == "push_front") {
int tmp;
cin >> tmp;
deq.push_front(tmp);
}
else if (cmd == "pop_front") {
if (deq.empty())
cout << -1 << '\n';
else {
cout << deq.front() << '\n';
deq.pop_front();
}
}
else if (cmd == "pop_back") {
if (deq.empty())
cout << -1 << '\n';
else {
cout << deq.back() << '\n';
deq.pop_back();
}
}
else if (cmd == "size") {
cout << deq.size() << '\n';
}
else if (cmd == "empty") {
cout << deq.empty() << '\n';
}
else if (cmd == "front") {
if (deq.empty())
cout << -1 << '\n';
else
cout << deq.front() << '\n';
}
else if (cmd == "back") {
if (deq.empty())
cout << -1 << '\n';
else
cout << deq.back() << '\n';
}
}
return 0;
}
|
cs |
19-2 씨앗 5회차(11.5)
11월 5일 (강의자: 윤대승)
icpc가 있는 주이기도 하고, 수요에 의해서 고급반 내용(Heavy-Light Decomposition)을 진행했습니다.
5916번. 농장 관리 (https://www.acmicpc.net/problem/5916)
5916번. 농장 관리
HLD를 사용하는 기초적인 문제. 세그먼트 트리와 lazy propagation이 필요함.
|
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define endl '\n'
#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MOD = 1e9 + 7;
const int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
const int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
vector<int> adj[100000];
int num[100000], hld[100000], ncnt;
int p[100000], d[100000], w[100000];
const int SZ = 1 << 17;
ll tree[SZ << 1], lazy[SZ << 1];
void dfs(int now) {
w[now] = 1;
for (int nxt : adj[now]) if (!w[nxt]) {
d[nxt] = d[now] + 1;
p[nxt] = now;
dfs(nxt);
w[now] += w[nxt];
}
}
void dfs2(int now) {
num[now] = ncnt++;
for (int nxt : adj[now]) {
if (p[nxt] == now && 2 * w[nxt] >= w[now]) {
hld[nxt] = hld[now];
dfs2(nxt);
}
}
for (int nxt : adj[now]) {
if (p[nxt] == now && 2 * w[nxt] < w[now]) {
hld[nxt] = nxt;
dfs2(nxt);
}
}
}
void prop(int idx, int s, int e) {
tree[idx] += (e - s + 1) * lazy[idx];
if (s != e) {
lazy[idx << 1] += lazy[idx];
lazy[idx << 1 | 1] += lazy[idx];
}
lazy[idx] = 0;
}
void update(int L, int R, int val, int idx = 1, int s = 0, int e = SZ - 1) {
prop(idx, s, e);
if (R < L || e < L || R < s) return;
if (L <= s && e <= R) {
lazy[idx] += val;
prop(idx, s, e);
return;
}
int m = s + e >> 1;
update(L, R, val, idx << 1, s, m);
update(L, R, val, idx << 1 | 1, m + 1, e);
tree[idx] = tree[idx << 1] + tree[idx << 1 | 1];
}
ll query(int L, int R, int idx = 1, int s = 0, int e = SZ - 1) {
prop(idx, s, e);
if (R < L || e < L || R < s) return 0;
if (L <= s && e <= R) return tree[idx];
int m = s + e >> 1;
return query(L, R, idx << 1, s, m) + query(L, R, idx << 1 | 1, m + 1, e);
}
void hld_update(int a, int b, int val) {
while (hld[a] != hld[b]) {
if (d[hld[a]] < d[hld[b]]) swap(a, b);
update(num[hld[a]], num[a], val);
a = p[hld[a]];
}
if (d[a] > d[b]) swap(a, b);
update(num[a] + 1, num[b], val);
}
ll hld_query(int a, int b) {
ll ret = 0;
while (hld[a] != hld[b]) {
if (d[hld[a]] < d[hld[b]]) swap(a, b);
ret += query(num[hld[a]], num[a]);
a = p[hld[a]];
}
if (d[a] > d[b]) swap(a, b);
return ret + query(num[a] + 1, num[b]);
}
int main() {
fastio;
int N, M;
cin >> N >> M;
for (int a, b, i = 1; i < N; ++i) {
cin >> a >> b;
adj[--a].push_back(--b);
adj[b].push_back(a);
}
dfs(0);
dfs2(0);
char q;
for (int a, b; M--; ) {
cin >> q >> a >> b;
--a, --b;
if (q == 'P') hld_update(a, b, 1);
else cout << hld_query(a, b) << endl;
}
return 0;
}
|
cs |
19-2 씨앗 4회차(10.7~8)
10월 7일 (강의자: 원승주)
배열과 연결리스트에 관한 내용을 강의하고 그와 관련된 문제를 boj.kr에서 풀어보았습니다.
1158번. 조세퍼스 문제 (https://www.acmicpc.net/problem/1158)
2346번. 풍선 터뜨리기 (https://www.acmicpc.net/problem/2346)
1406번. 에디터 (https://www.acmicpc.net/problem/1406)
1158번. 조세퍼스 문제
연결리스트를 이용하여 원소를 삭제하며 문제를 해결
|
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
|
#include <iostream>
#include <algorithm>
#include <list>
using namespace std;
int main()
{
int N, K;
cin >> N >> K;
// N 명의 원형 순열에서 K 번째 수를 계속해서 제거함.
list<int> li(N+1);
list<int>::iterator it = li.begin();
for (int i = 0; i <= N; i++) {
(*it) = i;
it++;
}
li.pop_front();
cout << '<';
// 여기 까지 오면, 1~N 까지 리스트에 있음 리스트의 사이즈는 N 임
it = li.begin();
while (!li.empty()) {
for (int i = 0; i < K - 1; i++) {
it++;
if (it == li.end()) it = li.begin();
}
if (li.size() == 1) {
cout << (*it) << '>';
}
else {
cout << (*it) << ", ";
}
it = li.erase(it);
if (it == li.end()) it = li.begin();
}
return 0;
}
|
cs |
2346번. 풍선 터뜨리기
마찬가지로 연결리스트를 이용하여 해결
|
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
|
#include <list>
#include <iostream>
using namespace std;
typedef pair<int,int> pii;
// first 는 풍선의 번호,
// second 는 종이에 적힌 내용
int N; // 풍선 수
int main()
{
cin >> N;
list<pii> li;
for(int i=1;i<=N;++i){
int t;
cin >> t;
li.push_back(make_pair(i,t));
}
auto it = li.begin();
while(1){
// it 이 가리키고 있는 풍선을 터뜨림
cout << it->first << ' ';
int t = it->second;
if(li.size() == 1) break;
it = li.erase(it);
if(it == li.end()) it = li.begin();
// 양수면 오른쪽이동
if(t>=1){
for(int i=1;i<t;++i){
++it;
if(it == li.end()) it = li.begin();
}
}
// 음수면 왼쪽이동
else{
for(int i=0;i<-t;++i){
if(it == li.begin()) it = li.end();
--it;
}
}
}
return 0;
}
|
cs |
1406번. 에디터
스택 풀이도 가능하나 연결리스트 풀이로 해결
|
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
|
#include <list>
#include <iostream>
#include <string>
using namespace std;
int main()
{
list<char> li;
string str;
cin >> str;
for (int i = 0; i < str.size(); ++i)
li.push_back(str[i]);
int N;
cin >> N;
auto cur = li.end();
for (int i = 0; i < N; ++i) {
char t;
cin >> t;
if (t == 'P') {
char tt;
cin >> tt;
li.insert(cur, tt);
}
else if (t == 'L') {
if (cur != li.begin()) --cur;
}
else if (t == 'D') {
if (cur != li.end()) ++cur;
}
else if (t == 'B') {
if (cur == li.begin()) continue;
--cur;
cur = li.erase(cur);
}
}
str = "";
for (cur = li.begin(); cur != li.end(); ++cur)
str.push_back(*cur);
cout << str;
return 0;
}
|
cs |
10월 8일 (강의자: 윤대승)
삼성 A형 기출문제 2개를 골라서 boj.kr에서 풀어보았습니다.
14888번. 연산자 끼워넣기 (https://www.acmicpc.net/problem/14888)
12100번. 2048 (Easy) (https://www.acmicpc.net/problem/12100)
14888번. 연산자 끼워넣기
재귀를 이용하여 매우 간단하게 해결 가능
|
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
|
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
int N, mn = 1e9, mx = -1e9;
int op[4], arr[11];
void go(int idx, int val) {
if (idx == N - 1) {
mn = min(mn, val);
mx = max(mx, val);
return;
}
if (op[0]) op[0]--, go(idx + 1, val + arr[idx + 1]), op[0]++;
if (op[1]) op[1]--, go(idx + 1, val - arr[idx + 1]), op[1]++;
if (op[2]) op[2]--, go(idx + 1, val * arr[idx + 1]), op[2]++;
if (op[3]) op[3]--, go(idx + 1, val / arr[idx + 1]), op[3]++;
}
int main() {
cin >> N;
for (int i = 0; i < N; ++i) cin >> arr[i];
for (int i = 0; i < 4; ++i) cin >> op[i];
go(0, arr[0]);
cout << mx << endl << mn;
return 0;
}
|
cs |
12100번. 2048 (Easy)
전형적인 삼성 스타일의 귀찮은 구현 문제. 상하좌우로 이동하는 동작을 일일이 구현해줘야 함.
|
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
#include <bits/stdc++.h>
#define X first
#define Y second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, s, n) for (int i = s; i < n; ++i)
#define fastio ios::sync_with_stdio(false); cin.tie(nullptr)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pdd = pair<double, double>;
const int MOD = 1e9 + 7;
const int INF32 = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3fLL;
const int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
const int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
const double PI = acos(-1);
int N, answer;
int bo[20][20];
void go(int cnt) {
if (cnt == 5) {
rep(i, 0, N) rep(j, 0, N)
answer = max(answer, bo[i][j]);
return;
}
int cpy[20][20];
memcpy(cpy, bo, sizeof(cpy));
vector<int> seq, res;
int flg;
rep(k, 0, 4) {
switch (k) {
case 0:
rep(i, 0, N) {
seq.clear();
res.clear();
rep(j, 0, N) if (bo[j][i] != 0)
seq.pb(bo[j][i]);
flg = 0;
rep(j, 0, sz(seq)) {
if (flg && seq[j - 1] == seq[j]) flg = 0, res.pop_back();
else flg = 1;
res.pb(seq[j] << (!flg && seq[j - 1] == seq[j]));
}
rep(j, 0, N) bo[j][i] = j < sz(res) ? res[j] : 0;
}
break;
case 1:
rep(i, 0, N) {
seq.clear();
res.clear();
for (int j = N - 1; j >= 0; --j)
if (bo[i][j] != 0) seq.pb(bo[i][j]);
flg = 0;
rep(j, 0, sz(seq)) {
if (flg && seq[j - 1] == seq[j]) flg = 0, res.pop_back();
else flg = 1;
res.pb(seq[j] << (!flg && seq[j - 1] == seq[j]));
}
rep(j, 0, N) bo[i][N - 1 - j] = j < sz(res) ? res[j] : 0;
}
break;
case 2:
rep(i, 0, N) {
seq.clear();
res.clear();
for (int j = N - 1; j >= 0; --j)
if (bo[j][i] != 0) seq.pb(bo[j][i]);
flg = 0;
rep(j, 0, sz(seq)) {
if (flg && seq[j - 1] == seq[j]) flg = 0, res.pop_back();
else flg = 1;
res.pb(seq[j] << (!flg && seq[j - 1] == seq[j]));
}
rep(j, 0, N) bo[N - 1 - j][i] = j < sz(res) ? res[j] : 0;
}
break;
case 3:
rep(i, 0, N) {
seq.clear();
res.clear();
rep(j, 0, N) if (bo[i][j] != 0)
seq.pb(bo[i][j]);
flg = 0;
rep(j, 0, sz(seq)) {
if (flg && seq[j - 1] == seq[j]) flg = 0, res.pop_back();
else flg = 1;
res.pb(seq[j] << (!flg && seq[j - 1] == seq[j]));
}
rep(j, 0, N) bo[i][j] = j < sz(res) ? res[j] : 0;
}
break;
}
go(cnt + 1);
memcpy(bo, cpy, sizeof(bo));
}
}
int main() {
scanf("%d", &N);
rep(i, 0, N) rep(j, 0, N) scanf("%d", bo[i] + j);
go(0);
printf("%d", answer);
return 0;
}
|
cs |
19-2 씨앗 3회차(9.30~10.1)
9월 30일 (강의자: 원승주)
이분탐색에 대한 개념을 강의하고 그와 관련된 문제를 boj.kr에서 풀어보았습니다.
1920번. 수 찾기 (https://www.acmicpc.net/problem/1920)
2805번. 나무 자르기 (https://www.acmicpc.net/problem/2805)
2512번. 예산 (https://www.acmicpc.net/problem/2512)
1654번. 랜선 자르기 (https://www.acmicpc.net/problem/1654)
1920번. 수 찾기
주어진 수열을 정렬하고 이분탐색으로 찾는 풀이
|
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
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
sort(a.begin(), a.end());
int m;
cin >> m;
for (int i = 0; i < m; ++i) {
int t;
cin >> t;
auto it = lower_bound(a.begin(), a.end(), t);
if (it != a.end() && (*it == t))
cout << 1 << '\n';
else
cout << 0 << '\n';
}
return 0;
}
|
cs |
2805번. 나무 자르기
최적해 높이 h를 이분탐색으로 찾는 풀이
|
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
|
#include <iostream>
#include <vector>
using namespace std;
vector<int> v;
long long need;
// 절단기의 높이를 h 로 해서 need 를 충족할수 있는가.
bool decision(int h)
{
// auto it = upper_bound(v.begin(), v.end(), h);
// if (it == v.end()) return false;
long long sum = 0;
for(int i=0;i<v.size();++i)
{
if(v[i] >= h) sum += v[i]-h;
}
return sum >= need;
}
int optimize()
{
int lo = 0; // 무조건 되는 거
int hi = 1000000001; // 안되는 거
while(lo +1 < hi )
{
int mid = (hi + lo) / 2;
if (decision(mid)) {
lo = mid;
}
else
hi = mid;
}
return lo;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N; // 나무 수
cin >> N >> need;
v = vector<int>(N);
for (int i = 0; i < N; ++i)
cin >> v[i];
// sort(v.begin(), v.end());
cout << optimize();
return 0;
}
|
cs |
2512번. 예산
나무 자르기 문제와 마찬가지로 최적해 예산을 이분탐색으로 찾는 풀이
|
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
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int M;
vector<int> v;
bool canAns(int mid)
{
int sum = 0;
for(int i=0;i<N;++i){
if(v[i] > mid){
sum += mid;
}
else sum += v[i];
}
return sum <= M;
}
int optimise()
{
int lo = 0;
int hi = 1000000001;
while(lo +1 < hi)
{
int mid = (lo+hi)/2;
// mid 로 예산을 배정할수있나?
if(canAns(mid)) lo = mid;
else hi = mid;
}
return lo;
}
int main()
{
cin >> N;
v = vector<int>(N);
int tmp = 0;
int max = 0;
for(int i=0;i<N;++i){
cin >> v[i];
tmp += v[i];
if(max < v[i] ) max = v[i];
}
cin >> M;
// 모든 요청이 배정될 수 있는지 검사
if(tmp <= M){
cout << max << '\n';
}
// 모든 요청으로 배정될 수 없다면?
else{
cout << optimise();
}
return 0;
}
|
cs |
1654번. 랜선 자르기
위의 2문제와 비슷한 풀이
|
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
|
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
long long N, K;
vector<long long> v;
bool decision(long long x) // 길이 x로 N개 이상 만들수 있는가
{
long long cnt = 0;
for (int i = 0; i < K; ++i) {
cnt += (v[i] / x);
}
return cnt >= N;
}
int optimise() // 만들수 있는 최대길이
{
long long lo = 1;
long long hi = INT_MAX;
for (int iter = 0; iter < 100; ++iter) {
long long mid = (lo +hi) / 2;
if (decision(mid)) {
lo = mid;
}
else
hi = mid;
}
if (decision(hi)) return hi;
return lo;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> K >> N;
v.resize(K);
for (int i = 0; i < K; ++i)
cin >> v[i];
cout << optimise();
return 0;
}
|
cs |
10월 1일 (강의자: 윤대승)
삼성 A형 대비로 구현 연습문제 2개를 boj.kr에서 풀어보았습니다.
14891번. 톱니바퀴 (https://www.acmicpc.net/problem/14891)
17135번. 캐슬 디펜스 (https://www.acmicpc.net/problem/17135)
14891번. 톱니바퀴
재귀를 사용하여 간단히 구현하는 방법에 대해 강의
|
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
|
#include <cstdio>
#include <string>
using std::string;
void change(string a[], int idx, int dir, int f) //dir 1->cw, 0->ccw
{
if (f != 1 && idx > 0 && a[idx][6] != a[idx - 1][2]) change(a, idx - 1, dir ^ 1, -1);
if (f != -1 && idx < 3 && a[idx][2] != a[idx + 1][6]) change(a, idx + 1, dir ^ 1, 1);
if (dir) a[idx] = a[idx].back() + a[idx].substr(0, 7);
else a[idx] = a[idx].substr(1, 7) + a[idx][0];
}
int main()
{
char tmp[10];
string dat[4];
for (int i = 0; i < 4; ++i)
{
scanf(" %s", tmp);
dat[i] = tmp;
}
int k, a, b;
scanf("%d", &k);
while (k--)
{
scanf("%d %d", &a, &b);
change(dat, a - 1, b > 0, 0);
}
int ans = 0;
for (int i = 0; i < 4; ++i)
ans |= (dat[i][0] == '1') << i;
printf("%d", ans);
return 0;
}
|
cs |
17135번. 캐슬 디펜스
모든 경우에 대해서 완전탐색하는 방법과 시간복잡도 설명, 핵심 구현내용에 대해 강의
|
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
|
#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define endl '\n'
#define fastio ios::sync_with_stdio(false); cin.tie(nullptr)
using namespace std;
using ll = long long;
const int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
const int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
int N, M, D, num;
int bo[16][15];
vector<int> enemy[15];
int simul(vector<int> &com) {
vector<int> cpy_enemy[15];
int num_enemy = num;
for (int i = 0; i < M; ++i) cpy_enemy[i] = enemy[i];
int ret = 0;
while (num_enemy) {
int arr[15]{};
for (int i = 0; i < M; ++i) if (com[i]) {
int idx = -1, mn = 100;
for (int j = 0; j < M; ++j) if (!cpy_enemy[j].empty()) {
int dist = abs(j - i) + N - cpy_enemy[j].back();
if (dist <= D && mn > dist) mn = dist, idx = j;
}
if (idx != -1 && arr[idx] == 0) {
arr[idx] = 1;
++ret;
}
}
for (int i = 0; i < M; ++i)
for (auto &j : cpy_enemy[i]) ++j;
for (int i = 0; i < M; ++i) {
if (arr[i]) --num_enemy, cpy_enemy[i].pop_back();
while (!cpy_enemy[i].empty() && cpy_enemy[i].back() >= N)
--num_enemy, cpy_enemy[i].pop_back();
}
}
return ret;
}
int main() {
fastio;
cin >> N >> M >> D;
for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) {
cin >> bo[i][j];
if (bo[i][j]) ++num, enemy[j].push_back(i);
}
vector<int> com(M);
for (int i = 0; i < 3; ++i) com[i] = 1;
int ans = 0;
do {
ans = max(ans, simul(com));
} while (prev_permutation(all(com)));
cout << ans;
return 0;
}
|
cs |
19-2 씨앗 2회차(9.23~24)
9월 23일 (강의자: 원승주)
동적계획법에 관한 기초 개념을 강의하고 그와 관련된 문제를 boj.kr에서 풀어보았습니다.
1463번. 1로 만들기 (https://www.acmicpc.net/problem/1463)
11726번. 2×n 타일링 (https://www.acmicpc.net/problem/11726)
11051번. 이항 계수 2 (https://www.acmicpc.net/problem/11051)
1003번. 피보나치 함수 (https://www.acmicpc.net/problem/1003)
1463번. 1로 만들기
top-down 방식의 접근법
|
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
|
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
int memo[1000001];
// dp(x) 는 x 를 1로 만드는데 필요한 연산의
// 최소 횟수
int dp(int x)
{
// part 1. 더 이상 계산이 필요없는 부분
if(x == 1) return 0;
// part 2. 메모가 되있는지 확인하는 부분
if( memo[x] != -1 ) return memo[x];
// part 3. 메모가 안되있으니까 메모를 하는 부분
memo[x] = 987654321;
if(x%3 == 0) memo[x] = dp(x/3) +1;
if(x%2 == 0) memo[x] = min(memo[x],dp(x/2)+1);
memo[x] = min(memo[x],dp(x-1)+1);
// part 4. return
return memo[x];
}
int main(){
// memo 를 전부 -1 로 초기화
memset(memo,-1,1000001*4);
int x;
cin >> x;
cout << dp(x);
return 0;
}
|
cs |
11726번. 2×n 타일링
마찬가지로 top-down 방식.
|
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
|
#include <iostream>
#include <cstring>
#include <algorithm>
#define MOD 10007
int cache[1001];
int tiling(int n)
{
int &ans = cache[n];
if (ans != -1) return ans;
return ans = (tiling(n-1)%MOD + tiling(n-2)%MOD)%MOD;
}
int main(void) {
int n;
std::cin >> n;
std::memset(cache, -1, 1001 * 4);
cache[1] = 1;
cache[2] = 2;
std::cout << tiling(n);
return 0;
}
|
cs |
11051번. 이항 계수 2
DP를 사용해 조합(콤비네이션)의 수를 구하는 방법
|
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
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#define MOD 10007
using namespace std;
int cache[1001][1001];
int Nck(int n, int k)
{
if (k == 0 || k==n) return 1;
int &ret = cache[n][k];
if (ret != -1) return ret;
ret = (Nck(n - 1, k - 1) + Nck(n - 1, k))%MOD;
return ret;
}
int main(void) {
memset(cache, -1, sizeof(cache));
int n, k;
scanf("%d %d", &n, &k);
printf("%d", Nck(n, k));
return 0;
}
|
cs |
1003번. 피보나치 함수
타일링 문제와 구조적으로 동일.
|
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
|
#include <iostream>
#include <cstring>
int cache[2][41];
// cache[0][n] 은 fibo(n) 이 fibo(0) 를 호출한 횟수
// cache[1][n] 은 fibo(n) 이 fibo(1) 을 호출한 횟수
int fibo(int i,int n)
{
if (i == n) return 1;
else if ((i + n) == 1) return 0;
int &ans = cache[i][n];
if (cache[i][n] != -1) return ans;
return ans = fibo(i, n - 1) + fibo(i, n - 2);
}
int main(void) {
int T;
std::cin >> T;
std::memset(cache, -1, 2 * 41 * 4);
cache[0][0] = cache[1][1] = 1;
cache[0][1] = cache[1][0] = 0;
while (T--) {
int N;
std::cin >> N;
std::cout << fibo(0, N) << ' ' << fibo(1, N) << '\n';
}
return 0;
}
|
cs |
9월 24일 (강의자: 윤대승)
여러 기업 코딩테스트에서 상당히 좋아하는 알고리즘 유형 중 하나인 BFS 알고리즘 관련 문제를 boj.kr에서 풀어보았습니다.
2178번. 미로 탐색 (https://www.acmicpc.net/problem/2178)
5427번. 불 (https://www.acmicpc.net/problem/5427)
2178번. 미로 탐색
가장 기초적인 BFS문제. 구현하는 데 있어서 상대좌표를 이용하는 방법에 대해 설명함.
|
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
|
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };
int main() {
cin.sync_with_stdio(false); cin.tie(nullptr);
int N, M;
cin >> N >> M;
char bo[100][101];
for (int i = 0; i < N; ++i) cin >> bo[i];
queue<pair<int, int>> Q;
Q.push({ 0, 0 });
bool vis[100][100]{};
vis[0][0] = 1;
int ans = 1;
while (!Q.empty()) {
int szQ = Q.size();
while (szQ--) {
auto now = Q.front(); Q.pop();
if (now.X == N - 1 && now.Y == M - 1)
return cout << ans, 0;
for (int i = 0; i < 4; ++i) {
int nx = now.X + dx[i];
int ny = now.Y + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= M ||
vis[nx][ny] || bo[nx][ny] == '0') continue;
vis[nx][ny] = 1;
Q.push({ nx, ny });
}
}
++ans;
}
return 0;
}
|
cs |
5427번. 불
크게 불을 모두 전파시킨 후 기록된 시간을 통해 사람이 빠져나갈 수 있는지와 불과 사람들 동시에 전파하여 빠져나갈 수 있는지
2가지 풀이에 대해 설명함.
|
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
|
#include <bits/stdc++.h>
#define X first
#define Y second
#define endl '\n'
using namespace std;
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };
void solve() {
int w, h;
cin >> w >> h;
queue<pair<int, int>> Q;
char bo[1000][1001];
int dist[1000][1000];
memset(dist, 0x3f, sizeof(dist));
int x, y;
for (int i = 0; i < h; ++i) {
cin >> bo[i];
for (int j = 0; j < w; ++j) {
if (bo[i][j] == '*') {
Q.push({ i, j });
dist[i][j] = 0;
}
else if (bo[i][j] == '@') x = i, y = j;
}
}
while (!Q.empty()) {
auto now = Q.front(); Q.pop();
for (int i = 0; i < 4; ++i) {
int nx = now.X + dx[i];
int ny = now.Y + dy[i];
if (nx < 0 || nx >= h || ny < 0 || ny >= w ||
dist[nx][ny] != 0x3f3f3f3f || bo[nx][ny] == '#') continue;
dist[nx][ny] = dist[now.X][now.Y] + 1;
Q.push({ nx, ny });
}
}
Q.push({ x, y });
int t = 0;
while (!Q.empty()) {
int szQ = Q.size();
while (szQ--) {
auto now = Q.front(); Q.pop();
if (dist[now.X][now.Y] <= t) continue;
for (int i = 0; i < 4; ++i) {
int nx = now.X + dx[i];
int ny = now.Y + dy[i];
if (nx < 0 || nx >= h || ny < 0 || ny >= w) {
cout << t + 1 << endl;
return;
}
if (bo[nx][ny] != '.') continue;
bo[nx][ny] = '@';
Q.push({ nx, ny });
}
}
++t;
}
cout << "IMPOSSIBLE\n";
}
int main() {
cin.sync_with_stdio(false); cin.tie(nullptr);
int T;
cin >> T;
while (T--) solve();
return 0;
}
|
cs |
19-2 씨앗 1회차(9.16~17)
9월 16일 (강의자: 원승주)
분할정복에 대해 강의하고 그와 관련된 문제를 boj.kr (백준온라인저지)에서 풀어보았습니다.
1629번. 곱셈 (https://www.acmicpc.net/problem/1629)
2630번. 색종이 만들기 (https://www.acmicpc.net/problem/2630)
1992번. 쿼드트리 (https://www.acmicpc.net/problem/1992)
1629번. 곱셈
분할정복을 이용한 빠른 제곱법
|
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 <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
using namespace std;
typedef unsigned long long ull;
ull myPow(ull a, ull b, ull MOD) {
// a^b(mod MOD) 를 반환.
a %= MOD;
if (b == 0) return 1;
else if (b == 1) return a;
// 지수가 짝수면
if (b % 2 == 0) {
ull c = myPow(a, b / 2, MOD);
return ((c%MOD)*(c%MOD)) % MOD;
}
else {
return ((a%MOD) * (myPow(a, b - 1, MOD)%MOD))%MOD;
}
}
int main() {
ull a, b, MOD;
cin >> a >> b >> MOD;
cout << myPow(a, b, MOD);
return 0;
}
|
cs |
2630번. 색종이 자르기
분할정복으로 색종이를 자르며 구간 내에 같은 색만 있는 경우를 기저사례로 설정
|
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
|
#include <iostream>
using namespace std;
int N; // 한 변의 길이
int board[128][128];
pair<int, int> operator+(const pair<int, int> &p1, const pair<int, int> &p2) {
return make_pair(p1.first + p2.first, p1.second + p2.second);
}
// 한 변의 길이가 n 이고 왼쪽 위 좌표과 (i,k) 인 정사각형에서
// -1 이면 여러색으로 이루어짐, 0이면 흰색으로만 이루어짐 1 이면 파란색으로만 이루어짐
int type(int i, int k, int n)
{
for (int y = i; y < i + n; ++y) {
for (int x = k; x < k + n; ++x) {
if (board[y][x] != board[i][k])
return -1;
}
}
return board[i][k];
}
// 한 변의 길이가 n 이고 왼쪽 위 좌표과 (i,k) 인 정사각형에서
// 하얀색 색종이와 파란 색 색종이 개수를 반환
pair<int, int> div_conq(int i, int k, int n)
{
if (type(i, k, n) == 0)
return make_pair(1, 0);
else if (type(i, k, n) == 1)
return make_pair(0, 1);
return div_conq(i, k, n / 2) + div_conq(i + n / 2, k, n / 2) + div_conq(i, k + n / 2, n / 2) + div_conq(i + n / 2, k + n / 2, n / 2);
}
int main() {
cin >> N;
for (int i = 0; i < N; ++i)
for (int k = 0; k < N; ++k)
cin >> board[i][k];
auto ans = div_conq(0, 0, N);
cout << ans.first << '\n' << ans.second;
return 0;
}
|
cs |
1992번. 쿼드트리
색종이 자르기와 비슷한 방법으로 풀이 가능
|
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
|
#include <iostream>
#include <cstdio>
using namespace std;
int N; // 한 변의 길이
int board[128][128];
// 한 변의 길이가 n 이고 왼쪽 위 좌표과 (i,k) 인 정사각형에서
// -1 이면 여러색으로 이루어짐, 0이면 0으로만 이루어짐 1 이면 1으로만 이루어짐
int type(int i, int k, int n)
{
for (int y = i; y < i + n; ++y) {
for (int x = k; x < k + n; ++x) {
if (board[y][x] != board[i][k])
return -1;
}
}
return board[i][k];
}
void div_conq(int i, int k, int n)
{
if (type(i, k, n) == 0) {
cout << 0;
}
else if (type(i, k, n) == 1) {
cout << 1;
}
else {
cout << '(';
div_conq(i, k, n / 2);
div_conq(i, k + n / 2, n / 2);
div_conq(i + n / 2, k, n / 2);
div_conq(i + n / 2, k + n / 2, n / 2);
cout << ')';
}
}
int main() {
cin >> N;
for (int i = 0; i < N; ++i)
for (int k = 0; k < N; ++k)
scanf("%1d", &board[i][k]);
div_conq(0, 0, N);
return 0;
}
|
cs |
9월 17일 (강의자: 윤대승)
삼성 SW역량테스트 A형 기출문제를 마찬가지로 boj.kr에서 풀어보았습니다.
실제 A형 기출 문제는 17406번이지만, 하위호환 버전인 16926번을 먼저 풀어보았습니다.
16926번. 배열 돌리기 1 (https://www.acmicpc.net/problem/16926)
17406번. 배열 돌리기 4 (https://www.acmicpc.net/problem/17406)
16926번. 배열 돌리기 1
여러 풀이가 있을 수 있지만, 큐를 사용하는 풀이로 강의
|
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
|
#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define endl '\n'
#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
const int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
bool vis[300][300];
int main() {
fastio;
int N, M, R;
cin >> N >> M >> R;
int arr[300][300];
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
cin >> arr[i][j];
int a = 0, b = N - 1, c = 0, d = M - 1;
while (a <= b && c <= d) {
queue<int> Q;
int x = a, y = c, dir = 2;
while (!vis[x][y]) {
Q.push(arr[x][y]);
if (sz(Q) > R) {
arr[x][y] = Q.front();
Q.pop();
vis[x][y] = 1;
}
while (1) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (a <= nx && nx <= b && c <= ny && ny <= d) {
x = nx;
y = ny;
break;
}
dir = (dir + 3) % 4;
}
}
++a, --b, ++c, --d;
}
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) cout << arr[i][j] << ' ';
cout << endl;
}
return 0;
}
|
cs |
17406번. 배열 돌리기 4
돌리는 것 뿐만 아니라, 6!의 모든 순열의 경우의 수를 완전탐색으로 따지는 문제
|
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
|
#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ini(x, y) memset(x, y, sizeof(x))
#define endl '\n'
#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
const int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
int arr[50][50], cpy[50][50];
void rotate(int a, int b, int c, int d) {
bool vis[50][50]{};
while (a < b && c < d) {
queue<int> Q;
int x = a, y = c, dir = 1;
while (!vis[x][y]) {
Q.push(arr[x][y]);
if (sz(Q) > 1) {
arr[x][y] = Q.front();
Q.pop();
vis[x][y] = 1;
}
while (1) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (a <= nx && nx <= b && c <= ny && ny <= d) {
x = nx;
y = ny;
break;
}
dir = (dir + 1) % 4;
}
}
++a, --b, ++c, --d;
}
}
int main() {
fastio;
int N, M, K;
cin >> N >> M >> K;
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
cin >> arr[i][j], cpy[i][j] = arr[i][j];
tuple<int, int, int> dat[6];
for (int a, b, c, i = 0; i < K; ++i) {
cin >> a >> b >> c;
dat[i] = { a, b, c };
}
sort(dat, dat + K);
int ans = '????';
do {
for (int i = 0; i < K; ++i) {
auto[r, c, s] = dat[i];
--r, --c;
rotate(r - s, r + s, c - s, c + s);
}
for (int i = 0; i < N; ++i) {
int cnt = 0;
for (int j = 0; j < M; ++j) cnt += arr[i][j];
ans = min(ans, cnt);
}
memcpy(arr, cpy, sizeof(arr));
} while (next_permutation(dat, dat + K));
cout << ans;
return 0;
}
|
cs |
17-2 씨앗 7회차(11.28)
bfs, dfs, 스택에 관한 문제들을 풀어보았습니다.
1. 1012 유기농 배추
2. 2178 미로 탐색
3. 1260 DFS와 BFS
4. 9012 괄호
-----------------------------------------
문제풀이
1. 1012 유기농 배추
dfsAll 함수에서 방문하지 않은 배추를 만나면 cnt를 증가하고, dfs 함수를 호출합니다.
dfs 함수는 주변에 방문하지 않은 배추가 있다면 해당 배추를 방문처리하고
재귀적으로 dfs 함수를 호출합니다.
위의 방법으로 dfsAll을 통해 모든 땅을 검사하면 cnt가 정답이 됩니다.
|
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
|
#include <iostream>
using namespace std;
int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int dfsAll(int ar[][50], bool chk[][50], int m, int n);
void dfs(int ar[][50], bool chk[][50], int i, int j, int m, int n);
int main() {
int t;
scanf("%d", &t);
while(t --> 0) {
int m, n, num;
int mat[50][50] = {0};
bool chk[50][50] = {false};
scanf("%d %d %d", &m, &n, &num);
for(int i = 0 ; i < num ; ++i) {
int x, y;
scanf("%d %d", &x, &y);
mat[x][y] = 1;
}
printf("%d\n", dfsAll(mat, chk, m, n));
}
return 0;
}
int dfsAll(int ar[][50], bool chk[][50], int m, int n) {
int cnt = 0;
for(int i = 0 ; i < m ; ++i)
for(int j = 0 ; j < n ; ++j)
if(ar[i][j] == true && chk[i][j] == false)
dfs(ar, chk, i, j, m, n), cnt++;
return cnt;
}
void dfs(int ar[][50], bool chk[][50], int i, int j, int m, int n) {
chk[i][j] = true;
for(int idx = 0 ; idx < 4 ; ++idx) {
int nx = i + dir[idx][0], ny = j + dir[idx][1];
if(0 <= nx && nx < m && 0 <= ny && ny < n)
if(ar[nx][ny] == 1 && chk[nx][ny] == false) dfs(ar, chk, nx, ny, m, n);
}
}
|
cs |
2. 2178 미로 탐색
시작 위치를 방문해야하는 목록(덱)에 넣어줍니다.(push_back)
이 때 자료형은 Point(struct)이고, Point는 x, y의 좌표와 해당 좌표에 몇 번째에 도달했는지를 나타내는 cnt를 가지고 있습니다.
반복문을 통하여 방문해야하는 목록(deq)이 빌 때 까지(정답을 찾으면 반복문 탈출) 미로를 탐색합니다.
탐색할 때는 push_front를 통해 가장 오래전에 넣은 위치를 기준으로 탐색합니다.
해당 위치에서 상하좌우의 방문하지 않은, 길이 있는 곳의 위치를 deq에 Point 형태로 추가해줍니다.
문제에서 답이 보장된다고 하였으므로 위의 과정을 수행하다보면 답을 구할 수 있습니다.
|
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
|
#include <cstdio>
#include <deque>
using namespace std;
typedef struct point { int x, y, cnt; }Point;
int maxX, maxY;
int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int map[100][100];
bool isVal(int x, int y);
int main() {
scanf("%d %d", &maxY, &maxX);
for (int y = 0; y < maxY; ++y)
for (int x = 0; x < maxX; ++x)
scanf("%1d", &map[x][y]);
deque<Point> deq;
deq.push_back(Point{ 0,0,1 });
int ans = 0;
while (!deq.empty()) {
Point p = deq.front();
deq.pop_front();
if (!isVal(p.x, p.y)) continue;
if (p.x == maxX - 1 && p.y == maxY - 1) {
ans = p.cnt;
break;
}
map[p.x][p.y] = 0;
for (int i = 0; i < 4; ++i) {
int tx = p.x + dir[i][0], ty = p.y + dir[i][1];
if (isVal(tx, ty))
deq.push_back(Point{ tx, ty, p.cnt + 1 });
}
}
printf("%d", ans);
return 0;
}
bool isVal(int x, int y) {
return (0 <= x && x < maxX && 0 <= y && y < maxY && map[x][y] != 0);
}
|
cs |
3. 1260 DFS와 BFS
스택과 덱을 이용하여 노드를 방문한 순서대로 해당 노드의 번호를 출력하면 됩니다.
dfs를 할 때는 스택을 이용하여 push_front, pop_front를 하였고,
bfs를 할 때는 덱을 이용하여 push_back, pop_front를 하였습니다.
방문해야하는 목록(스택 or 덱)에서 선택한 노드와 연결된 노드를 다시 방문해야하는 노드에 추가하고,
방문하는 과정을 반복하면 됩니다.
이미 방문 한 적 있는 노드라면 다음 노드를 탐색합니다.
|
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
|
#include <iostream>
#include <deque>
using namespace std;
int vNum; // vertex num
// map[i][0] == dfs에서 i번째 노드를 방문했는지 나타냄
// map[0][i] == bfs에서 i번째 노드를 방문했는지 나타냄
bool map[1001][1001];
int main() {
cin.sync_with_stdio(false);
cin >> vNum;
int eNum, start; // edge num
cin >> eNum >> start;
while (eNum--) {
int n1, n2;
cin >> n1 >> n2;
map[n1][n2] = map[n2][n1] = true;
}
deque<int> deq, stack;
// dfs
stack.push_front(start);
while (!stack.empty()) {
int pos = stack.front();
stack.pop_front();
if (map[pos][0]) continue;
cout << pos << ' ';
for (int i = vNum; i > 0; --i) {
if (map[pos][i] && !map[0][i])
stack.push_front(i);
}
map[pos][0] = true;
}
cout << '\n';
// bfs
deq.push_back(start);
while (!deq.empty()) {
int pos = deq.front();
deq.pop_front();
if (map[0][pos]) continue;
cout << pos << ' ';
for (int i = 1; i <= vNum; ++i) {
if (map[pos][i] && !map[0][i])
deq.push_back(i);
}
map[0][pos] = true;
}
return 0;
}
|
cs |
4. 9012 괄호
문자열로 입력을 받고, 문자열의 시작부터 끝까지 각 문자에 대해 반복문을 수행합니다.
해당 문자가 여는 괄호이면 스택에 push해주고, 닫는 괄호이면 스택에서 pop해줍니다.
만약 pop할 때 스택이 비어있다면 불완전한 괄호로 취급합니다.
또한 모든 문자에 대해 반복문을 돌았는데 스택이 비어있지 않는 경우에도 불완전한 괄호입니다.
|
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
|
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
cin.sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
stack<char> data;
string str;
cin >> str;
for (int i = 0; i < str.size(); ++i) {
if (str[i] == '(')
data.push(str[i]);
else {
if (!data.empty()) data.pop();
else {
data.push(str[i]);
break;
}
}
}
if (data.empty()) cout << "YES" << "\n";
else cout << "NO" << "\n";
}
return 0;
}
|
cs |
17-2 씨앗 6회차(11.21)
프로그래밍 경시대회에 나왔던 문제들을 다시 풀어보았습니다.
추가로 스택에 대해서도 간략하게 알아보았습니다.
1. 1082 자연스러운 정렬 easy
2. 1094 Self number
3. 1089 성능 평가를 부탁해
-----------------------------------------
문제풀이
1. 1082 자연스러운 정렬 easy
숫자 부분만 따로 추출하여 정렬한 뒤 재결합하는 방법이 있습니다.
하지만 문자열의 길이를 우선적으로 비교하고, 길이가 더 짧은 문자열을 앞으로 오게 하고,
길이가 같으면 문자열 비교를 하는 comp 함수를 만들어서 sort의 세번째 인자로 설정해주는 방법이 더 간단합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool comp(const string& str1, const string& str2);
int main() {
int n;
cin >> n;
string str[1000];
for(int i = 0 ; i < n; ++i)
cin >> str[i];
sort(str, str + n, comp);
for (int i = 0; i < n; ++i)
cout << str[i] << '\n';
return 0;
}
bool comp(const string& str1, const string& str2) {
if (str1.length() == str2.length()) return str1 < str2;
return str1.length() < str2.length();
}
|
cs |
2. 1094 Self number
어떤 숫자(num)가 Self number인지 아닌지를 검사할 때는
num보다 일정 값(약 60 이상) 만큼 작은 숫자부터 num까지
Self number인지 검사하는 연산을 수행해주면 됩니다.
한 번이라도 연산을 통해 num이 나오면 Self number가 아님을 출력하고,
num까지 검사가 끝나면 Self number임을 출력합니다.
여기서 연산은 해당 숫자와 해당 숫자의 각 자리 수를 더하는 것 입니다.
ex ) 123 + 1 + 2 + 3 = 129
-> 129는 Self number가 아님
|
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
|
#include <iostream>
using namespace std;
int mySum(int num);
bool isSelfNum(int num);
int main() {
cin.sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << (isSelfNum(n) ? "Self" : "No") << '\n';
}
return 0;
}
bool isSelfNum(int num) {
int start = num - 60;
while (start < num) {
if (mySum(start) == num)
return false;
++start;
}
return true;
}
int mySum(int num) {
int sum = num;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
|
cs |
3. 1089 성능 평가를 부탁해
정확한 알고리즘과 유사 알고리즘을 비교하여 해당 유사 알고리즘에서
누락된 거리의 개수와 누락된 거리의 최솟값을 구조체에 저장합니다.
구조체에 저장한 값을 이용하여 모든 유사 알고리즘 중에 가장 좋은 알고리즘의 위치를 구하고 출력합니다.
|
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
|
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct priority { int lossCnt, lossMin; }Priority;
int main() {
cin.sync_with_stdio(false);
int k, n;
cin >> k >> n;
// 원본 배열 입력
int src[50];
for (int i = 0; i < k; ++i)
cin >> src[i];
// 입력 끝
// 유사 알고리즘 입력 & 처리
int ans;
Priority prio = { k, 2147483647 }; // int_max 는 외워두면 편합니다^^
for (int i = 0; i < n; ++i) {
// 유사 알고리즘 입력
int sudo[50];
for (int idx = 0; idx < k; ++idx)
cin >> sudo[idx];
// 원본과 유사 알고리즘 비교
Priority tmp = { 0, 2147483647 };
for (int srcIdx = 0, sudoIdx = 0; srcIdx < k && sudoIdx < k;) {
if (src[srcIdx] < sudo[sudoIdx]) {
++tmp.lossCnt;
tmp.lossMin = min(tmp.lossMin, src[srcIdx]);
++srcIdx;
}
else if (src[srcIdx] == sudo[sudoIdx])
++srcIdx, ++sudoIdx;
else
++sudoIdx;
}
if (tmp.lossCnt < prio.lossCnt ||
(tmp.lossCnt == prio.lossCnt && tmp.lossMin > tmp.lossMin)) {
prio = tmp;
ans = i;
}
}
cout << ans;
return 0;
}
|
cs |
17-2 씨앗 5회차(11.14)
15일에 있는 교내 프로그래밍 대회를 대비하여 judge에 등록된
작년도 기출 문제들을 풀어봤습니다.
1. 1063 계단 오르기
2. 1064 마지막에 떨어지는 개미
3. 1071 암호 해석-오고고
4. 1046 빠른 길 찾기
-----------------------------------------
문제풀이
1. 1063 계단 오르기
n번째 계단에 도달하는 방법은 n - 1 번째 계단에서 한 칸 올라오는 경우와
n - 2 번째 계단에서 두 칸 올라오는 경우밖에 없습니다.
이를 점화식으로 표현하면 dp[n] = dp[n - 1] + dp[n - 2] 입니다.
초기값 dp[1] = 1, dp[2] = 2를 설정한뒤 점화식을 이용하여 반복문으로 답을 구하면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <iostream>
#include <cmath>
using namespace std;
int dp[26] = { 0, 1, 2, 3 };
int main() {
cin.sync_with_stdio(false);
for (int i = 4; i <= 25; ++i)
dp[i] = dp[i - 1] + dp[i - 2];
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << dp[n] << '\n';
}
return 0;
}
|
cs |
2. 1064 마지막에 떨어지는 개미
개미가 부딪 힐 경우 서로 방향을 바꾸어서 진행하는 상황은
개미가 서로 부딪히지 않고 관통하여 지나간다고 봐도 무방합니다.
이를 이용하여 모든 개미들이 떨어지는 시간을 각각 구하고,
떨어지는 시간중에 가장 큰 값을 출력합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <iostream>
using namespace std;
void simul();
int main() {
int t;
cin >> t;
while(t--)
simul();
return 0;
}
void simul() {
int n, l;
cin >> n >> l;
int ans = 0;
while (n--) {
int p, dir;
cin >> p >> dir;
int time = (dir == 1 ? l - p : p);
if (time > ans) ans = time;
}
cout << ans << '\n';
}
|
cs |
3. 1071 암호 해석-오고고
문자열을 시작부터 탐색하면서 정답을 저장하기 위한 새로운 문자열(dst)에
지속적으로 원본 문자를 복사해줍니다.
만약 의미없는 문자인 경우에는 문자를 복사하지 않고, 의미없는 문자의 마지막 부분에서 "***"을 dst에 추가해줍니다.
ogo 가 입력에 있는 경우, og까지만 봐서는 의미없는 문자인지 판단하지 못하고 dst에 추가하게 되는데
이런 경우, 예외를 처리하기 위해 dst에서 'og'를 빼주도록 합니다.(미리 판단하여 넣지 않는것이 더 좋은 방법입니다.)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <string>
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
string src = "", dst = "";
cin >> src;
for (int i = 0; i < src.size(); ++i) {
if (i >= 2 && src[i - 2] == 'o' && src[i - 1] == 'g' && src[i] == 'o') {
dst.pop_back();
dst.pop_back();
while (i + 2 < src.size() && src[i + 1] == 'g' && src[i + 2] == 'o')
i += 2;
dst.append("***");
}
else dst += src[i];
}
cout << dst;
return 0;
}
|
cs |
4. 1046 빠른 길 찾기
시작위치부터 상하좌우로 탐색을 시작합니다.
현재 위치가 이미 탐색이 끝났거나
상하좌우의 위치가 적합하지 않다면(배열 범위 밖 or 벽) 탐색하지 않습니다.
탐색이 필요한 위치를 deque에 넣어두고, 목적지에 도달하거나, deque가 비게되면 탐색을 종료합니다.
탐색을 할 때는 deque에서 pop_front()를 사용하고, 탐색위치를 저장할 때는 push_back()을 사용하여
bfs 탐색을 할 수 있도록 합니다.
탐색 결과에 따라 적절한 값을 출력해줍니다.
|
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
|
#include <cstdio>
#include <deque>
using namespace std;
typedef struct point { int x, y, cnt; }Point;
char map[100][100];
int dir[4][2] = { { -1, 0 },{ 0, -1 },{ 1, 0 },{ 0, 1 } };
int maxX, maxY;
inline bool isVal(int x, int y);
int main() {
int t;
scanf("%d", &t);
while (t--) {
deque<Point> deq;
scanf("%d %d", &maxY, &maxX);
for (int y = 0; y < maxY; ++y) {
for (int x = 0; x < maxX; ++x) {
scanf(" %c", &map[x][y]);
if (map[x][y] == 'S') deq.push_back(Point{ x, y, 1 });
}
}
int ans = 0;
while (!deq.empty()) {
Point p = deq.front();
deq.pop_front();
for (int i = 0; i < 4; ++i) {
int tx = p.x + dir[i][0], ty = p.y + dir[i][1];
if (isVal(tx, ty)) {
if (map[tx][ty] == 'E') {
ans = p.cnt;
break;
}
map[tx][ty] = '#';
deq.push_back(Point{ tx, ty, p.cnt + 1 });
}
}
if (ans != 0) break;
}
printf("%d\n", (ans == 0 ? -1 : ans));
}
return 0;
}
inline bool isVal(int x, int y) {
if (x < 0 || maxX <= x || y < 0 || maxY <= y || map[x][y] == '#')
return false;
return true;
}
|
cs |
17-2 씨앗 4회차(11.07)
알고리즘 문제를 풀면서 다양하게 활용되는 recursion(재귀)에 대해 공부했습니다.
아래의 문제들을 풀어보면서 recursion을 사용하는 법을 익혔습니다.
1. tobin 이진수로 변경
2. sfn 특별한 4자리 정수
3. mt 산크기 모양
4. 9095 1, 2, 3 더하기
5. 11729 하노이 탑 이동 순서
6. 1074 Z
-----------------------------------------
문제풀이
1. tobin 이진수로 변경
n을 2진수로 바꾸어 출력하는 재귀함수 tobin을 선언하여 풀었습니다.
tobin 함수는 tobin(n/2)를 호출하고 난 뒤 n % 2값을 출력합니다.
위 과정을 반복하다가 n 값이 2보다 작아지면 재귀가 종료됩니다.
#include <stdio.h>
void tobin(int n);
void main() {
int n;
scanf("%d", &n);
tobin(n);
}
void tobin(int n) {
if (n >= 2) tobin(n / 2);
printf("%d", n % 2);
}
2. sfn 특별한 4자리 정수
n을 base진법으로 변환한 숫자의 각 자리수의 합을 반환하는 basedSum(n, base) 함수를 이용하여 문제를 풀었습니다.
basedSum 함수는 n을 base로 나눈 나머지를 더하는 과정을 재귀적으로 계산하여 반환합니다.
n값이 base보다 작을 때에는 n을 반환하고 함수를 종료합니다.
#include <stdio.h>
int basedSum(int n, int base);
void main() {
int n = 2992;
while(n < 10000) {
int ten = basedSum(n, 10);
if(ten == basedSum(n, 12) && ten == basedSum(n, 16))
printf("%d\n", n);
++n;
}
}
int basedSum(int n, int base) {
if(n < base) return n;
return n % base + basedSum(n / base, base);
}
3. mt 산크기 모양
재귀함수 mt(top, start)는 기본적으로
start를 출력하고
mt(top, start + 1)을 재귀호출한뒤
start를 출력합니다.
start 값이 top에 도달한 경우에는 start를 한 번만 출력하고 함수를 종료합니다.
#include <iostream>
using namespace std;
void mt(int top, int start = 1);
int main() {
int n;
cin >> n;
mt(n);
}
void mt(int top, int start) {
cout << start;
if (start == top) return;
mt(top, start + 1);
cout << start;
}
4. 9095 1, 2, 3 더하기
n을 1, 2, 3의 조합으로 나타내는 경우의 수는
(n-1), (n-2), (n-3) 각각을 1, 2, 3의 조합으로 나타내는 경우의 수의 합과 같습니다.
n이 1일 때는 1가지,
n이 2일 때는 2가지,
n이 3일 때는 4가지 경우의 수가 있다는 것을 탈출조건으로 이용하여
방법의 수를 구하는 재귀함수 cnt를 구현하였습니다.
#include <iostream>
using namespace std;
int cnt(int n);
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << cnt(n) << '\n';
}
}
int cnt(int n) {
if (n <= 3) return 1 << (n - 1);
int ret = 0;
for (int i = 1; i <= 3; ++i)
ret += cnt(n - i);
return ret;
}
5. 11729 하노이 탑 이동 순서
하노이 탑의 시작 지점(src)과, 도착 지점(dst), 옮기려는 탑의 개수(h)가 주어지면
중간지점(tmp)이 어딘지 알 수 있습니다.(위치를 1, 2, 3이라 하면 1 + 2 + 3 = src + tmp + dst)
이를 이용하여 특정 하노이탑을 옮기는 과정은 아래와 같습니다.
src에서 tmp로 h-1개를 옮기고, - (1)
src에서 dst로 1개를 옮긴뒤,
((1)에서 옮겨놓았던 )tmp에서 dst로 h-1개를 옮기면 됩니다.
이때 h-1개를 옮기는 부분에서 위의 과정을 재귀적으로 반복합니다.
이를 재귀함수로 구현하고,
h == 1일 때 src, dst를 출력하고 함수를 종료하면 전체 이동경로를 출력할 수 있습니다.
#include <iostream>
using namespace std;
void hanoi(int src, int dst, int h);
int main() {
int n;
cin >> n;
cout << ((1 << n) - 1) << '\n';
hanoi(1, 3, n);
}
void hanoi(int src, int dst, int h) {
if (h == 1) {
cout << src << ' ' << dst << '\n';
return;
}
int tmp = 6 - src - dst;
hanoi(src, tmp, h - 1);
hanoi(src, dst, 1);
hanoi(tmp, dst, h - 1);
}
6. 1074 Z
전체 크기를 4등분하고, 4등분한 뒤의 r, c를 새로 계산하여 재귀함수를 호출합니다.
이때 r, c가 몇 사분면에 있는지에 따라 잘라낸 부분에 해당하는 횟수를 더하여줍니다.
2사분면 == 0
1사분면 == (n/2)^2
3사분면 == 2 x (n/2)^2
4사분면 == 3 x (n/2)^2
4등분한뒤 재귀함수를 호출할 때는 r, c의 값을 재설정해줍니다.
r, c 값 각각이 n/2보다 큰 경우에만 r, c에서 n/2 만큼 빼주면 됩니다.
#include <iostream>
using namespace std;
int z(int n, int r, int c);
int main() {
int n, r, c;
cin >> n >> r >> c;
cout << z(1 << n, r, c);
return 0;
}
int z(int n, int r, int c) {
int half = n / 2;
if(half == 1) return r * 2 + c;
if(r < half) {
if(c < half) return z(half, r, c); // 2사분면
else return half * half + z(half, r, c - half); // 1사분면
}
else {
if(c < half) return 2 * half * half + z(half, r - half, c); // 3사분면
else return 3 * half * half + z(half, r - half, c - half); // 4사분면
}
}
17-2 씨앗 3회차(10.10)
Backtracking의 개념에 대해 간략하게 알아보고,
이를 활용하여 아래의 문제를 풀어보았습니다.
1. 2661 좋은 수열
2. 9663 N-Queen
3. 2580 스도쿠
-----------------------------------------
문제풀이
1. 2661 좋은 수열
n번째 위치에 1~3의 숫자를 넣어보고, 좋은 수열인지 검사합니다.
좋은 수열이라면 n+1번째 위치에 1~3의 숫자를 넣고, 검사합니다.
모든 경우에 대해 좋은 수열이 아니라면 n-1번째 위치의 숫자를 변경해줍니다.
위의 과정을 반복하면 길이가 n인 좋은 수열을 만들 수 있습니다.
(1부터 숫자를 차례대로 넣으면 가장 작은 수열이 완성됩니다.)
좋은 수열인지 검사할 때는 n번째 위치에 숫자를 넣었을 때
나쁜 수열이 생길 수 있는 모든 경우의 수에 대하여 검사를 하도록 했습니다.
#include <stdio.h>
bool finish = false;
char str[82];
int gn;
void sequence(int n);
bool promising(int n);
bool compare(char* str1, char* str2, int size);
int main() {
scanf("%d", &gn);
str[gn + 1] = '\0';
sequence(1);
printf("%s", &str[1]);
return 0;
}
void sequence(int n) {
for (char i = '1'; i <= '3' && !finish; ++i) {
if (str[n - 1] == i) continue;
else str[n] = i;
if (promising(n)) {
if (n == gn) {
finish = true;
return;
}
else sequence(n + 1);
}
}
}
bool promising(int n) {
for (int i = 1; i < n; ++i) {
int size = n - i + 1;
if (size % 2 == 1) continue;
if (compare(&str[i], &str[i + size / 2], size / 2))
return false;
}
return true;
}
// compare
// str1 == str2 : return true
// str1 != str2 : return false
bool compare(char* str1, char* str2, int size) {
for (int i = 0; i < size; ++i)
if (str1[i] != str2[i]) return false;
return true;
}
2. 9663 N-Queen
해당 행에 있는 퀸의 열 위치를 저장하는 배열을 이용하여 퀸들의 위치를 나타내었습니다.
n번째 행의 1~n 열에 퀸을 놓고,
서로 공격이 불가능한 경우에는 n+1번째 행의 1~n열에 퀸을 놓습니다.
모든 경우에 대해 서로 공격 가능한 경우에는 n-1번째 행에 있는 퀸의 열을 바꿔줍니다.
위의 과정을 반복하면 n x n 크기의 체스판에 n개의 퀸이 서로 공격할 수 없도록 퀸을 배치할 수 있습니다.
퀸이 서로 공격 가능한지 검사할 때는
배열의 값이 같은지를 검사하여 같은 행에 있는지를 알 수 있고,
i행의 퀸과 j행의 퀸의 (행, 열)의 기울기가 1 or -1인지를 검사하여
대각선상에 있는지를 알 수 있습니다.
n번째 행에는 하나의 퀸만 배치하도록 구현하였기 때문에
퀸이 같은 열에 있는 경우는 고려하지 않아도 됩니다.
#include <iostream>
#include <cmath>
using namespace std;
const int SIZE = 15;
int map[SIZE];
int gn;
int queen(int n);
bool promising(int n);
int main() {
cin >> gn;
cout << queen(1);
return 0;
}
int queen(int n) {
static int cnt = 0;
for (int i = 1; i <= gn; ++i) {
map[n] = i;
if (promising(n)) {
if (n == gn) ++cnt;
else queen(n + 1);
}
}
return cnt;
}
bool promising(int n) {
for (int i = 1; i < n; ++i)
if (map[i] == map[n] || (n - i == abs(map[n] - map[i])))
return false;
return true;
}
3. 2580 스도쿠
배열을 이용하여 스도쿠의 빈 곳의 좌표를 저장합니다.(번호 부여)
n번째 위치에 1~9의 숫자를 넣어보고,
가로, 세로, 블럭 내에 같은 숫자가 있는지 검사합니다.
같은 숫자가 없다면 n+1번째 위치에 1~9의 숫자를 넣고,
같은 숫자가 있다면 n-1번째 위치에 있는 숫자를 변경합니다.
위의 과정을 반복하면 스도쿠의 해를 찾을 수 있습니다.
#include <stdio.h>
int s[9][9];
int empty[81][2]; // row. col
int emptyCnt;
int test(int row, int col, int n) {
for(int r=0; r<9; ++r)
if(s[r][col]==n) return 0;
for(int c=0; c<9; ++c)
if(s[row][c]==n) return 0;
int rs = row/3*3;
int cs = col/3*3;
int re = rs+3;
int ce = cs+3;
for(int r=rs; r<re; ++r)
for(int c=cs; c<ce; ++c)
if(s[r][c]==n) return 0;
return 1;
}
int solve(int present) {
// return==1 성공, return==0 실패
if(present >= emptyCnt) return 1;
int row = empty[present][0];
int col = empty[present][1];
for(int n=1; n<=9; ++n) {
if(test(row, col, n)==1) {
s[row][col] = n;
if(solve(present+1)==1)
return 1;
s[row][col] = 0;
}
}
return 0;
}
int main(void) {
for(int r=0; r<9; ++r) {
for(int c=0; c<9; ++c) {
scanf("%d", &s[r][c]);
if(s[r][c]==0) {
empty[emptyCnt][0] = r;
empty[emptyCnt][1] = c;
++emptyCnt;
}
}
}
solve(0);
for(int r=0; r<9; ++r) {
for(int c=0; c<9; ++c)
printf("%d ", s[r][c]);
printf("\n");
}
return 0;
}
17-2 씨앗 2회차(9.26)
Dynamic Programming (동적계획법)에 대해 간략히 설명하고,
이를 활용하여 여러 문제를 풀어보았습니다.
1. 11726 2xn 타일링
2. 11727 2xn 타일링 2
3. 2193 이친수
4. 1003 피보나치 함수
-----------------------------------------
문제풀이
1. 11726 2xn 타일링
길이가 n인 타일을 채우는 경우의 수는
n-1인 경우에 타일을 세로로 하나 놓는 경우와, n-2에 타일을 가로로 두개 놓는 경우의 합으로 구할 수 있습니다.
이를 점화식으로 나타내면
ans[n] = ans[n - 1] + ans[n - 2] 이고, 이를 활용하여 풀면 됩니다.
#include <iostream>
#include <cstring>
#define MOD %10007
using namespace std;
int ans[1001];
int tile(int n);
int main() {
memset(ans, -1, sizeof(ans));
int n;
cin >> n;
cout << tile(n) MOD << '\n';
return 0;
}
int tile(int n) {
if (n <= 2) return n;
int& ret = ans[n];
if (ret != -1) return ret;
return ret = (tile(n - 1) + tile(n - 2)) MOD;
}
2. 11727 2xn 타일링 2
1번 문제와 비슷한 방식으로 점화식을 세워서 풀면 됩니다.
점화식은 다음과 같습니다.
ans[n] = ans[n - 1] + ans[n - 2] * 2;
1번문제와 초기값이 다름을 주의해야 합니다.
ans[1] = 1, ans[2] = 3;
#include <iostream>
#include <cstring>
#define MOD 10007
using namespace std;
int ans[1001];
int tile(int n);
int main() {
memset(ans, -1, sizeof(ans));
int n;
cin >> n;
cout << tile(n) % MOD << '\n';
return 0;
}
int tile(int n) {
int& ret = ans[n];
if(n == 1) return ret = 1;
if (n == 2) return ret = 3;
if (ret != -1) return ret;
return ret = (tile(n - 1) + tile(n - 2) % MOD * 2) % MOD;
}
3. 2193 이친수
n번째 자리에 0을 놓는 경우의 수는 ans[n-1]이고, (n-1자리의 이친수 뒤에 0을 추가하는 경우)
1을 놓는 경우의수는 ans[n-2]임을 이용하면 (n-2자리의 이친수 뒤에 01을 추가하는 경우)
ans[n] = ans[n-1] + ans[n-2] 라는 점화식이 나옵니다.
#include <iostream>
using namespace std;
int main() {
cin.sync_with_stdio(false);
int n;
cin >> n;
pair<long long, long long>* ar = new pair<long long, long long> [n + 1];
ar[1].first = 0;
ar[1].second = 1;
for (int i = 2; i <= n; ++i) {
ar[i].first = ar[i - 1].first + ar[i - 1].second;
ar[i].second = ar[i - 1].first;
}
cout << ar[n].first + ar[n].second;
delete[] ar;
return 0;
}
4. 1003 피보나치 함수
f(n)에서 f(0)이 호출되는 횟수는
f(n-1)에서 f(0)이 호출되는 횟수와
f(n-2)에서 f(0)이 호출되는 횟수의 합이고,
f(1)이 호출되는 횟수도 위와 같습니다.
이에따라 알맞은 점화식을 세우고, 이차원 배열을 이용하여 답을 구하면 됩니다.
#include <stdio.h>
int main() {
int sol[2][41] = {0}, i, t, n;
sol[0][0] = 1;
sol[1][0] = 0;
sol[0][1] = 0;
sol[1][1] = 1;
for(i = 2; i <= 40 ; ++i) {
sol[0][i] = sol[0][i - 1] + sol[0][i - 2];
sol[1][i] = sol[1][i - 1] + sol[1][i - 2];
}
scanf("%d", &t);
while(t --> 0) {
scanf("%d", &n);
printf("%d %d\n", sol[0][n], sol[1][n]);
}
return 0;
}
17-2 씨앗 1회차(9.19)
첫 시간인 관계로 다양한 문제들을 풀어보고, 각자의 코딩 실력을 확인해보았습니다.
아래의 문제들을 풀고, 같이 코드리뷰를 하였습니다.
1. 2444 별찍기 - 7
2. 11070 피타고라스 기대값
3. 11068 회문인 숫자
4. 9012 괄호
-----------------------------------------
문제풀이
1. 2444 별찍기 - 7
반복문과 조건문을 이용하여 다이아몬드 모양의 별을 찍는 문제입니다.
직접 그림을 그려보고, 행과 열의 관계를 찾아내서 조건문을 작성하면 됩니다.
문제를 쉽게 풀기 위해서는 상단부와 하단부를 따로 작성하는것이 좋습니다.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
// 상단
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < n + i; ++j)
cout << ((j > n - i) ? '*' : ' ');
cout << '\n';
}
// 하단
for (int i = n - 1; i >= 1; --i) {
for (int j = 1; j < n + i; ++j)
cout << ((j > n - i) ? '*' : ' ');
cout << '\n';
}
}
2. 11070 피타고라스 기대값
각 팀의 득점, 손실, 기대값을 저장하기 쉽도록 하기 위해 구조체를 정의하였습니다.
구조체를 배열로 만들고, 입력을 모두 받은 뒤 피타고라스 기대값을 구하면 됩니다.
#include <iostream>
using namespace std;
typedef struct team {
int score = 0, loss = 0;
double expect = 0;
}TEAM;
void simul();
void input(TEAM *ar);
double calcExpect(TEAM & t);
int main() {
int t = 0;
cin >> t;
while(t--)
simul();
return 0;
}
void simul() {
int n = 0, m = 0;
cin >> n >> m;
TEAM *ar = new TEAM[n];
for(int i = 0 ; i < m ; ++i)
input(ar);
double min = 1, max = 0;
for (int i = 0; i < n; ++i) {
ar[i].expect = calcExpect(ar[i]);
if (ar[i].expect < min) min = ar[i].expect;
if (ar[i].expect > max) max = ar[i].expect;
}
cout << (int)(max * 1000) << '\n' << (int)(min * 1000) << '\n';
}
void input(TEAM *ar) {
int a = 0, b = 0, p = 0, q = 0;
cin >> a >> b >> p >> q;
--a, --b;
ar[a].score += p;
ar[a].loss += q;
ar[b].score += q;
ar[b].loss += p;
}
double calcExpect(TEAM & t) {
if (t.score == 0 && t.loss == 0) return 0;
else {
int sqS = t.score * t.score, sqL = t.loss * t.loss;
return (double)(sqS) / (sqS + sqL);
}
}
3. 11068 회문인 숫자
숫자를 입력받고, 해당 숫자를 2~64진법으로 변환한 뒤 회문인지 검사합니다.
변환할 때는 mod 연산과 나누기 연산을 반복적으로 수행하고, 각 자리수를 배열에 저장합니다.
회문인지 검사할 때는 배열의 앞과 뒤가 같은지 비교하고, 재귀함수를 이용하여 안쪽도 비교하였습니다.
#include <iostream>
#include <cstring>
bool solve();
bool isPal(int *ar, int low, int high);
int main() {
int t;
std::cin >> t;
while (t--)
std::cout << solve() << '\n';
return 0;
}
bool solve() {
int n;
std::cin >> n;
for (int b = 2; b <= 64; ++b) {
int num = n, idx = 0;
int ar[21] = { 0 };;
while (num > 0) {
ar[++idx] = num % b;
num /= b;
}
if (isPal(ar, 1, idx))
return true;
}
return false;
}
bool isPal(int *ar, int low, int high) {
if (low >= high) return true;
if (ar[low] == ar[high]) return isPal(ar, low + 1, high - 1);
else return false;
}
4. 9012 괄호
괄호의 짝이 잘 맞는지 검사하는 문제입니다.
여는 괄호 '(' 가 들어오면 스택에 저장하고,
닫는 괄호 ')' 가 들어오면 스택에 있는 '(' 를 pop 해줍니다.
입력이 끝났을 때 스택이 비어있는 경우 "YES"를 출력하고,
입력 도중 스택이 비어있는데 ')' 가 들어오거나
입력이 끝났는데 스택이 비어있지 않은 경우 "NO"를 출력합니다.
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
cin.sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
stack<char> data;
string str;
cin >> str;
for (int i = 0; i < str.size(); ++i) {
if (str[i] == '(')
data.push(str[i]);
else {
if (!data.empty()) data.pop();
else {
data.push(str[i]);
break;
}
}
}
if (data.empty()) cout << "YES" << "\n";
else cout << "NO" << "\n";
}
return 0;
}
17-1 씨앗 6회차(5.15)
codeground 사이트의 Practice 부분에 있는 문제들을 풀었습니다.
https://goo.gl/yU7WUk
1. 숫자 골라내기
2. 프로그래밍 경진대회
3. 시험 공부
4. 다트게임
--------------------------
문제 풀이
1. 숫자 골라내기
홀수 번 나타난 숫자만 XOR 하라고 되어있지만,
모든 숫자들을 XOR 하면 짝수번 나온 숫자들은 XOR을 두 번 씩 하게 되어있어 결과에 영향을 미치지 못합니다.
따라서 모든 숫자들을 XOR 연산 한 결과를 출력하면 됩니다.
#include <cstdio>
#include <iostream>
using namespace std;
int main(int argc, char** argv) {
cin.sync_with_stdio(false);
int TC;
int test_case;
cin >> TC;
for (test_case = 1; test_case <= TC; test_case++) {
int n = 0, num = 0, tmp;
cin >> n;
while (n--) {
cin >> tmp;
num ^= tmp;
}
cout << "Case #" << test_case << '\n';
cout << num << '\n';
}
return 0;
}
3. 시험 공부
받을 수 있는 점수들을 배열에 저장하고, 내림차순 정렬한 뒤
0번째부터 k개 만큼의 점수를 sum에 누적하여 출력한다.
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
bool comp(const int& a,const int& b) {
return a > b;
}
int main(int argc, char** argv) {
cin.sync_with_stdio(false);
int TC;
int test_case;
cin >> TC;
for (test_case = 1; test_case <= TC; test_case++) {
int sum = 0;
int n, k;
int score[200000] = { 0 };
cin >> n >> k;
for (int i = 0; i < n; ++i)
cin >> score[i];
sort(score, score + n, comp);
for (int i = 0; i < k; ++i)
sum += score[i];
cout << "Case #" << test_case << '\n';
cout << sum << '\n';
}
return 0;
}
17-1 씨앗 5회차(5.1)
이전 시간에 배운 내용들에 대해 간단히 복슴 및 설명하였고,
아래의 문제들을 풀었습니다.
1. 11049 행렬 곱셈
2. 1780 종이의 개수
3. 1509 팰린드롬 분할
4. 11062 카드게임
모두 dp를 활용하여 푸는 문제입니다.
--------------------------
문제 풀이
1. 11049 행렬 곱셈
dp와 메모이제이션을 이용하여 행렬 곱셈의 최소 횟수를 구합니다.
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int ans[500][500];
int rc[501];
int solve(int low, int high);
int main() {
cin.sync_with_stdio(false);
int size;
cin >> size;
memset(ans, -1, sizeof(ans));
for (int i = 0; i < size; ++i)
cin >> rc[i] >> rc[i + 1];
cout << solve(0, size);
return 0;
}
int solve(int low, int high) {
if (low == high - 1) return 0;
int& ret = ans[low][high];
if (ret != -1) return ret;
ret = 2147483647;
for (int mid = low + 1; mid < high; ++mid)
ret = min(ret, solve(low, mid) + solve(mid, high) + rc[low] * rc[mid] * rc[high]);
return ret;
}
2. 1780 종이의 개수
재귀함수를 이용하여 문제를 작은 사이즈로 분할하는 과정을 통해 해답을 구할 수 있습니다.
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int ans[3];
int map[2187][2187];
void solve(pair<int, int> idx, int size);
int chkSame(pair<int, int> idx, int size);
int main() {
int size;
cin >> size;
for (int i = 0; i < size; ++i)
for (int j = 0; j < size; ++j)
cin >> map[i][j];
solve(make_pair(0,0), size);
for (int i = 0; i < 3; ++i)
cout << ans[i] << '\n';
return 0;
}
void solve(pair<int, int> idx, int size) {
int chk = chkSame(idx, size);
if (chk == 3) {
for (int i = idx.first; i < idx.first + size; i += size / 3)
for (int j = idx.second; j < idx.second + size; j += size / 3)
solve(make_pair(i, j), size / 3);
}
else
++ans[chk+1];
}
int chkSame(pair<int, int> idx, int size) {
for (int i = idx.first; i < idx.first + size; ++i)
for (int j = idx.second; j < idx.second + size; ++j)
if (map[idx.first][idx.second] != map[i][j])
return 3;
return map[idx.first][idx.second];
}
17-1 씨앗 4회차(4.10)
sort
pair
string
등 간단히 복습하거나 설명하였고 아래의 문제들을 풀었습니다.
1. 11726 2xn 타일링
2. 10164 격자상의 경로
3. 11051 이항 계수 2
4. 10942 팰린드롬
5. 9251 LCS
6. 10814 나이순 정렬
--------------------------
문제 풀이
1. 11726 2xn 타일링 은 지난주 풀었던 문제와 유사합니다. n번째까지 타일을 채우는 경우의 수를 dp(n) 이라 한다면 dp(n) = dp(n-1) + dp(n-2) 가 됩니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
2. 10164 격자상의 경로 는 동적계획법 문제입니다. r행 c열까지 가는 경우의 수를 dp(r, c)라 한다면 dp(r, c) = dp(r-1, c) + dp(r, c-1) 이 됩니다. 행 또는 열이 0일 경우에는 경우의 수가 1이 됩니다. 사이에 지나쳐야 하는 길이 주어지면 그 곳을 모서리로 두고 경우의 수를 2번 구해서 곱하면 됩니다.
|
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 |
|
3. 11051 이항 계수 2 는 이항 계수의 성질을 이용하여 이항 계수를 구하는 문제입니다. (n, k) = (n-1, k-1) + (n-1, k) 성질을 이용합니다. 여기에 메모이제이션 기법을 이용합니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
4. 10942 팰린드롬 문제도 동적계획법 문제입니다. 문자열 str의 인덱스 a부터 b까지가 회문(팰린드롬)인지 여부를 pal(a, b) 라고 한다면 pal(a, b) = pal(a+1, b-1) && str[a]==str[b] 라고 표현할 수 있습니다. 만약 a와 b가 엇갈린다면 재귀를 그만 호출해야 할 때이므로 a>=b 이상일 때는 true를 반환하도록 합니다.
|
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 |
|
5. 9251 LCS 문제도 동적계획법 문제입니다. 문자열 A의 인덱스 a까지, 그리고 문자열 B의 인덱스 b까지의 LCS를 lcs(a, b)라 한다면 lcs(a, b)는 lcs(a-1, b) 또는 lcs(a, b-1) 이상이여야 합니다. 혹은 lcs(a-1, b-1) + A[a]==B[b] 가 될 수 있습니다. 따라서 이 중 최대값을 구하면 됩니다. 식으로 표현하면 lcs(a, b) = max( lcs(a-1, b), lcs(a, b-1), lcs(a-1, b-1) + A[a]==B[b] ) 가 됩니다.
|
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 |
|
6. 10814 나이순 정렬 문제는 정렬 라이브러리를 쓰면 되는 문제입니다. 나이순으로 정렬하고, 나이가 같다면 가입한 순(입력된 순)으로 정렬하라고 합니다. 입력된 순서에 따라 일련번호를 부여하고 (나이, 일련번호, 이름) 으로 데이터를 엮어 정렬시키면 문제가 원하는 답이 나오게 됩니다.
|
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 |
|
17-1 씨앗 3회차(4.3)
클래스 개념 및 사용방법
vector 멤버함수 push_back, pop_back
반복자
for each문과 레퍼런스형
min, max, min_element, max_element
동적계획법
memset 함수
에 대해 간략하게 섦명을 했고 아래와 같은 문제들을 풀었습니다.
1. 1547 공
2. 2231 분해합
3. 2579 계단 오르기
4. 11727 2xn 타일링 2
5. 11055 가장 큰 증가 부분 수열
6. 1937 욕심쟁이 판다
-----------------------
문제풀이
1. 1547 공 문제는 마지막에 공이 든 컵의 위치만 확인하면 되므로 공의 위치만 계속 주목하면 됩니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
2. 2231 분해합 문제는 모든 수에 대해 해당 수의 생성자인지 확인해서 가장 작은 생성자를 구하면 되는 문제입니다. 또한 생성자가 없는 경우를 확인할 수 있도록 합니다. 생성자는 무조건 해당 수보다 작으므로 해당 범위에서만 반복하도록 합니다.
|
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 |
|
3. 2579 계단 오르기 문제는 동적계획법 문제입니다. n번째 계단까지 최대 점수를 dp(n)이라 하고 n번째 계단의 점수를 stair(n)이라 하면 dp(n)은 1번과 2번 조건들에 따라, dp(n-3)+stair(n-1)+stair(n) 또는 dp(n-2)+stair(n) 값이 됩니다. 두 값 중 최대값을 취하면 됩니다. 이를 메모이제이션을 이용해 구현하면 됩니다. n-3까지 참조하므로 n=0...2 는 직접 초기화해줍니다.
|
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 |
|
4. 11727 2xn 타일링 2 문제도 동적계획법 문제입니다. n번째 위치에 블럭을 채울 때 이전 까지 채운 경우의 수를 이용하는 방법을 생각하면 됩니다. n번째 위치에 블럭을 채워넣는 경우의 수를 dp(n) 이라고 한다면, 넣을 수 있는 블럭 모양을 고려하면 dp(n-1) 과 dp(n-2) 그리고 dp(n-2) 가 있을 수 있습니다. 경우의 수이므로 이것들의 합이 dp(n)이 되므로 dp(n-1) + 2*dp(n-2) 가 구해집니다. 이를 메모이제이션으로 구현하면 됩니다.
|
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 |
|
5. 11055 가장 큰 증가 부분 수열 문제도 동적계획법 문제입니다. n번째 인덱스를 포함하는 n번째 인덱스까지의 최대 증가 부분 수열의 길이를 dp(n) 이라고 하고 수열의 n번째 인덱스 값을 seq(n) 이라 한다면, dp(n) = dp(k) + 1 (단, k는 k<n 그리고 seq(k)<seq(n) 을 만족하는 수) 입니다. 만약 만족하는 k가 없더라도 자신을 포함하면 적어도 길이는 1이 됩니다. 이것을 그대로 코드로 구현합니다.
|
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 |
|
6. 1937 욕심쟁이 판다 문제도 동적계획법으로 해결 가능하다. dp(r, c) 를 r행 c열에 판다를 풀었을 때 최대로 살아남을 수 있는 일수라 가정합니다. 판다는 적어도 하루는 살 수 있고, 인접한 r2행 c2열이 해당지역보다 대나무가 적다면 그 지역의 dp 값보다 하루는 더 살 수 있습니다. 따라서 r행 c열에서의 대나무의 양을 map(r, c)라 한다면 dp(r, c) = dp(r2, c2) + 1 (단, r2행 c2열은 r행 c열에 인접하고 map(r, c) > map(r2, c2)를 만족) 이 됩니다. 이를 메모이제이션을 이용하여 구현합니다.
|
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 |
|
17-1 씨앗 2회차(3.27)
1. 2751 수 정렬하기 2
2. 1181 단어 정렬
3. 10989 수 정렬하기 3
4. 1057 토너먼트
5. 10453 문자열 변환
6. 2448 별찍기 - 11
위의 문제들을 풀었습니다. ( boj.kr/문제번호 )
//////// 풀이
1. 수 정렬하기 2
2751 문제는 수를 정렬하는 문제로, 데이터의 크기가 최대 10만이므로 시간복잡도가 O(nlogn)인 정렬방법으로 처리해야합니다. 병합정렬, 퀵정렬을 구현하거나 라이브러리를 사용하면 됩니다. 위는 병합정렬을 구현한 코드, 아래는 라이브러리를 사용한 코드입니다.
#include
#include
using namespace std;
void mergeSort(vector& arr) {
if (arr.size() <= 1) return;
int mid = arr.size() / 2;
vector front(arr.begin(), arr.begin() + mid);
vector back(arr.begin() + mid, arr.end());
mergeSort(front);
mergeSort(back);
auto frontIt = front.begin();
auto backIt = back.begin();
for (int& d : arr) {
if (frontIt != front.end() && (backIt == back.end() || *frontIt <= *backIt)) {
d = *frontIt;
++frontIt;;
}
else {
d = *backIt;
++backIt;
}
}
}
int main(void) {
cin.sync_with_stdio(false);
int n;
cin >> n;
vector arr(n);
for (int& d : arr)
cin >> d;
mergeSort(arr);
for (int d : arr)
cout << d << '\n';
return 0;
}
#include
#include
using namespace std;
int arr[1000000];
int main(void) {
cin.sync_with_stdio(false);
int n;
cin >> n;
for(int i=0; i cin >> arr[i];
sort(arr, arr+n);
for(int i=0; i cout << arr[i] << '\n';
return 0;
}
2. 단어정렬
하라는대로 문자열을 입력받고, 제시한 규칙대로 정렬하면 됩니다.
#include
#include
#include
using namespace std;
bool comp(const string& str1, const string& str2) {
if(str1.size()==str2.size())
return str1 < str2;
else
return str1.size() < str2.size();
}
string str[20000];
int main(void) {
cin.sync_with_stdio(false);
int n;
cin >> n;
for(int i=0; i cin >> str[i];
sort(str, str+n, comp);
for(int i=0; i if(i==0 || str[i]!=str[i-1])
cout << str[i] << '\n';
}
return 0;
}
3. 수 정렬하기 3
들어오는 각 데이터의 범위는 10000 이하의 자연수로 좁고, 크기는 1000만으로 매우 큽니다. 따라서 후자가 아닌 전자에 초점을 맞춰서 구현합니다. 코드에서는 카운팅 정렬을 사용하였습니다.
#include
using namespace std;
int cnt[10001];
int main(void) {
cin.sync_with_stdio(false);
int n;
cin >> n;
for(int i=0; i int num;
cin >> num;
++cnt[num];
}
for(int i=1; i<=10000; ++i) {
while(cnt[i]) {
cout << i << '\n';
--cnt[i];
}
}
return 0;
}
4. 토너먼트
선수 번호를 1부터가 아닌 0부터 생각합니다. 선수 번호를 처음에 2로 나눴을 때 값이 같아지면 첫 번째 라운드에
만난다는 것이고, 한번 더 해야 같아진다면 두 번째 라운드에, 한번 더 해야 같아진다면 세 번째 라운드...로 가는 방식입니다. 이것을 그대로 코드로 옮깁니다.
#include
using namespace std;
int main(void) {
int a, b;
cin >> a >> a >> b;
--a, --b;
int cnt = 0;
while(a!=b) {
a/=2;
b/=2;
++cnt;
}
cout << cnt << endl;
return 0;
}
5. 문자열 변환
좋은 문자열의 조건을 잘 보면 문자열의 모든 인덱스에 대해 해당 인덱스 이하에서 a의 수가 b의 수 이하이면 좋은 문자열이 됨을 알 수 있다. 또한 a와 b만으로 이루어져 있으므로 인접한 두 문자를 스왑하는 것을 한 문자를 이동하는 것으로 이해해도 무방하다. 좋은 문자열 A, B에 대해서 A문자열의 a들을 한칸씩 움직여 B로 만든다고 한다. 이 때 a 문자들을 하나씩 대칭시킨다고 가정하면 각 위치들의 차이의 합이 최소로 옮기는 횟수가 될 것이다. 또한 두 문자열 모두 좋은 문자열이기에 각 문자를 옮기는 과정 중에도 좋은 문자열임은 보장된다.(첫줄 참고)
#include
#include
#include
using namespace std;
int pos1[50001];
int pos2[50001];
int main(void) {
int t;
cin >> t;
while(t--) {
string a,b;
cin >> a >> b;
int pos1Cnt=0, pos2Cnt=0;
for(int i=0; i if(a[i]=='a') {
pos1[pos1Cnt] = i;
++pos1Cnt;
}
}
for(int i=0; i if(b[i]=='a') {
pos2[pos2Cnt] = i;
++pos2Cnt;
}
}
if(pos1Cnt!=pos2Cnt)
cout << -1 << endl;
else {
long long ans = 0;
for(int i=0; i ans += abs(pos1[i]-pos2[i]);
cout << ans << endl;
}
}
return 0;
}
6. 별찍기 - 11
전형적인 재귀함수 문제이다. 프랙탈을 참고
#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> outBuf;
void draw(int r, int c, int n) {
if (n == 3) {
outBuf[r][c + 2] = '*';
outBuf[r + 1][c + 1] = outBuf[r + 1][c + 3] = '*';
for (int i = 0; i < 5; ++i)
outBuf[r + 2][c + i] = '*';
}
else {
draw(r, c + (n / 2), n / 2);
draw(r + (n / 2), c, n / 2);
draw(r + (n / 2), c + n, n / 2);
}
}
int main(void) {
int N;
cin >> N;
int width = N * 2 - 1;
outBuf.resize(N, string(width, ' '));
for (int i = 0; i < N; ++i)
outBuf[i].resize(width, ' ');
draw(0, 0, N);
for (int i = 0; i < N; ++i)
cout << outBuf[i] << '\n';
return 0;
}
17-1 씨앗 1회차(3.20)
3월 20일에는 다음과 같은 문제를 풀었습니다.(문제출처 boj.kr)
1. 1000 A+B
2. 11721 열 개씩 끊어 출력하기
3. 1003 피보나치 함수
4. 11501 주식
5. 2309 일곱 난쟁이
6. 11866 조세퍼스 문제 0
7. 2580 스도쿠
8. 11062 카드 게임
// 풀이
// 풀이 언어는 C++이지만, 대부분 C언어를 이용하여 처리하였습니다.
1. A+B의 경우에는 별도로 풀이하지 않겠습니다.
2. 열 개씩 끊어 출력하기는 문자를 입력받고 하나씩 출력하며 카운트를 해서, 카운트가 10이 되는 순간 개행('\n')을 해주면 되는 문제입니다.
#include <stdio.h>
int main() {
char str[101];
scanf("%s", str);
int cnt = 0;
for(int i=0; str[i]!='\0'; ++i) {
printf("%c", str[i]);
++cnt;
if(cnt==10) {
printf("\n");
cnt = 0;
}
}
return 0;
}
3. 피보나치 함수는 fibonachi(N)을 호출할 때, 0과 1이 각각 몇번 구해지는지, 즉 fibonachi(0)과 fibonachi(1)로 표현할 때 계수가 어떻게 되는지 묻는 문제입니다. 공책에 조금 끄적여보면 fibonachi(N)에서 fibonachi(0)의 계수는 fibonachi(N-2)이고 fibonachi(1)의 계수는 fibonachi(N-1)이 되는 것을 알 수 있습니다. 이것을 이용하여 코드를 짜면 됩니다.
#include <stdio.h>
int main() {
int fibo[40] = {1,1};
for(int i=2; i<40; ++i)
fibo[i] = fibo[i-2] + fibo[i-1];
int t;
scanf("%d", &t);
while(t--) {
int n;
scanf("%d", &n);
if(n==0) printf("1 0\n");
else if(n==1) printf("0 1\n");
else printf("%d %d\n", fibo[n-2], fibo[n-1]);
}
return 0;
}
4. 주식 문제는 N일동안 주식을 사고팔 때 최대 이익을 구하는 문제입니다. 이 때 i번째날 주식을 사고 팔때 최대이익이 되는 방법은 그 이후의 날의 주식 중 최대일 때 파는 것입니다. 따라서 i번째 날의 주식을 stock(i) 라 하고 이 날의 주식으로 얻을 수 있는 최대 이익을 max_profit(i), i번째 날부터 마지막 날까지의 최대 주식값을 max_from(i) 라고 한다면 max_profit(i) = stock(i) - max_from(i) 가 됩니다. 이 때 max_from(i)를 매번 계산하면 총 연산횟수는 최대 100만*100만, 약 1조로 추측할 수 있고 이는 1억번을 1초라고 보면 시간 제한을 아득히 넘어갑니다. 따라서 max_from(i)를 구할 때는 max_from(i) = max(stock(i), max_from(i+1)) 임을 이용해서 중복된 계산을 없애야합니다. 이하는 구현코드입니다.
#include <stdio.h>
int s[1000001];
int main() {
int t;
scanf("%d", &t);
while(t--) {
int n;
scanf("%d", &n);
for(int i=0; i<n; ++i)
scanf("%d", s+i);
int ms = 0;
long long ans = 0;
for(int i=n-1; i>=0; --i) {
if(ms < s[i]) ms = s[i];
ans += ms - s[i];
}
printf("%lld\n", ans);
}
return 0;
}
5. 일곱 난쟁이 문제는 모든 경우의 수를 검사하면 되는 문제입니다. 아홉명 중 일곱의 합이 100이 되는걸 찾든지, 아홉명의 합에 둘의 합을 뺀 것이 100을 되는 것을 찾아도 됩니다. 아래의 코드는 전자로 구현한 것입니다.
#include <stdio.h>
#include <algorithm>
int h[9];
int ans[7];
int solve(int until, int sum, int selected) {
// return 1 == 이게 정답, return 0 == 정답이 아님
if(sum==100 && selected==7)
return 1;
for(int next=until+1; next<9; ++next) {
ans[selected] = h[next];
if(solve(next, sum+h[next], selected+1)==1)
return 1;
}
return 0;
}
int main() {
for(int i=0; i<9; ++i)
scanf("%d", h+i);
solve(-1, 0, 0);
std::sort(ans, ans+7);
for(int i=0; i<7; ++i)
printf("%d\n", ans[i]);
return 0;
}
6. 조세퍼스 문제0 은 큐, 혹은 리스트를 이용하는 문제입니다. 그러나 해당 문제는 데이터셋이 적으므로 큐나 리스트를 사용하지 않고 배열에 잡고 하여도 시간 안에 통과가 가능합니다. 큐를 사용하는 것이 빠르고 알기도 쉽지만, 아직 배우지 않았기에 배열을 이용하여 해결하였습니다. 배열에서 사용한 방법은 사람 수만큼 배열을 잡고, 초기값을 0, 사람이 제거되었다면 -1을 넣고 커서를 하나씩 옮겨가며 카운트하는 것입니다.
#include <stdio.h>
int arr[1001];
int ans[1001];
int main(void) {
int n, m;
scanf("%d %d", &n, &m);
int cnt = 1, cur = 0, completed = 0;
while(completed<n) {
// 카운트가 됐는지 검사, 처리
if(cnt==m) {
ans[completed] = cur;
++completed;
cnt = 0;
arr[cur] = -1;
}
// 커서+1
cur = (cur + 1) % n;
if(arr[cur]==0) ++cnt;
}
printf("<");
for(int i=0; i<n; ++i) {
printf("%d", ans[i]+1);
if(i!=n-1)
printf(", ");
}
printf(">");
return 0;
}
7. 스도쿠는 백트로킹 문제입니다. 백트래킹이란 기본적으로 모든 경우의 수를 탐색해나가지만, 탐색하는 도중 이 줄기가 정답일 가능성이 전혀 없다면 해당 줄기를 무시하고 되돌아가 다음 경우의 수를 탐색하는 방법입니다. 아래의 test가 조건이 맞는지, 정답일 가능성이 있는지 전혀 없는지 판단하는 함수입니다.
#include <stdio.h>
int s[9][9];
int empty[81][2]; // row. col
int emptyCnt;
int test(int row, int col, int n) {
for(int r=0; r<9; ++r)
if(s[r][col]==n) return 0;
for(int c=0; c<9; ++c)
if(s[row][c]==n) return 0;
int rs = row/3*3;
int cs = col/3*3;
int re = rs+3;
int ce = cs+3;
for(int r=rs; r<re; ++r)
for(int c=cs; c<ce; ++c)
if(s[r][c]==n) return 0;
return 1;
}
int solve(int present) {
// return==1 성공, return==0 실패
if(present >= emptyCnt) return 1;
int row = empty[present][0];
int col = empty[present][1];
for(int n=1; n<=9; ++n) {
if(test(row, col, n)==1) {
s[row][col] = n;
if(solve(present+1)==1)
return 1;
s[row][col] = 0;
}
}
return 0;
}
int main(void) {
for(int r=0; r<9; ++r) {
for(int c=0; c<9; ++c) {
scanf("%d", &s[r][c]);
if(s[r][c]==0) {
empty[emptyCnt][0] = r;
empty[emptyCnt][1] = c;
++emptyCnt;
}
}
}
solve(0);
for(int r=0; r<9; ++r) {
for(int c=0; c<9; ++c)
printf("%d ", s[r][c]);
printf("\n");
}
return 0;
}
8. 카드 게임은 동적계획법 문제입니다. 동적계획법에 하나의 문제를 그 문제와 동일한 형태의 부분 문제로 나누어 해결하는 방법입니다. 이러한 문제는 점화식을 찾는게 키 포인트가 됩니다. 카드의 점수가 적힌 배열 card[MAX_NUM]에 대해 선수를 가질 때 최대 점수를 dp(left, right) 라고 가정한다면, 카드를 뽑는 것은 제일 왼쪽, 혹은 제일 오른쪽의 2가지 뿐이므로 dp(left, right)는 sum(left, right) - dp(left+1, right) 와 sum(left, right - dp(left, right-1) 중 최대값이 됩니다.(sum(left, right)은 left부터 right까지의 카드의 점수의 합) 또 dp(left, right)가 left==right라면 card[left]가 되는 것을 알 수 있습니다. 이 2가지를 이용하여 코드를 작성합니다.
#include <stdio.h>
#include <algorithm>
#include <string.h>
int card[1001];
int dp[1001][1001]; // 초기값 -1
int max_profit(int left, int right, int sum) {
if(left==right) return card[left];
if(dp[left][right]!=-1) return dp[left][right];
return dp[left][right] = std::max(
sum - max_profit(left+1, right, sum-card[left]),
sum - max_profit(left, right-1, sum-card[right])
);
}
int main(void) {
int t;
scanf("%d", &t);
while(t--) {
memset(dp, -1, sizeof(dp));
int n;
scanf("%d", &n);
int sum = 0;
for(int i=0; i<n; ++i) {
scanf("%d", card+i);
sum += card[i];
}
int ans = max_profit(0, n-1, sum);
printf("%d\n", ans);
}
return 0;
}
씨앗 11월 17일
프로그램 명: lotto
독일 로또에서는 1 에서 49 까지의 수 중 6 개를 고른다.
당첨되는 확률이 높아지는 것은 아니지만 로또의 일반적인 전략은 원소의 개수가 K 인 전체 집합 S 에서 6 개의 원소를 가지는 모든 부분집합 중에서 하나를 고르는 것이다.
예를 들어 , k = 8 이고 S = {1,2,3,5,8,13,21,34} 인 경우 6 개의 원소를 가지는 부분집합은 28 개가 있다.
[1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ... [3,5,8,13,21,34].
수 k 와 집합 S 가 주어질 때 가능한 모든 경우를 모두 출력하는 것이 문제이다.
입력
k 는 6 이상 13 이하의 정수이다. 다음으로 k 개의 수 S 가 주어진다. S 는 오름차순 순으로 입력된다.
출력
사전식으로 먼저 나오는 순으로 출력한다.
입출력 예
입력 7 1 2 3 4 5 6 7 출력 1 2 3 4 5 6 1 2 3 4 5 7 1 2 3 4 6 7 1 2 3 5 6 7 1 2 4 5 6 7 1 3 4 5 6 7 2 3 4 5 6 7 입력 8 1 2 3 5 8 13 21 34 출력 1 2 3 5 8 13 1 2 3 5 8 21 1 2 3 5 8 34 1 2 3 5 13 21 1 2 3 5 13 34 1 2 3 5 21 34 1 2 3 8 13 21 1 2 3 8 13 34 1 2 3 8 21 34 1 2 3 13 21 34 1 2 5 8 13 21 1 2 5 8 13 34 1 2 5 8 21 34 1 2 5 13 21 34 1 2 8 13 21 34 1 3 5 8 13 21 1 3 5 8 13 34 1 3 5 8 21 34 1 3 5 13 21 34 1 3 8 13 21 34 1 5 8 13 21 34 2 3 5 8 13 21 2 3 5 8 13 34 2 3 5 8 21 34 2 3 5 13 21 34 2 3 8 13 21 34 2 5 8 13 21 34 3 5 8 13 21 34
출처: Ulm Local 1996
int main(void)
{
int a,b,c,d,e,f,i;
int k,s[14];
scanf("%d",&k);
for(i=1;i<=k;++i)
scanf("%d",&s[i]);
for( a = 1 ; a <= k ; ++a)
for( b = a + 1 ; b <= k ; ++b)
for( c = b + 1 ; c <= k ; ++c)
for( d = c + 1 ; d <= k ; ++d)
for( e = d + 1 ; e <= k ; ++e)
for( f = e + 1 ; f <= k ; ++f)
printf("%d %d %d %d %d %d\n",s[a],s[b],s[c],s[d],s[e],s[f]);
}
Nikky 와 Byron 체육시간에 게임을 하고 있다.
선생님이 Nikky 에게는 a 보 전진 후에 b 보 후퇴하게 , Byron 에게는 c 보 전진 후 d 보 후퇴하는 작업을 반복적으로 하게 했다.
둘은 같은 보폭을 가지고 한 보폭당 걸리는 시간이 같다.
s 스텝 이후 선생님이 휘슬을 분 경우 둘 중 누가 처음 위치보다 멀리 가 있는가를 알아내는 프로그램을 하라.
입력
5 개의 정수 a,b,c,d,s 가 주어진다.
단, a,b,c,d 는 100 이하의 정수이고 a > b , c > d 이고 s 는 10000 이하의 정수이다.
출력
세 가지 중 하나를 출력한다.
- Nikky
- Byron
- Tied
입출력 예
입력 4 2 5 3 12 출력 Byron
입출력 보충
Nikky 는 12 스텝 후의 상태는 4 - 2 + 4 - 2 즉 첫 위치에서 4 스텝 만큼 떨어지고 Byron 는 5 - 3 + 4 즉 6 스텝 떨어져서 Byron 이 더 멀리 떨어져 있다.
출처:uwaterloo junior
#include <stdlib.h>
using namespace std;
int main(void)
{
int a, b, c, d, n, r, n2, r2, s;
cin >> a >> b >> c >> d >> s;
n = s % (a + b);
r = s % (c + d);
n2 = abs( a - b + (n<a ? n : a+b-n));
r2 = abs( c - d + (r<c ? r : c+d-r));
cout << (
n2 > r2 ? "Nikky" :
n2 < r2 ? "Byron" :
"Tied"
) << endl;
}