음악프로그램





줄 세우기 문제(http://js1jj2sk3.tistory.com/94?category=755224)와 같은 위상정렬문제다.


다만 간선을 만드는 과정과 사이클의 유무를 확인하는 데 유의하자.


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


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

백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 1766 문제집  (0) 2018.02.20
백준) 2252 줄 세우기  (0) 2018.02.19

문제집


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


위상정렬 문제.

다만 스페셜 저지가 아닌만큼, 같은 위상이라도 특수조건이 주어진다.

예제의 경우에, 3과 4는 같은 위상이지만, 조건3에 의해 3이 더 쉬운문제이므로 3을 먼저 풀어야 한다.

이제 3이 없어졌으니까(3이 뿜는 간선도 사라졌다) 문제 4와 1은 같은 위상이다. 조건 3에 의해 1을 먼저 푼다.


즉 큐는 큐지만, 문제 번호가 낮은 걸 먼저 pop해줄 자료구조로 우선순위 큐를 쓰면 풀 수 있다.

heap을 만들어서 풀어봤지만 속도는 같았다.


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
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int n, m, a, b;
int in[32001];
 
struct heap {
    int* arr;
    int cnt = 0;
 
    heap(int n) { arr = new int[n]; }
    ~heap() { delete[] arr; }
 
    void swap(int& a, int& b) {
        int t = a; a = b; b = t;
    }
 
    void push(int x) {
        ++cnt;
        arr[cnt] = x;
        int v = cnt;
 
        while (v / 2 >= 1 && arr[v/2] > arr[v]) {
            swap(arr[v], arr[v / 2]);
            v /= 2;
        }
    }
 
    void pop() {
        arr[1] = arr[cnt];
        cnt--;
 
        int v = 1;
        while (v * 2 <= cnt) {
            int iv = v * 2;
            if (iv + 1 <= cnt && arr[iv] > arr[iv + 1])
                iv++;
            if (arr[v] > arr[iv]) {
                swap(arr[v], arr[iv]);
                v = iv;
            }
            else
                break;
        }
    }
    int top() { return arr[1]; }
    bool empty() { return cnt == 0; }
};
 
int main() {
    scanf("%d %d", &n, &m);
    vector<vector<int>> edge(n + 1);
    for (int i = 0; i < m; ++i) {
        scanf("%d %d", &a, &b);
        edge[a].push_back(b);
        in[b]++;
    }
 
    //priority_queue<int> pq;
    heap pq(n + 1);
    for (int i = 1; i <= n; ++i)
        if (!in[i])
            pq.push(i);
 
    while (!pq.empty()) {
        int t = pq.top();
        printf("%d ", t);
        pq.pop();
 
        for (auto next : edge[t]) {
            in[next]--;
            if (in[next] == 0)
                pq.push(next);
        }
    }
 
    return 0;
}
cs


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

백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20
백준) 2252 줄 세우기  (0) 2018.02.19

문제집


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


그래프가 유향 그래프라면, 노드 간에는 위상이 정해진다.


a노드에서 b노드로 진출하는 간선이 있다면, a와 b의 위상이 서로 다른 셈이다.



실생활에서 노드간의 위상은, 선수강과목이나 테크트리에서 찾아볼 수 있다.


넥서스가 있어야 게이트웨이를 지을수 있드시, 객체지향프로그래밍을 들어야 자료구조를 들을 수 있드시,


간선의 방향에 따라 노드간에 위상이 결정된다.



위상정렬은, 이와 같은 유향 그래프에서 노드 간의 위상을 순서대로 구하는 알고리즘이다.


따라서 유향그래프 내 사이클이 존재한다면, 즉 DAG이 아니라면 위상정렬할 수 없다.



여러가지 방법이 있지만, 주로 사용하는 진입차수를 이용한 풀이를 소개하고자 한다.


진입차수는 해당노드를 향한 간선의 개수를 뜻한다.


즉 1->3 // 2->3 의 간선이 있다면, 노드3의 진입차수는 2다.



위상정렬은 우선 모든 노드의 진입차수를 구하고 시작한다.


다음에는 진입차수가 0인 노드들을 전부 큐에 넣는다.


이제 큐에서 하나씩 꺼내면서 노드에서 나가는 간선들을 모두 제거한다.


현재 간선은 진입차수로 표현되었기 때문에, 진입차수를 표현하고 있는 데이터를 변경하면 되겠다.


제거하고 난 뒤 만약 진입차수가 0이 된 노드가 있다면 큐에 넣는다.



진입차수가 0인 노드들을 찾고, 딸린 간선을 제거하고,


