Gorio Tech Blog search

BOJ 06086(최대 유량) 문제 풀이

|

참조

분류 URL
문제 최대 유량
참조 라이브러리 dinic.h, sharifa_header.h
이 글에서 설명하는 코드 06086_최대 유량

개요

시간복잡도: $ O(V^2 \cdot E) $

공간복잡도: $ O(V + E) $

문제 풀이

이 문제는 생긴 것부터가 네트워크 플로우 문제이다. Maximum Flow를 찾는 많은 알고리즘이 있지만, 디닉 알고리즘이 가장 빠르기 때문에 필자는 이 알고리즘을 사용하도록 하겠다.

구현

네트워크 플로우 문제는 모델링이 굉장히 중요한데, 이 문제는 모델링이 어렵지는 않다.

주의할 점으로는 간선을 입력받아 그래프를 생성할 때, 각 파이프가 양방향 수송이 가능하다고 하였으므로 최대 유량을 똑같이 (0이 아닌) cap으로 설정해주어야 한다는 것이다. 또 문자를 정점 번호로 변환할 때 번호가 겹치지 않도록 주의한다.

#include "../library/dinic.h"

#define MAX_V 52
#define S 0     // source
#define T 25    // sink
#define INF 1000000009

int E, cap, u, v;
Dinic network(MAX_V, S, T);

