2048 (Easy)



2048 게임을 하는데 5번 이동에 제일 큰 블록을 만들어야 한다.


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


블록이 어떻게 주어질지 모르니까 전략이 없다. 모든 경우를 실험해보자.


같은 상태에 도달하면 다시 할 필요가 없긴 하지만, 같은 상태를 확인하기도, 도달하기도 어렵다.


걍 백트래킹으로 조져보자.



백트래킹 함수는 다음과 같이 구성했다.


상단엔 5번 이동했는지 확인한다. 5번이면 가장 큰 블록을 찾아 답과 비교하고 종료시킨다.


5번 이하의 경우에 완전탐색을 수행해야 하는데,


이전 상태를 저장 -> 재귀호출 -> 복귀 와 같은 아주 간단한 구조로 되어있다.


아래 코드는 매우 더러우니 안 보는 것을 추천합니다..

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
#include <stdio.h>
#include <stack>
using namespace std;
 
int n, ans;
int map[20][20];
 
void save(int tmap[][20]) {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            tmap[i][j] = map[i][j];
}
 
void restore(int tmap[][20]) {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            map[i][j] = tmap[i][j];
}
 
void backtracking(int cnt) {
    if (cnt == 5) {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (ans < map[i][j])
                    ans = map[i][j];
 
        return;
    }
 
    stack<int> st;
    int tmap[20][20];
    save(tmap);
 
    for (int i = 0; i < n; ++i) { //우
        for (int j = 0; j < n; ++j) {
            if (map[i][j]) {
                st.push(map[i][j]);
                map[i][j] = 0;
            }
        }
 
        int b = n - 1;
        while (!st.empty()) {
            int t = st.top();
            st.pop();
 
            if (!map[i][b])
                map[i][b] = t;
            else if (t == map[i][b])
                map[i][b--] *= 2;
            else
                map[i][--b] = t;
        }
    }
    backtracking(cnt + 1);
    restore(tmap);
 
    for (int i = 0; i < n; ++i) { //좌
        for (int j = n - 1; j >= 0; --j) {
            if (map[i][j]) {
                st.push(map[i][j]);
                map[i][j] = 0;
            }
        }
 
        int b = 0;
        while (!st.empty()) {
            int t = st.top();
            st.pop();
 
            if (!map[i][b])
                map[i][b] = t;
            else if (t == map[i][b])
                map[i][b++] *= 2;
            else
                map[i][++b] = t;
        }
    }
    backtracking(cnt + 1);
    restore(tmap);
 
    for (int j = 0; j < n; ++j) { //위
        for (int i = 0; i < n; ++i) {
            if (map[i][j]) {
                st.push(map[i][j]);
                map[i][j] = 0;
            }
        }
 
        int b = n - 1;
        while (!st.empty()) {
            int t = st.top();
            st.pop();
 
            if (!map[b][j])
                map[b][j] = t;
            else if (t == map[b][j])
                map[b--][j] *= 2;
            else
                map[--b][j] = t;
        }
    }
    backtracking(cnt + 1);
    restore(tmap);
 
    for (int j = 0; j < n; ++j) { //아래
        for (int i = n - 1; i >= 0; --i) {
            if (map[i][j]) {
                st.push(map[i][j]);
                map[i][j] = 0;
            }
        }
 
        int b = 0;
        while (!st.empty()) {
            int t = st.top();
            st.pop();
 
            if (!map[b][j])
                map[b][j] = t;
            else if (t == map[b][j])
                map[b++][j] *= 2;
            else
                map[++b][j] = t;
        }
    }
    backtracking(cnt + 1);
    restore(tmap);
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            scanf("%d", &map[i][j]);
 
    backtracking(0);
    printf("%d", ans);
 
    return 0;
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 13460 구슬 탈출 2 // 구 째로탈출2  (0) 2018.04.11
백준) 14868 문명 - bfs, 유니온 파인드  (1) 2018.02.08
백준) 2615 오목  (0) 2018.02.06
백준) 1182 부분집합의 합  (0) 2018.02.06
백준) 4963 섬의 개수  (0) 2018.01.14

구슬 탈출 2 


보드에 빨간 공과 파란 공을 올려 두고, 보드를 4방향으로 기울여보면서 빨간 공을 보드의 구멍으로 탈출시키는게 목표다.

이 때 가장 적게 기울여보는 횟수는 얼마나 될까?


맵이 어떻게 주어질지 모르기 때문에 다 해보는 완전탐색이 필요하다. 동시에 최소 횟수를 요구하므로 bfs가 적당하다.

