https://www.acmicpc.net/problem/15688


위 문제를 counting sort로 구현해 봤다.


주어지는 수의 절댓값이 1,000,000 이하이기 때문에 배열의 인덱스를 활용할 때 음수 처리를 위해 1000000을 더해준 인덱스에 저장한다.


1의 갯수는 1000001에 저장되는 것이다. 


따라서 출력할 때, 1000000을 빼고 출력해주면 된다.


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<algorithm>
#include<vector>
using namespace std;
int arr[2000001];
bool cmp(int a, int b) {
    return a > b;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        arr[num + 1000000]++; // 저거 뺴고 출력하면 됨
    }
    for (int i = 0; i <= 2000000; i++) {
        while (arr[i]--)
            cout << i - 1000000 << '\n';
    }
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'Computer Science > Algorithm Theory' 카테고리의 다른 글

버블 정렬 알고리즘 구현 (C++)  (0) 2019.08.28
선택 정렬 알고리즘 구현 (C++)  (0) 2019.08.28
최대 공약수 gcd, 최소 공배수 lcm  (0) 2019.08.19
기하 및 그래프 알고리즘 간단 정리  (0) 2019.08.17
선분 교차 판별  (0) 2019.08.11

https://www.acmicpc.net/problem/17140



열이든 행이든 연산 하나를 제대로 구현하면, 나머지 하나는 똑같다.


보통 개수를 셀 때, cnt[m[i]]++ 이런 방식으로 세는데, 이 경우에는 1회 이상 등장한 숫자의 개수도 함께 필요하고,


이 수들의 빈도와 수 자체를 가지고 정렬을 해야하기 때문에 다른 방식을 사용했다.



먼저 map을 사용해서 숫자별 개수를 기록했다. 이후에 벡터에 pair 형태로 옮기면서 정렬했다.



주의할 것이, 중간에 R연산을 할 때는 열의 길이가 갱신되고, C연산을 할 때는 행의 길이가 갱신되는데, 따라서 연산을 시작할 당시의 값으로 반복문의 범위를 잡아줘야, 중간에 반복문의 범위가 바뀌는 것을 방지할 수 있다.



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
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
 
using namespace std;
typedef pair<int, int> pii;
 
int r, c, k, m[101][101], cnt[101], rnum = 3, cnum = 3;
map<int, int> mp;
vector<pii> v;
 
bool cmp(pii a, pii b) {
    if (a.second < b.second) return true;
    else if (a.second == b.second) {
        return a.first < b.first;
    }
    else return false;
}
 
void rOpr() {
    int curC = cnum; //연산 중간에 행길이를 갱신할 것이기 때문에 시작값 저장
    for (int i = 1; i <= rnum; i++) {
        for (int j = 1; j <= curC; j++) {
            if (m[i][j] == 0) continue;
            mp[m[i][j]]++;
        }
        
        for (map<int, int>::iterator itr = mp.begin(); itr != mp.end(); itr++)
            v.push_back({ itr->first, itr->second });
 
        sort(v.begin(), v.end(), cmp);
 
        int vSize = v.size();
        if (v.size() >= 50) vSize = 50; //100개까지만 취하도록
        for (int j = 0; j < vSize; j++) {
            m[i][2*j+1] = v[j].first;
            m[i][2*j+2] = v[j].second;
        }
        
        for (int j = vSize * 2 + 1; j <= curC; j++)
            m[i][j] = 0; // 원래 길이보다 짧아지면, 이전 것을 0으로 만들어줘야 함
 
        if (cnum < vSize * 2) cnum = vSize * 2; //최대 길이 갱신
        
        mp.clear();
        v.clear();
    
    }
}
 