int main_06086() {
    ios::sync_with_stdio(false);    cin.tie(NULL);
    cin >> E;

    while (E--) {
        char x, y;
        cin >> x >> y >> cap;

        u = 'A' <= x && x <= 'Z' ? x - 'A' : x - 'a' + 26;
        v = 'A' <= y && y <= 'Z' ? y - 'A' : y - 'a' + 26;

        network.addEdge(u, v, cap, true);
    }

    int ans = 0;

    while (network.bfs()) {
        network.reset_next_v();
        while (true) {
            int flow = network.dfs(S, INF);
            if (!flow)
                break;
            ans += flow;
        }
    }

    cout << ans;

    return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 당연히 틀린다. 저런 헤더 파일이 채점 사이트에 있을까?

Comment  Read more

디닉 알고리즘(Dinic's Algorithm)

|

참조

분류 URL
문제 최대 유량
응용 문제 스포일러 1
참조 라이브러리 sharifa_header.h, bit_library.h
이 글에서 설명하는 라이브러리 dinic.h

그림 출처: wikipedia


개요

시간복잡도: $ O(V^2 \cdot E) $

공간복잡도: $ O(V^2) $ 또는 $ O(V+E) $

  • V는 정점(vectex)의 수, E는 간선(edge)의 수이다.

이 글에서는 네트워크 플로우(Network Flow) 분야에서 Maximum Flow를 구하는 알고리즘인 디닉 알고리즘에 대해서 설명한다.

Maximum Flow를 구하는 다른 대표적인 알고리즘으로 에드몬드-카프 알고리즘(Edmonds–Karp algorithm), 포드-풀커슨 알고리즘(Ford–Fulkerson algorithm)이 있지만, 현재 PS에서 구현할 만한 알고리즘 중 가장 빠른 알고리즘은 디닉 알고리즘이다. 그래서 여러 개 외울 필요 없이 알고리즘 하나만 알아두는 것이 좋을 듯 하다.

Network Flow(네트워크 플로우)

네트워크 플로우에 대한 기본적인 설명을 조금 적어 두려고 한다. 예를 하나 들면, Network Flow는 파이프가 복잡하게 연결되어 있고, 각 파이프는 물이 흐를 수 있는 최대 양이 정해져 있고, source에서 sink방향으로 물이 흐를 때, 물이 흐를 수 있는 최대 양을 구하는 것이라고 보면 된다.

01_network_flow

  • s는 source를 의미한다. 물이 나오는 원천이라고 생각하면 된다.
  • t는 sink를 의미한다. 물이 최종적으로 들어가는 곳이라 생각하면 된다. 모든 물(유량)은 source에서 sink로 흐른다.
  • 두 정점을 잇는 간선은 해당 정점 사이에 흐를 수 있는 최대 물(유량)을 의미한다. s에서 1번 정점으로 0/10이라고 적혀 있는데, 여기서 10이 최대 유량이다.
  • 잔여유량은 최대유량에서 현재 유량을 뺀 값이다. s에서 1번 정점으로 0/10인 것은 현재 유량이 0이고 따라서 잔여유량은 10이다.

네트워크 플로우의 Maximum Flow는 Minimum Cut과 깊은 연관이 있다.


알고리즘

디닉 알고리즘은 크게 두 단계로 이루어진다.

  1. BFS를 써서 레벨 그래프(Level Graph)를 생성하는 것
  2. DFS를 써서, 레벨 그래프에 기초한 차단 유량(Blocking Flow)의 규칙을 지키면서, 최대 유량을 흘려주는 것

레벨 그래프(Level Graph)

레벨 그래프는 각 정점들에 source로부터의 최단 거리를 레벨 값을 할당한 그래프이다. 아래 그림에서 source의 레벨은 0이되고 source와 인접한 1번과 2번 정점의 레벨은 1, 이후는 2… 등이 된다. 빨간색 숫자로 적혀 있는 것이 레벨이다.

02_residual_capacity

레벨 그래프는 BFS로 구현한다.

차단 유량(Blocking Flow)

디닉 알고리즘에서는, 유량을 흘려보낼 때 레벨 차이가 딱 1이 나는 정점으로만 유량을 보낼 수 있다. 즉 바로 위의 그림에서의 간선과 같은 곳으로만 보낼 수 있다. 레벨이 같아도 안 된다.

유량을 흘려보내는 것은 DFS로 구현한다. source에서 시작하여, 차단 유량 규칙을 만족하는 정점으로만 따라가면서 최종적으로 sink에 도달할 때까지 탐색하는 과정을 반복한다.

위의 레벨 그래프에서는 다음 세 경로를 DFS로 찾을 수 있다.

(s, 1, 3, 4): 유량 4
(s, 1, 4, t): 유량 6
(s, 2, 4, t): 유량 4

반복

BFS 1번 그리고 DFS를 한번씩 해서는 최대 유량이 찾아지지 않는다. 다만 복잡한 것은 아니고, 위의 과정을 반복해주면 된다.

다시 BFS를 돌려 레벨 그래프를 새로 생성한다.

03_residual_capacity

위의 레벨 그래프에서는 다음 경로를 DFS로 찾을 수 있다.

(s, 2, 4, 3, t): 유량 5

다시 레벨 그래프를 그리면, 더 이상 sink로 가는 경로가 없음(sink의 레벨이 $\inf$)을 알 수 있다. 알고리즘을 종료한다.

04_residual_capacity

구현

BFS는 어려운 부분이 아니기 때문에 설명은 생략하도록 하겠다.

DFS의 구현은 조금 까다롭다.

  1. 우선 sink(T)에 도달하면 종료한다.
  2. 종료할 때 max_flow라는 것을 리턴한다. 이는 Network Flow에서 수송량은 경로에 포함된 파이프 최대 유량의 최솟값이기 때문이다. flow의 계산식을 잘 보면 최대 유량과 min 연산을 취하는 것을 볼 수 있다.
  3. 레벨 차이가 1 나는지를 먼저 검사한다. 그리고 그 정점의 잔여 용량이 0보다 큰지 또한 검사한다.
  4. 만약 그런 정점을 찾았으면, 재귀적으로 DFS를 수행한다.
  5. DFS가 리턴되어 반환한 flow 값이 0보다 크면, 아직 DFS로 탐색할 수 있는 경로가 남아 있다는 뜻이다.
  6. 경로를 찾았으므로, 해당 경로를 따라서(스택에 재귀 호출로 쌓인 함수에 의해 자동으로 역추적됨) 잔여 용량을 줄여준다.
  7. 만약 어떤 flow도 0이라면, 경로를 찾지 못한 것이므로 종료한다.
  8. next_v라는 배열(벡터)이 있다. 이는 DFS에서 다음 경로를 효율적으로 찾기 위해 존재하는 배열이다.
    1. DFS로 경로를 탐색할 떄 정점 번호가 낮은 정점부터 탐색한다.
    2. 만약 처음에 1번 정점으로 가는 경로를 모두 찾았다면, 더 이상 1번 정점으로는 갈 필요가 없다. 이때 next_v[u]를 1 증가시켜, 다음부터는 2번 정점부터 탐색을 시작하도록 한다.
    3. 2번도 끝났으면 또 next_v[u]를 증가시킨다. 이를 반복한다.
    4. 코드 상으로는 int &i로 되어 있다. i가 레퍼런스로 선언되어 있기 때문에 for loop의 i++ 구문에 따라 같이 증가한다(i는 next_v[u]와 값을 공유한다)
    int dfs(int u, int max_flow) {
        if (u == T)
            return max_flow;

        for (int &i = next_v[u]; i < edges[u].size(); i++) {
            int v = edges[u][i].v, cap = edges[u][i].cap;

            if (level[u] + 1 == level[v] && cap > 0) {
                int flow = dfs(v, min(max_flow, cap));

                if (flow > 0) {
                    edges[u][i].cap -= flow;
                    edges[v][edges[u][i].ref].cap += flow;
                    return flow;
                }
            }
        }
        return 0;
    }

addEdge 함수의 inv는 각 간선이 양방향 수송이 가능하면 true로 지정하면 된다. sparse graph일 경우를 대비해 edges를 2차원 배열로 표현하지 않고 대신 역방향 간선에 대한 참조를 저장하고 있다. 이러면 정점이 많을 경우에도 메모리 사용량을 줄일 수 있다.

구현은 다음과 같다.

#pragma once

#include "sharifa_header.h"

struct Edge {   // u -> v
    int v, cap, ref;
    Edge(int v, int cap, int ref) :v(v), cap(cap), ref(ref) {}
};

class Dinic {
    int S, T;
    vector<vector<Edge> > edges;    // graph
    // level: 레벨 그래프, next_v: DFS에서 flow 계산 시 역추적에 사용
    vector<int> level, next_v;

public:
    Dinic(int MAX_V, int S, int T):S(S), T(T) {
        edges.resize(MAX_V);
        level.resize(MAX_V);
        next_v.resize(MAX_V);
    }

    void addEdge(int u, int v, int cap, bool inv) {
        edges[u].emplace_back(v, cap, (int)edges[v].size());
        edges[v].emplace_back(u, inv ? cap : 0, (int)edges[u].size() - 1);
    }

    bool bfs() {
        fill(level.begin(), level.end(), -1);

        queue<int> q;
        level[S] = 0;
        q.push(S);

        while (!q.empty()) {
            int u = q.front();   q.pop();
            for (auto edge : edges[u]) {
                int v = edge.v, cap = edge.cap;

                if (level[v] == -1 && cap > 0) {
                    level[v] = level[u] + 1;
                    q.push(v);
                }
            }
        }
        return level[T] != -1;
    }

    void reset_next_v() {
        fill(next_v.begin(), next_v.end(), 0);
    }

    int dfs(int u, int max_flow) {
        if (u == T)
            return max_flow;

        for (int &i = next_v[u]; i < edges[u].size(); i++) {
            int v = edges[u][i].v, cap = edges[u][i].cap;

            if (level[u] + 1 == level[v] && cap > 0) {
                int flow = dfs(v, min(max_flow, cap));

                if (flow > 0) {
                    edges[u][i].cap -= flow;
                    edges[v][edges[u][i].ref].cap += flow;
                    return flow;
                }
            }
        }
        return 0;
    }
};

문제 풀이

BOJ 06086(최대 유량)

문제: 최대 유량

풀이: BOJ 06086(최대 유량) 문제 풀이

스포일러 문제

문제: 스포일러 문제

풀이: 스포일러 풀이

Comment  Read more

BOJ 11658(구간 합 구하기 3) 문제 풀이

|

참조

분류 URL
문제 구간 합 구하기 3
참조 라이브러리 fenwick_tree_2D_BIT.h, sharifa_header.h
이 글에서 설명하는 코드 11658_구간 합 구하기 3

개요

시간복잡도: $ O(N^2 + M \log^2 N) $

공간복잡도: $ O(N^2) $

  • N은 원소의 수, M은 연산의 수이다.

문제 풀이

이 문제도 역시 인덱스 트리라고 부르는 자료구조를 써도 풀리긴 하지만, 펜윅 트리가 굉장히 간단하기 때문에 이것으로 문제를 풀었다.

원소가 하나씩 업데이트될 때, 구간의 합을 구하라는 문제는 그냥 펜윅 트리를 쓰라는 문제이다. 왜냐하면 BIT가 그에 최적화되어 있기 때문이다.

이 문제는 구간 합 구하기와는 달리 2차원이기 때문에, data 배열도 2차원으로 잡아야 한다. 즉, data[][] 형식이 될 것이다.

구간 합을 구하는 것은 1차원을 2차원으로 확장한 것에 불과하다.

  • 1차원은 sum(a,b) = sum(b) - sum(a-1)이었다.
  • 2차원은 sum(x1~x2, y1~y2) = sum(x2, y2) - sum(x1-1, y2) -sum(x2, y1-1) + sum(x1-1, y1-1)이다.
    • 손으로 그림을 딱 한번만 그려보면 위 식이 단번에 이해될 것이다.

업데이트 연산 역시 2차원으로 확장한 것에 불과하다.

구현

이 문제는 2차원이기 때문에 sum과 update에서 중첩 while문을 볼 수 있을 것이다.
그리고 BOJ 02042(구간 합 구하기) 문제 풀이와는 달리 arr 배열을 만들지 않고 풀이를 적었다.

#include "../library/sharifa_header.h"
#include "../library/fenwick_tree_2D_BIT.h"

int N, m;

int main_11658() {
	ios::sync_with_stdio(false);    cin.tie(NULL);

	cin >> N >> m;

    FenwickTree2D BIT(N);

    int w, x1, y1, x2, y2, val;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> val;
			BIT.update(i, j, val);
		}
	}
	while(m--){
        cin >> w >> x1 >> y1;
		if (w){
            cin >> x2 >> y2;
			cout << BIT.sum(x1, y1, x2, y2) << '\n';
        } else {
            cin >> val;
			BIT.update(x1, y1, val);
		}
	}
	return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 당연히 틀린다. 저런 헤더 파일이 채점 사이트에 있을까?

Comment  Read more

BOJ 01280(나무 심기) 문제 풀이

|

참조

분류 URL
문제 나무 심기
이 글에서 설명하는 코드 01280_나무 심기

개요

시간복잡도: $ O(N \log M) $

공간복잡도: $ O(M) $

  • N은 원소의 수, M은 좌표의 범위이다.

순서대로 하나씩 주어지고, $i$번째에 대한 비용이나 시간이 1부터 $(i-1)$번째까지에만 의존하는 형식이라면 BIT, IT, 삽입 정렬, 우선순위 큐를 한번쯤 떠올려 보는 것이 중요하다.

문제 풀이

우선 문제의 정의에 따라, 문제의 정답(=2번 나무부터 N번 나무까지 심는 비용의 곱)을 수식으로 정리하면 다음과 같다.

$ A := $ 문제의 정답
$ p_i := i$번 나무가 심어진 위치
$ c_i := i$번 나무를 심는 비용

$ c_i = \displaystyle\sum_{j=1}^{i-1}{\vert(p_i - p_j)\vert} $

$ A = \displaystyle\prod_{i=2}^n{c_i} $

이제 약간의 수식 변형을 시키자.

$ c_i
= \displaystyle\sum_{j=1}^{i-1}{|(p_i - p_j)|} $

$ = \displaystyle\sum_{j: p_j \le p_i, \ 1 \le j \le i-1}{(p_i - p_j)} +
\displaystyle\sum_{j: p_j \gt p_i, \ 1 \le j \le i-1}{(p_j - p_i)} $

여기서 $ n_i := p_j < p_i $인 $j$의 개수라고 하자. 그러면,

$ c_i = ( n_i \cdot p_i - \displaystyle\sum_{j: p_j \le p_i, \ 1 \le j \le i-1}{p_j} ) + ( \displaystyle\sum_{j: p_j \gt p_i, \ 1 \le j \le i-1}{p_j} - (i-1-n_i) \cdot p_i )$

$ = (2n_i+1-i)\cdot p_i + \displaystyle\sum_{j: p_j \gt p_i, \ 1 \le j \le i-1}{p_j} - \displaystyle\sum_{j: p_j \le p_i, \ 1 \le j \le i-1}{p_j} $

그러면 이제 문제는

  1. $i$번째 나무보다 왼쪽에 심어져 있던 나무의 수와
  2. $i$번째 나무보다 왼쪽에 심어져 있던 나무들의 좌표(위치)의 합

을 알아야 하는 문제로 바뀐다($p_i$와 같은 나무는 어느 쪽에 넣어도 상관없다).

  • $i$번째 나무와 위치가 같은 경우는 어차피 0이 되니 처리를 해주든 말든 상관이 없다.
  • 그리고 오른쪽에 있는 나무들은 전체 나무에서 왼쪽 부분을 빼면 얻을 수 있다(사실 그냥 오른쪽을 구해버려도 된다).

이제 펜윅 트리를 쓸 차례다. 펜윅 트리를 두 개 만든다. 하나는 위치에 따른 나무 수의 합을 세는 것이고, 하나는 위치에 따른 나무 좌표의 합을 세는 것이다. 맨 아래의 구현에서 각각 count[]와 summ[]으로 구현되어 있다.

그리고 $i$번째 나무의 위치로 $p_i$가 들어오면, 왼쪽에 있는 나무의 수는 sum($p_i$, count=true)으로, 왼쪽에 있는 나무의 좌표의 합은 sum($p_i$, count=false)로 바로 구할 수 있다.

  • 구현한 코드를 보면 이해할 수 있다. update의 코드 중복을 방지하기 위해 bool 형인 count 파라미터를 받는다.
  • 구간 합(개수 혹은 좌표의 합)을 구하는 연산은 일반 펜윅 트리와 똑같다.

그리고 업데이트를 할 때는 위치는 $p_i$로 하고 count[]는 +1, summ[]에는 $p_i$만큼 더해 준다(두 배열의 정의에 의해).

오른쪽 나무에 대해 구할 때는 전체에서 왼쪽 나무들의 값을 빼면 어렵지 않게 구할 수 있다.

구현

이번에는 펜윅 트리의 형태가 조금 다르기 때문에 따로 필자의 라이브러리를 사용하지 않았다.

주의 사항이 조금 있다.

  • 좌표가 0부터 시작하는데, 펜윅 트리는 인덱스 0을 쓰지 않는다. 따라서 $p_i$를 1씩 증가시켜서 구현해야 한다. MAX_X가 200000 + 1인 이유가 이것이다.
  • 펜윅 트리의 크기는 원소의 수가 아닌 좌표의 범위이다.
  • MOD 연산은 그때그때 해주어야 한다. 그렇다고 남용해서 마이너스를 할 때 음수가 되어버리면 연산이 제대로 된다는 보장이 없다.
  • count[]는 int[]로 선언해도 되지만, int와 long long 사이에서 실수가 많다면 그냥 편하게 모든 것을 long long으로 해도 된다. 메모리가 아주 타이트한 것이 아니라면.
#include <iostream>
#include <vector>

using namespace std;

#define ll long long
#define MOD 1000000007
#define MAX_X 200001

class FenwickTree {
public:
    vector<ll> count, summ;

    FenwickTree() {
        count.resize(MAX_X + 1);
        summ.resize(MAX_X + 1);
    }

    void update(int x, int val) {
        while (x <= MAX_X) {
            ++count[x];
            summ[x] += val;
            x += (x&-x);
        }
    }

    ll sum(int x, bool cnt) {
        ll ret = 0;
        while (x) {
            ret += cnt? count[x] : summ[x];
            x &= x-1;
        }
        return ret;
    }
};

FenwickTree BIT;
int N, p_i;

int main_01280() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);    cin.tie(NULL);
    cin >> N >> p_i;    ++p_i;

    BIT.update(p_i, p_i);

    ll ans = 1;
    ll p_i_sum = p_i;

    for(int i=2;i<=N;i++){
        cin >> p_i; ++p_i;

        ll n_i = BIT.sum(p_i, true);
        ll smaller = BIT.sum(p_i, false);

        ll cost = (2 * n_i + 1 - i) * p_i;
        cost -= smaller;
        cost += p_i_sum - smaller;
        cost %= MOD;

        p_i_sum += p_i;
        ans = (ans*cost) % MOD;

        BIT.update(p_i, p_i);
    }

    cout << ans;

    return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 당연히 틀린다. 저런 헤더 파일이 채점 사이트에 있던가?

