텐서플로(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에 비동기적/병렬적으로 연산을 할당한다.

참조

개요

시간복잡도: $ O(N + (k+m)log N) $

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

• N, m, k는 문제에서 주어진 그대로이다. N은 원소의 수이다.

문제 풀이

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

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

본인이 인덱스 트리를 좋아한다면 그것으로 풀어도 상관없지만, 코딩하기 조오금 더 귀찮지 않은가?

별다른 풀이는 없다. 그냥 펜윅 트리를 쓴다. 그게 끝이다.

구현

• 참고로 m과 k의 구분은 전혀 필요가 없다. 그냥 합쳐서 생각하면 된다.
• 펜윅 트리 클래스의 구현을 보면 data[]에는 long long을 쓴다. 합이 int의 범위를 넘어가기 때문이다. 제출했는데 초반은 맞다가 갑자기 틀린다면, 오버플로우를 한번쯤 의심해 봐야 한다.

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

int N, m, k;

int main_02042() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);    cin.tie(NULL);

    cin >> N >> m >> k;
    m += k;

    FenwickTree<int> BIT(N);

    int a, b, c;

    for (int i = 1; i <= N; i++) {
        cin >> c;
        BIT.update(i, c);
    }

    while (m--) {
        cin >> a >> b >> c;
        if (a == 1)
            BIT.update(b, c);
        else
            cout << BIT.sum(b, c) << '\n';
    }
    return 0;
}

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

참조

개요

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

구간 합 구하기: $ O(log N) $

값 업데이트하기: $ O(log N) $

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

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

이 글에서는 펜윅 트리(Fenwick Tree) 라고 하는 자료구조와, 이를 활용한 문제들을 살펴볼 것이다.

펜윅 트리라니? 라고 생각할지도 모르겠지만, 이는 여러분이 아마 들어본 적이 있을 Binary Indexed Tree(BIT)와 같은 것이다.

참고로 펜윅 트리로 풀리는 문제는 전부 인덱스 트리로도 풀린다.

펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)

흔히 BIT라고 불리는 펜윅 트리(Fenwick Tree)는 ‘수시로 바뀌는 수열의 구간 합’을 빠르게 구할 수 있도록 고안된 자료 구조이다.

다음 상황을 살펴보자.

• 길이 10만짜리 수열이 있다.
• 12345~77777번 수들의 합을 구하라는 요청이 들어왔다. 65433개를 일일이 세어 합을 구해준다.
• 똑같은 요청이 여러 번 들어오자. 여러분은 부분 합이라는 스킬을 써서 꼬박꼬박 답을 해 주었다.
• 이번엔 20000번째 수와 55555번째 수를 업데이트하라고 했다.
• 부분 합을 8만 개를 업데이트해야 하는 여러분은 화가 나기 시작했다.

…물론 이런 상황이 실제로 일어나지는 않겠지만, PS의 세계에서는 자주 있는 일이다. 누군가 무슨 숫자를 구해야 하고 그걸 여러분에게 자주 시키지 않는가?

이런 상황에서 펜윅 트리를 쓸 수 있다. 즉 수시로 바뀌는 수열의 구간 합을 $O(log N)$만에 구할 수 있다.

펜윅 트리는 다음과 같은 장점을 갖고 있다.

1. 방금 말했듯이 업데이트가 하나씩 되는 수열의 구간 합을 $O(log N)$만에 구할 수 있다.
2. 비트 연산을 이해하고 있다면 구현이 굉장히 쉬운 편이다.
3. 속도도 빠르다(Big-O 표기법에서 생략된 상수가 작음).

그럼 펜윅 트리의 구조를 살펴보자.

펜윅 트리(BIT)의 구조

앞의 예를 조금 축소시켜서, 길이 10짜리 수열을 하나 생각하자. arr[]이라고 부르도록 하겠다.

펜윅 트리는 개념상 트리이지만, 구현할 때는 길이 N짜리 배열로 구현한다.
정확히는 앞에 하나를 비워 두기 때문에 배열 자체의 크기는 $N+1$이고, 사용하는 인덱스는 1이상 N 이하이다.