다시 진입차수가 0인 노드들을 처리하는 부분문제로 이어진다고 생각하면 편하다.



사이클의 유무는 어떻게 판단할까?


만약 큐를 전부 소모했음에도 위상이 판단되지 않은 노드가 여전히 있다면 사이클때문임이 자명하다.



다음은 2252번 줄 세우기에 대한 해답이다.


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


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

백준) 9470 Strahler 순서  (0) 2018.02.21
백준) 1005 ACM Craft  (0) 2018.02.21
백준) 1516 게임 개발  (0) 2018.02.20
백준) 2623 음악프로그램  (0) 2018.02.20
백준) 1766 문제집  (0) 2018.02.20

문명 


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



제대로 푼건지 모르겠다. 주변에 잘하시는 분들을 보면 다 유니온 파인드를 최적화하셨던데,


쌩 유니온 파인드로 제출했더니 맞긴했다.


나중에 재채점되면 틀릴 것 같지만, 일단 풀이를 공유하고자 한다.




맵에 k개의 문명 발상지가 있고, 매 턴마다 문명들은 사방향으로 진출하고, 경계선이 맞닿는다면(사방향) 해당 문명을 흡수한다.


이렇게 턴들이 진행될 때, 몇번째 턴에 모든 문명이 하나로 통일될 것인지 계산해야 한다.


예외적으로, 처음부터 k개의 발상지들이 모두 붙어있었다면, 바로 하나로 통일되고 답은 0이다.



사방향과 최소턴이라는 키워드로 일단 bfs를 쓰기로 했다.


탈출조건은, 문명이 줄고 줄어서 하나로 통일될 때 인데, 이를 구분하기 위해 유니온-파인드를 썼다.


맞닿는 경우에, 두 문명의 부모를 찾고, 다르다면 유니온하면서 문명 카운트를 하나 줄이는 것이다.


만약 카운트가 1이되면 bfs는 종료된다.



맞닿는 경우를 이중포문으로 어거지로 짠 것 같은데, 일단 맞았으니까 기분좋게 넘어간다.


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
#include <stdio.h>
#include <queue>
using namespace std;
 
int map[2000][2000];
int dir[4][2] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
int n, k, a, b;
 
struct civil{
    int num;
    int y, x;
};
queue<civil> init, q;
 
int p[100001];
 
int find(int x){
    if (x == p[x])
        return x;
    else
        return p[x] = find(p[x]);
}
void unite(int x, int y){
    x = find(x);
    y = find(y);
 
    if (x != y)
        p[x] = y;
}
 
int main(){
    scanf("%d %d", &n, &k);
 
    for (int i = 1; i <= k; ++i){
        scanf("%d %d", &a, &b);
        init.push({ i, b - 1, a - 1 });
        p[i] = i;
 
        map[b - 1][a - 1] = i;
    }
 
    while (!init.empty()){
        civil tmp = init.front();
        init.pop();
 
        for (int i = 0; i < 4; ++i){
            int yy = tmp.y + dir[i][0];
            int xx = tmp.x + dir[i][1];
 
            if (yy < 0 || xx < 0 || yy >= n || xx >= n)
                continue;
 
            if (map[yy][xx] != 0){
                if (find(tmp.num) != find(map[yy][xx])){
                    unite(tmp.num, map[yy][xx]);
                    map[yy][xx] = tmp.num;
                    k--;
                }
            }
        }
        q.push({ map[tmp.y][tmp.x], tmp.y, tmp.x });
    }
 
    if (k == 1){
        printf("0");
        return 0;
    }
 
    int ans = 0;
    while (!q.empty()){
        ans++;
        int s = q.size();
        for (int i = 0; i < s; ++i){
            civil tmp = q.front();
            q.pop();
 
            for (int i = 0; i < 4; ++i){
                int yy = tmp.y + dir[i][0];
                int xx = tmp.x + dir[i][1];
 
                if (yy < 0 || xx < 0 || yy >= n || xx >= n)
                    continue;
 
                if (map[yy][xx] != 0)
                    continue;
 
                map[yy][xx] = tmp.num;
                for (int j = 0; j < 4; ++j){
                    int yyy = yy + dir[j][0];
                    int xxx = xx + dir[j][1];
 
                    if (yyy < 0 || xxx < 0 || yyy >= n || xxx >= n)
                        continue;
 
                    if (map[yyy][xxx] != 0 && find(map[yyy][xxx]) != find(tmp.num)){
                        unite(tmp.num, map[yyy][xxx]);
                        k--;
 
                        if (k == 1){
                            printf("%d", ans);
                            return 0;
                        }
                    }
                }
                q.push({ tmp.num, yy, xx });
            }
        }
    }
}
cs


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

