Grace

1. str splite : substr을 이용해 '['와']'를 제거한 후  getline을 이용해서 받은 문자열을 splite 했다.

2.  명령 문자열(inst)를 순회하면서 reverse여부에 따라 앞에서 pop해야하는 횟수와 뒤에서 pop해야 하는 횟수를 카운팅한다.

3. pop의 횟수가 nums.size()보다 클 경우는 error를 출력한다.

4. 그렇지 않은 경우에는 카운팅한 값을 토대로 pop을 진행한 뒤 result 문자열을 만들어 출력한다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <deque>
#include <sstream>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 0;
    cin >> t;
    while(t--){
        string inst, str, buffer;
        char delim = ',';
        deque<string> nums;
        int n, front_count = 0, back_count = 0;
        bool isReverse = false;

        cin >> inst >> n >> str; 

        //str splite
        str = str.substr(1, str.size() - 2);
        stringstream f(str);
        while (getline(f, buffer, delim))
        {
            nums.push_back(buffer);
        }

        //inst 순회하며 카운팅.
        for (int i = 0; i < inst.size(); i++)
        {
            if(inst[i]=='R')
                isReverse = !isReverse;
            else{
                if(isReverse)
                    back_count++;
                else
                    front_count++;
            }
        }

        //result print
        if (back_count + front_count > nums.size())
        {
            cout << "error" << endl;
        }
        else
        {
            string result = "[";
            bool isFirst = true;

            //nums pop
            for (int i = 0; i < front_count; i++)
                nums.pop_front();
            for (int i = 0; i < back_count; i++)
                nums.pop_back();

            //result string 만들기
            if(isReverse){
                for (int i = nums.size() - 1; i >= 0; i--)
                {
                    if(!isFirst){
                        result += ",";
                    }else{
                        isFirst = false;
                    }
                    result += nums[i];
                }
            }else{
                for (int i = 0; i < nums.size(); i++){
                    if(!isFirst){
                        result += ",";
                    }else{
                        isFirst = false;
                    }
                    result += nums[i];
                }
            }
            //print
            result += "]";
            cout << result << "\n";
        }
    }
    return 0;
}

solve() : 전체 그림을 탐색하면서 bfs를 수행하는 횟수를 카운팅한다.

bfs() : 파라미터로 option을 넣어서

0일 경우에는 R / G / B 를 구분하는 탐색을 진행하고

1일 경우에는 R,G / B 를 구분하는 탐색을 진행하도록 했다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int n;
int fdx[4] = {0, 0, 1, -1};
int fdy[4] = {1,-1,0,0};
int v[100][100]={0,};
string a[100];

bool checkPosition(int x, int y){
    return x >= 0 && y >= 0 && x < n && y < n ? true : false;
}

void bfs(int sx, int sy, int option){
    queue<pair<char, pair<int,int>>> q;

    q.push({a[sx][sy], {sx,sy}});
    v[sx][sy] = 1;

    while (!q.empty())
    {
        int x = q.front().second.first;
        int y = q.front().second.second;
        char w = q.front().first;
        q.pop();
        for (int i = 0; i < 4; i++){
            int dx = x + fdx[i];
            int dy = y + fdy[i];
            if(checkPosition(dx,dy) && v[dx][dy] == 0){
                bool canPush = false;
                char dw = a[dx][dy];
                if(w == dw){
                    canPush = true;
                }
                if(option == 1){
                    if((w == 'R' || w == 'G' ) && (dw == 'R' || dw == 'G' )){
                       canPush = true; 
                    }
                }
                if(canPush){
                    q.push({dw, {dx, dy}});
                    v[dx][dy] = 1;
                }
            }
        }
    }
}

void solve(){
    int count = 0;
    int countRG = 0;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++){
            if(v[i][j] == 0){
                count++;
                bfs(i,j,0);
            }
        }
    }

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            v[i][j] = 0;
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++){
            if(v[i][j] == 0){
                countRG++;
                bfs(i,j,1);
            }
        }
    }
    cout << count << "\n";
    cout << countRG << "\n";
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    solve();
}

recursion 탐색 단계에서 현재 범위의 배열이 같은 숫자로 이루어지지 않은 경우

1. 결과 벡터에'(' push

2. 4범위로 분할하여 recursion

3. 결과 벡터에')' push

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int a[64][64]={0,};
vector<char> v;