그림에는 N=16일 때의 펜윅 트리가 그려져 있다. 배열의 경계 정하는 것이 헷갈리는 사람이라면 그림처럼 마음 편히 $2^n$ 꼴로 잡으면 된다.
하지만 펜윅 트리는 굳이 $2^n$ 꼴이 아니더라도 잘 작동한다. 이유는 이 글을 다 읽고 손으로 써 보면 알 수 있을 것이다.

앞으로 이 배열을 data[]라고 부르도록 하겠다. 필자의 코드에서 FenwickTree 클래스의 vector<int> data로 구현되어 있다.

이제 배열로 구현된 펜윅 트리의, data의 각 원소가 갖는 값을 살펴보자.

위 그림에 모든 것이 설명되어 있긴 하지만, 자세히 살펴보자. i는 0 이상인 정수이다.

1. 인덱스가 홀수인 원소는 수열의 해당 인덱스의 값을 그대로 가진다.
   1. $data[2i+1] = arr[2i+1]$
   2. data[1] = arr[1], data[3] = arr[3], …
2. 인덱스가 2의 배수이면서 4의 배수가 아닌 원소(2, 6, 10, 14, …)는 직전 두 arr 원소의 합을 보존한다.
   1. $data[4i+2] = arr[4i+1] + arr[4i+2]$
   2. data[2] = arr[1] + arr[2], data[6] = arr[5] + arr[6], …
3. 인덱스가 $2^k$의 배수이면서 $2^{k+1}$의 배수가 아닌 원소는 직전 arr의 $2^k$개의 값의 합을 보존한다.
   1. $data[2^{k+1} \cdot i + 2^k] = \Sigma_{j=1}^{2^k}{arr[2^{k+1} \cdot i + j]}$
   2. data[12] = arr[9] + arr[10] + arr[11] + arr[12], …

수식이 조금 복잡할 수는 있지만 그림을 보면 바로 이해될 것이다.

구간 합($O(log N)$)

이제 이 data[]로 구간 합을 어떻게 빠르게 구하는지 알아보자. 예를 들어서 arr[1…7]의 합을 구한다고 하자.

[\Sigma_{j=1}^7{arr[j]} = \Sigma_{j=1}^4{arr[j]} + \Sigma_{j=5}^6{arr[j]} + \Sigma_{j=7}^7{arr[j]}]

여기서 $\Sigma_{j=1}^4{arr[j]} = data[4]$, $\Sigma_{j=5}^6{arr[j]} = data[6]$, $\Sigma_{j=7}^7{arr[j]} = data[7]$ 임을 알았으면 여러분은 구간 합을 구하는 방법을 이해한 것이다.

N=10이라서 감이 잘 안 올 수는 있지만, 이렇게 구하는 방법이 $O(log N)$ 시간에 완료된다는 것도 알 수 있을 것이다.

아직 의문점이 좀 있을 것이다.

1. 그럼 arr[4…12]의 합은 어떻게 구하는가?
   1. arr[1…12] - arr[1…3]을 구하면 된다. 즉, sum 연산을 두 번 실행하고, 작은 쪽을 빼 주면 끝.
2. 눈으로 보면 arr[1…7] = data[4] + data[6] + data[7]인 것을 알 수 있지만, 구현은 어떻게 쉽게 하는가?
   1. 비트 연산을 이해한다면 구현도 굉장히 쉽다. 구체적인 예(arr[1…43])를 보자.
      1. arr[1…43] = data[32] + data[40] + data[42] + data[43]이다.
      2. 43을 이진법으로 나타내면 $101011_2$이다.
      3. 43의 LSB(1인 비트 중 끝자리)를 하나 뗀다. $101010_2 = 42$이다.
      4. 하나 더 떼 본다. $101000_2 = 40$이다.
      5. 하나 더 떼 본다. $100000_2 = 32$이다.
   2. 그럼 LSB를 어떻게 쉽게 구하는가?
      1. idx = 43으로 두고, idx &= idx – 1 연산을 idx가 0이 될 때까지 수행한다.
      2. 이게 왜 되는지 이해가 안 된다면 idx와 idx - 1을 이진법으로 나타내고, and 연산을 수행해보면 이해가 될 것이라 장담한다.
      3. 사실 LSB 자체를 구하는 것은 업데이트 연산에서 볼 수 있듯이 (idx & -idx)로 구할 수 있다. 하지만 LSB를 빼는 것은 idx &= idx - 1로도 가능하다.