Comment  Read more

TensorFlow 사용법 - 01. 소개 및 설치

|

텐서플로(TensorFlow)란?

텐서플로(TensorFlow)는 원애 머신러닝(ML)과 심층 신경망(Deep Neural Network) 연구를 수행하는 구글 브레인 팀에서 개발되었다.
텐서플로는 Tensor(텐서, 텐서플로의 기본 자료구조. 우선 다차원 배열이라고 생각하면 편하다)를 Data Flow Graph에 따라 수치 연산을 하는 라이브러리이기 때문에 그런 이름이 붙었다.

연동 라이브러리

텐서보드

모델(알고리즘)이 어떻게 돌아가고 있는이 모니터링/디스플레이해주는 모듈이다.
알고리즘이 잘 돌아가는지 아닌지를 볼 수 있기에 중요한 모듈이다.

실행하는 것은 명령창에서 tensorboard --logdir=<추적 파일 directory>를 입력하면 된다.
그리고 크롬 브라우저에서 http://localhost:6006으로 접속하면 로그를 확인할 수 있다.

텐서플로 서빙

텐서플로의 머신러닝 모델을 운영환경으로 배포하는 것을 도와준다.

일반적으로 작업 파이프라인은 다음과 같다.

  1. 데이터를 입수한다.
  2. 1의 데이터를 바탕으로 학습을 시킨다. 이 결과 모델이 생성된다.
  3. (텐서플로 서빙 등을 통해) 모델을 운영환경으로 배포한다.
  4. 배포된 모델을 gRPC(구글이 공개한 RPC 프레임워크)를 통해 클라이언트가 무언가 정보를 얻는다.
  5. 클라이언트의 피드백 등으로 데이터가 더 쌓이면, 1~2를 무한 반복한다.
  6. 모델의 성능이 향상되면 재배포한다.