void cOpr() {
    int curR = rnum;
    for (int i = 1; i <= cnum; i++) {
        for (int j = 1; j <= curR; j++) {
            if (m[j][i] == 0) continue;
            mp[m[j][i]]++;
        }
 
        for (map<int, int>::iterator itr = mp.begin(); itr != mp.end(); itr++)
            v.push_back({ itr->first, itr->second });
 
        sort(v.begin(), v.end(), cmp);
 
        int vSize = v.size();
        if (v.size() >= 50) vSize = 50;
        for (int j = 0; j < vSize; j++) {
            m[2 * j + 1][i] = v[j].first;
            m[2 * j + 2][i] = v[j].second;
        }
 
        for (int j = vSize * 2 + 1; j <= curR; j++)
            m[j][i] = 0;
 
        if (rnum < vSize * 2) rnum = vSize * 2;
 
        mp.clear();
        v.clear();
 
    }
}
int main(void) {
    cin >> r >> c >> k;
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            cin >> m[i][j];
 
    int time = 0;
    for (time = 0; time <= 100; time++) {
    
        if (m[r][c] == k) break; //종료 조건
        if (rnum >= cnum)  //r연산
            rOpr();
        
        else 
            cOpr();
    }
 
    if (time == 101) cout << -1;
    else cout << time;
 
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 1158번 조세퍼스 문제 (C++)  (0) 2019.08.24
백준 11053번 가장 긴 증가하는 부분 수열 (C++)  (0) 2019.08.24
백준 15684번: 사다리 조작 (C++)  (0) 2019.08.23
백준 16637번: 괄호 추가하기 (C++)  (0) 2019.08.21
백준 17135번: 캐슬 디펜스 (C++)  (0) 2019.08.21

https://www.acmicpc.net/problem/15684



초기 사다리의 정보를 입력받은 이후에, 사다리를 추가로 놓을 수 있는 곳들을 모두 찾아서 3개 이하로 사다리를 놓아보고, 문제에서 정해준 조건대로 i번에서 출발하면 i번 라인으로 도착할 수 있는지를 확인해주면 된다.




사다리를 모두 놓아보는 방법에는 여러가지가 있을 것 같은데, 본인은 먼저 사다리 하나를 놓을 수 있는 모든 경우를 찾아서 벡터에 담았다.



그리고 문제에서 3개 이하로만 확인하면 된다고 했기 때문에, 0개부터 3개까지 사다리를 놓아보고, i열에서 출발해서 i열로 도착할 수 있는지를 확인했다.



사다리를 놓을 수 있는 최솟값을 찾는 것이기 때문에, 중간에 어떤 경우라도 조건을 만족하면, 탐색을 멈추고 답을 출력한다.



사다리를 놓아볼 때는, 가령 (1,3) (1,4)에 놓아지는 사다리를 추가할 때는, 당연하게도 (1,4)에서 출발하는 사다리를 놓을 수 없기 때문에 이에 맞는 처리를 해주면 된다.


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
#include<iostream>
#include<vector>
using namespace std;
typedef pair<int, int> pii;
int col, m, row, map[31][11], st = 0;
bool isused[31][11], ansUpdate = false;
vector<pii> v;
int ans = -1;
 
void btk(int k, int num) {
    if (k == num) { //사다리의 개수
        
        bool suc = true; //답을 찾았는지
        for (int i = 1; i <= col; i++) {
            pii pos = { 1, i }; //출발 지점
            bool isFirst = true; //true면 가로로 이동, false면 세로로 이동
            while (pos.first <= row) {
                
                if (map[pos.first][pos.second] != 0) { //가로 사다리 만나면
                    if (isFirst == true) { //가로이동 할 차례
                        pos.second = map[pos.first][pos.second];
                        isFirst = false; //다음엔 세로 이동 하도록
                        
                    }
                    else { //세로로 이동할 차례
                        isFirst = true; //다음엔 가로로 이동하도록
                        pos.first++;
                        
                    }
                }
                else 
                    pos.first++; //가로 사다리가 없는 곳이면 아래로 이동
                
            }
            if (pos.second != i) { //출발점과 도착지점의 열값이 다르면 실패
                suc = false;
                break;
            }
        }
        if (suc) {
            ansUpdate = true;
            ans = num;
        }
        return;
    }
    if (k == 0) st = 0;
    for (int i = st; i < v.size(); i++) {
        int r = v[i].first; //r,c와 r,c+1이 사다리
        int c = v[i].second;
        if (!isused[r][c] && !isused[r][c + 1]) {
            isused[r][c] = true;
            isused[r][c + 1] = true;
            st = i;
            map[r][c] = c + 1; //r,c에서 사다리를 보면 r, c+1로 이동
            map[r][c + 1] = c; //위와 반대
            btk(k + 1, num);
            if (ansUpdate) return; //정답 찾으면 백트레킹 그만
            isused[r][c] = false;
            isused[r][c + 1] = false;
            map[r][c] = 0;
            map[r][c + 1] = 0;
        }
    }
}
int main(void) {
    cin >> col >> m >> row;
    for (int i = 0; i < m; i++) {
        int rw, st;
        cin >> rw >> st;
        map[rw][st] = st + 1;
        map[rw][st + 1] = st;
    }
 
    for (int i = 1; i <= row; i++) 
        for (int j = 1; j <= col; j++) 
            if (map[i][j] != 0)
                isused[i][j] = true; //처음부터 가로 사다리가 놓여진 곳
    
 
    //가로막대 놓을 수 있는 곳 찾아서 벡터에 시작점만 담기
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col - 1; j++) { //어짜피 가장 끝 열에는 사다리를 둘 수 없으니까 col -1
            if (!isused[i][j] && !isused[i][j + 1]) {
                isused[i][j] = true;
                isused[i][j + 1] = true;
                v.push_back({ i, j });
                isused[i][j] = false;
                isused[i][j + 1] = false;
            }
        }
    }
    
    
    for (int i = 0; i <= 3; i++) {
        if (ansUpdate) break; //최솟값 찾는 거니까 하나라도 찾으면 그만
        btk(0, i);
    }
    printf("%d", ans);
    return 0;
}
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 11053번 가장 긴 증가하는 부분 수열 (C++)  (0) 2019.08.24
백준 17140번: 이차원 배열과 연산 (C++)  (0) 2019.08.23
백준 16637번: 괄호 추가하기 (C++)  (0) 2019.08.21
백준 17135번: 캐슬 디펜스 (C++)  (0) 2019.08.21
백준 17406번: 배열돌리기4 (C++)  (0) 2019.08.20