3. 위와 같이 이진법으로 접근해보면, 시간복잡도가 $O(log N)$인 것을 알 수 있다.

값 업데이트($O(log N)$)

arr[7]을 업데이트했다고 가정해보자. 좀 전에 봤던 그림을 다시 가져왔다.

arr[7]을 업데이트했다면, data[i]는 arr[j]들의 합으로 이루어져 있고, 그 값을 프로그램이 끝날 때까지 유지해야 한다. 그러면 arr[7]이 계산식에 포함되어 있는 모든 data[i]들을 업데이트해야 한다.

그럼 문제는 다음으로 연결된다.

arr[7]을 계산식에 포함하는 data[i]들은 어떤 것이 있는가?

일단 답을 보자. data[7], data[8], data[16]이 있다. (N=16) 이는 위 그림에서 7 위쪽으로 화살표를 쭉 그려보면 알 수 있다. data[7]은 당연히 업데이트해야 하고, 화살표와 만나는 data[8]과 data[16]을 업데이트해야 한다.

각 숫자들을 이진법으로 나타내보자. $00111_2, 01000_2, 10000_2$이다. 규칙성이 보이는가? 조금은 어려울 것이다. 답은, LSB를 더하면 다음 수가 된다는 것이다.

다른 예를 들어보겠다. arr[3]을 업데이트하면, data[3], data[4], data[8], data[16]을 업데이트한다.

1. $3 = 00011_2$
2. $4 = 00011_2 + 00001_2 = 00100_2$
3. $8 = 00100_2 + 00100_2 = 01000_2$
4. $16 = 01000_2 + 01000_2 = 10000_2$

조금 전에 구간 합을 구할 때는 LSB를 빼 주었다. 업데이트를 할 때는 LSB를 더해 준다. 이것이 가능한 이유는 역시 손으로 몇 개 정도 그려 보면 이해할 수 있다.

구현

코드의 가독성을 위해 그리고 N이 작을 때 메모리를 아끼기 위해 동적으로 data를 vector<int>로 선언하여 FenwickTree class 안에 넣었다.

• 하지만, 실제 PS 문제를 풀 때는 그냥 $2^n + 1$ 크기만큼 배열을 전역 변수로 설정해버리는 것이 실행 시간이 더 빠르다.
• arr[i] = sum[i] - sum[i-1]임을 이용하면 arr배열을 유지할 필요가 없다.
• 사실 이 클래스의 경우 long long을 많이 사용하기 때문에 template을 사용하는 이유가 별로 없긴 하다.

#include "sharifa_header.h"

template <typename T>
class FenwickTree {
public:
    int size;
    vector<T> arr;
    vector<ll> data;

    FenwickTree<T>(int _N) {
        size = _N;
        arr.resize(size + 1);
        data.resize(size + 1);
    }

    void update(int x, T val) {
        T delta_val = val - arr[x];
        arr[x] = val;

        while (x <= size) {
            data[x] += delta_val;
            x += (x&-x);
        }
    }
    ll sum(int x) {
        ll ret = 0;
        while (x) {
            ret += data[x];
            x &= x - 1;
        }
        return ret;
    }
    ll sum(int x, int y) {
        return sum(y) - sum(x - 1);
    }
};

2차원 펜윅 트리 구현

이는 별다른 처리 해 줄 필요 없이 단순히 차원 확장을 한 것에 불과하다. 배열이 2차원이 되고, while문이 두 개가 되었을 뿐이다.

#include "sharifa_header.h"

class FenwickTree2D {
public:
    int size;
    vector<vector<long long> > data;

    FenwickTree2D(int _N) {
        size = _N;
        data = vector<vector<long long> >(size + 1, vector<long long>(size + 1));
    }

    void update(int x, int y, int val) {
        ll dval = val - sum(x, y, x, y);
        int yy;
        while (x <= size) {
            yy = y;
            while (yy <= size) {
                data[x][yy] += dval;
                yy += yy & -yy;
            }
            x += x & -x;
        }
    }
    ll sum(int x, int y) {
        ll ret = 0;
        int yy;
        while (x) {
            yy = y;
            while (yy) {
                ret += data[x][yy];
                yy -= yy & -yy;
            }
            x -= (x&-x);
        }
        return ret;
    }
    inline ll sum(int x1, int y1, int x2, int y2) {
        return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);
    }
};

