[문제 링크]

 

algospot.com :: QUADTREE

쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N × 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다. 이 그림의 모든

algospot.com

분할정복 알고리즘 부분은 교재에 나와있는 소스코드와 동일하다.

다만 책에서 설명이 안되어있는데, 매개변수로 반복자를 참조하기 위해서는 비 const 반복자를 전달해야한다.

tree.begin() 이 반환하는 반복자는 const 반복자이므로 따로 비 const 반복자를 선언하고 tree.begin()으로 초기화해줘야 한다는 점만 주의하면 될 것 같다.

#include <iostream>
#include <string>
using namespace std;

string Reverse(string::iterator& iter)

{

    char head = *iter;

    iter++;

    if (head == 'w' || head == 'b') return string(1, head);

 

    string upperLeft = Reverse(iter);

    string upperRight = Reverse(iter);

    string lowLeft = Reverse(iter);

    string lowRight = Reverse(iter);

 

    return string("x") + lowLeft + lowRight + upperLeft + upperRight;

}

int main(void)

{

    int testcase;

    cin >> testcase;

    string tree;

    while (testcase--)

    {

        cin >> tree;

        string::iterator iter = tree.begin();

        cout << Reverse(iter) << endl;

    }

}

Colored by Color Scripter

 

알고리즘 200일 프로젝트 - 34day

저작자표시 비영리

'알고리즘 > algospot' 카테고리의 다른 글

알고리즘 문제해결전략 예제: 외발 뛰기 (ID: JUMPGAME)  (0) 2020.05.22
알고리즘 문제해결전략 문제7.4 울타리 잘라내기 (ID: FENCE)  (0) 2020.05.09
알고리즘 문제해결전략 문제6.8 시계 맞추기(ID: CLOCKSYNC)  (0) 2020.04.10
알고리즘 문제해결전략 문제6.5 게임판 덮기(ID: BOARDCOVER)  (0) 2020.04.09
알고리즘 문제해결전략 문제6.3 소풍(ID: PICNIC)  (0) 2020.04.09

[문제 링크]

 

2966번: 찍기

문제 상근이, 창영이, 현진이는 역사와 전통을 자랑하는 Sogang ACM-ICPC Team에 가입하려고 한다. 하지만, 가입하려고 하는 모든 지원자는 C언어 필기시험을 통과해야 한다. 이들은 C언어를 할 줄 모른다. 따라서, 필기시험을 모두 찍으려고 한다. 상근이는 A, B, C, A, B, C, A, B, C, A, B, C, ...와 같이 찍어야 통과할 수 있다고 생각한다.  하지만, 창영이는 B, A, B, C, B, A, B, C, B, A, B

www.acmicpc.net

string 컨테이너와 반복자를 사용하여 손쉽게 해결한 문제였다.

Adrian의 찍는 순서는 "ABC", Bruno의 찍는 순서는 "BABC", Goran의 찍는 순서는 "CCAABB" 임을 알 수 있기 때문에

찍는 순서를 string에 저장하고 반복자를 한칸씩 증가시키는 방법으로 입력된 문자열과 비교하였다.

 
#include <iostream>
#include <string>
using namespace std;
 