백준) 12100 2048 (Easy)  (0) 2018.04.11
백준) 13460 구슬 탈출 2 // 구 째로탈출2  (0) 2018.04.11
백준) 2615 오목  (0) 2018.02.06
백준) 1182 부분집합의 합  (0) 2018.02.06
백준) 4963 섬의 개수  (0) 2018.01.14

대부분의 소프트웨어들은 명시적이다(explicit)


즉 코더가 일일이 이럴땐 이러케, 저럴땐 저러케 동작하라고 적어놓으면, 고대로 동작한다.


따라서 규칙이 겁나 복잡한(자율주행 자동차) 경우 코더들을 갈아넣어도 만들 수 없는 소프트웨어들이 있기 마련이다.



기계 학습은, 이러한 명시적이지 않은 동작들을 데이터로부터 학습하여 수행할 수 있게하는 알고리즘이다.


데이터들로부터 일반적인 동작을 알아내서 스스로 동작하는 것이다.



이러한 정의 하에, 데이터마이닝과 머신러닝은 교집합이 상당한데,


기계학습은, 데이터로부터 학습하고, 미래를 예측한다는 특성이 강한 반면에,


데이터마이닝은 데이터들에 감춰져있던 속성을 발견하는 특성이 강하다.


가령 사용자들의 sns를 분석해 소비 패턴을 파악하는 경우에 데이터마이닝 속성이 강하다고 할 수 있다.




머신러닝의 학습 방법은 크게 두가지로 나뉜다.



지도 학습(supervised learning)이란


학습할 데이터(training set)에 이미 속성(label, 정답)들이 부여되어 있고, 학습 이후에 올바른 정답(사용자가 원하는)을 밷게 하는 방법이다.


대부분의 머신러닝 분야는 지도 학습이 주를 이루고 있다.


가령 고양이와 사람 사진을 분류하게 학습시킨다던가, 손글씨를 읽어내게 학습시키는 류는 모두 지도 학습방법을 쓴다.


지도학습의 학습 데이터는 {입력, 정답} 쌍이다.



반면 비지도 학습(unsupervised learning)은


사용자도 정답(label)을 모르는 데이터들을 주고 학습시키는 방법이기 때문에


기계 스스로 비슷한 데이터들끼리 모아주는(군집화, clustering) 행동과 밀접하다.


군집화와 속성 분류는 개념은 비슷하지만 완전히 다른 기법이므로 명확히 구별해서 사용해야 한다.


비지도 학습의 학습 데이터는 입력만 있고 정답은 없다.




지도 학습도 데이터 종류에 따라 두 가지로 나눌 수 있다.


고양이와 사람은 명확히 다르기 때문에, 종을 구분하게 학습시키는 것은 분류(classification)라 한다.


반면 키와 같이 범위형으로 주어지는 학습 데이터로, 자식의 키를 예측하게 하는 등의 모델은 회귀분석(regression)이라 한다.


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

머신러닝 셋째날 - 가중치를 갱신하는 세 가지 방법(미완성)  (0) 2018.03.29
머신러닝 둘째날 - 신경망 - 델타 규칙  (0) 2018.03.27

오목


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



오목판이 주어지고 현재 누가 이겼는지를 판별해야한다.


모든 알을 보고 최대한 빨리 판별해보자.



오목에서 승리란 알을 연속으로 5개 두어야 생긴다. 방향은 가로, 세로, 대각선이 가능하다.


왼쪽 위부터 오른쪽으로, 아래로 모든 알을 본다면, 네 가지 방향으로 연속적인지만 판별하면 된다.


1. 아래 2. 오른쪽 3. 우하 대각선 4.우상 대각선



6개 두면 이긴게 아니기 때문에, 기존에 6개를 카운트 한 것을 방향 때문에 5개로 착각할 수 있다.


따라서 5개로 착각하지 않게 하기 위해, 정반대 방향의 돌을 하나 봐서, 현재 보는 돌이 시작점인지 확인할 수 있다.


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
#include <stdio.h>
 
int map[19][19];
int dir[4][2] = { {1,0},{1,1},{0,1},{-1,1} };
 
bool is_in_range(int y, int x) {
    return (y >= 0 && x >= 0 && y < 19 && x < 19);
}
 
int getMap(int y, int x) {
    if (y < 0 || x < 0 || y >= 19 || x >= 19)
        return 0;
    return map[y][x];
}
 