문제 풀이

BOJ 02042(구간 합 구하기)

문제: 구간 합 구하기

풀이: BOJ 02042(구간 합 구하기) 문제 풀이

BOJ 11658(구간 합 구하기 3)

문제: 구간 합 구하기 3

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

BOJ 01280(나무 심기)

문제: 나무 심기

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

주의: 이 글을 읽는 여러분이, 만약 git을 많이 써 봐서 익숙한 것이 아니라면, 반드시 손으로 직접 따라 칠 것을 권한다. 눈으로만 보면 100% 잊어버린다.

저번 글에서 작업하던 것을 이어서 한다. 저번 글에서는 git_tutorial 디렉토리를 생성하는 것까지 했었다.

Local Directory 생성

이제 git_tutorial 옆에 새로운 디렉토리를 생성한다. 이름은 자유지만 필자는 git_tutorial_clone으로 정했다.

이 상황은, git으로 협력할 때 다른 사람이 프로젝트 repo를 clone하거나, 여러분이 다른 컴퓨터로 이동하여 작업을 하고 싶을 때를 가정한 것이다.
그러나 다른 사람을 데려오거나 컴퓨터를 하나 더 사는 것은 부담이 될 테니, 다른 디렉토리에 새로 repo를 만든다.
한 가지 주의사항으로, 같은 디렉토리 내에서는 할 수 없다. 그래서 새 디렉토리를 만드는 것이다.

git clone 하기

이제 명령창을 켜서, 방금 생성한 디렉토리로 이동한다. 명령어를 잊어버렸을까봐 해서 다시 적어 둔다. 물론 이것은 예시일 뿐이다.

cd C:\Users\Sharifa-D\WebstormProjects\git_tutorial_clone

그리고 이제 clone을 할 것이다. clone 명령은 간단하다. git clone \<remote repo 주소\> 형식이다.
저번에 생성했던 git_tutorial git 주소를 사용하면 된다.

git clone https://github.com/greeksharifa/git_tutorial.git

클론은 이게 끝이다. 위 명령을 실행하면 git_tutorial 폴더가 또 만들어질 것이다.

이제 여러분의 디렉토리 구조는 다음과 같을 것이다.

• git_tutorial/
  • .git/
  • first.py
  • second.py
• git_tutorial_clone/
  • git_tutorial/
    • .git/
    • first.py
    • second.py

왜 .git/이 있지? 라고 생각할 수 있다.
.git/ 디렉토리는 윈도우라면 숨김 처리되어 있는 폴더인데, 이 .git/ 디렉토리가 있는 디렉토리만이 local repo로 인정받는다.
즉, 이 .git/이 있어야만 git repo로서의 역할을 할 수 있는 것이다.
그리고 git init으로 생성하거나 git clone으로 remote repo를 local repo로 가져온 경우에도 자동으로 .git/ 디렉토리가 존재하게 된다.

그리고 위의 두 개의 first.py와 second.py 각각은 완전히 동일한 파일일 것이다.

이제 두 개의 local repo와 remote repo 사이에 상호작용을 좀 시켜보자.
저번 글에서 했던 git status, git add, git commit, git push, git pull 등을 사용해 볼 것이다.

프로젝트 파일 수정하고 3종 세트 입력하기

아무거나 수정해보자. git_tutorial_clone/git_tutorial/first.py를 수정한다. 다음과 같은 내용으로 하자.

print(“Hello, git!”) # instead of “Hello, World!”
print(“Hi, git!!”)

그리고 명령창에서 git status를 실행한다. 무슨 일을 하는지 잊어버리지는 않았을 것이다.

이제 git add .와 git commit -m "Edit first.py"와 git push origin master 3종 세트를 입력하자.

옵션: 3종 세트 간편 입력(윈도우 기준)

우선 수정사항을 만들기 위해 git_tutorial_clone/git_tutorial/first.py 끝에 빈 줄을 하나 추가하자.

3종 세트를 한 번에 입력하는 것은 배치 파일을 만들면 쉽게 할 수 있다. 여러분의 git local repo 안에 push.bat이란 이름의 파일을 하나 만들자.
명령창에서 copy con push.bat이라 입력한 후 입력을 시작해도 된다.
파일 내용은 다음과 같이 한다.