참고로 진짜 모든 경우를 탐색해보는 방법으로도 통과가 가능하긴 하다. 시간이 더 걸리긴 하지만..


공이 두 개씩 굴러다니므로 visit 확인을 두 공의 좌표를 모두 확인해야 한다는 점을 유의해야 한다.

규칙이 조금 까다로운데, 분기를 다음과 같이 할 수 있다.

1. 일단 상대 공을 무시하고 두 공을 굴려서 어디로 가는지 확인한다.

2. 만약 파란 공이 구멍에 빠지면 이 경우는 글러먹은 경우니까 버린다.

3. 두 공이 겹칠 경우도 있다. 이 때는 굴리기 전의 좌표를 보고 잘 조정해줘야 한다. 아래로 굴렸고 겹쳤는데, 원래 빨간공이 위에 있었다면 빨간공을 파란공 위로 옮겨 줘야한다.

친절하게도 10을 초과하는 답은 원하지 않는다니까 4 ^ 10 안에 수행가능하다. 물론 한 번 굴리고, 다음번에 또 같은 방향으로 굴리는 경우 visit확인을 통해 가지치기가 되니까 훨씬 빠르게 문제가 풀린다.

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
#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
 
struct balls {
    int depth;
    int rx, ry, bx, by;
};
int irx, iry, ibx, iby, hx, hy;
 
int n, m, ans = -1;
int map[10][10];
int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
bool visit[10][10][10][10];
char str[11];
 
void move(int& x, int& y, int d) {
    while (1) {
        x += dir[d][0]; y += dir[d][1];
        if (map[x][y] == 1) {
            x -= dir[d][0]; y -= dir[d][1];
            break;
        }
        else if (map[x][y] == 2)
            break;
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", str);
        for (int j = 0; j < m; ++j) {
            switch (str[j]) {
            case '.':
                map[i][j] = 0; break;
            case '#':
                map[i][j] = 1; break;
            case 'O':
                map[i][j] = 2; hx = i, hy = j; break;
            case 'R':
                irx = i, iry = j; break;
            case 'B':
                ibx = i, iby = j; break;
            }
        }
    }
 
    queue<balls> q;
    q.push({ 0,irx,iry,ibx,iby });
    visit[irx][iry][ibx][iby] = true;
 
    while (!q.empty()) {
        balls cur = q.front(); q.pop();
 
        if (cur.depth > 10)
            break;
        if (cur.rx == hx && cur.ry == hy) {
            ans = cur.depth;
            break;
        }
 
        for (int i = 0; i < 4; ++i) {
            int rx = cur.rx, ry = cur.ry;
            int bx = cur.bx, by = cur.by;
            move(rx, ry, i), move(bx, by, i);
 
            if (bx == hx && by == hy)
                continue;
 
            if (rx == bx && ry == by) {
                switch (i) {
                case 0:
                    cur.rx < cur.bx ? rx-- : bx--; break;
                case 2:
                    cur.rx < cur.bx ? bx++ : rx++; break;
                case 1:
                    cur.ry < cur.by ? ry-- : by--; break;
                case 3:
                    cur.ry < cur.by ? by++ : ry++; break;
                }
            }
 
            if (!visit[rx][ry][bx][by]) {
                balls next = { cur.depth + 1,rx,ry,bx,by };
                q.push(next);
                visit[rx][ry][bx][by] = true;
            }
        }
    }
 
    printf("%d", ans);
 
    return 0;
}
cs


'알고리즘 > 브루트 포스' 카테고리의 다른 글

백준) 12100 2048 (Easy)  (0) 2018.04.11
백준) 14868 문명 - bfs, 유니온 파인드  (1) 2018.02.08
백준) 2615 오목  (0) 2018.02.06
백준) 1182 부분집합의 합  (0) 2018.02.06
백준) 4963 섬의 개수  (0) 2018.01.14

오늘은 여러 가중치 갱신 방법을 알아보고자 한다.


그 전에 생각할 점은, 앞서 본 은닉층 없는 허접한 신경망 대신 다층 신경망을 학습시킬 준비를 해야 한다.


이를 위해 먼저 1986년에 개발된 역전파(backpropagation) 알고리즘을 알아보자.


이 알고리즘은 은닉층의 가중치를 바꿀 때 얼마나 오차가 빨리 변하는지를 계산할 수 있다. 즉 개별 시냅스의 가중치를 변경할 때의 오차가 얼마나 빨리 변


하는지를 알 수 있는 것이다. 이를 통해 가장 가파른 하강 방향을 찾아 빠르게 극점으로 도달하는게 목표다.