설치

파이썬(3.6 또는 2.7)과 pip은 설치되어 있다고 가정한다. conda를 쓰고 싶다면 써도 된다.
본인이 프로젝트를 여러 개 할 것이라면 가상환경을 만드는 것을 추천한다(virtualenv 또는 conda)

CPU 버전 설치

우선 본인이 gpu가 없거나 사용할 계획이 없다면, cpu 버전 설치는 매우 간단하다.

윈도우라면 명령창(cmd)를 관리자 권한으로 실행한다. Mac/Linux라면 (sudo권한으로) 터미널을 실행한다.
다음 명령들을 차례대로 실행한다. ::뒤의 문구는 주석이므로 입력할 필요 없다.

virtualenv tensorflow_cpu :: tensorflow_cpu란 이름의 가상환경을 만든다. cd tensorflow_cpu/Scripts activate (tensorflow_cpu) pip install tensorflow :: 가상환경 (tensorflow_cpu) 안에서 tensorflow를 설치

가상환경에서 나오고 싶다면 deactivate를 입력하면 된다.

별다른 문제가 없다면 설치가 완료된다. 만약 에러 메시지가 보인다면 구글링을 하면 웬만해선 해결이 된다.

GPU 버전 설치

우선 본인의 GPU(그래픽카드)가 텐서플로 사양을 맞추는지 확인해 보자.
일반적으로 Compute Compatability가 3.0 혹은 3.5 이상이면 다 돌아간다고 보면 된다.