int main() {
    for (int i = 0; i < 19; ++i)
        for (int j = 0; j < 19; ++j)
            scanf("%d", &map[i][j]);
 
    int ans_y = -1, ans_x = -1, ans_c = -1;
 
    for (int d = 0; d < 4; ++d) {
        for (int x = 0; x < 19; ++x) {
            for (int y = 0; y < 19; ++y) {
                if (map[y][x] == 0)
                    continue;
 
                if (getMap(y - dir[d][0], x - dir[d][1]) == map[y][x])
                    continue;
 
                int yy = y, xx = x, cnt = 0;
                while (1) {
                    yy += dir[d][0];
                    xx += dir[d][1];
 
                    if (!is_in_range(yy, xx))
                        break;
 
                    if (map[yy][xx] != map[y][x])
                        break;
 
                    cnt++;
                }
                if (cnt == 4) {
                    ans_y = y;
                    ans_x = x;
                    ans_c = map[y][x];
                }
            }
        }
    }
 
    if (ans_c == -1) {
        printf("0");
        return 0;
    }
 
    printf("%d\n%d %d", ans_c, ans_y + 1, ans_x + 1);
    return 0;
}
cs


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

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

캥거루 세마리




캥거루 세 마리가 직선 위에 존재하고, 양 끝의 캥거루가 나머지 두 마리의 가운데로 점프해서 끼어들 수 있다.

단, 같은 지점에 두마리 이상 존재할 수 없을 때, 점프를 최대한 어람나 할 수 있을까?



세 마리가 동일한 지점에 있다면 항상 같은 결과가 나온다는 생각으로, dp를 시도해 볼 수 있다.


점프 이후 전에 계산했던 상황이 나오면 재활용 할 수 있는 것이다.


각 상황은 세 마리의 위치로 구분되므로, dp[100][100][100]으로 조질 수 있다. 최악의 경우 백만번의 연산을 수행한다.



재귀적으로 왼쪽, 오른쪽 캥거루가 움직일 경우에 최대 점프수를 알아내서, 그 중 최대값에 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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
 
int a, b, c;
int dp[100][100][100];
 
 
int func(int a, int b, int c) {
    if (a + 1 == b && b + 1 == c)
        return 0;
 
    int& ref = dp[a][b][c];
    if (ref != -1)
        return ref;
 
    int pp = 0;
    for (int p = a + 1; p < b; ++p) {
        int t = func(a, p, b);
        if (pp < t)
            pp = t;
    }
 
    int qq = 0;
    for (int q = b + 1; q < c; ++q) {
        int t = func(b, q, c);
        if (qq < t)
            qq = t;
    }
 
    return ref = max(pp, qq) + 1;
}
 
 
int main() {
    memset(dp, -1, sizeof(dp));
 
    scanf("%d %d %d", &a, &b, &c);
    printf("%d", func(a, b, c));
 
    return 0;
}
cs


'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준)15673 헤븐스 키친 2  (0) 2018.10.02
백준) 2156 포도주 시식  (0) 2018.02.04
백준) 1463 1로 만들기  (0) 2018.02.02
백준) 2579 계단 오르기  (0) 2018.02.02
백준) 1149 RGB거리  (0) 2018.02.01

부분집합의 합 





각 원소들을 넣던지, 빼던지 해서 2가지 경우씩 발생한다. 따라서 모든 원소와 관련해 부분집합은 2^n개 생긴다.

원소가 최대 20개 이므로 브루트포스로 백만번의 연산으로 답을 얻을 수 있다.

하지만 분명 쓸따리 없는 연산도 존재한다.


가령 예를 들어 {0, 1, 2, 3, 4, 5}의 집합에서, S=6을 만드는 부분집합을 찾기위해, 첫 원소부터 넣을 것인지를 고려하다가,

{0, 1, 2, 3}까지 더해서 이미 6을 만들었는데, 나머지 {4, 5}를 넣을지 뺄지 고민할 필요가 없는 것이다.


하지만 이러한 가지치기(prunning)는 뒤의 수가 앞의 수보다 크다는 가정하에 진행되므로, 배열의 정렬이 필요하다.

정렬 이후엔 재귀안에 가지치는 코드를 넣어주자.


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
#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n[20], N, S, ans;
 
void dfs(int cur_sum, int cnt, int idx) {
    if (idx >= N)
        return;
 
    if (cur_sum + n[idx] > S) {
        if (n[idx] >= 0)
            return;
    }
 
    if (cur_sum + n[idx] == S)
        ans++;
 
    dfs(cur_sum + n[idx], cnt + 1, idx + 1);
    dfs(cur_sum, cnt, idx + 1);
}
 
int main() {
    scanf("%d %d", &N, &S);
    for (int i = 0; i < N; ++i)
        scanf("%d", &n[i]);
 
    sort(n, n + N);
    dfs(0, 0, 0);
 
    printf("%d", ans);
 
    return 0;
}
cs


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