대충 생각해보면 기계학습은 매직 박스마냥 층만 잘 쌓으면 수행되는걸로 오해할 수 있다. 이처럼 추상화로 덮힌 부분을 잘 모르고 가져다 쓸 때 발생하는 


비효율을 leaky abstraction이라고 한다. 그래서 자체적으로 역전파를 이해하려는 노력이 필요한 것이다. 



하나의 은닉 노드는 모든 출력 노드에 영향을 미칠 수 있다. 따라서 오차에 대한 여러 은닉 노드들의 효과를 결합해서 분석해야한다.


이 때 역전파의 전략은 일종의 다이나믹 프로그래밍이다.


한 은닉층에 대해 오차 도함수를 얻은 다음에, 이를 전의 가중치에 대한 오차 도함수를 계산하는데 사용하는 것이다.



디피문제처럼 귀납적으로 다뤄진다.


먼저 j번째 층에 대한 오차 도함수가 있다고 생각해보자. 최종적으로는 i번째 층에 대한 오차 도함수를 알아내야 한다.


이를 위해 i번째 층의 아웃풋들이 j번째 층의 오차에 얼마나 영향을 주는지에 대한 정보를 모아야 한다. 



0. 역전파 알고리즘


먼저 출력층에서 오차 도함수를 각 출력층 뉴런에 대한 편미분으로 구하면 다음과 같다.


이제 귀납적으로 i번째 층의 뉴런 출력이 j번째 층의 모든 뉴런의 오차에 얼마나 영향을 미치는지에 대한 정보를 모아야 한다.


고맙게도 아래층에서 들어오는 출력의 오차를 연결 가중치 들로 편미분 될 수 있으므로 다음과 같이 표현할 수 있다.



또한 로짓에 대한 출력의 도함수를 표현한다면 시그모이드 함수르 쓴다면 다음과 같이 표현된다.


이제 두식을 합치면 j번째 층의 오차 도함수의 관점에서 본 i번째 층의 오차 도함수를 다음과 같이 표현할 수 있다.


모든 은닉층들도 재귀적으로 오차 도함수를 구할 수 있게 되었다. 다음은 한 데이터셋을 학습한 이후 어떻게 수정되어야하는지를 알려준다.

마지막으로 데이터셋에 전체 학습 데이터셋에 대한 도함수를 합산하면 다음과 같이 수정된 식으로 나타낼 수 있다.



수학적으로 주저리 주저리 쓰여있는데,


역전파는 말 그래도 내가 영향을 주었던 노드들에게서 전부 피드백을 받아 가중치를 수정해 나가는 과정이다.(겉핡기)


(미완성)


'머신러닝' 카테고리의 다른 글

머신러닝 둘째날 - 신경망 - 델타 규칙  (0) 2018.03.27
머신러닝 첫날 - 용어  (0) 2018.02.07

저번에 인공지능과 머신러닝, 딥러닝이 무슨 차이인지 설명하는걸 까먹어서 이번 차에 쓰려고 한다.


한 줄로 관계를 요약하면 다음과 같다.


"딥러닝은 머신러닝의 일종이고, 머신러닝은 딥러닝의 일종이다."


우선 인공지능은 뜻이 가장 포괄적으로, 지능적인 요소가 포함된 기술을 모두 일컫는 단어다.


스마트 머시기 하는데 들어가는 모든 기술은 인공지능이라고 하는 추세에서 알 수 있다.


여러 인공지능 분야에서 머신러닝은 "데이터를 이용한 모델링 기법" 이다.


딥러닝은 "여러 비선형 변환기법의 조합"으로 기계를 학습시키는 알고리즘이다.



머신러닝이 만능인것마냥 대중들에게 소개되고 있지만 이 분야에도 몇 가지 문제점이 존재한다.


1. 학습할 데이터와 입력 데이터의 질 : 학습 데이터가 입력 데이터의 특성을 잘 반영하지 않는 데이터면 일반화가 구려진다.


2. 학습 데이터를 너무 잘 맞춘다 : 주로 과적합이라고 말하는데, 학습데이터의 잡음도 정답이라 학습하기 때문에 일반화가 구려진다.



머신러닝은 오래전에 소개되었지만 속도 문제로 잊혀진 기술이었다.


하지만 최근엔 과적합에 대항하는 기법이 개발되었고, 복잡한 행렬연산을 빠르게 처리해줄 하드웨어(주로 GPU)의 발전으로 부상하게 된다.


과적합에 대항하는 기법은 다음 두 가지다.


1. 검증 : 학습 데이터를 학습용과 검증용으로 분류한다.(주로 4대1) 학습 이후 검증이 잘 안되면 다시 분류해서 수행한다.