https://developer.nvidia.com/cuda-gpus

그리고 그래픽 드라이버가 일정 버전 이상인지 확인하도록 한다. 390 이상이면 문제 없을 것이다.

http://www.nvidia.co.kr/Download/index.aspx?lang=kr

첫 예제 코드

본인이 원하는 곳에 test.py 파일을 하나 만든다. 그리고 그 안에 다음과 같이 입력해 본다.

import tensorflow as tf

a = tf.placeholder('float')
b = tf.placeholder('float')

y = tf.multiply(a, b)

sess = tf.Session()

print(sess.run(y, feed_dict={a:3, b:3}))

그리고 실행해 본다. 명령창이라면 python test.py를 입력하면 된다.

C:\tensorflow_cpu\Scripts\python.exe C:/tensorflow_cpu/test.py 2018-07-10 18:05:50.108245: IT:\src\github\tensorflow\tensorflow\core\platform\cpu_feature_guard.cc:140] Your CPU supports instructions that this TensorFlow binary was not compiled to use: AVX2 9.0

Process finished with exit code 0

위와 같이 나오면 정상이다.
CPU 버전을 설치했다면 중간에 Your CPU ... AVX2 라는 문구가 경고처럼 뜨는데, CPU 버전이라면 뜨는 문제이므로 별 신경쓰지 않아도 된다.
저 메시지를 끌 수는 있지만, 다른 경고 메시지까지 없어져 버리므로 추천하지 않는다.

