'분류 전체보기' 카테고리의 글 목록 (28 Page)

분류 전체보기

[C++] 백준 1992 - 쿼드트리

2020. 4. 27. 20:42

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

1992번: 쿼드트리

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

www.acmicpc.net

<풀이>

1. 주어진 영상을 입력받는다.

2. 영상이 모두 0 또는 1로 되어있을 경우 값을 저장한다.

3. 모두 0 또는 1이 아닐경우 영상을 4개로 나눈다.

4. 2,3번을 종료될 때까지 반복진행한다.(재귀함수)

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

#include <iostream>
#include <vector>
using namespace std;
 
int N;
int map[64][64];
vector<char> res;
 
void go(int n, int x, int y) {
 
    //부분이 모두 0 또는 1 인지 검사
    bool allZero = true;
    bool allOne = true;
 
    for (int i = x; i < x + n; i++) {
        for (int j = y; j < y + n; j++) {
            if (map[i][j] == 1) {
                allZero = false;
            }
            else {
                allOne = false;
            }
        }
    }
 
    //종료조건
    if (allZero || allOne) {
        if (allZero) {
            res.push_back('0');
        }
        else {
            res.push_back('1');
        }
        return;
    }
 
    //4부분 탐색
    res.push_back('(');
    go(n / 2, x, y);
    go(n / 2, x, y + (n / 2));
    go(n / 2, x + (n / 2), y);
    go(n / 2, x + (n / 2), y + (n / 2));
    res.push_back(')');
 
    return;
}
 
int main() {
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf_s("%1d", &map[i][j]);
        }
    }
 
    //go(변길이, 시작지점 i, 시작지점 j)
    go(N, 0, 0);
 
    //출력
    for (int i = 0; i < res.size(); i++) {
        cout << res[i];
    }
}
 

재귀함수에 대해 알아볼 수 있는 문제였습니다.

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

[C++] 백준 3987 - 보이저 1호 (0)	2020.04.30
[C++] 백준 2437 - 저울 (2)	2020.04.30
[C++] 백준 2436 - 공약수 (0)	2020.04.27
[C++] 백준 2559 - 수열 (0)	2020.04.27
[C++] 백준 2467 - 용액 (0)	2020.04.27

[C++] 백준 2436 - 공약수

2020. 4. 27. 20:37

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

2436번: 공약수

첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,000,000 이하이다.

www.acmicpc.net

<풀이>

1. 최대공약수 최소공배수를 입력받고, 최소공배수를 최대공약수로 나눈 숫자를 구한다.

2. 그 숫자들의 약수 짝(두 약수를 곱해서 다시 그 숫자가 되는 두 수)을 구한다.

3. 약수 짝이 서로소인 것을 구한다.

4. 약수 짝(두 수)에 각각 최대공약수를 곱하면, 정답이 가능한 두 수가 된다.

5. 가능한 두 수 중 합이 가장 작은 것을 출력한다.

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 <iostream>
#include <cmath>
using namespace std;
 
long long int gcd, lcm, tmp;
long long int resA = 0, resB = 0;
 
int main() {
 
    //입력
    cin >> gcd >> lcm;
 
    //tmp = 최소공배수 / 최대공약수
    tmp = lcm / gcd;
 
    //tmp의 약수 두 수 구하고, 서로소인지 판별
    for (long long int i = 1; i * i <= tmp; i++) {
        if (tmp % i == 0) {
            //약수 두 수
            long long int tmpA = i;
            long long int tmpB = tmp / i;
 
            //약수 두 수가 서로소인지 판별
            bool isAble = true;
            long long int cnt = 0;
            for (long long int j = 1; j <= tmpA; j++) {
                if (tmpA % j == 0 && tmpB % j == 0) {
                    cnt++;
                }
                //약수의 개수가 1개보다 많은 경우 불가능
                if (cnt > 1) {
                    isAble = false;
                    break;
                }
            }
 
            //가능한 경우 중 가장 마지막에 저장되는 값이 합이 가장 작게된다
            if (isAble) {
                resA = tmpA * gcd;
                resB = tmpB * gcd;
            }
        }
    }
 
    //출력
    cout << resA << " " << resB << "\n";
}
 

최대공약수, 최소공배수에 대해 알아볼 수 있는 문제였습니다.

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

[C++] 백준 2437 - 저울 (2)	2020.04.30
[C++] 백준 1992 - 쿼드트리 (0)	2020.04.27
[C++] 백준 2559 - 수열 (0)	2020.04.27
[C++] 백준 2467 - 용액 (0)	2020.04.27
[C++] 백준 2468 - 안전 영역 (0)	2020.04.27

[C++] 백준 2559 - 수열

2020. 4. 27. 20:33

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

2559번: 수열

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.

www.acmicpc.net

<풀이>

1. 숫자 N개 중 K개의 합을 처음부터 끝까지 모두 확인해보고 최댓값을 갱신한다.