2. 정칙화 : 모델을 최대한 간단하게 만들고자 하는게 기본 전략으로 다음 기회에 자세히 알아보자.



신경망(neural network)은 머신러닝의 모델로 많이 사용된다.


뇌의 신경세포들이 연결된 네트워크를 본 뜬 모델로, 정보를 노드들의 관계(가중치)로 저장하는 것이다.


박스 노드들은 입력층, 최우단의 짙은 노드들은 출력층이다. 사이사이 층들은 은닉층이라고 한다.


단층 신경망은 은닉층이 없는 경우를 말하고, 반대는 다층 신경망이다. 이 중에 얕은(=shallow vanilla) 신경망은 은닉층이 하나인 경우고,


심층 신경망은 은닉층들이 2개 이상인 경우다.



각 노드엔 여러 신호에 가중치가 곱해져 들어오고, 바이어스가 추가로 관여하여 활성함수를 이룬다. 함수의 결과가 출력된다.


따라서 신경망에서 정보는 가중치와 바이어스로 바뀌어 저장되는 것이다.


활성함수가 선형함수라면 결국엔 행렬곱들로 계산식을 나타낼 수 있는데,


잘 생각해보면 계산식을 잘 정리하면 다층 신경망이 단층 신경망이 된다는 점을 알 수 있다. 은닉층을 추가한 효과가 없다.



신경망 모델로 지도학습을 시키는 방법은 간단하다.


가충치를 초기화하고 학습 데이터의 출력값과 정답의 오차를 계산해본다. 오차가 크다면 피드백으로 가중치를 잘 조절해주면 된다.


오늘은 단층 신경망만 학습시켜보기로 한다.



대표적인 학습 방법인 델타 규칙(delta rule = adaline rule = widrow-hoff)에 대해 알아보자.


델타 규칙은 오차를 최소화 하고자 오차 그래프를 미분해 점진적으로 극점을 찾아가는 점진 하강법에서 비롯되었다.



최종적으로는 , 라는 수식으로 결과가 나오는데, 먼저 각 기호에 대해 정의하고, 증명하고 설명하도록 하겠다.


1.  는 상수로 학습률이라고 한다.(0과 1사이 값)


2.  는 활성화 함수다.


3.  는 j번 째 출력값이다.


4.  j번째 출력노드로 들어온 가중치가 곱해진 값들의 합으로  이다.


5.  j번째 출력값이다. 따라서 이다.


6.  는 i번째 입력값이다.



증명 

1) 오차의 합은  으로 쓸 수 있고, 이를 각 가중치로 편미분 한다고 치면 

2) 다음과 같이  표현할 수 있다.

3) 이번엔 체인 룰을 통해 가중치 편미분을 출력값 편미분으로 바꿔보자. 

4) 남은 편미분을 처리하기 위해 다시 체인 룰로 다음과 같이 표현되는데,  

5) 5번 정의에 의해 이다. 

6) 다시 한번 4번 정의에 의해 가 된다.

7) 모든 k중에 현재 i번째 가중치에 대해서만 편미분 중이므로 최종적으로 가 된다.



점진적 하강법은 미분직선을 따라 곡선의 극점을 향하는 방법으로 생각하면 되는데,


이를 위해 작은 상수인 학습률을 도입하면  가 얻어진다.


수식의 의미는 다음과 같다.


어떤 입력 노드가 출력 노드의 오차에 기여했다면 두 노드의 연결 가중치를 입력 노드의 출력 + 출력 노드의 오차를 고려해서 조절해야 한다는 것이다.


'머신러닝' 카테고리의 다른 글

머신러닝 셋째날 - 가중치를 갱신하는 세 가지 방법(미완성)  (0) 2018.03.29
머신러닝 첫날 - 용어  (0) 2018.02.07

현실에선 사칙연산과 괄호가 포함된 수식을 중위 표기법으로 기술한다.


예를들어 3 + 4 와 같은 꼴이다.



하지만 3 + ( 4 - 7 ) * 8 + 3 * 4 와 같이 우선순위가 꼬여버린 수식은 컴퓨터가 알아먹기 힘들다.


하지만 수식계산은 연산 순서만 잘 정리되면 술술 풀린다.


목표는 숫자(피연산자)는 가만히 냅두고, 연산자들의 서열만 정리시켜주려는 것이다.


위 수식의 연산순서를 그래프로 나타내면 다음과 같다.



위 그래프를 중위순회하면 원래의 수식이 나온다. 위 그래프를 후위순회하면 후위표기법대로 기술된다.


3 4 7 - 8 * + 3 4 * +