이제 위 코드의 의미를 살펴보면,

  1. import는 무엇인지 알 것이다.
  2. a와 b를 float형 placeholder로 정의했다. 이것은 a와 b가 각각 float타입의 데이터를 담을 그릇이라는 뜻이다. 하지만 아직 어떤 값이 담길지는 정해지지 않은 상태이다.
  3. y는 짐작하다시피 a와 b의 값을 곱한 값으로 정의된다. 하지만 마찬가지로 무슨 값이 곱해져서 들어갈지 정해지지 않았다. 단지 곱셈을 수행할 것이란 사실만을 정의했다.
  4. 텐서플로는 코드를 실행할 때 세션(Session)이라는 곳에서 수행해야 한다. 세션의 종류는 여러 개가 있지만, 나중에 설명하도록 하겠다. 지금은 텐서플로의 ‘실행 코드’는 무조건 세션 안에서 해야 한다는 사실만 기억하자.
  5. 이제 세션 안에서 ‘y’를 실행을 시킨다(sess.run). 그리고 feed_dict라는 옵션이 있다.
    1. sess라는 세션 안에서 y를 실행한다는 의미이다. 조금 전 y는 a와 b의 곱셈으로 정의된다고 하였다.
    2. 그런데 y를 계산하려면 a와 b를 알아야 한다고 했는데, 조금 전 a, b를 선언할 때 무슨 값이 들어갈지 정하지 않았다.
    3. 이것 때문에 feed_dict가 있는 것이다. feed_dict는 파이썬의 딕셔너리 형식인데, 잘 보면 a와 b에 각각 특정 값을 집어넣고 있음을 알 수 있다.
    4. 즉 a와 b에는 선언 시점(placeholder로 쓴 부분)이 아닌 실행 시점(sess.run)에 값이 들어가는 것이다.
    5. 그리고 feed_dict로 전달받는 a와 b의 값을 이용하여, 곱셈으로 정의된 y를 계산한다.
      1. 물론 이 때 y의 계산에 필요한 a, b가 모두 feed_dict 옵션에 들어가 있어야 한다. 넣지 않으면 에러를 뱉을 것이다.
    6. 계산된 y값을 print()로 출력한다. 9.0이 출력되었다.

