algospot.com/judge/problem/read/QUADTREE

 

algospot.com :: QUADTREE

쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적

algospot.com

<풀이>

1. 쿼드 트리로 압축된 문자열을 입력받는다.

2. 입력받은 쿼드 트리를 상하로 뒤집은 쿼드 트리를 출력한다.

 

<해법>

1. 쿼드 트리를 상하로 뒤집는 방법

=> 쿼드 트리를 상하로 뒤집었을 경우, 쿼드 트리의 순서는 x(아래 왼쪽)(아래 오른쪽)(위 왼쪽)(위 오른쪽)이 됩니다. 따라서, 압축된 쿼드 트리를 복원할 필요 없이, 각 부분의 압축된 문자열을 알아낸 후 위 순서에 따라 재배치를 해주면 됩니다.

 

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 <string>
 
using namespace std;
 
string str;
int pos;
string answer;
 
string quadtree() {
 
    char cur = str[pos++];
 
    //b나 w일 경우 해당 부분 완료
    if (cur == 'b' || cur == 'w') {
        return string(1, cur);
    }
 
    //4부분 나눠서 해결
    string upLeft = quadtree();
    string upRight = quadtree();
    string downLeft = quadtree();
    string downRight = quadtree();
 
    //상하로 뒤집었을 때의 순서
    return "x" + downLeft + downRight + upLeft + upRight;
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        str = "";
        pos = 0;
        answer = "";
 
        //입력
        cin >> str;
 
        //해법
        answer = quadtree();
 
        //출력
        cout << answer << "\n";
    }
 
    //종료
    return 0;
}
 

 

분할 정복에 대해 알아볼 수 있는 문제였습니다.

아래 문제를 응용한 것이 위 문제라고 생각합니다. 아래 문제도 풀어보는 것도 도움이 될 것 같습니다!

www.acmicpc.net/problem/1992

 

1992번: 쿼드트리

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

www.acmicpc.net

 

저작자표시

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

[C++] Algospot - 시계 맞추기(CLOCKSYNC)  (0) 2021.01.11
[C++] Algospot - 게임판 덮기(BOARDCOVER)  (0) 2021.01.07
[C++] Algospot - 소풍(PICNIC)  (0) 2021.01.06

www.algospot.com/judge/problem/read/CLOCKSYNC

 

algospot.com :: CLOCKSYNC

Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록

www.algospot.com

<풀이>

1. 16개 시계를 입력받는다.

2. 각 버튼을 0~3번씩 누르는 모든 경우를 시뮬레이션 해본다.

3. 가장 적게 버튼을 누른 횟수를 출력한다.

 

<해법>

1. 모든 경우를 다 해보는 방법

=> 모든 경우를 다 해야하므로 브루트 포스를 사용해야 합니다. 그 이후 어떤 방식을 다 해봐야 할지 고민해봐야 합니다. 곰곰히 생각해보면, 중요한 것은 버튼을 누르는 순서가 아닌 횟수라는 것을 알 수 있습니다. 그 횟수 또한 0에서 최대 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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <string>
#include <string.h>
 
using namespace std;
 
int clocks[16];
int playClocks[16];
string button[10] = {
    "xxx.............", //0번 버튼
    "...x...x.x.x....", //1번 버튼
    "....x.....x...xx", //2번 버튼
    "x...xxxx........", //...
    "......xxx.x.x...",
    "x.x...........xx",
    "...x..........xx",
    "....xx.x......xx",
    ".xxxxx..........",
    "...xxx...x...x.."
};
//0~9번 버튼을 몇 번 눌러야 하는지 저장하는 배열
int btnCnt[10];
int answer;
 
void makeClock(int index, int totalCount) {
 
    //정답보다 많은 스위치를 눌러야할 경우 -> 종료
    if (answer != -1 && answer <= totalCount) {
        return;
    }
 
    //종료 조건 : 10개의 버튼을 몇 번 눌러야할지 모두 정한 경우
    if (index == 10) {
 
        //시뮬레이션 위해 복사
        memcpy(playClocks, clocks, sizeof(playClocks));
 
        //시뮬레이션
        for (int i = 0; i < 10; i++) {
            int btn = i;
            int count = btnCnt[i];
 
            for (int j = 0; j < 16; j++) {
                if (button[btn][j] == 'x') {
                    playClocks[j] += 3 * count;
                }
            }
        }
 
        //모두 12시를 가르키는지 확인
        bool canAnswer = true;
        for (int i = 0; i < 16; i++) {
            if (playClocks[i] % 12 != 0) {
                canAnswer = false;
                break;
            }
        }
 
        //결과 갱신
        if (canAnswer) {
            if (answer == -1 || totalCount < answer) {
                answer = totalCount;
            }
        }
 
        return;
    }
 
    //0~3번 누르는 모든 경우 해보기
    for (int i = 0; i < 4; i++) {
        btnCnt[index] = i;
        makeClock(index + 1, totalCount + i);
    }
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        memset(clocks, 0, sizeof(clocks));
        memset(btnCnt, 0, sizeof(btnCnt));
        answer = -1;
 
        //입력
        for (int i = 0; i < 16; i++) {
            cin >> clocks[i];
        }
 
        //해법
        /*
        각 스위치마다 몇 번씩 눌러야 하는지 정하고,
        각 경우마다 모두 시뮬레이션
        */
        makeClock(0, 0);
 
        //출력
        cout << answer << "\n";
    }
 
    //종료
    return 0;
}

 