우리가 보기엔 해괴한 수식이지만, 컴퓨터가 보기엔 앞에서 부터 계산만 하면 되는 편한 식이다.(괄호가 없다)


어떻게 계산 하냐면, 앞에서부터 보면서 연산자가 나오면 앞의 두 피연산자를 뽑아 연산하는 것이다. 다음과 같다.


1. - 때문에 4와 7을 뺀 -3을 기록한다.


2. * 때문에 (1)의 -3과 8을 곱한 -24를 기록한다.


3. + 때문에 (2)의 -24와 3을 더한 -21을 기록한다.


4. * 때문에 3과 4를 곱한 12를 기록한다.


5. + 때문에 (3)과 (4)의 -21과 12를 더한 -9를 기록한다.


6. 최종기록 -9가 결과다.


따라서 계산하는데 O(n) 걸린다.



따라서 중위식을 후위식으로 변환하는데 O(n)만 걸리면 아름다운 알고리즘이 될 것이다.


이제부터 중위식을 후위식으로 변환하는 과정을 설명하고자 한다.


하려는 짓은 결국엔 연산순서를 잘 일렬로 세워주는 것이다. 숫자는 앞에서 부터 잘 기억만 하면 된다.



아이디어는 다음의 생각들을 잘 섞으면 된다.


1. +와 -는 당연히 *와 /보다 나중에 계산해야 한다.


2. (는 수식안에 새로운 수식이 생기게 한다.


3. )는 그 새로운 수식을 닫는 역할을 한다.


4. 따라서 곱하기 > 더하기 > 괄호질로 연산 우선순위가 높다. ( 다음을 생각해보자. (1+2)*3 ) 



이제 이 아이디어로 중위식을 앞에서부터 보면서 후위식으로 바꿔보자


1. 현재 문자가 ( 라면 스택에 ( 를 넣어준다. 새로운 수식이 언제 시작되었는지 기억하기 위함이다.


2. 현재 문자가 ) 라면 수식이 끝난 것이다. 스택에 ( 가 보일 때 까지 파내면서 후위식에 기록한다. ( 는 버린다.


괄호질은 서열이 제일 낮기때문이다.


3. 현재 문자가 연산자라면, 서열을 정해야 한다. 스택에 나보다 쎈 연산자가 있다면 파내고 후위식에 기록한다.


나와 우선순위가 같은 연산자라면, 수식의 왼쪽이 우선순위가 더 높으므로 사실 나보다 쎈 연산자다. 파내고 기록해야한다.


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
#include "calc.h"
#include <stack>
using namespace std;
 
int order[256];
char post[202];
 
int stoi(char* from, char* to) {
    int ans = 0;
    int t = 1;
    while (1) {
        ans += (*to - '0') * t;
        t *= 10;
 
        if (from == to)
            break;
        else
            to--;
    }
    return ans;
}
 
int calc(char str[])
{
    order['('] = order[')'] = 0;
    order['+'] = order['-'] = 1;
    order['*'] = order['/'] = 2;
 
    char* infix = str;
    char* postfix = post;
 
    stack<char> st;
    while (*infix) {
        if (*infix == '(') {
            st.push('(');
            infix++;
        }
        else if (*infix == ')') {
            while (st.top() != '(') {
                *postfix++ = st.top();
                *postfix++ = ' ';
                st.pop();
            }
            st.pop();
            infix++;
        }
        else if (*infix == '+' || *infix == '-' || *infix == '*' || *infix == '/') {
            while (!st.empty() && order[*infix] <= order[st.top()]) {
                *postfix++ = st.top();
                *postfix++ = ' ';
                st.pop();
            }
            st.push(*infix++);
        }
        else if ('0' <= *infix && *infix <= '9') {
            do {
                *postfix++ = *infix++;
            } while ('0' <= *infix && *infix <= '9');
            *postfix++ = ' ';
        }
    }
 
    while (!st.empty()) {
        *postfix++ = st.top();
        *postfix++ = ' ';
        st.pop();
    }
    --postfix;
    *postfix = '\0';
    //중위표기법 -> 후위표기법
 
    stack<int> ans;
    postfix = post;
    char* from = post;
    char* to = post;
    bool started = false;
 
    while (*postfix) {
        if (*postfix == '+') {
            int a = ans.top(); ans.pop();
            int b = ans.top(); ans.pop();
            ans.push(a + b);
            started = false;
        }
        else if (*postfix == '-') {
            int a = ans.top(); ans.pop();
            int b = ans.top(); ans.pop();
            ans.push(b - a);
            started = false;
        }
        else if (*postfix == '*') {
            int a = ans.top(); ans.pop();
            int b = ans.top(); ans.pop();
            ans.push(a * b);
            started = false;
        }
        else if (*postfix == ' ') {
            if (started) {
                ans.push(stoi(from, to));
                started = false;
            }
        }
        else {
            if (!started) {
                from = to = postfix;
                started = true;
            }
            else
                to = postfix;
        }
        postfix++;
    }
    //후위표기법 계산
 
    return ans.top();
}
cs


calc 함수는 문자열을 받아 계산결과를 리턴해준다.

'알고리즘 > 미분류' 카테고리의 다른 글

백준) 2512 예산  (0) 2018.07.19
백준) 11003 최소값 찾기  (0) 2018.07.13
백준) 2257 화학식량  (0) 2018.01.31
백준) 2841 외계인의 기타 연주  (0) 2018.01.22
백준) 3986 좋은 단어  (0) 2018.01.22