https://www.acmicpc.net/problem/16637



중요한 부분은


1. 수식의 길이를 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
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
#include<iostream>
#include<string>
#include<limits.h>
#include<vector>
 
using namespace std;
typedef long long ll;
int n, maxBrac, arr[20], st = 1, num[20];
vector<ll> numV; //피연산자
vector<char> oprV; //연산자
 
char opr[20];
string cmd;
bool isused[20], picked[20], done[20];
int ans = -1 * INT_MAX;
 
void init() {
    for (int i = 0; i < n; i++) {
        picked[i] = false;
        done[i] = false;
    }
}
ll cal(int a, char op, int b) { //계산 과정에서 int 범위를 벗어날 수 있다
    if (op == '+')
        return (ll)(a + b);
    else if (op == '*')
        return (ll)(a*b);
    else if (op == '-')
        return (ll)(a - b);
}
void btk(int k, int maxBr) {
    if (k == maxBr) {
        for (int i = 0; i < maxBr; i++) {
        
            picked[arr[i]-1] = true;
            picked[arr[i]] = true;
            picked[arr[i]+1] = true;
        }
        
        for (int i = 0; i < n; i++) { //괄호로 묶인 값들 계산하면서 연산자, 피연산자 벡터에 삽입
            if (!picked[i]) {
                if (num[i] != -1)
                    numV.push_back(num[i]);
                else
                    oprV.push_back(opr[i]);
            }
            else if(picked[i]){
                if (done[i]) continue;
                else {
                    numV.push_back(cal(num[i], opr[i + 1], num[i + 2]));
                    done[i] = true;
                    done[i + 1] = true;
                    done[i + 2] = true;
                }
            }
        }
 
        ll res = numV[0]; //수식 계산
        for (int i = 1; i < numV.size(); i++) {
            res = cal(res, oprV[i - 1], numV[i]);
        }
    
        if (ans < res) ans = res;
        init();
        oprV.clear();
        numV.clear();
        return;
    }
    if (k == 0) st = 1;
    for (int i = st; i < n; i += 2) {
        if (!isused[i]) {
            arr[k] = i;
            st = i;
            isused[i] = true;
            isused[i + 2] = true; //연산자를 선택하면, 바로 인접한 연산자는 고를 수 없음
            btk(k + 1, maxBr);
            isused[i + 2] = false;
            isused[i] = false;
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> cmd;
 
    maxBrac = (n + 1) / 4; //수식의 길이가 n일 때, 넣을 수 있는 괄호의 최대 개수
    for (int i = 0; i < cmd.length(); i++) {
        if (i % 2 == 0) num[i] = cmd[i]-'0'; //입력은 문자로 들어온다
        else {
            opr[i] = cmd[i];
            num[i] = -1; //입력이 음수가 들어오는 경우는 없으므로 -1로 초기화
        }
    }
    for(int i = 0 ; i <= maxBrac ; i++)
        btk(0, i);
    cout << ans;
    return 0;
}
 
cs


저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글

백준 17140번: 이차원 배열과 연산 (C++)  (0) 2019.08.23
백준 15684번: 사다리 조작 (C++)  (0) 2019.08.23
백준 17135번: 캐슬 디펜스 (C++)  (0) 2019.08.21
백준 17406번: 배열돌리기4 (C++)  (0) 2019.08.20
백준 11053번 가장 긴 증가하는 부분 수열 (C++)  (0) 2019.08.19

https://www.acmicpc.net/problem/16637


백준 16637번 괄호 추가하기라는 문제인데, 이 문제를 풀면서 했던 뻘짓을 기록해두려고 한다.


3+8*2 이런 문자열이 있다고 할 때, 결과값을 내도록 구현하려면 어떻게 해야할까?


그냥 str[0] ~ str끝까지 한 문자 한 문자 확인하려고 생각하는 순간 굉장히 피곤해진다.


324 + 232 이런 경우처럼, 한 자리수가 아닌 숫자가 존재할 수 있기 때문이다. 처음에 이렇게 접근했다가, 결과적으로 아래와 같은 뻘짓을 하게 되었다.


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
string calculate(int a, char opt, int b) {
 
    if (opt == '+') return to_string(a + b);
 
    else if (opt == '-') return to_string(a - b);
    else
        return to_string((ll)(a*b));
}
int makeAns(string cur) {
    if (cur.length() == 0) return 0;
    int res = stoi(cur.substr(0, 1));
    for (int i = 1; i < cur.length() - 1; i++) {
        if (cur[i] - '0' < INT_MAX && cur[i] - '0' > -1 * INT_MAX) continue;
        if (!(cur[i] - '0' < INT_MAX && cur[i] - '0' > -1 * INT_MAX)) {
            if (cur[i + 1] - '0' < INT_MAX && cur[i + 1] - '0' > -1 * INT_MAX) {
                res += stoi(calculate(res, cur[i], stoi(cur.substr(i + 1, 1))));
            }
            else {
                i++;
                res += stoi(calculate(res, cur[i], -1 * stoi(cur.substr(i + 2, 1))));
            }
        }
    }
    cout << "계산결과 : " << res << '\n';
}
void process() {
    string str = "";
    for (int i = 0; i < n; i++) {
        if (!picked[i]) str += cmd[i];
        else {
            if (done[i]) continue;
            else {
                int a, b;
                a = stoi(cmd.substr(i, 1));
                b = stoi(cmd.substr(i + 2, 1));
                str += calculate(a, cmd[i + 1], b);
                done[i] = true;
                done[i + 1] = true;
                done[i + 2] = true;
            }
        }
    }
    cout << str << '\n';
 
 
}
cs



위와 같은 뻘짓을 하지 않으려면, 연산자와 피연산자를 분리해서 벡터(배열)에 저장하고 있으면 된다. 연산하기가 훨씬 수월하다.


1
2
3
4
ll res = numV[0];
        for (int i = 1; i < numV.size(); i++) {
            res = cal(res, oprV[i - 1], numV[i]);
        }
cs


이렇게 간단하게 계산할 수 있다.


정상적인 수식이라면, 연산자의 개수가 피연산자의 개수보다 하나 적을 것이므로, 깔끔하게 위와 같은 반복문을 만들어낼 수 있다.



저작자표시 비영리 변경금지

'알고리즘 문제 풀이 > 오답' 카테고리의 다른 글

백준 2251번: 물통 (C++)  (0) 2019.08.31
백준 1525번: 퍼즐 (C++)  (0) 2019.08.30
[오답] 카카오 2018 블라인드 테스트: 무지의 먹방 라이브 C++  (0) 2019.08.20
[오답] 백준 1941 소문난 칠공주 C++  (0) 2019.08.10
[오답] 백준 1799번: 비숍 (C++)  (0) 2019.07.24

+ Recent posts

티스토리툴바