void solve(int x, int y, int n){
    int target = a[x][y];
    for (int i = x; i < x + n; i++)
    {
        for (int j = y; j < y + n; j++){
            if(target != a[i][j]){
                v.push_back('(');
                solve(x, y, n / 2);
                solve(x, y + n / 2, n / 2);
                solve(x + n / 2, y, n / 2);
                solve(x + n / 2, y + n / 2, n / 2);
                v.push_back(')');
                return;
            }
        }
    }

    char temp = (char)target;
    v.push_back(temp);
    return;
}

int main(){
    int n;
    string str;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> str;
        for (int j = 0; j < n; j++){
            a[i][j] = str[j];
        }
    }

    solve(0,0,n);

    for (int i = 0; i < v.size(); i++){
        cout << v[i];
    }
}

❗ network jitter를 해결하기 위한 DASH와 manifestfile

streaming 서비스에서는 네트워크 jitter(network delay)가 존재한다. 서버에서 영상을 받는 과정에서 딜레이가 발생할 수 밖에 없다. 딜레이를 방지하기 위해 버퍼링 시간을 가진다. 이것이 유튜브에서 영상을 클릭하는 순간 곧 바로 재생되는 것이 아니라 순간적으로 버퍼링이 걸리는 이유이다. 버퍼링은 버퍼를 채우는 과정이다. 클라이언트에서의 영상재생 속도보다 서버에서 받아오는 영상 데이터 량이 더 느리다면 영상이 끊기고 다시 버퍼링이 시작된다.

버퍼링이 길면 데이터를 많이 받은 후에 시작하는 것이기 때문에 영상시청 중간에 끊길 확률이 적다. 하지만 너무 길면 유저의 이탈률이 늘어날 것이다. 사람의 인내심과 영상이 끊기지 않은 정도 사이의 중용을 지켜야한다.

youtube ↔ client 통신은 에플리케이션간 통신으로 tcp 혹은 udp 에 의존한다.

udp를 쓰면 인코딩된 bps를 충족하는 속도로 server가 영상을 보낼 수 있지만 네트워크 상황을 고려하지 않기 때문에 네트워크 환경이 일정 수준 이하로 떨어지면 영상의 퀄리티에 심각한 피해가 생긴다. 그렇다고 tcp를 쓰자니 서버가 전송 속도를 조절할 수 없기에 원활한 서비스를 제공할 수 가 없다.

youtube에서 실제 사용하는 방식은 tcp를 사용하되 application layer에서 DASH라는 기술을 이용하는 방식이다. DASH는 Dynamic Adaptive Streaming Http의 약자로 네트워크에 적응하며 동적으로 http 스트리밍을 하는 방식이다. 이를 구현하기 위해 manifest file이 사용된다.

manifest이란?

영상이 업로드 될때, 영상전체가 올라가는 것이 아니라 256kb정도의 chanks로 분할되어서 저장된다. 또한 동일한 chanks에 대해서 여러개의 coding rate version이 생성된다.(128kbps, 256kbps, 512kbps, 1mbps, 2mbps, …) 유튜브에서 영상을 클릭하면 유튜브 서버는 클라이언트에게 manifestfile 을 넘겨준다. 그때 그때 네트워크 상황에 맞는 청크를 요청해서 가져온다. 이는 영상 중간에 화질 바뀌는 이유이다.

[manifestfile 예시]

❗ 서버 부화 방지와 통신속도 상향을 위한 CDN 분산저장(content delivery network)

manifestfile를 받아서 네트워크 환경에 따라 다른 버전의 chanks를 요청한다고 해도 많은 사용자가 서버 한곳에 몰리게 되면 과부화가 걸릴 수 밖에 없다. 이것을 해결하기 위해 전세계 CDN업체에 각 chanks를 분산저장하는 방식이 사용된다.

[구현원리]

manifestfile의 chanks URL의 ip를 알아내기 위해 cdn업체의 dns 서버에 접근하게 된다.(URL이 CDN 업체의 URL이기 때문이다.) 이때 요청자의 ip 주소를 기반으로 요청자의 위치와 가장 가까운 cdn 서버의 ip를 준다.

cdn위치는 사용자에게 가장 가까운 곳에 존재하는 것이 유리하다. 그래서 보통 access network(skt ,kt같은)의 내부 혹은 근처에 CDN이 즐비해 있다.

priority_queue를 사용한 dijkstra 알고리즘으로 접근했다.

4방향으로 탐색을 하면서 pq를 통해 최소경로을 탐색해준다.

#include <iostream>
#include <math.h>
#include <vector>
#include <queue>
#define INF 987654321
#define NODEN 126

using namespace std;

int a[NODEN][NODEN];
int dist[NODEN][NODEN];
int fdx[4] = {0, 0, 1, -1};
int fdy[4] = {1, -1, 0, 0};
int n;