최종 순위




기존 위상이 주어지고, 노드끼리의 위상을 뒤바꿨을 때, 새롭게 위상들이 잘 정렬되는지 확인해야 하는 문제다.

따라서 그래프를 잘 정의해서 위상이 뒤바뀜을 잘 데이터로 표현해야 한다.


위상이 뒤바뀌면 그래프에선 무슨 일이 생길까?

주의할 점은 두 노드끼리의 위상순서만 바꾸는 것이지, 다른 노드들와의 위상순서는 그대로야 한다는 점이다.


첫번째 테스트 케이스를 보면 위상순서는 5 < 4 < 3 < 2 < 1 이다.

이후 2와 4 // 3과 4의 위상순서를 바꾸라고 한다.

기존의 위상비교는 2 > 4 // 3 > 4 였으니, 2 < 4 // 3 < 4로 바꿔야 한다.

이 때 기존의 위상비교, 예를 들어 5 < 4 나 3 < 1 같은 순서는 바뀌면 안되는 것이다.


그래프에선 간선만 휘까닥 뒤집어주면 된다. 애초에 a->b로 진출하는 간선이었다면,

이는 명확히 위상순서가 a<b임을 나타내고 있다.

따라서 간선만 a<-b로 바꿔주면 기존의 위상순서를 지키면서 바꿔줄 수 있다.


이제 그래프를 무엇으로 표현할지 생각해보자.

인접리스트로 표현한 그래프라면 뒤집어야 할 해당간선을 찾는데 해당 리스트를 전부 뒤져야 한다.

하지만 위상정렬을 위한 큐질에서, 진출간선을 찾는 것은 그냥 리스트 전부를 보면 되는데 간편함이 있다.


반면 인접행렬로 표현한 그래프라면 뒤집어야 할 해당간선을 바로 찾을 수 있음에 이점이 있다.

하지만 위상정렬을 위한 큐질에서, 진출간선을 찾는 것은 해당 행을 전부 봐야하는데 단점이 있다.


큐질에서 어차피 둘 다 O(n)이므로 인접행렬로 하자.

주의할 점은 기존 순위로 간선을 만들 때에, 5->4->3->2->1로 간선 4개만 만드는게 아니라,

5->4, 5->3, 5->2, 5->1
4->3, 4->2, 4->1
3->2, 3->1,
2->1

모든 간선을 만들어줘야 한다는 점이다. 이래야 나중에 간선을 뒤집을 때에 기존 위상순서를 유지할 수 있다.


정답은 세 가지로 분류되는데, 확실한 순위가 정해지든지(1), 순위가 안정해지든지(2), 데이터에 일관성이 없든지(3) 세 가지다.

(1)은 위상정렬이 완료되면 당연한 결과다.

(2)는 테크트리가 완료되는 노드가 동시에 2개 이상 생긴다는 뜻으로, 큐에 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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;
 
int tc, n, m, a, b;
int mat[501][501], order[501], in[501];
 
int main() {
    scanf("%d", &tc);
    while (tc--) {
        memset(mat, 0, sizeof(mat));
        memset(in, 0, sizeof(in));
 
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &order[i]);
 
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                mat[order[i]][order[j]] = 1;
                in[order[j]]++;
            }
        }
 
        scanf("%d", &m);
        for (int i = 0; i < m; ++i) {
            scanf("%d %d", &a, &b);
            if (mat[a][b]) {
                mat[a][b] = 0;
                mat[b][a] = 1;
                in[b]--, in[a]++;
            }
            else {
                mat[b][a] = 0;
                mat[a][b] = 1;
                in[a]--, in[b]++;
            }
        }
 
        queue<int> q;
        for (int i = 1; i <= n; ++i)
            if (!in[i])
                q.push(i);
 
        bool certain = true;
        vector<int> ans;
        while (!q.empty()) {
            if (q.size() > 1) {
                certain = false;
                break;
            }
 
            int cur = q.front();
            q.pop();
            ans.push_back(cur);
 
            for (int next = 1; next <= n; ++next) {
                if (mat[cur][next]) {
                    in[next]--;
                    if (!in[next])
                        q.push(next);
                }
            }
        }
 
        if (!certain) //uncertain
            puts("?");
        else if (ans.size() == n) { //possible
            for (int i = 0; i < n; ++i)
                printf("%d ", ans[i]);
            puts("");
        }
        else //impossible
            puts("IMPOSSIBLE");
    }
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 2637 장난감조립  (0) 2018.02.21
백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20