git add .
git status

set str=
set /p str=enter commit message :

git commit -m "%str%"
git push

그리고 명령창에서 push.bat이라고 입력하여 방금 만든 배치 파일을 실행시켜보자.
그러면 enter commit message: 앞에서 멈춰 있을 것이다. 원하는 커밋 메시지를(enter를 입력하지 않고) 짧게 입력해보자.
그러면 3종 세트가 하는 모든 것이 완료된다.

local repo 상태 확인하고 git pull로 local repo 업데이트하기

이제 명령창에서 다음 명령을 입력한다. git_tutorial 디렉토리로 이동하기 위함이다(git_tutorial_clone 내부의 것이 아니다).

cd ../../git_tutorial/

여기서 first.py를 확인해 보면, print("Hi, git!!") 문장이 없는 것을 확인할 수 있다.
즉, local repo는 자동으로 업데이트되지 않는다.

이제 새로운 명령어를 몇 개 배워 볼 것이다. 명령창에 다음을 입력한다.

git log

이 명령은 현재 local repo의 commit history를 보여준다. 아마 다음과 같을 것이다.

이제 local 말고 remote repo가 궁금할 것이다(git_tutorial_clone에서 커밋을 한두 개 날렸으니까).
그럴 때는 다음 명령을 사용한다.

git log HEAD..origin/master

• 우선 git log 명령은 commit log를 보여준다.
• ..은 Double Dot으로, 한쪽에는 있고 다른 쪽에는 없는 커밋이 무엇인지 Git에게 물어보는 것이다.
• 한쪽은 HEAD이다. 다른 한쪽은 origin/master이다.
• HEAD는, 현 local repo의 현재 상태를 의미한다. HEAD에 대한 자세한 설명은 나중에 다룰 것이다.
• 이 명령은 HEAD에는 없고 origin/master에는 있는 커밋이 무엇인지 보여준다.
  • 즉 local repo에는 없고 remote repo에는 있는 커밋을 볼 수 있다.
• HEAD는 생략할 수 있다. 즉, git log ..origin/master로도 같은 효과를 얻는다.
• 순서를 바꾸면 remote repo에는 없고 HEAD에는 있는 커밋을 보여주게 된다. 현 시점에서는 아무것도 표시되지 않을 것이다.
• git log 명령을 쓸 때 간략하게 보고 싶으면 --oneline 옵션을 추가한다.

git log ..origin/master –oneline

이렇게 확인하고 나면 local repo와 remote repo가 어떤 status를 갖고 있는지 확인할 수 있다. 즉,

• local repo status
  • 97f92d3 (HEAD -> master) Initial commit for git_tutorial
• remote repo status
  • 9401817 (origin/master) 3set simple commit
  • f569352 Edit first.py
  • Initial commit for git_tutorial

이 부분까지 자세히 알 필요는 없지만, 그래도 있으니 간략한 설명을 적어둔다.

• 앞의 16진수 숫자는 커밋의 고유 번호이다(해시값). 유일한 값이므로, 혹시 커밋 메시지를 너무 간결히 작성해서 커밋이 비슷해 경우 이 해시값으로 구분할 수 있다.
• (HEAD -> master)은 HEAD(현재 local repo 상태)에서 master(remote repo의 master 브랜치)로 push했다는 것을 의미한다.
• (origin/master)는 remote repo의 현재 상태를 의미한다.

그러고 git status로 상태를 한번 확인해 본다. 깨끗하다는 메시지를 볼 수 있을 것이다.

이제 git pull origin master(혹은 git pull)을 입력할 차례다.

이제 local repo가 최신으로 업데이트되었다.

.gitignore 추가

이제 .gitignore 파일을 추가해 보자.
.gitignore 파일은 remote repo에 올리지 않을 파일이나 디렉토리를 지정하는 파일이다.
즉, 여러분이 git add *를 아무리 시도해도, .gitignore파일에 명시된 파일 혹은 디렉토리는 절대 staging area에 올라가지 않는다.

올라가지 않겠지만 파일을 하나 추가하자. third.py로 하면 좋을 것 같다.

# third.py
print('This file is useless!')