void dijkstra(int sx, int sy){
    priority_queue<pair<int, pair<int,int>>> pq;
    pq.push({-a[sx][sy], {sx, sy}});
    dist[sx][sy] = a[sx][sy];
    
    while (!pq.empty())
    {
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        int w = -pq.top().first;
        pq.pop();

        if(w > dist[x][y]) continue;

        for (int i = 0; i < 4; i++){
            int dx = x + fdx[i];
            int dy = y + fdy[i];
            int dw = w + a[dx][dy];
            
            if (dx > 0 && dy > 0 && dx <= n && dy <= n)
            { 
                if (dist[dx][dy] > dw)
                {
                    dist[dx][dy] = dw;
                    pq.push({-dw, {dx, dy}});
                }
            }
        }
    }
}

int main(){
    int t = 0;
    while (1)
    {
        t++;
        cin >> n;
        if(n==0)
            break;
        for (int i = 1; i <= n; i++)
        {
            for (int d,j = 1; j <= n; j++){
                cin >> d;
                a[i][j] = d;
            }
        }

        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                dist[i][j] = INF;
            }
        }

        dijkstra(1, 1);

        printf("Problem %d: %d\n", t, dist[n][n]);
    }
}

recursion으로 접근한다.

BaseCase

1) n=1인 경우에는 각 케이스에 맞게 count를 1증가시키고 종료해준다.

RecursionCase

1) 모든 칸이 동일한 숫자로 채워져 있다면 해당 숫자에 맞게 count를 1증가시키고 종료해준다.

2) 그렇지 않다면 9개의 구역에 해당하는 recursion을 실행한다.

#include <iostream>
#include <math.h>

using namespace std;

int a[2200][2200] = {0,};
int count[3] = {0,};

void solve(int x, int y, int n){
    if(n==1){
        if(a[x][y] == -1)
            ::count[0]++;
        if(a[x][y] == 0)
            ::count[1]++;
        if(a[x][y] == 1)
            ::count[2]++;
        return;
    }

    int target = a[x][y];
    for (int i = x; i < x + n; i++)
    {
        for (int j = y; j < y + n; j++){
            if(target != a[i][j]){
                int d = n / 3;
                for (int c = 0; c < d * 3; c+=d){
                    for (int l = 0; l < d * 3; l += d)
                    {
                        int dx = x + c;
                        int dy = y + l;
                        solve(dx, dy, d);
                    }
                }
                return;
            }
        }
    }

    if(a[x][y] == -1)
        ::count[0]++;
    if(a[x][y] == 0)
        ::count[1]++;
    if(a[x][y] == 1)
        ::count[2]++;

    return;
}

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }
    
    solve(0,0,n);

    for (int i = 0; i < 3; i++){
        cout << ::count[i] << "\n";
    }
}

0의 개수에 영향을 미치는 것은

1~n까지의 숫자 중에서,

각 숫자가 갖는 5와 2의 개수이다.

왜냐면 소수 5와 2가 곱해질때 만이 10이 만들어지기 때문이다.

따라서 각 숫자의 소인수 중 2와 5의 개수를 카운팅한다음

10이 얼마나 만들어 지는지를 찾는다. -> min(2의 개수, 5의 개수)

#include <iostream>
#include <math.h>

using namespace std;

int main(){
    int n;
    cin >> n;

    int a=0, b=0, count=0;
    for (int i = 1; i <= n; i++)
    {
        int num = i;
        while(num%5 == 0){
            num /= 5;
            a++;
        }
        while(num%2 == 0){
            num /= 2;
            b++;
        }
    }
    count = min(a, b);
    cout << count << "\n";
}

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

기본적인 BFS / DFS 문제이다.

BFS를 이용해 접근했다.

모든 노드에 대해 BFS를 시도하면서 이미 방문한 노드인 경우 건너뛰는 방식이다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int n, m;
int count = 0;
vector<int> a[1001];
int v[1001] = {
    0,
};

void bfs(int start){
    if(v[start] == 1)
        return;

    queue<int> q;
    q.push(start);
    v[start] = 1;
    ::count++;

    while(!q.empty()){
        int x = q.front();
        q.pop();
        for (int i = 0; i < a[x].size(); i++){
            int y = a[x][i];
            if(v[y] == 0){
                v[y] = 1;
                q.push(y);
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for (int x,y,i = 0; i < m; i++){
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for (int i = 1; i <= n; i++){
        bfs(i);
    }
    cout << ::count << "\n";
}