브루트포스, 구현, 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] Algospot - 쿼드 트리 뒤집기(QUADTREE)  (0) 2021.01.13
[C++] Algospot - 게임판 덮기(BOARDCOVER)  (0) 2021.01.07
[C++] Algospot - 소풍(PICNIC)  (0) 2021.01.06

www.algospot.com/judge/problem/read/BOARDCOVER

 

algospot.com :: BOARDCOVER

게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이

www.algospot.com

<풀이>

1. 보드를 입력받는다.

2. 해당 보드를 제시된 블록들로 채울 수 있는 모든 경우의 수를 출력한다.

 

<해법>

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
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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <iostream>
#include <string>
#include <string.h>
 
using namespace std;
 
//구조체 : 좌표
struct pos {
    int x, y;
};
 
int H, W;
char map[20][20];
int answer;
 
//4개 블록의 좌표
pos block[4][3] = {
    {{0,0}, {0,1}, {1,0}},  //①
    {{0,0}, {1,0}, {1,-1}}, //②
    {{0,0}, {1,0}, {1,1}},  //③
    {{0,0}, {0,1}, {1,1}}   //④
};
 
int countWhite() {
    int count = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (map[i][j] == '.') {
                count++;
            }
        }
    }
    return count;
}
 
pos firstWhitePos() {
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (map[i][j] == '.') {
                return { i, j };
            }
        }
    }
}
 
bool isTypeAble(pos p, int type) {
 
    for (int i = 0; i < 3; i++) {
        int x = p.x + block[type][i].x;
        int y = p.y + block[type][i].y;
 
        if (x < 0 || y < 0 || x >= H || y >= W) {
            return false;
        }
 
        if (map[x][y] == '#') {
            return false;
        }
    }
 
    return true;
 
}
 
void colorBoard(pos p, int type, char color) {
 
    for (int i = 0; i < 3; i++) {
        int x = p.x + block[type][i].x;
        int y = p.y + block[type][i].y;
 
        map[x][y] = color;
    }
 
}
 
void boardCover(int remainCnt) {
    
    //종료 조건 : 블록을 모두 놓은 경우
    if (remainCnt == 0) {
        answer++;
        return;
    }
 
    //칠해할 흰색 부분(가장 첫 번째 등장한 흰색)
    pos cur = firstWhitePos();
 
    //4개의 블록 타입 모두 넣어보기
    for (int type = 0; type < 4; type++) {
 
        //타입을 칠할 수 있다면
        if (isTypeAble(cur, type)) {
            
            //검정색으로 칠하기
            colorBoard(cur, type, '#');
 
            //재귀 호출
            boardCover(remainCnt - 1);
 
            //흰색으로 다시 칠하기
            colorBoard(cur, type, '.');
        }
    }
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        H = 0, W = 0;
        memset(map, '#', sizeof(map));
        answer = 0;
 
        //입력
        cin >> H >> W;
        for (int i = 0; i < H; i++) {
            string tmp;
            cin >> tmp;
            for (int j = 0; j < W; j++) {
                map[i][j] = tmp[j];
            }
        }
 
        //해법
        /*
        모두 검정색으로 채워져 있는 경우 or 흰색 개수 3의 배수 아닌 경우 -> 탐색X
        나머지 경우는 블록을 모두 놓아본다
        */
        if (countWhite() != 0 && countWhite() % 3 == 0) {
            boardCover(countWhite() / 3);
        }
 
        //결과 출력
        cout << answer << "\n";
    }
 
    //종료
    return 0;
}
 

 

브루트포스와 구현에 대해 알아볼 수 있는 문제였습니다.

위 문제에서 구현이 어렵다고 생각되시면, 아래 문제를 먼저 풀어보시는 것도 도움이 될 것 같습니다!

www.acmicpc.net/problem/14500

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변

www.acmicpc.net

 