장난감조립




완제품을 조립하기위해 기본 부품들과 기본 부품들로 만드는 중간 부품들이 필요하다.

기본->중간 // 중간->중간 // 중간->완제품 으로 만들기 위해 필요한 개수가 주어질 때,

완제품을 만들기 위해 필요한 기본 부품들의 갯수를 구해보자.


테크트리를 탄다는 점에서 위상정렬을 생각해 볼 수 있다.

또한 부품을 여러개 써야 다음 단계로 넘어갈 수 있다는 점에서, 간선에 그 몇개에 해당하는 정보도 저장해야 한다.

그리으로 나타내면 다음과 같다.


간선을 잘 정의해서 그래프를 구성하자.

또한 각 노드마다 어떤 기본 부품이 몇개 필요한지 저장할 배열도 필요하다.

기본 부품은 진입차수가 0인 노드임을 금방 알 수 있다. 기본 부품들의 부품배열엔 자기 자신만 들어가 있을 것이다.


이제 위상정렬을 위한 큐질을 하면서 노드의 부품배열에 간선의 가중치를 전부 곱해서 다음 노드의 부품배열에 더해주자.

이후 간선을 제거해가면서 진입차수가 0이 된다면 부품이 완성된 것이고, 다음 단계로 넘어갈 수 있다. 큐에 넣는다.

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
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
struct edge {
    int num, val;
};
int blocks[101][101];
int in[101];
int n, m, x, y, k;
 
int main() {
    scanf("%d %d", &n, &m);
    vector<vector<edge>> vec(n+1);
 
    for (int i = 0; i < m; ++i) {
        scanf("%d %d %d", &x, &y, &k);
        vec[y].push_back({ x,k });
        in[x]++;
    }
 
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (!in[i]) {
            q.push(i);
            blocks[i][i] = 1;
        }
    }
        
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for (auto next : vec[cur]) {
            for (int i = 1; i <= n; ++i)
                blocks[next.num][i] += blocks[cur][i] * next.val;
 
            in[next.num]--;
            if (!in[next.num])
                q.push(next.num);
        }
    }
 
    for (int i = 1; i <= n; ++i)
        if (blocks[n][i])
            printf("%d %d\n", i, blocks[n][i]);
 
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 3665 최종 순위  (0) 2018.02.21
백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20

Strahler 순서




위상정렬의 변형문제.

strachler 순서가 정해지는 데 일련의 규칙이 있고, 따라서 간선을 지울 때 다른 작업을 추가로 해줘야 한다.


먼저 진입차수가 0인 노드들의 strachler 순서는 0이다. 이제 이 노드들이 큐에서 꺼내질 때, 노드의 진출 간선들을 지우면서

규칙에 따른 작업을 한다.


규칙은 다음과 같다.

  • 나머지 노드는 그 노드로 들어오는 강의 순서 중 가장 큰 값을 i라고 했을 때, 들어오는 모든 강 중에서 Strahler 순서가 i인 강이 1개이면 순서는 i, 2개 이상이면 순서는 i+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
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
struct Strahler {
    int max, order_cnt[1001], order;
};
 
int in[1001];
int k, kk, m, p, a, b;
 
int main() {
    scanf("%d", &k);
    while (k--) {
        scanf("%d %d %d", &kk, &m, &p);
        for (int i = 1; i <= m; ++i)
            in[i] = 0;
 
        vector<vector<int>> vec(m + 1);
        for (int i = 0; i < p; ++i) {
            scanf("%d %d", &a, &b);
            vec[a].push_back(b);
            in[b]++;
        }
 
        vector<Strahler> st(m + 1);
        queue<int> q;
        for (int i = 1; i <= m; ++i) {
            if (!in[i]) {
                q.push(i);
                st[i].order = 1;
            }
        }
 
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
 
            for (auto next : vec[cur]) {
                if (st[next].max < st[cur].order)
                    st[next].max = st[cur].order;
 
                st[next].order_cnt[st[cur].order]++;
 
                in[next]--;
                if (!in[next]) {
                    if (st[next].order_cnt[st[next].max] == 1)
                        st[next].order = st[next].max;
                    else if (st[next].order_cnt[st[next].max] > 1)
                        st[next].order = st[next].max + 1;
                    q.push(next);
                }
            }
        }
        printf("%d %d\n", kk, st[m].order);
    }
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 3665 최종 순위  (0) 2018.02.21
백준) 2637 장난감조립  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20