백준) 14868 문명 - bfs, 유니온 파인드  (1) 2018.02.08
백준) 2615 오목  (0) 2018.02.06
백준) 4963 섬의 개수  (0) 2018.01.14
백준) 1012 유기농 배추  (0) 2018.01.14
백준) 2206 벽 부수고 이동하기  (0) 2018.01.14

포도주 시식




포도주를 최대한 마시려고 한다. 앞에서 부터 잔들을 마실 수 있지만, 연속해서 세잔은 마실 수 없다.

계단 문제(http://js1jj2sk3.tistory.com/85?category=725178)와 같은 상황이다.

다만 한 번에 한 층만 오를 수 있게 조건만 변화했을 뿐이다.

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 <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
int n;
int arr[10000];
int dp[10000][3];
 
int func(int p, int cnt) {
    if (p >= n)
        return 0;
 
    int& ref = dp[p][cnt];
    if (ref != -1)
        return ref;
 
    if (cnt == 0) {
        int a = func(p + 1, 1) + arr[p];
        int b = func(p + 1, 0);
 
        return ref = max(a, b);
    }
    else if (cnt == 1) {
        int a = func(p + 1, 2) + arr[p];
        int b = func(p + 1, 0);
 
        return ref = max(a, b);
    }
    else
        return ref = func(p + 1, 0);
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
 
    memset(dp, -1, sizeof(dp));
 
    printf("%d", func(0, 0));
 
    return 0;
}
cs


'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준)15673 헤븐스 키친 2  (0) 2018.10.02
백준) 2965 캥거루 세마리  (0) 2018.02.06
백준) 1463 1로 만들기  (0) 2018.02.02
백준) 2579 계단 오르기  (0) 2018.02.02
백준) 1149 RGB거리  (0) 2018.02.01

1로 만들기





디피로 완전탐색하자.


덜 논리적이라 디피는 재귀로 풀곤하는데(2)(완전 거의 대부분) 포문풀이(1)와 속도 차이가 4배정도 난다.


또한 재귀적으로 나누기 3의 상태를 보는게(3) 더 빠르다. 아마 더 빨리 1에 가까워져서가 아닐까 싶다



(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
 
int dp[1000001];
 
int main() {
    int n, i;
    scanf("%d", &n);
    dp[1] = 0, dp[2] = 1, dp[3] = 1;
    for (i = 4; i <= n; i++) {
        dp[i] = dp[i - 1] + 1;
        if (i % 2 == 0 && dp[i / 2] + 1 < dp[i])
            dp[i] = dp[i / 2] + 1;
        if (i % 3 == 0 && dp[i / 3] + 1 < dp[i])
            dp[i] = dp[i / 3] + 1;
    }
    printf("%d", dp[n]);
}
cs


(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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
 
#define fail 987654321
 
 
int n, dp[1000001];
 
int func(int x) {
    if (x < 1)
        return fail;
 
    if (x == 1)
        return 0;
 
    int& ref = dp[x];
    if (ref != -1)
        return ref;
 
    int a = fail, b = fail, c = fail;
    if (x % 3 == 0)
        a = func(x / 3) + 1;
    if (x % 2 == 0)
        b = func(x / 2) + 1;
    c = func(x - 1) + 1;
    
    return ref = min(min(a, b), c);
}
 
int main() {
    scanf("%d", &n);
    memset(dp, -1, sizeof(dp));
    printf("%d", func(n));
 
    return 0;
}
cs


(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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
 
 
#define fail 987654321
 
 
int n, dp[1000001];
 
int func(int x) {
    if (x < 1)
        return fail;
 
    if (x == 1)
        return 0;
 
    int& ref = dp[x];
    if (ref != -1)
        return ref;
 
    int a = fail, b = fail, c = fail;
    c = func(x - 1) + 1;
    if (x % 2 == 0)
        b = func(x / 2) + 1;
    if (x % 3 == 0)
        a = func(x / 3) + 1;
    
    return ref = min(min(a, b), c);
}
 
int main() {
    scanf("%d", &n);
    memset(dp, -1, sizeof(dp));
    printf("%d", func(n));
 
    return 0;
}
cs


'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준) 2965 캥거루 세마리  (0) 2018.02.06
백준) 2156 포도주 시식  (0) 2018.02.04
백준) 2579 계단 오르기  (0) 2018.02.02
백준) 1149 RGB거리  (0) 2018.02.01
백준) 2342 Dance Dance Revolution  (0) 2017.09.21

+ Recent posts

티스토리툴바