세션을 만들고 실행하는 것이 좀 비직관적이지만, 이것이 텐서플로의 구조이다. 이는 나름대로의 장점이 있다.

  1. 우선 계산 그래프를 만든다(전체 알고리즘을 기술한다).
  2. 그 다음 세션을 생성하고 연산을 실행하는 형태이다.

즉 텐서플로는 ‘선언(definition)’과 ‘실행(run)’이 따로 이루어진다. 사실 대부분의 다른 머신러닝 라이브러리는 선언과 대입, 실행이 동시에 이루어지긴 한다.

위의 코드에서는 곱셈만 썼지만, 기본 연산으로 다음과 같은 것들이 있다.

print('add:', sess.run(tf.add(a,b), feed_dict={a:3, b:4}))
print('subtract:', sess.run(tf.subtract(a,b), feed_dict={a:3, b:4}))
print('multiply:', sess.run(tf.multiply(a,b), feed_dict={a:3, b:4}))
print('divide:', sess.run(tf.divide(a,b), feed_dict={a:3, b:4}))
print('mod:', sess.run(tf.mod(a,b), feed_dict={a:3, b:4}))
print('abs:', sess.run(tf.abs(a), feed_dict={a:3}))
print('negative:', sess.run(tf.negative(a), feed_dict={a:3}))
print('sign:', sess.run(tf.sign(a), feed_dict={a:3}))
print('square:', sess.run(tf.square(a), feed_dict={a:3}))
print('round:', sess.run(tf.round(a), feed_dict={a:3.5}))
print('sqrt:', sess.run(tf.sqrt(a), feed_dict={a:3}))
print('pow:', sess.run(tf.pow(a,b), feed_dict={a:3, b:4}))
print('exp:', sess.run(tf.exp(a), feed_dict={a:3}))
print('log:', sess.run(tf.log(a), feed_dict={a:3}))
print('log1p:', sess.run(tf.log1p(a), feed_dict={a:3}))
print('maximum:', sess.run(tf.maximum(a,b), feed_dict={a:3, b:4}))
print('minimum:', sess.run(tf.minimum(a,b), feed_dict={a:3, b:4}))
print('cos:', sess.run(tf.cos(a), feed_dict={a:3}))
print('sinh:', sess.run(tf.sinh(a), feed_dict={a:3})) # hyperbolic 함수

이외에도 함수는 많지만 간단한 함수들 위주로 적어 보았다.

IPython 같은 대화형 환경을 사용하는 경우 코드의 일부분만 수행하면서 그래프 구조를 만들고 싶을 때가 있다. 이때는 tf.interactiveSession() 세션을 사용하지만, 이것도 나중에 설명하도록 하겠다.

알아두어야 할 점은, 연산과 데이터에 대한 모든 정보는 그래프 구조(수학 계산을 표현함) 안에 저장된다는 것이다.
그래프의 노드는 수학 연산(앞에서 설명한 multiply 등)을, 엣지는 노드 사이의 관계를 표현하며 동시에 텐서플로의 기본 자료구조인 텐서를 전달한다.

텐서플로는 그래프 구조로 표현된 정보를 이용해서 트랜잭션 간 의존성을 인식하고 노드에 입력 데이터로 들어올 텐서가 준비되면 cpu/gpu에 비동기적/병렬적으로 연산을 할당한다.

01_new_repository

Comment  Read more