ACM Craft


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



전의 게임 개발 (https://www.acmicpc.net/problem/1516)과 같은 문제다.


게임 개발은 모든 건물의 최소 건설 완료 시간을 물어봤다면, 이 문제는 한 건물만 물어본다.



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
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int time[1001], in[1001];
int t, n, k, a, b, w;
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &k);
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &time[i]);
            in[i] = 0;
        }
 
        vector<vector<int>> vec(n + 1);
        for (int i = 0; i < k; ++i) {
            scanf("%d %d", &a, &b);
            vec[a].push_back(b);
            in[b]++;
        }
 
 
        vector<int> ans(n + 1);
        queue<int> q;
        for (int i = 1; i <= n; ++i) {
            if (!in[i]) {
                q.push(i);
                ans[i] = time[i];
            }
        }
 
        scanf("%d", &w);
        while (!q.empty()) {
            int m = 0;
            int cur = q.front();
            q.pop();
            if (cur == w)
                break;
 
            for (auto next : vec[cur]) {
                in[next]--;
 
                if (ans[next] < ans[cur] + time[next])
                    ans[next] = ans[cur] + time[next];
 
                if (!in[next])
                    q.push(next);
            }
        }
        printf("%d\n", ans[w]);
    }
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 2637 장난감조립  (0) 2018.02.21
백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20
백준) 1766 문제집  (0) 2018.02.20

게임 개발


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



테크트리를 타고 모든 건물을 지어야 한다. 모든 건물을 짓는데 시간이 얼마나 들까?


생각해야 할 점은 건물들이 동시에 지어질 수 있다는 점이다.


예를 들어 현재 배럭과 벙커를 지을 수 있다면, 배럭을 짓는데 시간이 더 오래 걸리므로 배럭 건설시간이 정답이 된다.



큐는 현재 지을 수 있는 건물(진입차수가 0이 된 노드)을 담고 있으므로,


큐를 건설시간이 작은 순으로 정렬되는 우선순위 큐로 바꾼다면, 맨 뒤에 있는 배럭이 정답에 반영될 것이다.



다르게 말하자면,


a->b (10)// c->b (20)라는 테크트리에 대해, 


b를 짓기 위해선 a와 c를 둘 다 지어야 하지만, b를 짓기 위한 준비 시간은 c만 포함된다.



따라서 b로 진입하는 두 간선 중 가벼운 a가 먼저 지어지면서 간선이 없어지지만, 무거운 c간선이 남아있으므로


정답에 반영되지 않는다.


다음으로 c간선이 없어지면서 b를 지을 수 있게되었다. 이제 가장 무거웠던 c간선의 20초가 정답에 들어간다.


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
#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
 
struct build {
    int num, time;
};
bool operator <(const build& a, const build& b) {
    if (a.time != b.time)
        return a.time > b.time;
    return a.num > b.num;
}
build buildings[501];
 
int n, a, b, c;
int in[501];
 
int main() {
    scanf("%d", &n);
    vector<vector<int>> vec(n + 1);
 
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a);
        buildings[i].time = a;
 
        while (1) {
            scanf("%d", &a);
            if (a == -1)
                break;
 
            vec[a].push_back(i);
            in[i]++;
        }
    }
 
    priority_queue<build> q;
    for (int i = 1; i <= n; ++i) {
        if (!in[i])
            q.push({i,buildings[i].time});
    }
 
    while (!q.empty()) {
        int cur = q.top().num;
        q.pop();
 
        for (auto next : vec[cur]) {
            in[next]--;
            if (!in[next]) {
                buildings[next].time += buildings[cur].time;
                q.push({next, buildings[next].time});
            }    
        }
    }
 
    for (int i = 1; i <= n; ++i)
        printf("%d\n", buildings[i].time);
 
    return 0;
}
cs


'알고리즘 > Topological sort 위상정렬' 카테고리의 다른 글

백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 2623 음악프로그램  (0) 2018.02.20
백준) 1766 문제집  (0) 2018.02.20
백준) 2252 줄 세우기  (0) 2018.02.19

+ Recent posts

티스토리툴바