int max(const int a, const int b)
{
    return a > b ? a : b;
}
int max(const int a, const int b, const int c)
{
    return a > max(b, c) ? a : max(b, c);
}
int main(void)
{
    int len, AdrCnt = 0, BruCnt = 0, GoCnt = 0;
    string problem, Adrian("ABC"), Bruno("BABC"), Goran("CCAABB");
    cin >> len >> problem;
 
    string::iterator AdrIter = Adrian.begin(), BruIter = Bruno.begin(), GoIter = Goran.begin();
    for (int i = 0; i < len; i++)
    {
        if (problem[i] == *AdrIter++) AdrCnt++;
        if (AdrIter == Adrian.end()) AdrIter = Adrian.begin();
 
        if (problem[i] == *BruIter++) BruCnt++;
        if (BruIter == Bruno.end()) BruIter = Bruno.begin();
 
        if (problem[i] == *GoIter++) GoCnt++;
        if (GoIter == Goran.end()) GoIter = Goran.begin();
    }
 
    int maxNum = max(AdrCnt, BruCnt, GoCnt);
    cout << maxNum << endl;
    if (AdrCnt == maxNum) cout << "Adrian" << endl;
    if (BruCnt == maxNum) cout << "Bruno" << endl;
    if (GoCnt == maxNum) cout << "Goran" << endl;
    
    return 0;
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
 

알고리즘 200일 프로젝트 - 32day

저작자표시 비영리

'알고리즘 > BOJ' 카테고리의 다른 글

백준 1074번: Z  (2) 2020.05.12
백준 11729번: 하노이 탑 이동 순서  (0) 2020.05.11
백준 4641번: Doubles  (0) 2020.05.06
백준 2858번: 기숙사 바닥  (0) 2020.05.05
백준 1405번: 미친 로봇  (0) 2020.05.03

[문제 링크]

 

4641번: Doubles

문제 2~15개의 서로 다른 자연수로 이루어진 리스트가 있을 때, 이들 중 리스트 안에 자신의 정확히 2배인 수가 있는 수의 개수를 구하여라. 예를 들어, 리스트가 "1 4 3 2 9 7 18 22"라면 2가 1의 2배, 4가 2의 2배, 18이 9의 2배이므로 답은 3이다. 입력 입력은 여러 개의 테스트 케이스로 주어져 있으며, 입력의 끝에는 -1이 하나 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 2~15개의 서로 다른 자연수가 주어진다.

www.acmicpc.net

 

입력받은 숫자들을 전부 vector에 담아 2중 for문을 돌려도 정답은 쉽게 찾을 수 있겠지만, 효율성을 늘리기 위해 하나의 for문을 사용하는 쪽으로 구현하였다.

자연수의 최대값이 100을 넘지 않기 때문에 계수정렬을 이용하였고, for_each 함수를 사용하여 벡터에 담긴 모든 원소를 탐색하였다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
 
int numberCnt[101], result;
 
void Pred(const int a)
{
    result += numberCnt[a*2];
}
int main(void)
{
    vector<int> v;
    while (1)
    {
        result = 0;
        memset(numberCnt, 0, sizeof(numberCnt));
        while (1)
        {
            int num;
            cin >> num;
            if (num == -1) return 0;
            else if (num == 0) break;
            v.push_back(num);
            numberCnt[num]++;
        }
        for_each(v.begin(), v.end(), Pred);
        v.clear();
        cout << result << endl;
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

알고리즘 200일 프로젝트 - 32day

저작자표시 비영리

'알고리즘 > BOJ' 카테고리의 다른 글

백준 11729번: 하노이 탑 이동 순서  (0) 2020.05.11
백준 2966번: 찍기  (0) 2020.05.06
백준 2858번: 기숙사 바닥  (0) 2020.05.05
백준 1405번: 미친 로봇  (0) 2020.05.03
백준 1213번: 팰린드롬 만들기  (0) 2020.04.30

[문제 링크]

 

2858번: 기숙사 바닥

문제 상근이는 기숙사 생활을 한다. 상근이의 방의 크기는 L*W 이다. 수업시간에 타일 채우기 경우의 수를 계산하던 상근이는 자신의 방도 1*1크기 타일로 채우려고 한다. 이때, 가장자리는 빨간��

www.acmicpc.net

갈색타일(B)의 개수는 빨간타일(R)이 몇 줄로 이루어져 있느냐에 따라 달라진다.

따라서 빨간타일(R)이 1줄 일 때 부터 (R/2)줄 까지 갈색타일 개수를 구하고 입력받은 B와 일치할 때 결과를 출력해주면 원하는 정답을 얻을 수 있다.

#include <iostream>
using namespace std;
 
int main(void)
{
    int R, B;
    cin >> R >> B;
    int i = 0;
    while (++i)
    {
        if (B % i == 0)
        {
            int row = B / i;
            if ((row + i + 2) * 2 == R)
            {
                cout << row + 2 << ' ' << i + 2 << endl;
                break;
            }
        }
        else continue;
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

알고리즘 200일 프로젝트 - 31day

저작자표시 비영리

'알고리즘 > BOJ' 카테고리의 다른 글

백준 2966번: 찍기  (0) 2020.05.06
백준 4641번: Doubles  (0) 2020.05.06
백준 1405번: 미친 로봇  (0) 2020.05.03
백준 1213번: 팰린드롬 만들기  (0) 2020.04.30
백준 2981번: 검문  (0) 2020.04.30

[문제 링크]

 

1405번: 미친 로봇

첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고,  모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다.

www.acmicpc.net

이동할 때마다 그 방향에 부여된 확률을 곱해주면 그 경로로 이동하는 확률을 구할 수 있다.

다양한 경로가 있을 것이고, 각각의 경로로 이동하는 확률을 차곡차곡 더해줌으로써 전체 확률 또한 구할 수 있다.

완전 탐색을 통해 이미 방문한 좌표를 다시 방문하지 않는 경로를 모두 구해서 그 경로로 이동하는 확률을 결과값에 누적해준다면 원하는 결과를 얻을 수 있다.

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
 
bool map[29][29];
vector<double> directPer;
vector<pair<int, int>> dydx = { make_pair(1,0), make_pair(-1,0), make_pair(0,1), make_pair(0,-1) };
int moveMax;
double result = 0;
 
void Solution(int Y, int X, int moveCnt, double multiPercent)
{
    if (moveCnt == moveMax)
    {
        result += multiPercent; // 퍼센트 누적
        return;
    }
 
    for (int i = 0; i < 4; i++) // 동 서 남 북
    {
        int nextY = Y + dydx[i].first, nextX = X + dydx[i].second;
        if (map[nextY][nextX]) continue;
        map[nextY][nextX] = true;
        Solution(nextY, nextX, moveCnt + 1, multiPercent * directPer[i]);
        map[nextY][nextX] = false;
    }
 
}
int main(void)
{
    int E, W, N, S;
    cin >> moveMax >> E >> W >> N >> S;
    directPer.push_back(E*0.01);
    directPer.push_back(W*0.01);
    directPer.push_back(N*0.01);
    directPer.push_back(S*0.01);
 
    map[14][14] = true;    // 중앙에서 시작
 
    Solution(14, 14, 0, 1);
 
    printf("%.9f", result);
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

알고리즘 200일 프로젝트 - 29day

저작자표시 비영리

'알고리즘 > BOJ' 카테고리의 다른 글

백준 4641번: Doubles  (0) 2020.05.06
백준 2858번: 기숙사 바닥  (0) 2020.05.05
백준 1213번: 팰린드롬 만들기  (0) 2020.04.30
백준 2981번: 검문  (0) 2020.04.30
백준 1062번: 가르침  (0) 2020.04.29

[문제 링크]

 

1213번: 팰린드롬 만들기

첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.

www.acmicpc.net

뇌를 자극하는 C++ STL을 공부하면서 배운 내용을 사용해볼 수 있어서 재밌게 푼 문제였다.

처음엔 next_permutation() 함수를 사용해서 구현해보았지만 알파벳 개수가 50개까지 있어서 시간초과가 발생했다.

따라서 다른 방식으로 구현하기로 하였고, 그 방법은 다음과 같다.

 

1. 입력받은 문자열을 오름차순으로 정렬한다.

 

2. 문자열의 첫 번째 원소를 가리키는 반복자를 만든 다음 count()함수를 통해 반복자가 가리키는 실제 값이 몇개 존재하는지 확인한다.

IF : 만약 홀수개라면 홀수갯수를 1 증가시킨 다음 (이 때 홀수갯수가 2개 이상이라면 팰린드롬을 만들 수 없기 때문에 " I'm Sorry Hansoo " 출력 후 프로그램을 종료한다.) 값을 char 변수에 저장하고 erase() 멤버함수를 사용해 원소 하나를 삭제한다.

 

3. 문자 개수의 절반을 stack에 담고 문자열에서 삭제한다. 그리고 반복자가 다음 알파벳을 가리키도록 이동시킨다.

 

4. 모든 원소에 대해 작업을 마쳤다면 char변수에 저장한 홀수개 알파벳을 문자열 뒤에 붙이고 (없다면 건너뜀)

스택에 저장한 원소를 늦게 들어온 순서대로 문자열 뒤에 붙여준다.

 

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
48
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
 
int main(void)
{
    string str;
    cin >> str;
    sort(str.begin(), str.end());
    string::iterator iter = str.begin();
 
    stack<char> alpha;
    int cnt = 0, oddCnt = 0, strLen = str.length();
    char oddChar;
    while (cnt < strLen)
    {
        int c = count(str.begin(), str.end(), *iter);
        if (c % 2 != 0)
        {
            oddCnt++; // 홀수개로 존재하는 알파벳 개수카운팅
            if (oddCnt == 2) // 홀수개가 두개 이상이면 안됨
            {
                cout << "I'm Sorry Hansoo" << endl;
                return 0;
            }
            oddChar = *iter;
            iter = str.erase(iter);
        }
        int n = c / 2;
        while (n--)
        {
            alpha.push(*iter);
            iter = str.erase(iter);
        }
        cnt += c;
        iter += c / 2;
    }
    if(oddCnt == 1) str.push_back(oddChar);
    while (!alpha.empty())
    {
        str.push_back(alpha.top());
        alpha.pop();
    }
    cout << str << endl;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

알고리즘 200일 프로젝트 - 25day

내일도 열심히!

저작자표시 비영리

'알고리즘 > BOJ' 카테고리의 다른 글

백준 2858번: 기숙사 바닥  (0) 2020.05.05
백준 1405번: 미친 로봇  (0) 2020.05.03
백준 2981번: 검문  (0) 2020.04.30
백준 1062번: 가르침  (0) 2020.04.29
백준 6679번: 싱기한 네자리 숫자  (0) 2020.04.28

[문제 링크]

 

2981번: 검문

문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는

www.acmicpc.net

문제를 보고 뭔가 최대 공약수의 약수들을 출력하면 될 거 같다는 솔루션을 얻는데까지는 오래 걸리지 않았다.

하지만 문제는 M으로 나눴을 때 나머지가 같은 M을 출력하는 것이었기에, 입력받은 숫자 중 가장 작은 숫자를 M으로 하고 그 수를 1씩 감소하면서 나눴을 때 나머지가 같은 M을 벡터에 저장하고, 나머지가 0이 되면 그 때의 M이 최대공약수이므로 최대공약수 M의 약수들을 출력해주는 식으로 구현하려했다.

하지만 999999999, 999999998, 999999997 이런식으로 숫자가 주어지게 되면 1씩 감소해가지고는 시간초과가 날 것이 분명했기 때문에 잘못된 접근이라 생각하고 다른 사람들의 풀이를 참고하였다.

최대공약수를 구하는 유클리드호제법에 대하여 알게 되었고, 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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> v, result;
int GCD(int a, int b) // 최대공약수 구하기
{
    if (a % b == 0) 
        return b;
 
    return GCD(b, a%b);
}
int main(void)
{
    int testcase;
    cin >> testcase;
    while (testcase--)
    {
        int number;
        cin >> number;
        v.push_back(number);
    }
    sort(v.begin(), v.end());
    int diff = v[1] - v[0];
    for (vector<int>::size_type i = 2; i < v.size(); i++)
        diff = GCD(diff, v[i] - v[i - 1]);
    for (int i = 2; i*i <= diff; i++)
    {
        if (diff%i == 0)
        {
            result.push_back(i);
            result.push_back(diff / i);
        }
    }
    result.push_back(diff);
    sort(result.begin(), result.end());
    vector<int>::iterator iter_end = unique(result.begin(), result.end()); // 중복된 원소를 뒤로 넘김
    for (vector<int>::iterator iter = result.begin(); iter != iter_end; iter++)
        cout << *iter << ' ';
    cout << endl;
    return 0;
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
 

알고리즘 200일 프로젝트 - 24day

내일도 열심히!

저작자표시 비영리

'알고리즘 > BOJ' 카테고리의 다른 글

백준 1405번: 미친 로봇  (0) 2020.05.03
백준 1213번: 팰린드롬 만들기  (0) 2020.04.30
백준 1062번: 가르침  (0) 2020.04.29
백준 6679번: 싱기한 네자리 숫자  (0) 2020.04.28
백준 1074번: 게임  (0) 2020.04.28

[문제 링크]

 

1062번: 가르침

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

www.acmicpc.net

STL 공부하면서 배운거좀 써먹어보겠다고 까불다가 이틀동안 고생한 문제..

for_each 함수로 입력받은 단어에서 anta, tica 를 제외한 나머지 단어를 검사해서 가르칠 횟수가 남아있고, 아직 배우지 않은 알파벳이라면 alpha 문자열에 추가하는 식으로 구현했는데, 알파벳 하나하나 검사하는 것이 아닌 입력받은 단어 순서대로 검사하게되어 반례가 존재하는 구현이었다...ㅜ ㅜ 다른 사람들의 구현을 보고 모든 알파벳에서 남극언어(a,n,t,i,c)를 다 배운다는 가정하에 배울 수 있는 모든 경우의 수를 구하는 방향으로 다시 구현하였다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<string> voca;
bool alpha[26];
int maxLearn, n, maxCnt = 0;
 
void Solution(int start, int pick)
{
    if (pick == maxLearn) // 다 가르쳤다면
    {
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            bool check = true;
            for (string::size_type j = 0; j < voca[i].size(); j++)
            {
                if (alpha[voca[i][j] - 'a']) continue;
                check = false;
                break;
            }
            if (check) cnt++;
        }
        maxCnt = max(maxCnt, cnt);
        return;
    }
    for (int i = start; i < 26; i++)
    {
        if (alpha[i]) continue;
        alpha[i] = true;
        Solution(i + 1, pick + 1);
        alpha[i] = false;
    }
}
 
int main(void)
{
    cin >> n >> maxLearn;
    for (int i = 0; i < n; i++)
    {
        string str;
        cin >> str;
        voca.push_back(str);
    }
    if (maxLearn < 5)
    {
        cout << 0 << endl;
        return 0;    // antic
    }
    else if (maxLearn == 26)
    {
        cout << n << endl;
        return 0;
    }
    alpha['a' - 'a'] = true;
    alpha['n' - 'a'] = true;
    alpha['t' - 'a'] = true;
    alpha['i' - 'a'] = true;
    alpha['c' - 'a'] = true;
    maxLearn -= 5;
    Solution(1,0);
 
    cout << maxCnt << endl;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

알고리즘 200일 프로젝트 - 24day

내일도 열심히!

저작자표시 비영리

'알고리즘 > BOJ' 카테고리의 다른 글

백준 1213번: 팰린드롬 만들기  (0) 2020.04.30
백준 2981번: 검문  (0) 2020.04.30
백준 6679번: 싱기한 네자리 숫자  (0) 2020.04.28
백준 1074번: 게임  (0) 2020.04.28
백준 7453번: 합이 0인 네 정수  (0) 2020.04.26

+ Recent posts

티스토리툴바