<해법>

1. 배열 처음~끝까지 K개의 합을 비교하는 방법

=> 투 포인터 활용한다. 부분집합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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <iostream>
using namespace std;
 
const int MAX = 100000 + 1;
 
int arr[MAX];
long long int res;
 
int main() {
 
    int N, K;
 
    //입력
    cin >> N >> K;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    //초기 배열1 설정
    int s = 0;
    long long int sum = 0;
    for (int i = s; i < s+K; i++) {
        sum += arr[i];
    }
    res = sum;
 
    //배열 탐색
    while (true) {
        //기존 합에 앞에 부분을 뺀다
        sum -= arr[s];
        //배열의 범위를 벗어날 경우
        if (s+K >= N) {
            break;
        }
        //합에 뒷부분을 더한다
        sum += arr[s+K];
        if (sum > res) {
            res = sum;
        }
        //다음 배열 index
        s++;
    }
 
    //출력
    cout << res;
}

투포인터에 대해 알아볼 수 있는 문제였습니다.

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

[C++] 백준 1992 - 쿼드트리 (0)	2020.04.27
[C++] 백준 2436 - 공약수 (0)	2020.04.27
[C++] 백준 2467 - 용액 (0)	2020.04.27
[C++] 백준 2468 - 안전 영역 (0)	2020.04.27
[C++] 백준 2469 - 사다리 타기 (0)	2020.04.27

[C++] 백준 2467 - 용액

2020. 4. 27. 20:26

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

2467번: 용액

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 서로 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

www.acmicpc.net

<풀이>

1. 용액 배열 양쪽에서 다가오면서, 두 개의 합이 0에 가장 가까울 경우 저장해준다.

2. 두 개의 합이 0 보다 작을 경우, 조금 더 0보다 가까운 경우가 있는지 알아보기 위해 왼쪽에서 다가오는 index를 하나 늘려준다.

3. 두 개의 합이 0보다 클 경우, 조금 더 0보다 가까운 경우가 있는지 알아보기 위해 오른쪽에서 다가오는 index를 하나 줄여준다.

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;
 
const int MAX = 100000 + 1;
 
int N;
long long int arr[MAX];
long long int resA, resB;
 
int main() {
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    //양쪽에서 다가오는 index의 초기값
    int left = 0;
    int right = N - 1;
 
    //결과값의 초기값
    int resLiquid = abs(arr[left] + arr[right]);
    resA = arr[left];
    resB = arr[right];
 
    //양쪽에서 다가오는 반복, 모든 경우 탐색 완료시 종료
    while (left < right) {
        int tmpLiquid = arr[left] + arr[right];
        if (abs(tmpLiquid) < resLiquid) {
            resLiquid = abs(tmpLiquid);
            resA = arr[left];
            resB = arr[right];
        }
 
        if (tmpLiquid < 0) {
            left++;
        }
        else {
            right--;
        }
    }
 
    //출력
    cout << resA << " " << resB << "\n";
}
 

투포인터에 대해 알아볼 수 있는 문제였습니다.

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

[C++] 백준 1992 - 쿼드트리 (0)	2020.04.27
[C++] 백준 2436 - 공약수 (0)	2020.04.27
[C++] 백준 2559 - 수열 (0)	2020.04.27
[C++] 백준 2468 - 안전 영역 (0)	2020.04.27
[C++] 백준 2469 - 사다리 타기 (0)	2020.04.27

[C++] 백준 2468 - 안전 영역

2020. 4. 27. 20:21

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

2468번: 안전 영역

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어

www.acmicpc.net

<풀이>

1. 가능한 비의 높이마다 맵 탐색(BFS) 후, 안전영역 개수 구한다.

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

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
struct field {
    //영역 좌표
    int x, y;
};
 
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int N;
int map[100][100];
bool visited[100][100];
queue<field> q;
int tmpRes;
int res = 0;
 
void bfs(int rain) {
    while (!q.empty()) {
        field cur = q.front();
        q.pop();
 
        //4방향 모두 탐색
        for (int i = 0; i < 4; i++) {
            field nxt = cur;
 
            nxt.x += di[i];
            nxt.y += dj[i];
 
            //범위를 벗어나는 경우 continue
            if (nxt.x < 0 || nxt.y < 0 || nxt.x >= N || nxt.y >= N) {
                continue;
            }
 
            //안전한 곳만 큐에 담기
            if (map[nxt.x][nxt.y] > rain && !visited[nxt.x][nxt.y]) {
                visited[nxt.x][nxt.y] = true;
                q.push(nxt);
            }
        }
    }
}
 