다음으로는 .gitignore 파일은 만들 차례다.
윈도우에선 .으로 시작하는 파일을 그냥은 만들어 주지 않기 때문에, 명령창에서 조금 전처럼 copy con .gitignore이라고 입력한다.
그러면 빈 줄에서 커서가 깜빡거리는데, 이때 다음을 입력한다.

third.py

엔터 한번 쳐 준 다음에, Ctrl + C를 누른다. 그럼 파일 입력을 종료하고 다시 터미널로 빠져나온다.

이제 git status를 입력해보자.

상태창에 third.py는 없고 .gitignore 파일만 있다.

• .gitignore 파일이야 방금 추가했으니 목록에 뜨는 것이 맞다.
• third.py는 .gitignore 파일에 지정되어 staging area에 올라갈 수 없다. 즉, git add 명령을 써도 staging area에 올라가지 않는다.

이제 3종 세트를 입력하거나, 옵션에서 했던 push.bat 파일을 실행시킨다. 여기서는 3종 세트를 입력하겠다.

이제 브라우저에서 remote repo의 상태를 확인해 보자.

third.py는 존재하지 않는다. .gitignore 파일이 third.py를 훌륭하게 무시해 주었다.

.gitignore파일은 이럴 때 많이 쓴다.

• (용량이 큰) 데이터 파일. git repo는 기본적으로는 아주 큰 파일은 repo에 올려주지 않는다. 총 git repo 용량 제한도 있다(기업의 경우는 잘 모르겠다). 따라서 데이터 파일은 제외하는 경우가 많다.
• 프로젝트 설정 파일. 열려 있는 파일이라 오류가 날 수도 있고, IDE가 수시로 바꾸는 경우가 많으므로 제외할 때가 많다.
• dependency 파일. 누구나 웹에서 다운받아 설치할 수 있는 용량 큰 파일을 굳이 git repo에 넣지 않는다.
  • 대신 따로 dependency 목록을 만들어 관리한다.

이제 git의 프로젝트에 대한 설명은 대략 다 끝났다. 다음 글에서는 branch에 대해서 알아본다.

Git 명령어

GitHub 사용법 - 00. Command List에서 원하는 명령어를 찾아 볼 수 있다.

참조

개요

시간복잡도: $ O(N) $

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

• N은 두 수의 길이 중 max값이다.

문제 풀이

풀이 자체는 어렵지 않다. 빠른 곱셈을 위해, FFT 를 쓰면 된다. 그게 이 문제의 풀이의 전부이다.

문제 자체가 데이터에 대한 전처리는 다음과 같은 것을 해주면 된다.

1. reverse를 시켜준다. 큰 수 처리는 가장 낮은 자리수를 맨 앞에 두므로, reverse를 해야 한다.
2. 곱셈을 할 경우 자리수가 최대 두 배 정도까지 늘어나므로 자리수를 두 배만큼 늘려 준다.
3. 다시 reverse를 한다. 이 때 앞쪽의 0들은 출력하지 않도록 한다.
4. 곱셈 결과가 0인 경우 따로 0을 출력하도록 예외처리를 해 준다.

위의 사항만 주의하면, 입력받고, FFT를 적용하고, 출력하는 것이 끝이다.

구현

입출력이 조금 많으므로, string과 cin을 사용할 것이라면

ios::sync_with_stdio(false);
cin.tie(NULL);

를 해주자.

#include "../library/conversion_library.h"
#include "../library/fft.h"

int main_13277() {
    ios::sync_with_stdio(false);    cin.tie(NULL);
    string a, b;
    cin >> a >> b;
    vector<int> A = string_to_vi(a);
    vector<int> B = string_to_vi(b);
    reverse(A.begin(), A.end());	reverse(B.begin(), B.end());

    vector<int> ret = multiply(A, B);

    int i = 0;
    while (i < ret.size()) {
        if (ret[i] >= 10) {
            if (i == ret.size() - 1)
                ret.push_back(ret[i] / 10);
            else
                ret[i + 1] += ret[i] / 10;
            ret[i] %= 10;
        }
        ++i;
    }

    reverse(ret.begin(), ret.end());

    bool start = false;
    for (auto elem : ret) {
        if (elem)start = true;
        if (start)cout << elem;
    }
    if (!start)cout << '0';

    return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 당연히 틀린다. 못 믿겠다면, 저런 헤더 파일이 채점 사이트에 있을 것이라 생각하는가?