저작자표시

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

[C++] Algospot - 쿼드 트리 뒤집기(QUADTREE)  (0) 2021.01.13
[C++] Algospot - 시계 맞추기(CLOCKSYNC)  (0) 2021.01.11
[C++] Algospot - 소풍(PICNIC)  (0) 2021.01.06

www.algospot.com/judge/problem/read/PICNIC

 

algospot.com :: PICNIC

소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로

www.algospot.com

<풀이>

1. 학생 수와 친구 정보를 입력받는다.

2. 모든 학생의 짝을 지으면서, 서로 친구인지 확인한다.

3. 짝이 모두 지어진 경우의 개수를 출력한다.

 

<해법>

1. 모든 학생의 짝을 지을 때, 중복을 처리하는 방법

=> 모든 학생의 짝을 지을 때, 다음과 같은 중복들이 있습니다. 학생 수는 6명이라고 가정하겠습니다.

 

첫 번째는, (0 1), (2 3), (4 5)로 짝을 짓고, (1 0), (3 2), (5 4)로 또 짝을 짓는 경우입니다. 친구끼리 순서는 상관이 없기 때문에 중복됩니다. 

두 번째는, (0 1), (2 3), (4 5)로 짝을 짓고, (2 3), (4 5), (0 1)로 또 짝을 짓는 경우입니다. 짝끼리 순서는 상관이 없기 때문에 중복됩니다.

 

저는 이 문제를 풀기 전에, '수학적으로 어떻게 풀었지?'를 먼저 생각하였습니다.

'짝 개수를 찾는 경우의 수를 어떻게 구했더라?'

 

(6C2 x 4C2 x 2C2) / 3! 이었습니다.

 

위 수식에서 중복의 힌트를 얻었습니다. 

6C2에서 C는 첫 번째 중복의 경우를 제거합니다. 친구끼리 순서는 상관이 없으므로, C(조합)을 사용합니다.

3!은 두 번째 중복의 경우를 제거합니다. 짝 끼리 순서는 상관이 없으므로, 3개의 짝을 세우는 순서(3!)로 나눕니다.

 

그렇다면 코드로 두 개의 중복을 어떻게 제거해야 할까요?

 

첫 번째 중복의 제거는 '앞의 친구가 무조건 숫자가 더 작다'의 로직을 사용합니다. (0 1)은 가능하지만 (1 0)은 불가능하게 만드는 것입니다.

두 번째 중복의 제거는 '앞 짝의 첫 번째 친구의 숫자가 더 작다'의 로직을 사용합니다. (0 1), (2 3)은 가능하지만 (2 3), (0 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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <string.h>
 
using namespace std;
 
int n, m;
bool areFriendsMap[10][10];
bool visited[10];
int answer;
 
//모든 친구쌍 만들어 보기
void makeFriends(int pairCnt) {
 
    //종료조건 : 친구쌍을 모두 만들었을 경우
    if (pairCnt == n / 2) {
        answer++;
        return;
    }
 
    //짝을 찾아야할 다음 친구 찾기(번호가 가장 작은 친구) -> 분모의 3! 부분
    int firstPerson = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            firstPerson = i;
            break;
        }
    }
 
    //친구의 짝 찾기 -> 6C2, 4C2, 2C2의 C(조합) 부분
    for (int i = firstPerson + 1; i < n; i++) {
 
        //짝이 없고, 둘이 친구인 경우 -> 짝 만들기
        if (!visited[i] && areFriendsMap[firstPerson][i]) {
 
            visited[firstPerson] = true, visited[i] = true;
 
            makeFriends(pairCnt + 1);
 
            visited[firstPerson] = false, visited[i] = false;        
        }
    }
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
        
        //초기화
        n = 0; m = 0;
        memset(areFriendsMap, false, sizeof(areFriendsMap));
        memset(visited, false, sizeof(visited));
        answer = 0;
 
        //입력
        cin >> n >> m;
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            areFriendsMap[a][b] = true; areFriendsMap[b][a] = true;
        }
 
        //해법
        /*
        가능한 친구쌍 모두 만들어보기
        */
        makeFriends(0);
 
        //출력
        cout << answer << "\n";
    }
 
    //종료
    return 0;
}
 

 

브루트포스에 대해 알아볼 수 있는 문제였습니다.

저작자표시

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

[C++] Algospot - 쿼드 트리 뒤집기(QUADTREE)  (0) 2021.01.13
[C++] Algospot - 시계 맞추기(CLOCKSYNC)  (0) 2021.01.11
[C++] Algospot - 게임판 덮기(BOARDCOVER)  (0) 2021.01.07

+ Recent posts

티스토리툴바