int main() {
 
    //입력
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
 
    //가능한 비의 높이마다 탐색
    for (int rain = 0; rain < 100; rain++) {
 
        //비 높이 때 사용되는 변수들 초기화
        memset(visited, false, sizeof(visited));
        tmpRes = 0;
 
        //맵 완전탐색
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                //안전한 곳 큐에 담고 bfs, 안전영역 찾기
                if (map[i][j] > rain && !visited[i][j]) {
                    field start;
                    start.x = i;
                    start.y = j;
 
                    q.push(start);
                    visited[start.x][start.y] = true;
                    bfs(rain);
 
                    //한 곳에서 안전한 영역을 찾으면, 안전영역++
                    tmpRes++;
                }
            }
        }
 
        //최대 안전영역 개수 저장
        res = max(tmpRes, res);
    }
 
    //출력
    cout << res << "\n";
}

BFS에 대해 알아볼 수 있는 문제였습니다.

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

[C++] 백준 1992 - 쿼드트리 (0)	2020.04.27
[C++] 백준 2436 - 공약수 (0)	2020.04.27
[C++] 백준 2559 - 수열 (0)	2020.04.27
[C++] 백준 2467 - 용액 (0)	2020.04.27
[C++] 백준 2469 - 사다리 타기 (0)	2020.04.27

[C++] 백준 2469 - 사다리 타기

2020. 4. 27. 20:16

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

2469번: 사다리 타기

첫 줄에는 참가한 사람의 수 k가 나온다(3≤k≤26). 그 다음 줄에는 가로 막대가 놓일 전체 가로 줄의 수를 나타내는 n이 나온다(3≤n≤1,000). 그리고 세 번째 줄에는 사다리를 타고 난 후 결정된 참가자들의 최종 순서가 길이 k인 대문자 문자열로 들어온다. k와 n, 그리고 도착순서 문자열이 나타난 다음, 이어지는 n개의 줄에는 앞서 설명한 바와 같이 ‘*’와 ‘-’ 문자로 이루어진 길이 k-1인 문자열이 주어진다. 그 중 감추어진 가로 줄

www.acmicpc.net

<풀이>

1. 사다리 시작 알파벳 문자순서와 사다리 종료 알파벳 문자순서를 알고 있으므로, '?'전까지 위와 아래에서 각각 알파벳 문자순서를 수정한다.

2. 위에서 내려온 문자순서와 아래에서 올라온 문자순서를 비교한다.

3. 문자가 같다면 '*', 순서가 서로 교차되어 같다면 '-', 그 외의 경우라면 불가능한 경우이다.

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

#include <iostream>
using namespace std;
 
int k, n;
char map[1000][25];
char up[26];
char down[26];
char q[25];
int qLine;
bool isAble = true;
 
int main() {
 
    //입력
    cin >> k >> n;
    for (int i = 0; i < k; i++) {
        up[i] = 'A' + i;
        cin >> down[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k - 1; j++) {
            cin >> map[i][j];
            if (map[i][j] == '?') {
                qLine = i;
            }
        }
    }
 
    //위에서부터 '?'전까지 문자 순서 바꾸기
    for (int i = 0; i < qLine; i++) {
        for (int j = 0; j < k - 1; j++) {
            if (map[i][j] == '-') {
                char tmp = up[j];
                up[j] = up[j + 1];
                up[j + 1] = tmp;
            }
        }
    }
 
    //아래에서부터 '?'전까지 문자 순서 바꾸기
    for (int i = n - 1; i > qLine; i--) {
        for (int j = 0; j < k - 1; j++) {
            if (map[i][j] == '-') {
                char tmp = down[j];
                down[j] = down[j + 1];
                down[j + 1] = tmp;
            }
        }
    }
 
    //위에 문자열, 아래 문자열 비교
    for (int i = 0; i < k - 1; i++) {
 
        //위에 문자 == 아래 문자 : *
        if (up[i] == down[i]) {
            q[i] = '*';
        }
        // 1 2 // 2 1 처럼 교차 : -
        else if (up[i] == down[i + 1] && up[i + 1] == down[i]) {
            q[i] = '-';
            char tmp = up[i];
            up[i] = up[i + 1];
            up[i + 1] = tmp;
        }
        //위에 두경우가 아닐경우 : x
        else {
            isAble = false;
            break;
        }
    }
 
    //출력
    if (isAble) {
        for (int i = 0; i < k - 1; i++) {
            cout << q[i];
        }
        cout << "\n";
    }
    else {
        for (int i = 0; i < k - 1; i++) {
            cout << 'x';
        }
        cout << "\n";
    }
}
 

구현에 대해 알아볼 수 있는 문제였습니다.

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

[C++] 백준 1992 - 쿼드트리 (0)	2020.04.27
[C++] 백준 2436 - 공약수 (0)	2020.04.27
[C++] 백준 2559 - 수열 (0)	2020.04.27
[C++] 백준 2467 - 용액 (0)	2020.04.27
[C++] 백준 2468 - 안전 영역 (0)	2020.04.27

PREV 1 ···25 26 27 28 NEXT

알고리즘 고수가 되기까지