🙂 문제 분석 및 프로그램 설계

2xn 타일링과 비슷한 문제이다. 숫자가 주어지면 그 숫자를 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 구하는 방법이다. 이것도 dp문제이고 전 문제와 매우 유사하다.

💻 소스코드

#include <iostream>
#include <array>
using namespace std;

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

    array<int, 11> arr;

    arr[0] = 1;
    arr[1] = 2;
    arr[2] = 4;

    for (int n = 3; n < 11; n++) {
        int k = n-1;
        int l = k-1;
        int m = l-1;

        arr[n] = arr[k] + arr[l] + arr[m];
    }

    while (T--) {
        int N;
        cin >> N;
        N--;
        cout << arr[N] << endl;

    }
}

😊 문제를 풀기 위해 생각하고 해결했던 과정 및 느낀점

2xn 타일링 문제는 마지막 타일의 경우를 구하였다. 이것도 비슷하다. 마지막에 더할 수가 무엇인지 경우를 나누고 경우의 수를 계산하면 된다. 마지막에 1을 더하면 남은 수는 n-1을 1, 2, 3을 이용하여 나타낼 경우, 마지막에 2를 더하면 n-2를, 마지막에 3을 더하면 n-3을 나타낼 경우를 생각하면 된다. 즉 n을 나타낼 경우는 n-1, n-2, n-3을 나타낼 경우들의 합이다. N의 범위가 작으므로 배열을 만들어서 각각 경우의 수를 계산하여 대입하고 출력을 해줬다.

🙂 문제 분석 및 프로그램 설계

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하는 것이다. n의 크기를 입력받고 경우의 수를 구한후 10007으로 나눈 나머지를 출력하면 된다.

⭐ 문제를 해결하는데 필요한 개념

다이나믹 프로그래밍(dp)가 무엇인지 알 수 있는 문제이다. 마치 수열의 점화식을 구하듯 찾아서 간단화하고 그것을 코드로 풀어서 내면 된다.

🗒️ 소스코드

#include <iostream>
#include <array>

using namespace std;

int main() {
    array<long long, 1001>arr;
    arr[0] = 1;
    arr[1] = 2;

    for (int i = 2; i < 1001; i++) {
        arr[i] = (arr[i - 1] + arr[i - 2]) % 10007;
    }

    int N;
    cin >> N;
    N--;
    cout << arr[N];

    return 0;
} 

😊 문제를 풀기 위해 생각하고 해결했던 과정 및 느낀점

경우의 수를 생각해 보다가 마지막 제일 오른쪽에 놓을 수 있는 경우가 위 그림처럼 2가지라는 것을 알 수 있었다. 첫번째처럼 하면 남은 공간은 2 x (n-1) 공간을 채울 수 있는 경우의 수가 있을 것이고 두번째처럼 하면 남은 공간은 2 x (n-2) 공간을 채울 수 있는 경우의 수이다. 즉 점화식이 a_n = a_(n-1) + a_(n-2) 이렇게 나오고 그것을 코드로 풀어서 작성했다.

중간에 조건에 10007로 나눈 나머지 출력인데 이거 때문에 몇번 틀렸다.. 조건을 잘보자.. 코드에는 long long으로 하였는데 int로 해도 잘 돌아갈 것 같다. 나는 코드가 커도 딱히 문제는 없으니 맘편하게 long long으로 작성하긴 했다.

이번 포스팅은 짧을 것입니다. 1.6절에서 하지 못한 라그랑주 보간법과 1.7절의 일차독립인 극대 부분집합에 대해서 짧게 정리해보려 합니다.

🗒️1.6.라그랑주 보간법

이미 알고 있는 값을 바탕으로 그 사이의 값을 추정하는 방법을 보간법 또는 내삽법(imterpolation)이라 한다.

아래와 같은 다항식을 라그랑주 다항식(Lagrange polynomial)이라 합니다.

책에서는 $$x_i$$가 아닌 $$c_i$$로 표기되어 있긴 합니다. 즉, 위 식에서는 $$x_1, x_2,...,x_i$$로 책에서는 $$c_1,c_2,c_3,...,c_i$$로 표기했습니다. (밑첨자가 없는 $$x$$는 책에서도 $$x$$입니다. 즉, $$x$$에 대한 다항식인건 같습니다.)

$$x_1, x_2,...,x_i$$는 무한체 F에서 꺼낸 서로다른 스칼라입니다.

각 다항식 $$f_i(x)$$는 차수가 $$n$$인 다항식이고 $$P_n(F)$$의 원소입니다. 이 다항함수 $$f_i : F\to F$$에 대하여 다음과 같이 나타낼 수 있습니다.

$$f_i(x_j)=\begin{cases}0 (i\neq j) \ 1 (i=j)\end{cases}$$

라그랑주 다항식의 성질은 집합 $$\beta = {f_0, f_1, ..., f_n}$$이 $$P_n(F)$$의 일차독립인 부분집합임을 보이는데 사용됩니다.

아래함수가 영함수라 가정합시다.

• $$\displaystyle \sum_{k=1}^n a_if_i = 0$$ (단, $$a_0, a_1,...,a_n$$은 스칼라)

이 함수에 $$x_j$$를 입력하면 $$\displaystyle \sum_{k=1}^n a_if_i(x_j) = 0$$ ( $$j=0,1,...,n$$)입니다.

한편, $$f_i(x_j)=\begin{cases}0 (i\neq j) \ 1 (i=j)\end{cases}$$에 의해 $$\displaystyle \sum_{k=1}^n a_if_i(x_j) = a_j$$입니다. 따라서 모든 $$0\leq j\leq n$$에 대하여 $$a_j=0$$이고 $$\beta$$는 일차독립입니다.

또, $$P_n(F)$$의 차원이 n+1이므로 $$\beta$$는 $$P_n(F)$$의 기저입니다.

즉, $$P_n(F)$$에 속하는 모든 다항식 g는 $$\beta$$의 일차결합 $$\displaystyle \sum_{i=0}^n b_if_i$$로 표현할 수 있습니다. 식의 양변에 $$x=x_j$$를 입력하면 $$g(x_j)$$는 다음과 같습니다.

$$g(x_j)=\displaystyle \sum_{i=0}^n b_if_i(x_j) = b_j$$

따라서 $$\displaystyle \sum_{i=0}^n g(x_i)f_i$$ 는 $$\beta$$에 대한 유일한 일차결합 표현입니다. 이 식을 라그랑주 보간법(Lagrange interpolation formula)이라 합니다.

위 식에 따르면 입력값이 $$x_j(j = 0, 1,...,n)$$ 일 때, 출력 값이 $$b_j$$이며 차수가 $$n$$을 넘지 않는 유일한 다항식을 항상 찾을 수 있습니다.

라그랑주 보간법을 바탕으로 확인할 수 있는 중요한 사실은 다음과 같습니다.

다항식 $$f \in P_n(F)$$와 서로 다른 $$n+1$$개의 스칼라 $$x_1, x_2,...,x_i\in F$$에 대하여 $$f(c_i)=0$$이면 $$f$$는 영함수이다.

♦️ 1.7 일차독립인 극대 부분집합

이번 절에서는 1.6절의 결과를 무한차원 벡너공간에서 성립하는 형태로 일반화합니다. 가장 중요한 목표는 '모든 벡터공간은 기저가 존재함'을 증명하는 것입니다.

이것의 가장 큰 걸림돌은 수학적 귀납법을 더 이상 사용할 수 없다는 점입니다. 그래서 대신 하우스도르프 극대원리를 사용할 것이고 이 원리를 서술할 때 필요한 몇 가지 용어를 확인할것입니다.

정의 | $$\mathcal {F}$$를 집합족(family)이라 하자. 다음 조건을 만족하는 $$\mathcal {F}$$의 멤버(member) $$M$$은 (집합의 포함 관계에 대한) 극대(maximal)이다.

• $$M$$을 포함하는 $$\mathcal {F}$$의 멤버는 오직 $$M$$뿐이다.

정의 | 공집합이 아닌 집합 $$S$$의 모든 부분집합을 원소로 가지는 집합족(family) $$\mathcal {F}$$를 생각하자. 이 집합족은 $$S$$의 멱집합(power set)이라 한다. 집합 $$S$$는 당연히 $$\mathcal {F}$$의 극대원소(maximal element)이다.

정리 | 공집합이 아닌 두 집합 $$S,T$$가 서로소일 때, (두 집합의) 멱집합의 합집합으로 정의한 집합족 $$\mathcal {F}$$를 생각하자. 두 집합 $$S$$와 $$T$$는 모두 집합족 $$\mathcal {F}$$의 극대원소이다.

정리 | 무한집합 $$S$$의 모든 유한 부분집합을 원소로 가지는 집합족 $$\mathcal {F}$$를 생각하자. 집합족 $$\mathcal {F}$$는 극대원소를 가지지 않는다. 그 이유는 집합족 $$\mathcal {F}$$에 속한 어떤 집합 $$M$$을 가져오더라도 $$M$$에 속하지 않은 $$s\in S$$를 사용하여 ($$\mathcal {F}$$의 멤버인) $$S$$의 유한 부분집합 $$M \cup {s}$$를 만들 수 있다. 이 집합은 $$M$$을 포함하는 더 큰 집합이다.

정의 | 다음 조건을 만족하는 집합족(collection) $$\mathcal {C}$$는 사슬(chain)이라 한다.

• $$\mathcal {C}$$의 멤버 $$A, B$$를 임의로 선택할 때 $$A \sube B$$ 또는 $$B \sube A$$가 반드시 성립한다.

이제 하우스도르프 극대원리를 서술해 봅시다.

하우스도르프 극대원리(Hausdorff maximal principle) 집합족(family) $$\mathcal {F}$$에 포함되는 임의의 사슬 $$\mathcal {C}$$를 가져왔을 때, $$\mathcal {C}$$의 모든 멤버를 포함하는 $$\mathcal {F}$$의 멤버가 존재하면 $$\mathcal {F}$$에는 극대원소가 있다.

(참고) 하우스도르프 극대원리는 선택공리(axiom of choice)와 동치입니다. 선택공리는 공리(axiom)에 기반한 집합론을 구성하는 가장 중요한 주춧돌입니다.

하우스도르프 극대원리는 집합족(family)이 특정한 조건을 만족하면 극대원소가 반드시 존재함을 보장합니다. 이제 극대원리의 관점에서 기저의 정의를 다른 형태로 표현해 봅시다.

정의 | 벡터공간 V의 부분집합 S를 생각하자. S의 일차독립인 극대 부분집합(maximal linearly independent subset) B는 다음 두 가지 조건을 만족하는 S의 부분집합이다.

1. 집합 B는 일차독립이다.
2. 집합 B를 포함하고 일차독립인 (S의) 부분집합은 오직 B 뿐이다.

벡터공간 V의 기저 $$\beta$$는 일차독립인 극대 부분집합입니다. 그 이유는 아래와 같습니다.

1. 정의에 따르면 당연히 $$\beta$$는 일차독립이다.
2. $$v \in V , v \notin \beta$$이면 $$\beta \cup {v}$$는 일차종속이다. span($$\beta$$) = $$V$$이기 때문이다.

역이 성립함을 보입시다.

정리 | V는 벡터공간이고, 부분집합 S는 V를 생성한다. $$\beta$$가 S의 일차독립인 극대 부분집합이면 $$\beta$$는 V의 기저이다.

증명은 생략합니다.

기저와 '일차독립인 극대 부분집합'은 동치입니다. ** **즉, 모든 벡터공간마다 '일차독립인 극대 부분집합'이 존재함을 보이는 것과 모든 벡터공간이 기저를 가짐을 보이는 것은 같습니다. 이 결과로 다음 정리를 이끌어 낼 수 있습니다.

정리 | 벡터공간 V와 일차독립인 부분집합 S를 생각하자. S를 포함하는 V의 (일차독립인) 극대 부분집합이 존재한다.

하우스도르프 극대원리에 의해 $$\mathcal {F}$$에는 극대원소가 있습니다. 이 극대원소는 V의 일차독립인 극대 부분집합이며 S를 포함합니다.

따름정리 | 모든 벡터공간은 기저를 포함한다.

위 두 정리의 증명은 생략합니다.

두 집합 사이에 일대일대응이 존재할 때, 두 집합은 기수(cardinality)가 같습니다. 위의 정리와 따름정리를 무한차원으로 유추하면 다음의 참인 명제를 생각할 수 있습니다.

무한차원 벡터공간이 주어질 때, 무한차원 벡터공간의 모든 기저는 기수가 같다.

😊 마무리

이번 포스팅에서는 라그랑주 보간법을 공부하고 마지막으로 유한차원에서 무한차원으로 기저의 존재성을 확장했습니다. 사실 완벽히 공부하기 위해서는 교재에 있는 1.7절의 연습문제 47을 풀어야 합니다. 다만 그걸 다 적기에 양이 많아서 적지 않겠습니다(사실은 귀찮..).~~

드디어 1장이 끝났습니다. 1장은 아주 기초인 벡터공간에 대해서 학습했습니다. 벡터가 무엇인지 부터 벡터공간, 부분공간, 그리고 일차결합, 일차종속, 일차독립, 기저, 생성, 추가로 이것을 유한차원에서 무한차원까지 법칙을 확장시켰고 심화과정 느낌으로 라그랑주 보간법까지 학습했습니다.

다음 2장은 선형변환과 행렬에 대해서 학습합니다. 1장에서 배운 내용이 계속해서 쓰이고 뿌리가 되니 열심히 복습하며 학습해야 겠다고 느꼈습니다. 계속해서 이 책이 끝날때까지 열심히 해봐야 겠습니다!

저번 장까지는 벡터공간과 부분공간에 대해 자세히 알아보았다. 이번 포스팅에서는 아주 중요한 일차결합, 일차독립, 기저 등에 대해 공부해보았다.

🔢 1.4 일차결합과 연립일차방정식

저번 포스팅에서 세점 A, B, C를 지나는 평면의 방정식이 $$x = A + su + tv$$임을 설명했었습니다. 여기서 만약 A가 원점이면 평면의 방정식이 $$x = su+tv$$가 됩니다. 그리고 이 평면은 $$R^3$$의 부분공간입니다. 이를 일반화 하여 다음과 같이 정의가 가능합니다.

정의 | V는 벡터공간이고 S는 V의 공집합이 아닌 부분집합이라고 하자. 유한개의 백터 $$u_1, u_2,...,u_n \in S$$와 스칼라 $$a_1,a_2,...,a_n$$에 대하여 다음을 만족하는 벡터 $$v\in$$ V는 S의 일차 결합(linear combination)이라 한다.

• $$v=a_1 u_1 + a_2 u_2 + ... + a_n u_n$$
  이때, $$v$$는 벡터 $$u_1 , u_2 , ... , u_n$$의 일차결합이고 $$a_1 , a_2 , ... ,a_n$$은 이 일차결합의 계수(coefficient)이다.

• 연립일차방정식을 풀기 위한 방법은 연립방정식을 해가 같으면서도 훨씬 풀기 쉬운 연립방정식으로 바꾸는 것이다.

구체적으로는, 한 연립방정식을 다른 방정식에서 적절히 더하거나 빼서 일부 미지수를 다른 미지수에 대한 식으로 표현하려는 것이다.

그 방법으로는 3가지 이다.

1. 두 방정식의 위치를 바꾼다.
2. 방정식에 0이 아닌 상수를 곱한다.
3. 상수배하여 얻은 방정식을 다른 방정식에 더한다.

이러한 과정을 반복하는 이유는 주어진 연립일차방정식이 다음 성질을 가지도록 하기 위해서이다.

성질 1 | 각 방정식에서 처음으로 등장하는 0이 아닌 계수는 1이다. 성질 2 | 어떤 미지수가 어떤 방정식에서 처음으로 등장하면(계수가 처음으로 0이 아니면), 그 외의 다른 행에서는 등장하지 않는다. 다시 말해, 다른 행에서 그 미지수에 붙은 계수는 0이다. 성질 3 | 처음 등장하는 미지수(계수가 처음으로 0이 아닌 미지수)의 첨자는 다음 행으로 내려갈 때마다 반드시 증가한다.

이제 어떤 집합의 일차결합을 원소로 하는 집합에 이름을 붙여봅시다.

정의 | 벡터공간 V의 공집합이 아닌 부분집합 S를 생각하자. S의 생성공간(span)은 S의 벡터를 사용하여 만든 모든 일차결합의 집합이며 span(S)라 표기한다. 편의를 위해 span($$\emptyset$$) = {0}으로 정의한다.

정리 | 벡터공간 V의 임의의 부분집합 S의 생성공간은 S를 포함하는 (V의) 부분공간이다. 또한 S를 포함하는 V의 부분공간은 반드시 S의 생성공간을 포함한다.

증명은 생략하겠습니다.

정의 | 벡터공간 V의 부분집합 S에 대하여 span(S) = V 이면 S는 V를 생성한다(generate 또는 span). 이 경우 S의 벡터가 V를 생성한다고 말하기도 한다.

⭐ 1.5 일차종속과 일차독립

무한체에서 벡터공간 V와 부분공간 W를 생각합시다. 점공간이 아닌 W는 무한집합이고 이때 W를 생성하는 W의 '조그마한' 유한 부분집합 S를 찾을 수 있으면 좋을 것 같습니다. 왜냐하면 이러한 집합은 W의 모든 벡터를 S에서 꺼낸 유한개의 벡터의 일차결합으로 표현할 수 있기 때문입니다.

여기서 S에서 꺼낸 한 벡터가 S에서 꺼낸 또 다른 벡터의 일차결합으로 표현되는지 판단해 봅시다. 일차결합의 정의 데로 하나하나 확인도 가능하지만 S의 모든 벡터가 다른 벡터의 일차결합으로 표현되지 않는다는 것을 단정하는 것은 매우 어렵습니다. 여기서 다른 방법이 있습니다. 영벡터를 S의 벡터의 일차결합으로 표현하는 모든 계수가 0인 것 외에 다른 방법이 존재하면, S의 어떤 벡터는 다른 벡터의 일차결합입니다.

그러니 쉽게 말하면 영벡터를 S의 벡터의 일차결합으로 표현할 때, 모든 계수가 0인 경우 외에 또 다른 표현이 존재하는지 확인하는 것이 더 효과적입니다.

정의 | 벡터공간 V의 부분집합 S에 대하여 $$a_1 u_1 + a_2 u_2 + ... + a_n u_n = 0$$을 만족하는 유한개의 서로 다른 벡터 $$u_1 , u_2 , ... , u_n \in S$$와 적어도 하나는 0이 아닌 스칼라 $$a_1 , a_2 , ... ,a_n$$이 존재하면 *집합 S는 *일차종속(linearly dependent)이라 한다. 이때, S의 벡터 또한 일차종속이다.

임의의 벡터 $$u_1 , u_2 , ... , u_n$$에 대하여 $$a_1 = a_2 = ... = a_n = 0$$이면 $$a_1 u_1 + a_2 u_2 + ... + a_n u_n = 0$$입니다. 이를 $$u_1 , u_2 , ... , u_n$$의 일차결합에 대한 영벡터의 자명한 표현(trivial representation of 0)이라 합니다.

집합이 일차종속이면 적절한 벡터를 택하여 영벡터를 자명하지 않은 방식으로 표현할 수 있습니다. 영벡터 0을 포함하는 모든 부분집합은 일차종속입니다. 0 = 1*0은 영벡터의 자명하지 않은 표현이기 때문입니다.

정의 | 벡터공간의 부분집합 S가 일차종속이 아니면 일차독립(linearly independent)이다. 이때, S의 벡터 또한 일차독립이다.

그리고 일차독립인 집합에 대한 다음 명제는 모든 벡터공간에서 참입니다.

명제 1 *공집합은 일차독립이다. 어떤 집합이 일차종속이기 위해선 반드시 공집합이 아니어야 한다. *명제 2 영이 아닌 벡터 하나로 이루어진 집합은 일차독립이다. 만약 {$$u$$}가 일차종속이면 0이 아닌 스칼라 $$a$$에 대하여 $$au = 0$$이다. 양변에 $$a$$^-1을 곱하면 $$u = a$$^-1$$(au)=a$$^-1$$0=0$$이므로 $$u$$가 영벡터가 아니라는 사실에 모순이다. 명제 3 어떤 집합이 일차독립이기 위한 필요충분조건은 $$0$$을 주어진 집합에 대한 일차결합으로 표현하는 방법이 자명한 표현뿐인 것이다.

명제 3은 유한집합이 일차독립인지 판정할 때 아주 유용하게 사용됩니다.

다음 정리는 일차종속과 일차독립의 정의를 바탕으로 바로 얻을 수 있으며 매우 중요합니다.

정리 | $$V$$는 벡터공간이고 $$S_1 \sube S_2 \sube V$$이다. $$S_1$$이 일차종속이면 $$S_2$$도 일차종속이다.

따름 정리 | $$V$$는 벡터공간이고 $$S_1 \sube S_2 \sube V$$이다. $$S_2$$가 일차독립이면 $$S_1$$도 일차독립이다.

증명은 생략하겠습니다.

S가 최소생성집합인지 판단하는 것은 집합 S가 일차독립인지 확인하는 것과 같습니다. 결과적으로 S의 어떤 진부분집합도 S와 같은 공간을 생성하지 못하면 S는 일차독립입니다. 이것을 다르게 표현하면 다음 정리와 같습니다.

정리 | 벡터공간 $$V$$ 그리고 일차독립인 부분집합 S를 생각하자. S에 포함되지 않는 벡터 $$u \in V$$에 대하여, $$S \cup {u}$$가 일차종속이기 위한 필요충분조건은 $$u \in span(S)$$이다.

증명은 생략합니다.

🔑 1.6 기저와 차원

정의 | 벡터공간 V와 부분집합 $$\beta$$를 생각하자. $$\beta$$가 일차독립이고 V를 생성하면 V의 기저(basis)라 한다. $$\beta$$가 V의 기저일 때, $$\beta$$의 벡터는 (V의) 기저를 형성한다.

• span($$\emptyset$$) = {$$0$$}이고, $$\emptyset$$은 일차독립이다. 즉, $$\emptyset$$은 점공간의 기저이다.
• 벡터공간 $$F^n$$에 대하여 다음 벡터를 생각하자. $$e_1$$ = (1, 0, 0,..., 0), $$e_2$$ = (0, 1, 0, ..., 0), ..., $$e_n$$ = (0, 0, ..., 1) 집합 {$$e_1 , e_2 , ... , e_n$$}은 $$F^n$$의 기저이다. 이 특별한 기저를 $$F^n$$의 표준기저(standard basis)라 한다.
• 집합 {$$1, x, x^2 , ... ,x^n$$}은 벡터공간 $$P_n (F)$$의 기저이다. 이 특별한 기저를 $$P_n (F)$$의 표준기저라 한다.
• 집합 {$$1, x, x^2 , ...$$}은 $$P(F)$$의 기저이다.

위에 따르면 기저는 유한집합이 아닐 수도 있습니다. 그리고 기저가 유한집합이 아닌 벡터공간도 존재합니다.

정리 | 벡터공간 V와 이 공간에 속한 서로 다른 n개의 벡터 $$u_1 , u_2 , ... , u_n$$을 생각하자. 집합 $$\beta$$ = {$$u_1 , u_2 , ... , u_n$$}가 V의 기저가 되기 위한 필요충분조건은 '임의의 벡터 $$u \in$$ V를 $$\beta$$에 속한 벡터의 일차결합으로 나타낼 수 있고, 그 표현은 유일하다'는 것이다. 즉, 유일한 스칼라 $$a_1 , a_2 , ... ,a_n$$에 대하여 벡터 $$v$$는 다음과 같다.

• $$v=a_1 u_1 + a_2 u_2 + ... + a_n u_n$$

정리 | 유한집합 S가 벡터공간 V를 생성하면, S의 부분집합 중 V의 기저가 존재한다. 즉, V에는 유한집합인 기저를 포함한다.

증명은 생략합니다.

곧이어 나오는 정리와 따름정리들은 1장에서 가장 중요한 결과 입니다.

정리 | 대체정리 (replacement theorem) $$n$$개의 벡터로 이루어진 집합 $$G$$가 벡터공간 V를 생성한다고 하자. $$L$$이 $$m$$개의 일차독립인 벡터로 이루어진 V의 부분집합이면, $$m \le n$$이다. 또한 다음 조건을 만족하는 집합 $$H \sube G$$가 존재한다. $$H$$는 $$n-m$$개의 벡터로 이루어졌으며, $$L \cup H$$는 V를 생성한다.

따름정리 1 | 벡터공간 V가 유한집합인 기저를 포함한다고 가정하자. V의 모든 기저는 유한집합이며, 같은 개수의 벡터로 이루어져 있다.

정의 | 기저가 유한집합인 벡터공간을 유한차원(finite dimension)이라 한다. V의 기저가 $$n$$개의 벡터로 이루어질 때, 유일한 자연수 $$n$$은 주어진 벡터공간의 차원(dimension)이고, dim(V)라 표기한다. 유한차원이 아닌 벡터공간은 무한차원(infinite dimension)이다.

따름정리 2 | (1) V의 유한 생성집합에는 반드시 $$n$$개 이상의 벡터가 있다. 또한 $$n$$개의 벡터로 이루어진 (V의) 생성집합은 (V의) 기저이다. (2) 일차독립이고 $$n$$개의 벡터로 이루어진 (V의) 부분집합은 V의 기저이다. (3) 일차독립인 (V의) 부분집합을 확장시켜 기저를 만들 수 있다. 다시 말해 $$L(\sube V)$$이 일차독립이면 $$L\sube \beta$$인 V의 기저 $$\beta$$가 존재한다.

이쯤에서 이번 절의 주요 내용을 정리해보겠습니다.

• 벡터공간 V의 부분집합이 기저이기 위해서는 V를 생성하고 일차독립이어야 한다.

• V의 어떠 기저가 유한집합이면, V의 모든 기저는 이 집합과 같은 개수의 벡터를 포함한다. 이 자연수(개수)는 V의 차원이고 V는 유한차원 벡터공간이다.
• 벡터공간 V의 차원이 n이면, V의 모든 기저는 반드시 n개의 벡터로 이루어져 있다.
• 더 나아가 V의 일차독립인 부분집합은 n개를 초과하는 벡터를 가질 수 없으며, 적절히 몇 개의 벡터를 추가하여 기저로 확장할 수 있다.
• V의 모든 생성집합은 적어도 n개 이상의 벡터를 가지며 몇 개 벡터를 적절히 제외하면 V의 기저로 축소할 수 있다.

위 내용을 아래의 벤 다이어그램으로 표현이 가능합니다.

• 기저는 일차독립인 집합과 생성집합의 교집합입니다.

정리 | 유한차원 벡터공간 V에 대하여 부분공간 W는 유한차원이고, dim(W) $$\le$$ dim(V)이다. 특히 dim(W) = dim(V) 이면 V = W이다.

따름정리 | 유한차원 벡터공간 V의 부분공간 W를 생각하자. W의 임의의 기저를 가져오면 이 기저를 확장하여 V의 기저를 얻을 수 있다.

증명은 생략하겠습니다.

🙂 마무리

분량이 생각보다 많아져서 1.6의 뒷부분인 라그랑주 보간법은 다음 포스팅인 1.7절과 함께 작성하겠습니다.

이번 포스팅 내용은 일차결합부터 일차종속, 일차독립, 그리고 기저와 차원에 대해 자세히 학습하였습니다. 내용이 많고 중요한 만큼 복습을 열심히 해야겠다고 느꼈습니다. 계속해서 열심히 공부해 봐야 겠습니다😊

들어가며

인공지능을 공부하면서, 아니 컴퓨터 공학을 공부하면서 느끼게 된 점은 수학이 필수라는 것이고 그중 선형대수의 중요성이 매우 높다는 것이다. 물론 대학 수업중에 공학선형대수학을 들었지만 제대로 듣지도 않고 학점을 딴다는 느낌으로만 들었고 그 개념자체가 현재 기억에 거의 없어서 다시 공부한다는 느낌으로 제대로 공부를 시작하려고 한다.

교재

공부를 할 교재를 고르는데 많은 시간이 걸리진 않았다. 아래의 조건을 만족시키는 것으로 바로 보인것이 이 교재이기 때문이다.

• 원서가 아닌 번역본이였으면 좋겠다.
• 쉽게쉽게 설명이 납득이 가면 좋겠다.

우선 나는 수학과 학부 수준 ~ 공대에서 정말 간단히 배우는 수준, 이 두 수준 사이의 학습을 원하기 때문에 그렇게 깊게 공부를 할 생각은 없다. 다만, 선형대수는 내 전공 특성상 매우 중요하기에 가능한 깊게 공부를 해 볼 생각이다.

추가로 할 말

시작 전 여기 벨로그는 내가 학습한 것을 간단히 정리한다는 생각으로 작성하는 것이라 증명을 최대한 적지 않을 것이고(물론 매우 중요하지만), 간단하게 작성하고 넘어갈 것이다.

벨로그에 무작정 길게 적는 것도 오래 걸리고 복습의 효율이 줄어들 것 같고, 증명은 때에 따라 다르긴 하지만 그 길이가 길어질 수 밖에 없는 경우가 매우 많기 때문이고 증명이 매우 많기 때문이다. 물론 증명이 중요하지 않다는 것이 아니다. 본인은 매우 중요하게 생각하고 증명을 하는 과정이 수학적 논리력을 높여준다고 생각이 들기 때문이다. 하지만 여기에는 작성하지 않을 것이고 궁금한 독자가 있다면 스스로 찾아보자. 본인은 책을 보면 그만이지만..

📖 1.1 개론

이 책의 첫번째 단원은 벡터공간이다. 말그대로 벡터공간에 대해 학습을 하게 된다. 먼저 가장 처음 개론 부분을 학습해보았다.

벡터가 무엇인지 설명한다.

벡터(vector)란

• 크기와 방향을 모두 가진 물리량
• 주로 화살표로 표현하며 벡터의 크기는 화살표의 길이로, 벡터가 작용하는 방향은 화살표의 방향으로 나타낸다.
• 크기와 방향만 고려하면 충분한 경우가 많아 벡터가 어디에 위치했는지와 무관하게 크기와 방향이 같으면 동일한 벡터로 생각한다.

두 벡터의 합(sum) := 평행사변형 법칙(parallelogram law)를 이용한다.

벡터 합의 평행사변형 법칙 := 시점이 P로 일치하는 두 벡터 x, y의 합은 점 P에서 시작하는 벡터이고, 이는 x와 y를 이웃한 변으로 하는 평행사변형의 대각선으로 나타낸다.

쉽게 위 사진과 같이 평행사변형 법칙을 이해하면 좋습니다(평행사변형 맞습니다).

여기서 만약 P를 원점으로 보고 x벡터의 종점을 (a₁, a₂), y벡터의 종점을 (b₁, b₂)라 하면 x+y의 종점은 (a₁ + b₁, a₂ + b₂)가 됩니다.

그리고 벡터의 크기를 확대하거나 축소할 수도 있습니다. 벡터에 실수를 곱하는 스칼라 곱(scalar multiplication)을 하면 됩니다.

벡터 x에 스칼라 t배를 한 tx는 (ta₁, ta₂)의 종점을 가집니다. 음수면 180도 뒤집어 주면 됩니다.

벡터를 이용하여 직선의 방정식과 평면의 방정식을 공간에서 나타낼 수 있습니다.

종점이 A, B이고 시점이 O인 두 벡터를 각각 u, v라 하겠습니다. 그리고 시점이 A이고 종점이 B인 벡터를 w라 하겠습니다. w = v - u가 됩니다.

직선의 방정식(두 점 A, B를 지날 때) := $$x = u + tw = u + t(v-u)$$ (단, t는 임의의 실수이고 x는 직선 위 임의의 점)

이번엔 평면의 방정식 입니다. 시점이 A이고 종점이 B, C인 벡터를 각각 u, v라 하겠습니다.

평면의 방정식(세 점 A, B, C를 포함하는 평면의 방정식) := $$x = A + su + tv$$ (단, s, t는 임의의 실수이고 x는 평면 위 임의의 점)

🔢 1.2 벡터공간

다음을 벡터공간이라고 합니다.

체 F에서의 벡터공간(vector space) 또는 선형공간(linear space) V는 다음 8가지 조건을 만족하는 두 연산, 합과 스칼라 곱을 가지는 집합이다.

• 합(sum)은 V의 두 원소 $$x, y$$에 대하여 유일한 원소 $$x + y \in$$ V를 대응하는 연산이다. 이때, $$x + y$$는 $$x$$와 $$y$$의 합이라 한다.
• 스칼라 곱(scalar multiplication)은 체 F의 원소 $$a$$와 벡터공간 V의 원소 $$x$$마다 유일한 원소 $$ax \in$$ V를 대응하는 연산이다. 이때, $$ax$$는 $$a$$와 $$x$$의 스칼라 곱(product)이라 한다.
  (VS1) 모든 $$x, y \in$$ V에 대하여 $$x+y=y+x$$이다. (덧셈의 교환법칙) (VS2) 모든 $$x, y, z \in$$ V에 대하여 $$(x+y)+z=x+(y+z)$$이다. (덧셈의 결합법칙) (VS3) 모든 $$x\in$$ V에 대하여 $$x+0=x$$인 $$y\in$$ V가 존재한다. (VS4) 각 $$x\in$$ V마다 $$x+y=0$$인 $$y\in$$ V가 존재한다. (VS5) 각 $$x\in$$ V에 대하여 $$1x=x$$이다. (VS6) 모든 $$a, b \in F$$와 모든 $$x\in$$ V에 대하여 $$(ab)x=a(bx)$$이다. (VS7) 모든 $$a \in F$$와 모든 $$x,y\in$$ V에 대하여 $$a(x+y)=ax+ay$$이다. (VS8) 모든 $$a, b \in F$$와 모든 $$x\in$$ V에 대하여 $$(a+b)x=ax+bx$$이다.

체 F의 원소는 스칼라, 벡터공간 V의 원소는 벡터라 합니다. 이 책에서 다루는 벡터공간의 체는 주로 실수 집합 $$R$$ 또는 복소수 집합 $$C$$입니다.

벡터공간을 정의하기 위해서는 단순히 집합과 원소뿐만 아니라 두 연산도 정확히 서술해야 합니다.

교재에서는 행렬, 수열, 다항식이 벡터공간을 정의한다는 것을 보이는 데 여기서는 넘어가겠습니다.

정리 1 | 벡터 합의 소거법칙 $$x, y,z \in$$ V이고 $$x+z=y+z$$일 때, $$x=y$$이다.

따름 정리 1 | (VS3)을 만족하는 벡터 $$0$$은 유일하다.

따름 정리 2 | (VS4)를 만족하는 벡터 $$y$$는 유일하다.

정리 2 | 모든 벡터공간 V에 대하여 다음이 성립한다.

1. 모든 벡터 $$x$$에 대하여 $$0x=0$$이다.
2. 모든 스칼라 $$a$$와 모든 벡터 $$x$$에 대하여 $$(-a)x = -(ax) = a(-x)$$이다.
3. 모든 스칼라 $$a$$에 대하여 $$a0 = 0$$이다.

증명은 생략하겠습니다.

💡1.3 부분공간

정의 | F-벡터공간 V의 부분집합 W를 생각하자. 이 부분집합 W가 V에서 정의한 합과 스칼라 곱을 가진 F-벡터공간일 때, V의 부분공간(subspace)이라 한다.

모든 벡터공간 V에 대하여 V와 {0}은 부분공간이다. 특히 {0}은 점공간인 부분궁간(zero subspace)이라 한다.

부분집합 W가 V의 부분공간이기 위한 필요충분조건은 다음 4가지 성질을 만족하는 것이다.

• 성질 1 : 모든 $$x\in$$ W, $$y\in$$ W에 대하여 $$x+y\in$$ W이다.(W는 덧셈에 대하여 닫혀있다).

• 성질 2 : 모든 $$c\in F$$와 모든 $$x\in$$ W에 대하여 $$cx\in$$ W이다.(W는 스칼라 곱에 대하여 닫혀있다).
• 성질 3 : W는 영벡터를 포함한다.
• 성질 4 : W에 속한 모든 벡터의 덧셈에 대한 역벡터는 W의 원소이다.

부분공간인지 확인할 때 성질 4는 굳이 확인할 필요가 없다.

m x n 행렬 A의 전치행렬(transpose matrix) A^t는 A의 행과 열을 바꾸어 얻은 n x m 행렬이다. 즉, (A^t)_ij = A_ji이다.

대칭행렬(symmetric matrix)은 A^t = A인 행렬이다. 대칭행렬은 반드시 정사각행렬이어야 한다.

대각성분 아래의 모든 성분이 0이면 상삼각행렬 또는 위삼각행렬(upper triangular matrix)이라 한다. 즉, i > j일 때 A_ij = 0 인 행렬이다.

대각성분을 제외한 모든 성분이 0인 정사각행렬을 대각행렬(diagonal matrix)이라 한다. 다시 말해, $$i\ne j$$일 때 M_ij=0인 n x n 행렬 M이다.

n x n 행렬 M의 대각합(trace)은 모든 대각성분의 합이고, tr(M)으로 표기한다.

정리 : 벡터공간 V의 부분공간들을 생각하자. 이 부분공간들의 임의의 교집합은 V의 부분공간이다.

증명은 생략하겠습니다. 행렬의 기본 특징들은 기본적인 것이니 확실히 알고 넘어가는 것이 좋을 것 같습니다.

😊 마무리

1장 자체가 내용이 많아서 중간에 한번 끊었다가 가기 위해 1.3까지만 작성해 보았습니다. 벡터가 무엇인지, 행렬의 가장 간단한 명칭/분류, 그리고 벡터공간이 무엇인지, 부분공간이 무엇인지를 알았습니다.
아마 가장 중요한 것은 벡터공간과 부분공간의 정의 일 것이라고 생각합니다. 교환/결합/분배 법칙과 항등원과 역원의 존재, 그리고 스칼라 곱과 합이 닫혀있다는 것. 이것들을 기억하면 될 것 같습니다.

다음 1.4~1.6까지의 내용은 일차결합, 일차종속, 일차독립, 그리고 기저에 대한 내용으로 매우 중요하다고 볼 수 있고 아마 양도 많을 것입니다. 다만 증명을 적지 않은 관계로 이 포스팅보다 글 자체의 길이는 적을 수 있는데 증명은 필히 공부해야 할 것입니다.

그리고 1.7은 무한차원 벡터공간에서 기저가 존재함을 증명하는 것인데.. 내용이 쉽지는 않지만 다루고 넘어가는 것이 좋을 것 같아서 매우 짧게 포스팅할것 같습니다.

쉽지 않은 내용들이라 저도 열심히 해야겠습니다. 화이팅입니다!

⭐시작

서론

원래 컴퓨터 공학과인 나는 수학이라는 학문 그 자체에 관심이 없었다. 하지만 사실상 필수인 선형대수를 다시 제대로 공부하기 위해 찾아보다 미적분학, 그리고 인공지능을 깊게 공부하려면 미분기하학까지 쓰일 수 있다는 것을 알았다.

그래서 현재 수학관련 공부를 수학과 학부수준에서 고등학교 과정 그 사이정도로 학습을 하자 싶어 선형대수와 미분기하의 선이수격인 해석학관련 교재를 탐색후 구매하고 공부를 하기 시작하였다.

공부를 하며 수학이라는 학문이 나에게 너무 재미있다고 느꼈다. 특히 해석학이 그랬다. 현재는 페아노 공리까지만 학습하긴 하였는데 그냥 자연수라는 것이 무엇인지 수학적으로 학습하는 것이 너무 재미있었다.

그리고 그냥 공부하기 아쉬워 이 벨로그에 간단히 남겨보기로 하였다.

교재

우선 해석학은 좋은 교재가 너무 많다. 하지만 많은 만큼 들어가는 깊이와 범위가 다르다. 이리저리 찾아보다가 결국 고르게 된 것은 테렌스 타오(Terence Tao)의 해석학이였다. 이 책을 고른 이유는 다음과 같다.

1. 수학의 기초부터 시작한다.
2. 서술이 잘 되어있어서 이해하기 쉽다.
3. 한글 번역본이 있고 그 번역 상태가 좋다.

원래 깊이 공부하려면 원서가 낫지만 나는 수학과 학부 수준까지 깊이 공부할 생각은 없고 영어를 번역하면서 까지 공부를 하기엔 시간도 많이 걸릴거 같아서 한글 번역본으로 학습하기로 결정하였다.

📖해석학 소개

첫번째 세션은 해석학이 무엇인지에 관한 것이였다. 간단히 저자가 적은 것을 요약하면

1. 실해석학(real analysis)은 실수, 실수열과 급수, 실숫값함수를 분석하는 학문이고 이 책은 최우등 학부생을 위한 실해석학 입문서이다.

2. 해석학(analysis)은 수학적 대상의 질적 및 양적 행동을 정확하고 날카롭게 파악하는 데 중점을 두고 수학적 대상에 관해 엄밀한 연구를 하는 학문이며, 그중에서도 실해석학은 미분적분학(calculus)의 기초가 되고 이론적 토대를 구성한다.

3. 해석학은 "어떻게"가 아닌 "왜"에 대해서 학습을 하는 것이다.

4. 해석학을 학습하면 '분석적 사고방식'을 개발할 수 있는데, 새로운 수학 규칙을 접하거나 기존 규칙으로 충분히 설명되지 않는 새로운 상황을 다룰 때 분석적 사고방식이 큰 힘이 되어줄 것이다.

이렇게 요약 가능하다.

간단히 요약한 것이 이런 것이고 책에서는 실제로 다양한 예시를 들어서 10쪽을 이용해 자세히 설명하고 있다. 이제 해석학을 학문적으로 시작해보겠다.

🔢페아노 공리

수체계와 순환 논리의 오류

우선 수 체계를 설명한다. 수 체계는 수가 복잡해지는 순서대로 자연수 $\mathbb{N}$, 정수 $\mathbb{Z}$, 유리수 $\mathbb{Q}$, 실수 $\mathbb{R}$이 있다. 복소수 $\mathbb{C}$처럼 다른 수체계도 존재하지만 지금은 고려하지 않겠다.

자연수 {0, 1, 2, ...}는 가장 원시적인 수체계이지만 정수를 구성하는데 사용되고, 정수는 유리수를 구성하는 데, 유리수는 실수를 구성하는데, 실수는 결국 복소수를 구성하는 데 사용된다. 그러므로 자연수부터 들여다 봐야 하는데 그럼 "어떻게 자연수를 실제로 정의할까?"

우선 순환 논리(circularity)를 피하기 위해서 알려진 사실을 이용하지 않는 방법이 필요하다. 순환 논리란 A를 증명하기 위해 더 발전된 형태의 B를 이용한 뒤, 사실 B를 증명하기 위해 다시 사실 A를 이용하는 것이다. 즉 자연수를 정의하기 위해선 더하기, 빼기 같은 사칙연산의 정의를 이용하면 안된다.

페아노 공리

페아노 공리(Peano axiom)은 주세페 페아노가 창시한 자연수를 정의하기 위한 방법이다.

우선 자연수를 간단히 정의해 보자.

자연수(natural number)는 다음과 같은 집합 $\mathbb{N}$의 임의의 원소를 의미한다. $\mathbb{N}$ := {0, 1, 2, 3, ...} 이때 집합 $\mathbb{N}$은 0에서 시작하여 무한히 앞으로 세면서 생성되는 모든 수로 이루어져 있다. $\mathbb{N}$을 자연수 집합이라고 한다.

이 정의에 따르면 "자연수는 무엇일까?"라는 질문에 "자연수는 집합 $\mathbb{N}$의 임의의 원소이다"라고 답할 수 있다.

하지만 만족스러운 답은 아니다. "0으로 되돌아가지 않고 무한히 계속 셀 수 있음을 어떻게 알 수 있을까?", "덧셈이나 곱셈, 거듭제곱과 같은 연산을 어떻게 수행할 수 있을까?"와 같은 질문에 답을 낼 수 없다.

우선 둘째 문제를 해결해 보면 간단한 연산을 이용하여 복잡한 연산을 정의할 수 있다. 거듭제곱은 반복된 곱셈이며 곱셈은 반복된 덧셈이다. 그렇다면 덧셈은 어떨까? 덧셈은 앞으로 세거나 증가하는 반복 연산에 불과하고 증가시키는 연산은 더 간단한 연산으로 축소할 수 없는 근본적인 연산으로 보인다.

자연수를 정의하기 위해 두 가지 개념을 사용한다.

1. 영을 나타내는 수인 0을 사용한다.
2. 다음수 연산(successor operation) 또는 증가연산(increment operation)을 사용한다.

그리고 컴퓨터 언어의 기호를 사용하여 n의 다음수를 n++라고 나타낸다.

그러므로 $\mathbb{N}$은 0, 0++, (0++)++ 와 같은 수학적 대상들을 포함해야 한다.

공리 1 | 0은 자연수이다.

공리 2 | n이 자연수이면 n++도 자연수이다.

조금더 쉽게 표현하면

수 0++를 1로 정의하고, 수 (0++)++를 2라 정의한다. (즉, 1 := 0++, 2 := (0++)++ 등이다.)

** 3은 자연수이다 **

위 명제를 증명해보자.

<증명> 공리 1에 따르면 0은 자연수 이고 공리 2에 따르면 0++ = 1은 자연수이다. 이렇게 공리 2를 반복적으로 이용하면 2++ = 3은 자연수이다.

위 정의들로 자연수를 충분히 정의한것 같지만 그렇지 않다. 아래의 예를 보자.

수 0, 1, 2, 3으로 구성되어 있고 3에 증가연산을 적용하면 0으로 돌아가는 수체계를 생각하자. 즉 3++는 0과 같다. 즉 4와 0이 같아진다.

이러한 되돌아가는(wrap-around) 문제를 방지하기 위해 새로운 공리를 추가한다.

공리 3 | 0은 어떤 자연수의 다음수도 될 수 없다. 즉, 모든 자연수 n에 대해 n++ =! 0이다. (=!는 같지 않다라는 것을 나타낸 것이다.)

이를 토대로 아래의 명제를 증명해보자.

4는 0과 다르다

<증명> 정의로부터 4 = 3++이다. 공리 1과 2에 의해 3은 자연수이고 공리 3에 의해 3++ =! 0이다. 즉, 4 =! 0이다.

하지만 다음과 같으면 어떨까?

0, 1, 2, 3, 4로 구성되어 있고 증가 연산이 4에서 '천장'에 부딪히는 수체계를 생각하자. 즉 4++ = 4이다.

이럴땐 아래와 같은 공리를 추가하면 해결된다.

공리 4 | 서로 다른 자연수는 서로 다른 다음수를 가진다. 즉, 두 자연수 n과 m이 n =! m 이면, n++ =! m++이다.

위와 같이 정의해도 한 가지 문제가 남아있다. 이 수체계에 다른 형태의 '변이'원소가 존재할 수 있다.

$\mathbb{N}$ 수체계에 정수오 반정수로 구성된 집합이라면? $\mathbb{N}$ := {0, 0.5, 1, 1.5, 2, ...} 이 같은 경우에도 위의 공리를 모두 만족한다.

이럴땐 수학적 귀납법 원리를 이용하면 된다.

공리 5 | 수학적 귀납법 원리 (principle of mathematical induction) P(n)이 자연수 n과 관련있는 임의의 성질(property)이라고 하자. P(0)이 참이라 가정하고, P(n)이 참일 때마다 P(n++) 또한 참이라고 가정하자. 그러면 모든 자연수 n에 대해 P(n)은 참이다.

위의 추론으로는 P(0.5)가 참이라는 결론에 도달하지 못한다. 그러므로 공리 5는 0.5와 같은 '불필요한' 원소를 포함하는 수체계에서 성립하면 안된다.

여기서 공리1 ~ 공리5는 자연수에 대한 페아노 공리(Peano axiom)라고 한다.

즉 다음과 같이 가정할 수 있다.

공리1 ~ 공리5를 만족하는 수체계 $\mathbb{N}$이 존재한다. $\mathbb{N}$의 원소를 자연수(natural number)라고 한다.

현대 해석학이 이룩한 뛰어난 업적은 바로 원시적인 공리 5개와 집합론 공리 몇 가지만으로 시작하여 다른 모든 수체계를 구축하고, 함수를 만들었으며, 모든 대수와 미분적분학을 만들어 냈다는 것이다.

<참고> 각각의 자연수는 유한하지만 자연수 집합은 무한하다. 즉, $\mathbb{N}$자체는 무한집합이지만 개별로 보면 유한인 원소로 구성되어 있다. (전체는 그 어떤 일부분보다 크다.) 즉, 자연수는 무한에 접근할 수 있지만 실제로는 무한에 절대 도달할 수 없으므로 무한대는 자연수가 아니다.

공리를 이용하여 얻는 결과 중 하나로 수열의 재귀적(recursive) 정의가 있다.

명제 | 재귀적 정의 각각의 자연수 n에 대해 자연수에서 자연수로 가는 어떤 함수 f_n : $\mathbb{N}$ -> $\mathbb{N}$이 존재하고, c가 자연수라고 하자. 그러면 자연수 n마다 유일한 자연수 a_n을 배정해서 a₀ = c이고 a_n++=f_n(a_n)을 만족하게 할 수 있다.

<증명> 귀납법을 이용하자. 먼저 이 절차가 a₀에 단일값, 즉 c를 지정함을 확인하라. 이제 이 절차가 a_n에 단일값을 지정한다는 점을 귀납적으로 가정하자. 그러면 a_n++에 단일값이 a_n++ := f_n(a_n)으로 지정된다. 이로써 귀납법 증명을 완료할 수 있다. 더불어 자연수 n마다 a_n을 정의할 수 있는데, 이는 a_n마다 단일값을 배정하는 방식이다.

재귀적 정의는 매우 강력한 도구이다.

😊마무리

수학에서 가장 기본이 되는 수체계인 자연수에 대해 자연수 체계가 무엇인지 정의하는 것을 학습하였다. 가장 기초적인 부분의 존재를 증명, 정의하는 것이라 아무 생각없이 풀기에는 매우 어려웠는데 책의 내용데로 차근차근 아주 작은것부터 정의, 이용하니 어느정도 쉽게 풀어나간 것 같다.

어렵기도 어렵고 내가 아는 수학이랑도 많이 달랐는데 그만큼 재미있었다. 뭔가 수학보다는 철학이나 논리학 공부한 느낌..?

다음 절은 덧셈과 곱셈을 정의하는 것 같은데 기대된다.

+벨로그에 정리해서 적으려니 너무 오래걸린다.. 다음부터는 최대한 줄여봐야겠다..!

📍문제 분석 및 프로그램 설계

2차원의 배열, 즉 정사각행렬이 주어지고 그 요소들의 값이 주어진다. 그리고 x1, x2, y1, y2가 주어지고 행렬의 행과 열의 크기인 N이 주어지면 (x1, y1)부터 (x2, y2)까지의 sub matrix의 요소값들의 합을 입력받은 M의 횟수만큼 출력한다. 원하는 범위만큼 2중 for문을 써서 하나하나 접근+더해서 값을 출력해도 되지만 시간복잡도 상 그렇게 하면 시간초과가 되므로 누적합이라는 것을 사용을 한다.

💡문제를 해결하는데 필요한 개념

누적합의 개념. 단순히 값들을 전부 저장하고 일일이 전부 더하는 것이 아닌 값들의 합들을 누적시킨 누적합을 저장하고 접근하는 것이 시간적으로 유리하다.

💻소스 코드

#include <iostream>

using namespace std;

int v1[1025][1025], v2[1025][1025];

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;

    cin >> N;
    cin >> M;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> v1[i][j];
            v2[i][j] = v2[i - 1][j] + v2[i][j - 1] - v2[i - 1][j - 1] + v1[i][j];
        }
    }

    while (M--) {
        int x1, x2, y1, y2;
        int sum;

        cin >> x1 >> y1 >> x2 >> y2;
        x1--; x2--; y1--; y2--;

        sum = v2[x2][y2] - v2[x1 - 1][y2] - v2[x2][y1 - 1] + v2[x1 - 1][y1 - 1];
        cout << sum << '\n';

    }

    return 0;
}

👌문제를 풀기 위해 생각하고 해결했던 과정 및 느낀점

우선 문제를 처음 보고 생각난 것은 다름 아닌 범위의 값을 for문을 통해 전부 순회하고 그 값들을 다 더해서 출력을 하는 것이다. 하지만 당연하게도 시간초과가 떴고 시간을 줄일 수 있는 다른 방법을 생각해 보았다. 그렇게 혼자 생각을 하다가 도저히 떠오르지 않아 구글링 후 누적합이라는 것을 알게되었다. 예를 들어 {1, 2, 3, 4}의 값을 더해서 {1, 3, 6, 10}을 구한다고 하면 {1, 1+2, 1+2+3, 1+2+3+4} 이런 식으로 구하는 것이 아니라 그 전 단계의 누적된 합을 이용하여 {1, 1+2, 3+3, 6+4} 이런식으로 구하는 것이 이렇게 적은 범위에서 봐도 더 좋아보인다.

그래서 누적합을 이용하여 문제를 풀려고 시도를 하였다. 위 예시와 다르게 이 문제는 2차원 배열, 즉 행렬이다. 그러니 단순히 가로로만 누적합을 적용하는 것이 아닌 가로와 세로 둘다 적용을 해야한다.

그래서 우선 주어진 행렬자체의 값을 그대로 저장하는 배열(v1)을 만들고 그것을 통해 누적합을 저장하는 배열(v2)을 만들었다.

여기서 주의해야 할 점이 있었다. 누적합을 저장할 행과 열의 바로 전 누적합들([i-1][j]와 [i][j-1]) 그리고 원래 그 자리의 값을 다 더한 후 중복값을 빼줘야 한다. 그렇지 않으면 두번 중복 되기에 정확한 누적합이 아니게 된다.

그런식으로 누적합을 구한 후 원하는 범위에서의 값들의 합은 누적합 행렬의 [0][0]부터 범위의 상한까지의 누적합에서 범위에 해당하지 않는 부분들을 빼고 두번 빼진 중복값을 더해주기만 하면 구할 수 있다. 하지만 이렇게 했음에도 시간초과가 계속하여 발생하였고 또 한번의 구글링 결과 아래와 같은 코드들을 넣었다.

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

찾아보니 전부 입출력 시간을 줄여주는 역할을 하는 것이였다.(buffer관련된 것들인 것 같다.) 이 코드 세줄을 넣음으로써 문제를 풀 수 있게 되었다.

논문의 분량 상 이번 포스팅에서는 1. Introduction부터 3. Results and Comparison with Other Methods까지 작성해보았습니다.

1. Introduction

이 논문의 패턴 인식 시스템에서 기존의 수작업 기반 휴리스틱 방식에서 벗어나, 자동 학습에 더 의존하는 방식으로 전환해야 한다고 주장합니다. 특히 경사 하강법 기반 학습(gradient-based learning)과 머신러닝 기술, 대용량 데이터셋의 가용성이 어떻게 더 뛰어난 패턴 인식 시스템을 구축할 수 있는지를 보여주고자 합니다.

기존의 패턴인식체계는 아래 사진과 같습니다.

첫번째 모듈인 'Feature Extraction Module'에서는 입력 데이터를 저차원 벡터나 짧은 문자열로 변환합니다. 이것은 데이터를 쉽게 매칭 또는 비교할 수 있고, 입력 패턴의 본질을 바꾸지 않는 변형 및 왜곡에 관하여 상대적으로 불변합니다. 이는 수작업이 이용되어 많은 시간이 소요됩니다.

두번째 모듈인 'Trainable Classifier Module'은 'feature extractor'에 비해 보편적이고 학습 가능합니다.

여기서 문제점은 인식의 성능이 feature extractor를 설계하는 사람에 의해 좌우되고, 매번 다른 문제에 새로운 feature extractor를 설계해야 한다는 것입니다.

A. Learning from Data

먼저 그 당시 자주 이용되는 기법인 gradient-based learning(경사 기반 학습)에 대해 설명합니다. 위 식에서 Z^p는 p번째 입력 패턴이고 W는 adjustable(조정 가능)한 파라미터입니다. 함수의 출력 Y^p는 패턴 Z^p에 대해 예측한 class의 label이거나 각각의 class에 관련된 확률 또는 점수입니다.

E^p는 loss function(손실함수)이고 D^p는 실제 label을 의미합니다. loss function은 D^p와 F(W,Z^p)의 불일치(discrepancy)를 측정합니다.

그리고 E_train를 {(Z¹, D¹),..., (Z^p, D^p)}까지의 평균 오차인 avarage loss function를 의미합니다.

학습의 목표는 loss function을 가장 작게 만드는 W 파라미터를 찾는 것입니다.

실제로 측정해야 하는 것은 error rate입니다. 그것은 위의 식과 같이 구할 수 있습니다. P는 학습 데이터의 크기이고 h는 machine의 complexity(복잡도) 혹은 effective capacity입니다. 그리고 k는 상수이고 $\alpha$는 0.5와 1.0 사이의 수 입니다. E_test는 test data에 대한 loss function 입니다.

이와 같이 두 측정값의 차이를 줄이면서 E_train를 줄이는 것을 목표로 하고 그것을 structural risk minimization 이라고 합니다.

그래서 실제로는 위 식의 값을 줄이는 방식으로 진행됩니다. $\beta$는 상수이고 함수 H(W)는 regularization function입니다. H(W)는 매개변수 공간에서 고용량의 부분집합을 취하도록 선택됩니다. H(W)를 최소화 하는 것은 파라미터 공간에서 접근 가능한 subset을 줄어드는 단점이 있으므로 E_train를 줄이는 것입니다.

B. Gradient-Based Learning

경사 기반 학습은 매끄럽고 연속적인 함수를 최소화하는 데 효과적인 방법입니다. 손실 함수의 기울기(gradient)를 계산하여 파라미터를 반복적으로 조정하는 원리입니다. loss function은 파라미터 값의 작은 변화의 영향을 측정하여 최소화 시킬 수 있고 이것에 gradient-based learning이 효과적으로 사용됩니다.

파라미터 값은 위 식을 토대로 수정됩니다. $\epsilon$은 스칼라 상수이고 E(W)는 연속적이고 미분 가능한 loss function입니다. W는 실수의 매개변수 집합입니다.

online update 라고도 불리는 stochastic gradient algorithm(확률적 경사법)은 위와 같습니다. stochastic gradient 알고리즘은 매개변수를 noisy하거나 approximated 된 average gradient를 사용하여 갱신합니다.

C. Gradient Back Propagation

경사 기반 학습 절차는 1950년대 후반 이후로 사용되었지만 대부분 선형 시스템에 한정되었습니다. 하지만 3가지 사건으로 인해 복잡한 머신러닝 과정에서도 유용하다고 밝혀지게 됩니다.

1. loss function의 local minima 문제가 실제로는 큰 문제가 아니라는 것
2. Rumelhart에 의해 back-propagation 알고리즘이 non-linear system에서 대중화된 것
3. back-propagation 과정이 sigmoidal unit을 사용한 multi-layer neural network에 적용되면 복잡한 머신러닝 과업을 해결할 수 있다는 것

역전파의 기본 아이디어는 출력에서 입력 방향으로 기울기를 전파하여 계산하는 것입니다.

D. Learning in Real Handwriting Recognition System

필기체 인식의 어려운 문제 중 하나는 개별 문자를 인식하는 것뿐만 아니라, 단어나 문장 내에서 문자를 분리하는 '분할(segmentation)' 과정입니다. 그 당시 표준이라 불리는 segmentation 방식은 HOS(Heuristic OverSegmentation) 입니다. HOS는 이미지 처리 기술을 사용하여 가능한 많은 문자 경계 후보를 생성한 뒤, 인식기가 각 후보 문자에 부여하는 점수를 기반으로 최적의 조합을 선택하는 방식입니다. 하지만 이는 labeling된 database를 생성하는 것이 어렵기 때문에 한계가 있습니다.

E. Globally Trainable System

부분 패턴 인식 시스템은 multiple modules로 구성되어 있습니다. 예를 들면 field locator, field segmenter, recognizer, contextual postprocessor와 같이. 모듈간 데이터 전송을 나타내는 것은 그래프로 나타내는 것이 잘 나타냅니다. 전체를 보고 파라미터를 조정하는 것은 많은 시간 소비 등의 단점이 있고 이 대안으로 global error를 측정하고 최소화 하는 방법으로 조정하는 것이 효과적입니다. 그리고 그 loss function E는 gradient-based learning을 사용하여 찾을 수 있습니다. 하지만 시스템이 복잡해 진다면 gradient-based learning을 적용시키기 어려워 보입니다.

먼저 loss function $E^p$($Z^p$,W)가 미분가능하기 위해선 전체 시스템이 미분 가능한 모듈의 feedforward network 이여야 합니다. 즉, 각각의 모듈의 함수들은 연속적이고 미분가능해야 합니다. 그리고 이 때 back propagation의 일반화가 시스템의 모든 파라미터들의 loss function의 기울기를 계산하는 곳에 쓰이는 것으로 잘 알려져 있습니다.

위와 같은 함수로 구성된 각 모듈들로 구성된 시스템을 고려해 봅시다. $X_n$은 벡터로 표현된 output이고 $W_n$은 그 모듈에서 벡터로 표현된 tunable parameters(W의 부분집합), X_n-1은 모듈에 input 벡터 (즉, 이전 모듈의 output 벡터), $X_0$는 input pattern $Z^p$과 같고 첫번째 input 입니다.

loss function $E^p$에 대한 $W_n$과 X_n-1의 편미분은 각각 위의 식들과 같습니다. 첫 번째 수식은 $E^p(W)$의 일부 항의 gradient를 계산합니다. 두 번째 수식은 back-propagation 과정입니다. 위 식에서 Jacobian 곱을 partial derivatives에 이용하는데 그것 없이 직접적인 곱으로 계산하는게 대체로 쉽습니다.

2. Convolutional Neural Networks for Isolated Character Recognition

전통적인 패턴 인식 모델에는 hand-designed feature extractor가 정보를 모으고 관계없는 변수는 삭제하고 trainable classifier가 결과로 나온 특징 백터들을 클래스들로 카테고리화 합니다. 이와 같은 과정은 완전 연결 순전파 네트워크에는 잘 수행되는 반면 아래와 같은 문제들이 있었습니다.

1. 보통 이미지의 크기는 커서 시스템의 capacity를 증가시키고 더 많은 training set을 필요로 합니다. 또한 메모리도 크게 잡아먹습니다. 그러나 이미지 또는 음성 응용을 위한 비정형 네트워크의 주요 결함은 번역이나 입력의 국부적 왜곡에 대한 내장된 불변성이 없다는 점입니다.

2. input의 topology가 무시될 수 있습니다.

이러한 문제들을 CNN(Convolutional Neural Networks)가 해결 가능합니다.

A. Convolutional Networks

Convolutional networks(합성곱 신경)은 세가지 아키텍쳐 아이디어를 조합합니다. 이 세가지 아이디어는 shift, scale, distortion invariance를 견디기 위해 조합합니다.

그 아이디어들은 아래와 같습니다.

1) local receptive field 2) shared weights (or weight replication) 3) spatial or temporal subsampling

위 사진은 문자 인식을 위한 convolutional networks인 LeNet-5이다.

input으로 문자의 이미지를 받고 이 각각의 레이어의 유닛들은 이전 레이어의 근처에 위치한 유닛들의 집합에서 input을 받습니다. local receptive fields neurons은 엣지, endpoints, 코너와 같은 기초적인 시각적 특징들을 추출 가능합니다. 이 특징들은 subsequent layers로 조합이 되고 그것은 고차원의 특징에 접촉하기 위해 사용됩니다. 상태가 초기일수록 input의 distrotions 또는 shift는 salient features의 position을 다르게 하는데 원인이 될 수 있습니다. 게다가 하나의 이미지 부분에 유용한 초기 특징 detectors은 전체 이미지에 유용할 가능성이 있습니다.

레이어의 유닛들은 각각의 모든 유닛이 공유하는 같은 weights 집합을 공유하는 planes으로 구성되어 있습니다. 이러한 plane의 유닛들의 outputs 집합은 feature map이라고 부릅니다.

feature map의 모든 units은 이미지의 다른 부분의 같은 operation으로 구성되었습니다. complete convolutional layer은 몇몇의 feature map으로 구성되었고 그래서 multiple 특징은 각각의 location에서 뽑아낼 수 있습니다.

이것의 예시가 LeNet-5의 첫번째 layer입니다. 사진을 보시면 첫번째 hidden layer는 6개의 plane으로 구성되었고 이것이 각각 feature map 입니다. feature map은 5x5의 25개 input들이 연결되었고 이것을 receptive field of the unit이라 부릅니다. feature map에서 연속 단위의 수신 필드는 이전 레이어의 해당 연속 단위에 중심을 둡니다. 즉, 인접 유닛의 수신 필드 중첩됩니다. 다른 feature map의 layer은 다른 weights와 biases를 사용하고 다른 타입의 local features를 뽑아낼 수 있습니다. LeNet-5의 예시에서 6개 feature map은 각각 다른 6개의 타입을 가집니다.

feature map의 연속적인 구성요소들은 입력 이미지를 하나의 유닛으로 스캔이 가능하고 feature map에서 서로 대응하는 위치의 이 유닛의 상태들을 수집합니다. 이 작업에서 additive bias와 squashing function만 추가하면 convolution과 동등해서 이것을 convolutional network라 이름이 붙었습니다.

convolutional layer의 흥미로운 특징은 만약 입력 이미지가 shift되면 결과 output featuremap 또한 같은 양만큼 shift 될것이고 그 외에는 변하지 않습니다.

특징이 감지되면 정확한 위치는 덜 중요해지고 그것의 관계있는 다른 특징의 대략적인 위치가 관련있습니다. 각 특징의 정확한 위치는 패턴을 식별하는 데 중요하지 않을 뿐만 아니라, 문자의 경우에 따라 위치가 다를 가능성이 있기 때문에 잠재적으로 해로울 수 있습니다.

이렇게 정확도를 줄이는 방법으로 feature map의 부분적인 해상도를 줄이는 방법이 있습니다. 이를 담당하는 layer를 subsampling layer라고 하고 LeNet-5의 2번째 hidden layer입니다.

이 layer는 이전 layer의 각 피처 맵마다 하나씩 총 6개의 feature map으로 구성됩니다. 그리고 수용 필드는 이전 layer의 대응하는 feature map의 2x2영역을 각각의 유닛으로 가집니다. 이런 unit은 2x2의 평균을 계산하고 해당 unit의 trainable coefficient와 곱한 다음 trainable bias와 더합니다. 그리고 sigmoid function을 적용시킵니다. 이전 convolutional layer와는 다르게 인접한 unit들 간의 overlapping은 하지 않습니다. 따라서 행의 수와 열의 수가 이전 layer에 비해 반으로 줄어들게 됩니다.

모든 weight들은 back-propagation을 통해 학습되기 때문에 convolutional network는 앞서 언급한 pattern recognition system의 feature extractor가 아예 합쳐진 것 처럼 보입니다. 그리고 weight sharing technique이 machine의 capacity를 줄여 앞에서 언급한 test error와 train error 사이의 격차를 줄일 수 있을 것이라고 생각됩니다.

B. LeNet-5

LeNet-5은 input을 제외하고 7개의 Layer로 이루어져 있습니다. input은 32x32 픽셀의 이미지이고 이것은 데이터베이스의 가장 큰 문자의 크기보다 큽니다. 그 이유는 stroke end-point나 corner와 같은 뚜렷한 feature들은 첫 번째 convolutional layer의 중간 receptive field에서 나타나기 때문입니다. 배경(흰색)은 -0.1로 글자(검은색)는 1.175로 nomalize 시킴으로써 평균 입력을 대략 0으로 만들고 분산을 대략 1로 만들어 학습을 가속화합니다.

먼저 다음과 같이 정의하였습니다. Cx는 convolutional layer, Sx는 subsampling layer, Fx는 fully connected layer를 나타냅니다. 여기서 x는 layer index입니다.

LeNet-5의 C1은 6개의 feature map들을 가지고 있습니다. 각 feature map의 unit은 input의 5x5의 근처요소와 연결됩니다. C1은 156개의 trainable한 파라미터와 122304개의 연결이 있습니다.

S2 layer는 subsampling layer이고 6개의 14x14크기의 feature map들을 가지고 있습니다. 각각의 feature map은 C1의 feature map에 대응 되는 2x2들과 연결됩니다. S2는 12개의 trainable한 파라미터들과 5880개의 연결이 있습니다.

C3 layer는 16개의 feature map들이 있고 각각의 feature map의 unit들은 S2 feature map의 부분적인 주위 5x5와 각각 연결됩니다. 위 사진은 table은 S2와 C3의 연결을 보여줍니다. S2의 모든 feature map이 C3의 모든 feature map과 연결되지 않은 이유는 두 가지가 있습니다. 첫 번째로 불완전한 연결 체계는 연결의 수를 합리적인 범위 내에서 유지합니다. 두 번째는 network의 대칭을 파괴합니다. 다른 feature map은 다른 feature를 추출합니다. C3 layer는 1516개의 trainabel한 파라미터들과 156000개의 연결이 있습니다.

S4는 16개의 5x5크기의 feature maps들이 있고 2x2들과 연결됩니다. 파라미터는 32개가 있고 2000개의 연결이 있습니다.

C5는 1x1 크기의 120개의 feature map들이 있고 각각의 unit은 5x5와 연결되어 있습니다. C5는 48120개의 trainable한 연결이 있습니다.

마지막 F6은 84개의 유닛들과 C5와 fully connect 되어 있습니다. 10164개의 trainable한 파라미터들이 있습니다.

클래식한 NN에서는 F6의 레이어들을 dot prouct를 그들의 input 벡터와 weight 벡터로 하고 bias를 더하게 됩니다. unit $i$에 대하여 가중된 합을 $a_i$라 하고 이것을 시그모이드 함수에 넣어서 만들어진 값을 $x_i$라 하면 아래로 표현할 수 있습니다.

그리고 활성화 함수(squashing function)은 아래와 같이 hyperbolic tangent로 표현됩니다.

여기서 $A$는 함수의 amplitude이고 $S$는 원점에서의 기울기를 의미합니다.

마지막의 output layer는 Euclidean Radial Basis Function(RBF)으로 구성되어 있습니다. 아래 식을 이용해 각각의 RBF의 출력($y_i$)을 구할 수 있게 됩니다.

RBF의 unit들은 input 벡터와 parameter 벡터의 유클리드 거리를 계산하고 output으로 나오게 됩니다.

RBF는 입력 패턴과 정답 패턴 간의 차이를 측정하는 벌점 항(penalty term)으로 해석될 수 있습니다. 확률론적으로는 가우시안 분포의 unnormalized negative log-likelihood로 해석될 수 있습니다. RBF는 F6 layer에서 target vector 역할을 합니다. F6 layer의 weight들은 +1 아니면 -1인데 이는 sigmoid의 최대 곡률과 일치합니다. 그렇기 때문에 loss function의 느린 수렴을 야기하는 시그모이드 포화를 방지합니다.

C. Loss Function

LeNet-5에 사용하기 좋은 loss function은 MSE(Minimum Mean Squared Error)에 해당하는 Maximum Likelihood Estimation(MLE)입니다. 식은 아래와 같습니다.

위 식에서 y_Dp는 RBF의 $D_p$번째 요소입니다. 즉, 올바른 클래스의 입력 패턴 Z^p에 해당하는 것입니다. 이 식이 대부분이 옳지만 아래와 같은 세가지의 결점이 있습니다.

1) RBF의 매개변수들을 학습시키면 E(W)가 매우 작아지나, RBF의 모든 매개변수 벡터는 동일하기 때문에 결국 network의 입력은 무시한 채 모든 RBF의 출력이 0이 되게 됩니다.

2) 클래스들 사이에 경쟁이 없다는 것입니다. 이러한 경쟁은 HMM(은닉 마르코프 모델)을 훈련시키는 데 때때로 사용되는 최대 상호 정보량 기준과 유사한, 최대 사후 확률(maximum a posteriori, MAP) 기준이라고 불리는 더 판별적인 훈련 기준을 사용하여 얻을 수 있습니다. 이는 입력 이미지가 여러 클래스 중 하나 또는 배경 "쓰레기(rubbish)" 클래스 레이블로부터 올 수 있다는 조건 하에서, 정답 클래스 $D_p$의 사후 확률을 최대화(또는 정답 클래스 확률의 로그 값을 최소화)하는 것에 해당합니다. 페널티의 관점에서 볼 때, 이 기준은 평균 제곱 오차(MSE) 기준처럼 정답 클래스의 페널티를 밀어 내리는 것 외에도, 오답 클래스들의 페널티를 끌어올린다는 것을 의미합니다.

위의 식이 MAP기준을 구체화한 손실함수 입니다.

두 번째 항의 음수 값은 "경쟁적인" 역할을 합니다. 이 값은 필연적으로 첫 번째 항보다 작거나 같으므로, 이 손실 함수는 양수입니다. 상수 j는 양수이며, 이미 페널티가 매우 큰 클래스들의 페널티가 더 이상 올라가는 것을 방지합니다.

3. Results and Comparison with Other Methods

각각의 문자를 인식하는 것은 실용적 인식 시스템을 구축하는 것을 포함한 많은 문제들 중 하나이지만 shape recognition methods를 비교하는데 좋은 benchmark 입니다.

A. Database : The Modified NIST Set

훈련과 테스트에 쓴 데이터베이스틑 NIST의 Special Database 3와 Special Database 1 입니다. 이것들은 손글씨의 binary image를 포함하고 있습니다. 원래 NIST는 SD-3를 train set으로 SD-1을 test set으로 사용하였습니다. 하지만 SD-3이 SD-1에 비해서 인식하기에 cleaner, easier 합니다. 학습 실험에서 합리적인 결론을 도출하려면 전체 샘플 세트 중에서 훈련 세트와 테스트 선택에 관계없이 결과가 독립적이어야 합니다. 따라서 NIST's datasets을 mixing한 새로운 database가 필요합니다.

먼저 본래의 dataset의 SD-1을 작성자 별로 재정렬 한 후 250명 작성자로 두개로 나누어 처음 하나는 train set으로, 남은 하나는 test set으로, 즉 약 30000개의 데이터로 나누었습니다. SD-3 또한 각각 데이터를 나누어서 train set과 test set을 60000개로 보충하여 사용하였습니다. 이 중 train set으로는 60000개를 전부 사용하였지만 test set은 각각 5000개씩, 총 10000개의 데이터를 사용하였습니다.

결과로 나온 이 데이터셋을 modified NIST, 즉 MNIST dataset이라 부릅니다.

원본 흑백 이미지는 가로세로 비율을 유지하면서 20x20 픽셀 상자에 맞도록 크기가 정규화되었습니다. 데이터베이스는 세 가지 버전이 사용되었습니다.

1) 이미지들은 픽셀의 무게 중심을 계산하고 이 점이 28x28 영역의 중앙에 위치하도록 이미지를 평행 이동시켜 28x28 이미지의 중앙에 배치되었습니다. 어떤 경우에는 이 28x28 영역이 배경 픽셀을 추가하여 32x32로 확장되었습니다. 이 버전의 데이터베이스는 일반(regular) 데이터베이스라고 부를 것입니다.

2) 문자 이미지가 기울기 보정된 후 20x20 픽셀 이미지로 잘렸습니다. 기울기 보정은 픽셀의 2차 관성 모멘트를 계산하고(전경 픽셀은 1, 배경 픽셀은 0으로 계산), 주축이 수직이 되도록 각 라인을 수평으로 이동시켜 이미지를 층밀림 변환합니다. 이 버전의 데이터베이스는 기울기 보정(deslanted) 데이터베이스라고 부를 것입니다.

3) 세 번째 버전의 데이터베이스는 일부 초기 실험에 사용되었으며, 이미지가 16x16 픽셀로 축소되었습니다. 그림 4는 테스트 세트에서 무작위로 뽑은 예시들을 보여줍니다.

B. Results

LeNet-5의 여러 버전이 MNIST 데이터베이스로 훈련되었습니다. 각 세션마다 전체 훈련 데이터에 대해 20회의 반복이 수행되었습니다. 전역 학습률(global learning rate) η의 값은 다음 스케줄에 따라 감소되었습니다.

• 처음 두 번의 패스(pass) 동안은 0.0005

• 다음 세 번 동안은 0.0002

• 그 다음 세 번 동안은 0.0001

• 그 다음 네 번 동안은 0.00005

• 그리고 그 이후에는 0.00001

각 반복 전에, diagonal Hessian 근사는 500개의 샘플에 대해 재평가되었고, 전체 반복 동안 고정되었습니다. 파라미터 μ는 0.02로 설정되었습니다. 첫 번째 패스 동안 결과적인 유효 학습률(effective learning rate)은 파라미터 집합에 걸쳐 대략 7×10⁻⁵에서 0.016 사이에서 변동했습니다.

test error rate는 test set에 대한 약 10번의 패스 이후 0.95%에서 안정화됩니다. train set에 대한 error rate은 19번의 패스 이후 0.35%에 도달합니다. 많은 저자들은 다양한 과제에 대해 NN이나 다른 적응형 알고리즘을 훈련할 때 overfitting(과적합)이라는 현상을 관찰했다고 보고했습니다. 과적합이 발생하면, 훈련 오차는 시간이 지남에 따라 계속 감소하지만 테스트 오차는 최솟값을 찍고 일정 횟수의 반복 이후 다시 증가하기 시작합니다.

위 그림의 학습 곡선에서 볼 수 있듯이 LeNet-5의 경우에는 관찰되지 않았습니다. 가능한 이유는 학습률이 상대적으로 크게 유지되었기 때문입니다. 이것의 효과는 가중치가 local minimum에 안주하지 않고 무작위로 계속 진동한다는 것입니다. 그러한 변동 때문에, cost는 더 넓은 최솟값에서 더 낮아질 것입니다. 따라서, 확률적 경사 하강법(stochastic gradient)은 더 넓은 최솟값을 선호하는 regularization 항과 유사한 효과를 가질 것입니다. 더 넓은 최솟값은 파라미터 분포의 엔트로피가 큰 해에 해당하며, 이는 일반화 오차에 이롭습니다.

training set size의 영향은 15000, 30000, 60000개의 예제로 network를 train할때 측정되었습니다. training error와 test error는 위 그래프에서 볼 수 있습니다. LeNet-5 같은 전문화된 아키텍처에서는 더 많은 training data가 정확도를 향상시켜준다는 것이 명확합니다.

이 가설을 입증하기 위해서는 더 많은 training examples들을 원본 tringing images를 랜덤하게 분류하여 인공적으로 생성하여야 합니다. training set을 원래 60000개에서 540000개의 패턴을 더 추가하였습니다.

distortion은 다음과 같은 planar affine transformations들의 조합이었습니다:

• 수평 및 수직 이동
• scaling
• 찌그러뜨리기(수평 압축과 수직 신장의 동시 발생, 또는 그 반대)
• horizontal shearing

위 그림은 훈련에 사용된 distort 된 패턴의 예시를 보여줍니다.

distort 된 데이터를 훈련에 사용했을 때, test error rate는 0.8%로 떨어졌습니다 (변형이 없었을 때는 0.95%). deformation을 사용하지 않았을 때와 동일한 훈련 파라미터가 사용되었습니다. 전체 훈련 세션의 길이는 변경되지 않았습니다 (각각 60,000개 패턴으로 구성된 20번의 패스). 이 20번의 패스 과정 동안 네트워크가 각 개별 샘플을 실질적으로 단 두 번만 본다는 점은 흥미롭습니다.

위 그림은 잘못 분류된 테스트 예시 82개 전부를 보여줍니다. 이 예시들 중 일부는 정말로 모호하지만, 몇몇은 잘 나타나지 않는 스타일로 쓰였음에도 불구하고 사람에게는 완벽하게 식별 가능합니다. 이는 더 많은 훈련 데이터가 있다면 추가적인 개선이 기대된다는 것을 보여줍니다.

C. Comparison with Other Classifiers

비교를 위해 같은 database를 이용하였습니다. 다양한 방법의 test set의 error rate는 아래 그래프에 보여집니다.

1. Linear Classifier and Pairwise Linear Classifier

각 입력 픽셀 값은 각 출력 유닛에 대한 weighted sum에 기여합니다. 가장 높은 합계(편향 상수의 기여 포함)를 가진 출력 유닛이 입력 문자의 클래스를 나타냅니다. regular data에서 error rate는 12%이며, 이때 네트워크는 7850개의 free parameters를 가집니다. deslanted 이미지에서 test error rate는 8.4%이고, 네트워크는 4010개의 자유 파라미터를 가집니다.

2. Baseline Nearest Neighbor Classifier

이 방법의 classifier는 input images 사이의 유클리드 거리를 측정함으로써 사용하는 K-NN classifier입니다. 이 classifier는 training time이 필요 없고 디자이너의 생각이 필요하지 않다는 장점이 있습니다. 하지만 많은 메모리가 필요하고 인식 시간이 큽니다(완전한 60000개의 20x20 픽셀 트레이닝 이미지가 run time에 이용가능해야 합니다). k=3일 때, regular data에서는 error rate가 5.0%이고 deslanted data에서는 error rate가 2.4% 입니다. realistic Euclidean distance nearest-neighbor system은 직접적으로 픽셀보다는 feature 벡터로 나타나지만 이 연구의 다른 모든 시스템은 픽셀로 나타나기 때문에 이 결과는 baseline comparison에 유용합니다.

3. PCA and Polynomial Classifier

훈련 벡터 집합의 40개 주성분에 대한 입력 패턴의 projection을 계산하는 전처리 단계를 구성했습니다. 주성분을 계산하기 위해, 먼저 각 입력 성분의 평균을 계산하여 훈련 벡터에서 뺐습니다. 그 결과 나온 벡터들의 공분산 행렬을 계산한 다음 특이값 분해를 사용하여 대각화했습니다. 이 40차원의 특징 벡터는 2차 다항식 분류기의 입력으로 사용되었습니다. 이 분류기는 입력 변수 쌍들의 모든 곱을 계산하는 모듈 뒤에 821개의 입력을 가진 선형 분류기가 오는 것으로 볼 수 있습니다. regular test set error rate는 3.3%였습니다.

4. RBF Network

첫 번째 계층은 28x28 입력을 받는 1000개의 가우시안 RBF 유닛으로 구성되었고, 두 번째 계층은 1000개의 입력을 받아 10개의 출력을 내는 간단한 linear classifier 였습니다. RBF 유닛들은 100개씩 10개의 그룹으로 나뉘었습니다. 각 유닛 그룹은 적응형 K-평균 알고리즘(adaptive K-means algorithm)을 사용하여 10개 클래스 중 하나의 모든 훈련 예시에 대해 훈련되었습니다. 두 번째 계층의 가중치는 정규화된 유사역행렬 방법을 사용하여 계산되었습니다. 일반 테스트 세트에서의 오차율은 3.6%였습니다.

5. One-Hidden-Layer Fully Connected Multilayer NN

regular test set에서의 오차율은 은닉 유닛 300개를 가진 네트워크에서 4.7%, 은닉 유닛 1000개를 가진 네트워크에서 4.5%였습니다. 인공적인 왜곡을 사용하여 더 많은 훈련 데이터를 생성하는 것은 약간의 개선만을 가져왔습니다. 은닉 유닛 300개에서 3.6%, 은닉 유닛 1000개에서 3.8%였습니다. deslanted images를 사용했을 때, 은닉 유닛 300개를 가진 네트워크의 테스트 오차율은 1.6%로 내려갔습니다.

저자는 다층 신경망에서 경사 하강법 학습의 동역학이 "자기-정규화(self-regularization)" 효과를 가진다고 추측합니다. 가중치 공간의 원점은 거의 모든 방향에서 매력적인 안장점(saddle point)이기 때문에, 처음 몇 에포크 동안 가중치는 언제나 줄어듭니다. 작은 가중치는 시그모이드 함수가 거의 선형적인 영역에서 작동하게 만들어, 네트워크를 본질적으로 용량이 작은 단일 계층 네트워크와 동일하게 만듭니다. 학습이 진행됨에 따라 가중치는 커지고, 이는 점진적으로 네트워크의 effective capacity를 증가시킵니다.

6. Two-Hidden-Layer Fully Connected Multilayer NN

28x28-300-100-10 네트워크의 테스트 오차율은 3.05%로, 단일 은닉층 네트워크보다 훨씬 좋은 결과였습니다. 가중치와 연결을 약간만 더 사용했음에도 불구하고 말입니다. 네트워크 크기를 28x28-1000-150-10으로 늘리자 오차율이 2.95%로 약간 개선되었습니다. distorted patterns로 성능을 향상시키자 28x28-300-100-10 네트워크는 2.50%, 28x28-1000-150-10 네트워크는 2.45%의 오차율을 보였습니다.

7. A Small Convolutional Network--LeNet-1

CNN은 학습할 수 없는 작은 네트워크와 과적합된 것으로 보이는 큰 네트워크 사이의 딜레마를 해결하려는 시도입니다. LeNet-1은 CNN 아키텍처의 초기 구현으로, 여기서는 비교 목적으로 포함되었습니다. 이미지는 28x28 입력 계층에서 16x16 픽셀로 다운샘플링되고 중앙에 배치되었습니다. LeNet-1을 평가하는 데 약 100,000개의 곱셈/덧셈 단계가 필요하지만, 컨볼루션 특성 덕분에 자유 파라미터의 수는 약 2,600개로 유지됩니다. LeNet-1은 USPS(미국 우편 서비스) 데이터베이스의 자체 버전을 사용하여 개발되었으며, 그 크기는 가용한 데이터에 맞춰 조정되었습니다. 이렇게 적은 수의 파라미터를 가진 네트워크가 이처럼 좋은 오차율을 달성할 수 있다는 사실은 이 아키텍처가 해당 작업에 적합하다는 것을 나타냅니다. 테스트 오차율은 1.7%였습니다.

8. LeNet-4

LeNet-4는 아키텍처의 세부 사항에서 LeNet-5와 매우 유사합니다. 이는 2개의 첫 번째 특징 맵, 이어서 각 첫 번째 계층 특징 맵에 연결된 쌍으로 구성된 8개의 서브샘플링 맵, 그 다음 16개의 특징 맵, 이어서 120개의 유닛으로 구성된 완전 연결 계층, 마지막으로 출력 계층(10개 유닛)으로 구성됩니다. LeNet-4는 약 260,000개의 연결과 약 17,000개의 자유 파라미터를 포함합니다. 테스트 오차율은 1.1%였습니다.

9. Boosted LeNet-4

여러 신경망을 결합하는 부스팅(boosting) 방법을 개발했습니다. 3개의 LeNet-4가 결합되는데, 첫 번째 신경망은 일반적인 방식으로 훈련됩니다. 두 번째 신경망은 첫 번째 신경망이 통과시킨 패턴들과 첫 번째 신경망이 틀렸거나 맞혔던 패턴들의 50%로 구성된 혼합 데이터로 훈련됩니다. 세 번째 신경망은 첫 번째와 두 번째 신경망이 동의하지 않는 새로운 패턴들로 훈련됩니다. 테스트 시에는 세 신경망의 출력이 단순히 더해집니다.

LeNet-4의 오차율은 매우 낮기 때문에, 두 번째와 세 번째 신경망을 훈련시킬 충분한 샘플을 얻기 위해 인공적으로 왜곡된 이미지를 사용해야 했습니다. 테스트 오차율은 0.7%로, 다른 어떤 분류기보다도 좋은 결과였습니다. 언뜻 보기에는 단일 신경망보다 3배 더 비용이 많이 들 것 같지만, 실제로는 그렇지 않습니다. 첫 번째 신경망이 높은 신뢰도의 답을 내놓지 않을 경우에만 다른 신경망들이 호출됩니다. 평균적인 계산 비용은 단일 신경망의 약 1.75배입니다.

10. Tangent Distance Classifier

탄젠트 거리(Tangent Distance)는 거리 함수가 입력 이미지의 작은 왜곡과 이동에 둔감하게 만들어진 최근접 이웃 방법입니다. 이미지를 고차원 픽셀 공간의 한 점으로 생각할 때, 문자 특성의 왜곡은 픽셀 공간에서 곡선으로 나타납니다. 이 모든 왜곡들을 함께 고려하면 원본 이미지의 픽셀 공간 내에 저차원 매니폴드(manifold)를 정의합니다. 이 manifold는 접평면(tangent plane)으로 근사될 수 있습니다. 문자 이미지에 대한 "근접성"의 훌륭한 척도는 그들의 접평면 간의 거리이며, 여기서 평면을 생성하는 데 사용되는 왜곡 집합에는 평행 이동, 크기 변환, 찌그러뜨리기, 회전 및 선 굵기 변형이 포함됩니다. 16x16 픽셀 버전을 사용했을 때 테스트 오차율은 1.1%였습니다. 단순한 유클리드 거리를 사용한 전처리 기술은 접선 거리 계산에 필요한 반복 횟수를 줄였습니다.

11. SVM

SVM(Support Vector Machine)은 복잡한 결정 표면을 생성하기 위해 잘 연구된 다항식 분류기입니다. 안타깝게도 다항식 항의 수 때문에 고차원 문제에는 실용적이지 않습니다. 서포트 벡터 기술은 고차원 공간, 심지어 여러 유형의 곡면을 포함하는 공간에서 복잡한 표면을 나타내는 매우 경제적인 방법입니다.

특히 흥미로운 결정 표면의 부분 집합은 두 클래스의 볼록 폐포(convex hulls)로부터 최대 거리에 있는 초평면(hyperplanes)에 해당하는 것입니다. Boser 외는 최대 마진(maximum margin) 집합이 훈련 샘플의 부분 집합(support vector)과 입력 이미지의 dot product을 계산하고, 그 결과를 거듭제곱한 후, 얻어진 숫자들을 선형적으로 결합함으로써 임의의 차수 k의 다항식을 구현할 수 있다는 것을 깨달았습니다. 서포트 벡터와 계수를 찾는 것은 선형 부등식 제약 조건이 있는 고차원 이차 최소화 문제를 푸는 것과 같습니다.

일반 SVM을 사용했을 때 regular test set에서의 오차율은 1.4%였습니다. Cortes와 Vapnik은 약간 다른 기술을 사용하여 동일한 데이터에서 1.1%의 오차율을 보고했습니다. 이 기술의 계산 비용은 인식 건당 약 1,400만 번의 곱셈-덧셈 연산으로 매우 높습니다. Schölkopf의 V-SVM 기술을 사용하면 1.0%의 오차율을 달성했습니다. 더 최근에 Schölkopf는 V-SVM의 수정된 버전을 사용하여 0.8%에 도달했습니다. 안타깝게도 V-SVM은 일반 SVM보다 약 두 배나 비용이 많이 듭니다. 이 문제를 완화하기 위해 Burges는 RS-SVM 기술을 제안했으며, 일반 테스트 세트에서 1.1%의 오차율을 달성했습니다. 이는 인식 건당 65만 번의 곱셈-덧셈 연산의 계산 비용으로, LeNet-5보다 단지 60% 더 비싼 수준입니다.

D. Discussion

분류기들의 성능 요약은 그림 9~12에 나와 있습니다. 그림 9는 10,000개의 예시 테스트 세트에 대한 분류기들의 원본 오차율을 보여줍니다. Boosted LeNet-4가 0.7%의 점수를 달성하며 최고의 성능을 보였고, LeNet-5가 0.8%로 그 뒤를 바짝 쫓았습니다.

위 그림 10은 일부 방법에서 0.5%의 오차율을 달성하기 위해 기각해야 하는 테스트 세트 패턴의 수를 보여줍니다. 해당 값이 미리 정해진 임계값보다 작을 때 패턴이 기각됩니다. 많은 응용 분야에서 기각 성능은 원본 오차율보다 더 중요합니다. 패턴 기각 여부를 결정하는 데 사용된 점수는 상위 두 클래스의 점수 차이였습니다. 다시 한번, Boosted LeNet-4가 최고의 성능을 보였습니다. LeNet-4의 향상된 버전들은 원본 LeNet-4보다 성능이 좋았지만, 원본 정확도는 동일했습니다.

위 그림 11은 각 방법에 대해 단일 정규화된 이미지를 인식하는 데 필요한 곱셈-누적 연산의 횟수를 보여줍니다. 예상대로, 신경망은 메모리 기반 방법보다 훨씬 덜 까다롭습니다. CNN은 규칙적인 구조와 가중치에 대한 낮은 메모리 요구량 때문에 특히 하드웨어 구현에 적합합니다. LeNet-5의 선행 모델들의 칩 혼합 아날로그-디지털 구현은 초당 1000자 이상의 속도로 작동하는 것으로 나타났습니다. 그러나 주류 컴퓨터 기술의 급속한 발전은 이러한 이국적인 기술들을 빠르게 구식으로 만듭니다. 메모리 기반 기술의 효과적인 구현은 막대한 메모리 및 계산 요구 사항으로 인해 더 파악하기 어렵습니다.

훈련 시간도 측정되었습니다. K-NN과 탄젠트 거리 분류기는 본질적으로 훈련 시간이 없습니다. 단일 계층망, 쌍별 망, PCA+quadratic net은 1시간 이내에 훈련될 수 있었지만, 다층 신경망은 훈련 세트를 10-20회 통과해야 했습니다. 이는 단일 200MHz R10000 프로세서를 사용하는 Silicon Graphics Origin 2000 서버에서 LeNet-5를 훈련시키는 데 2~3일에 해당합니다. 훈련 시간은 설계자에게는 다소 중요하지만, 최종 사용자에게는 거의 중요하지 않다는 점에 유의하는 것이 중요합니다. 상당한 훈련 시간을 희생하여 약간의 개선을 가져오는 기존 기술과 새로운 기술 사이에서, 최종 사용자는 후자를 선택할 것입니다.

위 그림 12는 다양한 분류기들의 메모리 요구 사항, 즉 자유 파라미터의 수를 저장해야 할 변수의 수로 측정한 값을 보여줍니다. 대부분의 방법은 적절한 성능을 위해 변수당 약 1바이트만 필요합니다. 그러나 최근접 이웃 방법은 템플릿 이미지를 저장하기 위해 픽셀당 4비트가 필요할 수 있습니다. 놀랍지 않게도, 신경망은 메모리 기반 방법보다 훨씬 적은 메모리를 필요로 합니다.

전반적인 성능은 정확도, 실행 시간 및 메모리 요구 사항을 포함한 많은 요인에 따라 달라집니다. 컴퓨터 기술이 향상됨에 따라 더 큰 용량의 인식기가 실현 가능해집니다. 더 큰 인식기는 훈련 시간이 더 오래 걸립니다. LeNet-1은 1989년에 사용 가능한 기술에서는 적절했지만 LeNet-5는 그렇지 않았습니다. 1989년에는 LeNet-5만큼 복잡한 인식기는 몇 주간의 훈련과 더 많은 데이터가 필요했을 것이므로 고려되지 않았습니다. 오랫동안 LeNet-1은 최첨단 기술로 간주되었습니다. 지역 학습 분류기, 최적 마진 분류기 및 탄젠트 거리 분류기는 LeNet-1을 기반으로 개발되었으며 성공했습니다. 그러나 결국 개선된 신경망 아키텍처에 대한 동기가 생겼습니다.

저자는 Boosting이 메모리와 계산 비용을 약간만 증가시키면서 정확도를 약간 향상시킨다는 것을 발견했습니다. Distortion Models는 실제로 추가 데이터를 수집하지 않고도 데이터 세트의 유효 크기를 늘리는 데 사용될 수 있습니다.

SVM은 다른 고성능 분류기들보다 사전 지식이 현저히 적기 때문에 우수한 성능을 보여줍니다. 사실, 이 분류기는 이미지 픽셀이 뒤섞여 그림 구조를 잃더라도 거의 비슷한 성능을 보일 것입니다. 그러나 CNN에 필적하는 성능 수준에 도달하는 것은 메모리와 계산 요구 사항에서 상당한 비용을 치러야만 가능합니다. RSVM 요구 사항은 두 컨볼루션 신경망의 범위 내에 있으며 오차율은 매우 가깝습니다.

데이터가 많을 때, 많은 방법이 비슷한 행동을 보일 수 있습니다. NN 기반 방법은 훨씬 적은 공간을 차지하고 메모리 기반 방법보다 훨씬 적은 계산을 필요로 합니다. 훈련 데이터베이스의 크기가 계속 증가함에 따라 신경망의 이점은 더욱 두드러질 것입니다.

E. Invariance and Noise Resistance

CNN은 실제 단어 인식 시스템에서 휴리스틱 분할기에 의해 생성되는 것과 같이 위치, 크기 및 방향이 크게 다른 객체를 인식하거나 거부하는 데 특히 적합합니다.

위에서 설명한 실험에서는 크기 왜곡과 이동 불변성의 중요성이 명확하지 않습니다. 실제 응용 분야에서의 상황은 다릅니다. 문자는 일반적으로 인식 전에 컨텍스트에서 분리되어야 합니다. 분할 알고리즘은 거의 완벽하지 않으며 종종 문자 이미지에 외부 표시를 남기거나 때로는 너무 많이 잘라 불완전한 문자를 생성합니다. 이러한 이미지는 안정적으로 크기를 정규화하거나 중앙에 배치할 수 없습니다. 불완전한 문자를 정규화하는 것은 매우 위험할 수 있습니다. 따라서 많은 시스템이 단어나 필드의 수준에서 정규화를 시도했습니다. 한 경우, 전체 필드(예: 금액)의 상단 및 하단 경계가 감지되고 고정된 높이로 정규화하는 데 사용됩니다. 이는 stray mark가 문자 크기로 부풀려지지 않도록 보장하지만, 분할 후 문자의 크기와 수직 위치에 변화를 만듭니다. 따라서 이러한 변화에 강건한 recognizer를 사용하는 것이 좋습니다. 위 그림은 LeNet-5에 의해 정확하게 인식되는 왜곡된 문자의 몇 가지 예를 보여줍니다.

정확한 인식은 약 2배의 크기 변화, 문자 높이의 약 절반에 해당하는 상하 이동, 그리고 최대 ±30도의 회전까지 발생하는 것으로 추정됩니다. 복잡한 모양의 완전한 불변 인식은 여전히 어려운 목표이지만, CNN은 기하학적 왜곡에 대한 불변성 또는 강건성 문제에 대한 부분적인 해답을 제공하는 것으로 보입니다.

위 그림에는 극도로 잡음이 많은 조건 하에서 LeNet-5의 강건성 예시가 포함되어 있습니다. 이러한 이미지를 처리하는 것은 많은 방법에서 분할 및 특징 추출의 극복할 수 없는 문제를 제기하지만, LeNet-5는 이러한 어수선한 이미지에서 두드러진 특징을 강건하게 추출할 수 있는 것으로 보입니다. 여기에 표시된 네트워크에 사용된 훈련 세트는 소금-후추 잡음이 추가된 MNIST 훈련 세트였습니다. 각 픽셀은 0.1의 확률로 무작위로 반전되었습니다.

포스팅 마무리

논문의 분량상 나누어서 포스팅을 올릴 수 밖에 없었습니다. 논문이 총 10개의 섹션으로 나누어져 있는데 이번에는 3번째 섹션까지만 작성해 보았습니다. 나머지도 다 읽긴 했는데 포스팅을 올리는데 시간이 꽤 걸릴것 같지만 최대한 빨리 올려야 겠습니다.

아마 총 3개의 포스팅으로 나누어져서 올릴것 같고 다음은 46이나 47정도의 섹션을 올릴 것 같습니다.

주제

주제는 '행복한 대학생활'이다. 사실 너무 폭넓은 주제라 보이긴 하다. 그리고 지름길 이용하여 길찾기 같은 이미 많이들 했을 것이고 뻔하디 뻔한 세부주제들도 많기 때문에 주제를 잡는 것이 가장 어려웠던것 같다.

그러다 정하게 된 주제가 '캠퍼스 와이파이 품질 지도 자동 수집 시스템'이다.

우리의 주제

그래서 우리의 주제가 정확하게 뭐냐? 사실 그 부분이 가장 어려웠다. '와이파이 품질을 수집해서 무엇을 할건데?', '그게 왜 행복한 대학생활이냐' 라고 하는것에 대답을 할 줄 알아야 했다.

세부주제를 정하는 것에 대한 어려움

우린 처음에 학생을 대상으로 하였다. 행복한 대학생활이면 당연히 학생들을 위한 것이라 생각했고 그렇게 하자고 다들 말은 안했지만 분위기가 당연히 그쪽으로 넘어가는 느낌이였다.

그래서 우리는 이렇게 정하였다.

• 서비스 타깃은 학생
• 웹을 이용하고 지도를 통해 시각화
• 아두이노나 라즈베리파이 센서를 통해 와이파이 품질(rssi, 속도, 핑)을 측정
• 자주 확인할 강의실을 즐겨찾기 기능을 통해 추가 가능

그리고 문제를 '강의실 와이파이가 잘 안 되어서 불편을 겪는 학생들이 많음' -> 문제 해결을 '학생들이 와이파이가 잘 되는 강의실을 확인 가능하게 하여 이동을 통해 문제 해결을 유도'

하지만 이것에 문제가 있었다. 근본적인 문제해결이 안되는 것이다. 학생들이 직접 이동하는 것이 근본적인 문제해결이 아니라는 것이다. 그렇게 피그마를 통해 발표 ppt까지 다 작성한 우리는 그것을 갈아엎고 주제를 조정하려 하였다.

다시 시작..

중간에 운영진 분들의 피드백을 받고 세부주제를 조금 수정하기로 하였다. 그래서 우리는 이렇게 수정을 했다.

• 타깃을 학생에서 학교 와이파이 관리자로 변경
• 웹을 이용하는 것이 아닌 와이파이 관리자에게 알람이나 메일 등으로 정보를 전송
• 와이파이 품질과 관련되어 문제 발생시 문제 원인 파악을 위해 머신러닝을 이용
• 라즈베리파이 센서를 이용하여 와이파이의 rssi, 속도, 핑을 이용

머신러닝

나는 머신러닝을 맡기로 하여서 머신러닝에 대해서만 자세히 적어보겠다.

우선 우리가 머신러닝을 이용할 방법은 다음과 같다.

• 와이파이가 문제가 생길시 원인이 다양하다(트래픽증가, 전파간섭 등)
• 이러한 원인들은 각각 고유한 와이파이 품질 요소 흐름이 있는데 그것을 머신러닝을 통해 분류를 하는 것이다.
• 그 과정에서 랜덤 포레스트라는 툴을 이용할 예정이다.

  아래 사진이 랜덤 포레스트다.

  

사실 딥러닝이 아닌 머신러닝을 이용하는 것에도 이유가 있다.

• 데이터 양이 많지 않고 적을 가능성이 큼
• 시간이 많지 않음.(최종발표까지 2주정도밖에 없음)

사실 딥러닝을 공부하고 있고 딥러닝이 개인적으론 더 재밌어서 딥러닝을 하고 싶지만 머신러닝을 위 이유들로 선택하게 되었다.

결론

아직 구현은 시작하지 않았지만 어느정도 머리속으론 틀이 잡히긴 한다. 문제는 데이터.. 학습을 위해서라도 어느정도 양의 데이터가 필요한데 그게 가장 중요하긴 하다. 이제 기획은 마무리되었으니 구현에 머리를 많이 써야겠다..

🙌서론

저번 주차에는 미니맥스 알고리즘에 대해서 학습했다. 이번 주차에는 미니맥스와 비슷한 몬테 카를로 트리 탐색법에 대해서 학습하였다. 탐색공간의 크기가 크면 시간이 오래 걸려 미니맥스로는 엄두도 내지 못할 탐색을 몬테 카를로 트리 탐색법(줄여서 MCTS)으로 할 수 있게 되었다. MCTS는 알파고에도 도입하였다. 참고로 몬테 카를로는 모나코의 도박 도시 몬테 카를로에 있는 세계 최초의 카지노 이름이다.

🤔몬테 카를로 접근법

몬테 카를로 추정법

• 몬테 카를로 접근법이란 무작위적 시행을 통해 문제의 해에 대한 추정치나 근사치를 구하려는 확률론적 접근법이다.

예를 들어, 피적분 함수 f가 매우 복잡하여 해석적 적분이 힘들때 몬테 카를로 적분법으로 참 적분값의 근사치를 얻을 수 있다.

f(x) = -x²+9 가 있다고 하면 이것의 -3부터 3까지의 적분값을 구하는 문제라고 해보면 해석적으로 구하면 36이 나온다. 그리고 그것은 곡선 아래의 면적에 해당한다.

여기서 1사분면의 x가 0에서 8까지, y를 0에서 10까지로 보면 전체 면적은 80이고, 전체면적에서 곡선 아래의 면적의 비율r을 알수 있으면 적분값은 단순히 80*r로 계산된다.

만약 r을 정확히 모르더라도 근사적으로 추정할 수 있으면 적분값 I의 추정치 Î은 다음과 같이 구할 수 있다.

• Î = 80 * r̂

r의 추정치 r̂은 위 그림에 무수히 많은 수[n_total]의 점을 무작위적으로 찍어 보고 몇개[n]의 점이 곡선 아래에 찍혔는지를 세어 보면 될 것이다. 즉 다음과 같이 구할 수 있다.

• r̂ = n/n_total

그리고 위와 같은 방식의 적분을 몬테 카를로 적분이라고 한다. 전체 점의 수가 증가할 수록 참값 36에 가까운 결과를 보여준다.

랜덤 플레이 아웃

미니맥스 알고리즘을 이용한 평가법이 '대국이 끝나는 시점까지 서로가 최선의 수들을 찾는 것을 시뮬레이션 해보고, 이로부터 다음 수들을 평가하는 것'이라면, 몬테 카를로 접근법을 이용한 평가법은 '대국이 끝나는 시점까지 서로가 무작위적인 수를 두는 것을 시뮬레이션 해보고, 이로부터 다음 수들을 평가하는 것'이라 할 수 있다.

• 어떤 시점에서 둘 수 있는 수 중의 하나를 a라 하면, a가 두어진 후 승패가 판정될 때까지 무작위적인 수[상대의 수 포함]를 두어 보는 시뮬레이션을 해볼 수 있다. 이를 랜덤 플레이 아웃이라고 한다.

랜덤 플레이아웃이 완료되면 말단 노드의 상태[승리, 무승부, 패배]에 따라 보상[r]값을 결정한다. 예를 들어, 승리는 +1, 무승부는 0, 패배는 -1을 r의 값으로 한다고 하자.

• 랜덤 플레이 아웃을 실시하기 전, a의 가치는 무한대로 평가한다. 이 점은 상당히 중요하다.

랜덤 플레이 아웃이 시작되면 보상의 누적값 c를 구하고, 이로부터 a의 가치 v에 대한 몬테카를로 추정치를 구한다.

• v̂ = c/n

위와 같은 식으로 추정된 평가 점수[수의 가치]에 따라 수를 선택해 가는 방법이 가장 기본적인 몬테 카를로 접근법이다.

이 방법은 속도가 미니맥스 알고리즘 보다는 빠르겠지만 몬테 카를로 접근법 또한 모든 가능한 수들에 대하여 랜덤 플레이 아웃을 실시하므로, 탐색 공간이 크면 실행 시간 대비 만족할만한 기량을 보이지 못한다.

😀몬테 카를로 트리 탐색법[MCTS]

몬테 카를로 트리 탐색은 랜덤 플레이아웃만 실시하는 기본적인 몬테 카를로 방법을 개선한 것으로써, 선택, 확장, 평가, 갱신이라 칭하는 일련의 과정을 반복하면서 유력한 수를 더 깊게 살펴보는 방법이다.

바둑을 예로 들면 현재 국면이 수 a_0,0에 의해서 얻어진 것이라 하고 현재의 국면을 초기 노드 (0,0)이라 하자. 현재 국면을 내가 둘 차례인 국면이라 하자. MCTS는 초기 노드(0,0)이 주어졌을 때, 현 국면에서 가능한 수들을 나열하는 것에서 부터 시작한다. 이를 초기 확장이라 한다. 즉, 초기 확장은 초기 노드의 하위 노드들을 얻는 과정이다. 현 국면에서 둘 수 있는 수가 a_1,1, a_1,2, a_1,3 인 것으로 가정하자.

c는 앞으로 계산하게 될 보상[r]의 누적값이고, n은 노드의 방문횟수를 나타낸다. 그리고 노드를 표시할 원 속의 숫자는 노드의 가치[엄밀히는 가치의 추정치]를 나타낸다.

초기 확장 단계에서 모든 노드들의 n과 c는 0으로 한다. 그리고 초기확장 단계에서 모든 노드들의 가치는 무한대로 한다.

선택 단계에서는 가치가 가장 큰 하위 노드를 선택한다. 만약 선택된 노드에 하위 노드가 있다면 하위 노드 중에서 추정 가치가 가장 큰 노드를 선택한다. 여기서는 노드(1,1)을 선택했다고 하자.

평가 단계에서는 랜덤 플레이아웃을 실시하여 보상r을 얻는다. 랜덤 플레이 아웃의 결과로 승리에 도달하여 보상으로 +1점을 얻었다고 하자.

이렇게 랜덤 플레이 아웃으로 선택된 노드에 대한 r이 얻어지면, 초기 노드 (0,0)까지 거슬러 올라가면서 선택된 노드에 대한 보상 누적값 c와 방문횟수 n을 갱신하고 노드의 추정가치를 계산한다. 이 과정을 역전파라 하기도 한다.

위 예시에서는 노드(1,1)의 보상 누적값과 방문 횟수는 1로, 초기 노드의 보상 누적값과 방문 횟수를 1로 업데이트 하였다. 노드 업데이트가 완료되면 항상 초기노드로 돌아가서, 다시 추정가치가 가장 높은 하위노드를 선택하고 평가하는 과정을 반복한다.

선택된 노드의 하위 노드를 전개하는 것을 확장이라 하는데 지금까지는 초기 노드의 하위 노드들은 확장되지 않았었다. 노드 방문 횟수n가 미리 정한 n에 도달하면 노드를 확장한다. 만약 노드(1,1)의 방문 횟수가 미리 정한 횟수가 되었으면 노드(1,1)의 하위 노드들을 전개한다. 국면(1,1)에서 둘 수 있는 수가 a_2,1과 a_2,2라면, 노드 (1,1)은 두개의 노드로 확장된다.

이제 다시 초기 노드로 돌아가서 초기 노드의 하위 노드인 (1,1)이 선택될 텐데, 노드(1,1)은 하위 노드가 있으므로 노드(1,1)의 하위 노드인 (2,1)과 (2,2)의 추정 가치에 따라 이 중 하나를 선택한다.

이러한 일련의 과정을 초기 노드의 방문값이 특정한 횟수에 도달할 때까지 반복한다. 모든 반복이 완료된 후 현 국면에서 어떤 수를 두어야 할 지를 결정하는데, 노드 방문 횟수가 가장 많은 수를 최선의 수로 한다.

노드 방문 횟수가 많다는 것은 해당 수를 더 깊게 들여다보았다는 것이며, 이는 그 수가 승리를 끌어낼 가능성이 더 크다는 것을 의미한다.

활용과 탐험

• 지금까지 얻어진 결과나 경험을 충분히 잘 활용하는 것도 중요하지만, 가끔은 방문해보지 않은 또는 잘 알지 못하는 노드들의 위험을 무릅쓰고 탐험해 보는 것도 중요하다.
• 탐험을 통해 지금까지 경험하지 못했던 더 큰 보상을 얻을 수도 있기 때문이다.
• 활용만 한다면 우물 안 개구리가 될 수도 있고, 탐험만 한다면 실질적 이득은 얻지 못할 수도 있다. 활용과 탐험 사이의 균형을 잘 맞추는 것은 강화학습의 중요한 요소 중 하나이다.

🌈마무리

저번 주차에는 미니맥스 알고리즘에 대해 학습했고, 이번에는 몬테 카를로 탐색 트리에 대해서 학습하였다. 인공지능의 강화 학습을 위한 아주 기본적인 알고리즘들을 학습한 것 같은데 개인적으로 이런 기본적인 알고리즘들도 쉽지는 않다고 느껴졌다. 특히 알고리즘이 어떻게 흘러가는지 알게 되더라도 이것을 구현하는 것은 또다른 어려움이라고 느껴졌다. 이런 어려움을 이겨내기 위해서라도 열심히 공부해야겠다고 느껴졌다. 화이팅해보자:)

이번 주차 스터디는 미니맥스 알고리즘에 대해 학습하였습니다. 이제 본격적으로 인공지능의 알고리즘에 대해 공부하게 되었군요. 이번주차 부터 인공지능 알고리즘에 대해 학습을 하게 될 것 같습니다. 그리고 가장 처음으로 배우는 알고리즘이 미니맥스 알고리즘입니다.

🕹️미니맥스 알고리즘이란

미니맥스(Minimax) 알고리즘은 게임 이론과 인공지능 분야에서 널리 사용되는 알고리즘으로, 2인 완전정보 턴제 게임(예: 틱택토, 체스, 오델로 등)에서 최적의 수를 선택하기 위해 사용된다. 즉, 두 참여자가 교대로 어떤 결정을 해가면서 진행되는 과정 등에서, 종료시점까지의 모든 과정을 내다보고 현시점에서 어떤 결정이 최선인지를 알아내는 알고리즘이다. 참여자의 선택에 무작위성이 개입하지 않고 모든 정보가 서로에게 공개되는 과정에 적합하다.

바둑을 예로 들면 내가 두는 수를 I라 하고 상대가 두는 수를 O라고 하면 시점 t에서 내가 선택할 수 있는 수들 I_t들 중 최선의 수 I_t^*를 둬야 한다. 이때 모든 I_t를 평가하여 가장 점수가 높은 수(가장 나에게 유리한 수)를 고르면 될 것이다. 그런데, 이것은 근시안적이다.

한 수 앞 보기

한 수 앞, 즉 t+1의 시점에서 보는 것이다. 상대도 역시 상대가 둘 수 있는 모든 수 O_t+1들 중 최선의 수를 찾아 두려고 할 것이기 때문에 I_t에서 O_t+1^*를 고려해서 나의 I_t^*를 결정하겠다는 것이다. 시점 t에서 당장 나에게 큰 유리함을 주는 수라 할지라도 O_t+1^*에 철저히 무력화 되어 오히려 상대에게 큰 유리함을 주는 악수로 봐야한다.

즉, 우리는 우리가 수를 두면 그 수에 대한 상대의 가장 강력한 대응을 고려하여 최대한 무력화 당하고 난 다음의 점수를 I_t의 점수로 봐야 한다. 그러니 점수는 상대가 가하는 무력화를 최대한 당한 다음의 점수이므로 그 수를 두었을 때 내가 얻을 수 있는 점수의 최소값이 된다.

두 수 앞 보기

그렇다면 한 수 앞 상대의 수 O_t+1는 어떻게 평가해야 할까? 상대도 나와 같은 생각을 할 것이라고 보면 된다. 즉, 상대는 t+2시점에서 내가 상대에게 가하는 무력화를 최소화 하는 수를 찾으려 할 것이다. 그런데 이는 상대 입장에서 최소화이지만 나의 입장에서는 최대화이므로 O_t+1^*를 무력화하는 수 I_t+2^*까지 고려해서 최선의 수를 I_t^*로 하겠다는 것이다.

종료 시점까지 보기

이 방식으로 종료시점까지 반복하면 된다. 이것을 트리로 나타낼 수 있는데 최소화는 역삼각형으로, 최대화는 정삼각형으로 나타내면 된다. 이 같은 트리를 게임 트리라고 한다.

이 트리의 말단노드에는 구체적인 숫자 형태의 점수가 입력된다. 승리는 +1, 패배는 -1, 무승부는 0으로 할 수 있다. 그리고 트리의 깊이는 바둑의 경우 361, 틱택토는 9가 된다.

*이 구조를 보면 알 수 있다시피 수 읽기 깊이가 깊어질 수록 계산해야 하는 경우의 수들이 급격히 증가한다는 단점을 가진다. *

🖥️알고리즘 구현

가장 기본적인 방법

구조를 보면 알다시피 같은 알고리즘이 반복된다 봐도 된다. 이는 재귀를 이용하여 구현을 하면 편하다. 참고로 파이썬에서 재귀의 깊이는 1024까지로 제한된다.

틱택토용 미니맥스 함수

def get_minimax_score(state, player_type, terminal_score=1, minimizer=True):
    if state.check_if_win(player_type):
        return terminal_score

    elif state.check_if_win(-player_type):
        return -terminal_xcore

    elif state.check_if_game_finished():
        return 0

    else:
        if minimizer==True:
            minimax_score = np.inf
            legal_actions = state.get_legal_actions()

            for action in legal_zctions:
                next_state = state.get_next_state_from_action(action,-player_type)
                score = get_minimax_score( next_state, -player_type
                        , -terminal_score, minimizer=False)

                if score < minimax_score:
                    minimax_score = score

        if minimizer==False:
            minimax_score = -np.inf
            legal_actions = state.get_legal_actions()

            for action in legal_actions:

                next_state = state.get_next_state_from_action(action, -player_type)
                score = get_minimax_score(next_state, -player_type,-terminal_score
                        , minimizer=True)

                if score > minimax_score:
                    minimax_score = score

          return minimax_score

여기서 -부호가 끼여 있는 것은 최대값과 최소값을 구분해야 되기 때문이다(다음 수는 상대방이 둔다는 것을 알리기 위해). 5장에서 작성한 State 클래스의 state 인스턴스와 함수를 호출한 대국자가 선수[+1]인지 후수[-1]인지를 player_type으로 입력받도록 한다.

알파-베타 가지치기 알고리즘

미니맥스 알고리즘은 트리의 깊이가 증가함에 따라 탐색 공간의 크기가 급격히 증가하기 때문에 틱택토보다 복잡도가 조금만 더 증가하더라도 실질적인 목적으로 사용하기가 힘들다. 그래서 이에 대한 개선 방안 중의 하나인 알파-베타 가지치기 알고리즘이 있다. 이는 불필요한 계산을 하지 않게 함으로써 미니맥스 알고리즘의 계산 시간을 줄이는 방법이다.

예를 들면 최대화 함수 d는 말단 노드 값들 중 순서대로 본후 그 위의 노드로 큰 값을 결정할 것이다. 마찬가지로 그 옆 노드인 최대화 함수 e도 큰 값을 결정할 것인데 이들의 상위노드인 최소화 함수 b는 이들중 최소값을 결정할 것이다. 즉, d에서 결정한 값이 있으면 그 옆노드이며 상위노드가 같은 e에서 d에서 결정한 값보다 큰값이 하나라도 나오면 더 이상 e를 탐색할 필요가 없는 것이다. 즉 더 큰값이 나오면 e는 탐색을 종료한다. 이렇게 더 큰 값이 나와 e의 탐색을 종료하는 것을 베타 절단 이라고 한다.

반대로 최대화 함수와 최소화 함수가 바껴 더 작은 값이 나오면 탐색을 할 필요가 없을 텐데 이때 더 작은 값이 나오면 탐색을 종료하는 것을 알파 절단이라한다.

이러한 방식으로 게임 트리의 불필요한 부분들을 제거하는 것을 알파-베타 가지치기라 한다.

알파-베타 가지치기 알고리즘의 구현은 간단하다. get_minimax_score에 알파절단과 베타절단에 대한 부분만 추가하면 된다.

😀마무리

이렇게 스터디를 진행하며 가장 처음으로 인공지능 알고리즘을 학습했고 그것은 미니맥스 알고리즘이였다. 하면서 느낀점은 개념적인 부분은 이해가 된다. 하지만 파이썬에 미숙해서 그런지 구현은 쉽지 않다고 느꼈다. 아직은 학기 중이니 방학때 파이썬 공부를 열심히 해야겠다고 느꼈다. 이번주부터 기말시험기간이다.. 사실 이미 시험하나는 치뤘다. 점수는 어떻게 될지 모르겠지만..

나도 아래 커비 사진처럼 아무것도 안하고 아무 걱정없이 먹고 자고 놀기만 하고 싶다.... 나머지 시험도 열심히 공부하러 가야겠다. 다들 화이팅:)

🙌서론

이번 주차 내용은 상태와 행동입니다. 교재의 예제로는 n목이 있습니다. 사실 저번주차에 이번 주차 내용의 단원 명만 봤을 때 이제 강화학습의 무언갈 배우겠구나 라고 생각했지만 학습하다보니 저번주차 처럼 예제 하나를 가지고 알고리즘 공부를 하는 느낌이긴 했습니다. 그래도 교재순서대로 차근차근 학습해 보겠습니다.

🤔상태와 행동

사실 단어 그대로 의미를 유추하는 것이 편하긴 하겠습니다. 교재에 적혀있는 것 그대로(교재에는 오목을 예시로 말했습니다) 말하자면 아래와 같이 정의 가능합니다.

상태 : 바둑판 위에 흑백의 돌들이 놓인 국면 행동 : 참여자가 두는 수

✨N목 환경

우선 이번 주차 스터디에서는 다음과 같은 모듈/패키지를 이용했습니다.

import numpy as np
import time

환경은 다음과 같이 설정했습니다.

• 흑돌과 백돌은 각각 +1/-1
• 돌을 놓지 않은 곳은 0으로 표현

따라서 초기 상태의 보드는 np.zeros(shape, dtype=int)이고 shape는 틱택토는 (3,3), 오목은 (9,9) 등입니다.

유저 인터페이스는 GUI, CUI가 있지만 여기서는 CUI를 이용하겠습니다.

가능한 착수점

돌이 두어지지 않은 곳을 0으로 나타내므로 board에서 0인 요소들의 인덱스를 반환하면 됩니다.

def get_legal_actions(board):
    zero_idx = np.where(board == 0)
    legal_actions = list(zip(zero_idx[0], zero_idx[1]))
    return legal_actions

위 함수는 0인 요소들의 인덱스를 반환하는 함수입니다. np.where로 0인 곳의 인덱스를 찾고 행과 열이 따로 반환된 이것을 zip을 이용하여 (행, 열) 형태의 튜플로 묶고 그것을 리스트에 담아 반환합니다.

승리 판단

승리는 n개의 돌이 가로/세로/대각선 방향으로 연달아 나오면 됩니다. 즉 -1/+1 이 n개가 연달아 있는지 여부로 판단하면 됩니다.

가장 간단한 방법은 길이가 n인 창을 한칸씩 이동시키면서 창안에 보이는 모든 요소들이 +1이나 -1 인지 확인하면 됩니다. 이와 같은 기법을 활주창기법이라고 합니다. 다른 방법으로는 창안의 요소들의 합이 +5인지 -5인지 확인하면 됩니다. 아래의 코드와 같이 작성가능합니다.

n_connects = 5

board_1d = np.zeros(10000, dtype=int)
board_1d[-n_connects:] = 1
win_mark = np.ones(n_connects)

for i in range(len(board_1d) - (n_connects-1)):
    window = board_1d[i:i+5]
    if (window==win_mark).all():
        print("WIN")

대각선 방향은 조금 까다롭습니다. 대각선은 두가지 방향이 있는데 하나는 왼쪽위에서 오른쪽 아래로, 다른 하나는 오른쪽 위에서 왼쪽 아래로 향하는 방향이 있습니다.

주어진 배열은 np.diag로 얻을 수 있는데, 정 중앙의 주대각선에서 몇칸 떨어져 있는 대각선에 대해서인지는 인자 k[+는 위쪽, -는 아래쪽]로 지정가능합니다. 아래의 코드와 같이 작성가능합니다.

delta_row = n_rows - n_conn
delta_col = n_cols - n_conn

# diagonal forward (up left to down right)
for k in range(-delta_row, delta_col+1):
    l = list(np.diag(board, k))
    result = check_n_mok_in_list(l, player_type, n_conn)
    if result == True:
        break

# diagonal backward (up right to down left)
for k in range(-delta_col, delta_row+1):
    l = list(np.diag(upside_down_board, k))
    result - check_n_mok_in_list(l, player_type, n_conn)
    if result == True:
        break

게임종료/무승부 판단

돌을 더 둘 곳이 있는지 판단하면 됩니다. 돌이 놓이지 않은 곳이 0이므로 board의 모든 요소들을 곱한 값이 0인지 확인하면 됩니다.

def check_if_game_finishied(board):
    if board.prod() == 0:
        return False
    else:
        return True

🧙‍♀️ 대국자

인간 대국자

인간 대국자의 수는 보드의 행과 열의 인덱스를 요소로 하는 튜플로 입력받습니다.

def human(state):
    legal_actions = state.get_legal_actions()
    while True:
        action = input("input player action (e.g., '0,0'): ")
        if "," in action:
            action = tuple(int(float(x)) for x in action.split(","))
            if action in legal_actions:
                break
            else:
                print('invalid format")
        return action

오타 또는 착수 불가는한 수가 입력되는 것을 방지하기 위하여, 착수가 가능한 수가 입력되기 전까지는 "invalid format"을 출력하고 while루프가 반복되도록 합니다.

무작위적인 수를 두는 인공지능

착수 가능한 수 중에서 아무 수나 무작위적을 선택하여 대국하는 대국자를 구현한 함수입니다.

def AI-random(state):
    legal_actions = state.get_legal_actions()
    random_idx = np.random.randint(low=0, high=len(legal_actions))
    action = legal_actions[random_idx]
    return action

😀마무리

이번 주차 스터디도 이렇게 마무리되었습니다. 사실 하다보니 저번 주차처럼 인공지능 보다는 파이썬과 numpy에 익숙해지고 이것들을 이용해서 간단한(?) 알고리즘을 작성해 본 것 같습니다. 확연히 np.random만 사용한 저번주차 보다 numpy를 더 다양하게 이용해 본 것 같긴 합니다.

코드들을 보고 작성해보면서 느낀 것인데 생각보다 파이썬도 복잡하게 코드가 작성할 수 있겠구나 싶었습니다. 아니면 실제로 복잡한 것이 아닌데 제 실력이 부족해서일 수도 있고 혹은 정말 이 교재의 코드가 쓸데없이 복잡한 것일 수도 있을 것입니다. 아무튼 방학때 파이썬도 조금 더 공부해야 겠다고 느꼈습니다.

벌써 6월 입니다. 그리고 시험이 다가오는군요..😱😱 그만큼 종강이 별로 안남았다는 뜻이니 저도 화이팅하고 이글을 보는 모든 분들도 화이팅입니다!!

🙌서론

이번 주차 스터디는 간단히 요약해서 말하면 저번주차까지 배운 파이썬과 넘파이를 알고리즘을 통해 복습해본다는 느낌이 강합니다. 실제로 교재에서도 무언갈 새로이 배우기 보다는 숫자야구라는 예시를 통해 파이썬, 넘파이를 활용해 알고리즘을 짜보는 느낌이 강합니다. 그래서 저도 이번 주차 스터디는 이때까지 배운 파이썬과 간단한 넘파이를 복습하고 총정리 한다는 느낌으로 학습해보았습니다.

참고로 제목이 피동적 알고리즘인 이유는 교재의 필자가 다음과 같이 적어놨다. 필자가 고안한 해법에 따라서만 답을 찾아간다는 점에서 이 장의 제목은 피동적 알고리즘이라 하였다.

🧢숫자 야구

교재에선 이번 주차 내용 통채로 숫자야구라는 것을 파이썬, 넘파이를 이용해 작성하고 설명하는 내용으로만 이루어져 있습니다.

숫자야구란?

'숫자야구'라고 그냥 들으면 무엇인지 감이 안오실 수도 있는데 규칙을 들으면 아? 하고 생각나실 수 있을 겁니다. 아마 다들 한번씩 해봤을 겁니다(저도 기억속에서 초딩때 해본게 떠오르네요..ㅎㅎ).

각자 3/4자리의 숫자를 임의로 정한 뒤, 서로에게 3/4자리의 숫자를 불러서 결과를 확인한다. 
그리고 그 결과를 토대로 상대가 적은 숫자를 예상한 뒤 맞힌다.
사용되는 숫자는 0에서 9까지 서로 다른 숫자이다. 
경우에 따라 0은 사용하지 않기도 하며 0이 첫번째 숫자로 올 수 없게하는 룰도 있다.

1. 숫자는 맞지만 위치가 틀렸을 때는 BALL.

2. 숫자와 위치가 전부 맞으면 STRIKE.
(물론 무엇이 BALL이고 STRIKE인지는 알려주지 않는다.)

3. 숫자와 위치가 전부 틀리면 OUT. 

- 두 숫자가 중복되면 경우의 수가 많아져서 그런지 중복 숫자는 잘 사용하지 않는다.

저희가 학습할 코드는 정답 숫자를 3자리로 하고 0은 포함하지 않은 1~9까지 숫자로 합니다. 또한 숫자 중복도 없다고 하겠습니다.

또한 코드를 짜기전 사용할 패키지는 다음과 같습니다. import numpy as np

응답자 코드

우선 컴퓨터가 응답자 역할을 하는 코드를 작성해 보겠습니다. (응답자라 함은 컴퓨터가 숫자 3개를 정하고 문제를 만들었다 생각하면 됩니다. 즉 컴퓨터가 스트라이크가 몇개인지, 볼이 몇개인지 등을 알려줍니다.)

rsp_nums = [i for i in range(1, 10)]
rsp_nums = np.random.choice(rsp_nums, size = 3, replace = False)

우선 위 코드는 컴퓨터 응답자가 사용할 숫자를 무작위적으로 생성하는 코드입니다.

1부터 9까지의 정수 아홉개가 포함된 리스트 rsp_nums를 생성한 다음, np.random.choice를 사용해서 rsp_nums에 포함된 숫자 중에서 세개의 숫자를 중복이 없도록 무작위적으로 선택하도록 한 후 반환되는 배열 객체에 rsp_nums를 다시 붙여 만들었습니다.

다음 아래 코드는 rsp_nums배열과 해결자(문제를 해결할 사람)가 추측한 세 개의 숫자가 담긴 guess 리스트를 입력받고 응답하는 함수입니다.

def get_response_from_guess(rsp_nums, guess):
    n_stk = 0
    n_bll = 0
    for i in range(3):
        if guess[i] == rsp_nums[i]:
            n_stk += 1
        elif guess[i] in rsp_nums:
            n_bll += 1
        else:
            pass
    respose = (n_stk, n_bll)
    return response

n_stk와 n_bll은 각각 스트라이크와 볼의 개수이고 rsp_nums와 guess를 각각 if문을 통해 비교해가며 스트라이크와 볼의 개수를 증가시켜 반환하면 됩니다.

class Responder():

    def __init__(self):
        self.rsp_nums = np.random.choice(
        [i for i in range(1, 10), size = 3, replace = False)

    def get_response_from_guess(rsp_nums, guess):
        n_stk = 0
        n_bll = 0

        for i in range(3):
            if guess[i] == rsp_nums[i]:
                n_stk += 1
                elif guess[i] in rsp_nums:
                    n_bll += 1
            else:
                pass

        respose = (n_stk, n_bll)

        return response

마지막으로 입력을 받아 guess를 생성하는 코드를 만들어보겠습니다.

while True:
    guess = input("Guess:")
    if len(guess) == 3 and len(set(guess))==3:
        break
guess = [int(item) for item in guess]

눈 여겨 볼 구간은 len(set(guess)) == 3 이부분입니다. 저희는 중복숫자를 받지 않기로 하였기에 set을 이용한 것입니다. (집합은 중복숫자를 count하지 않기 때문이죠)

이렇게 응답자 코드를 짜보았습니다.

해결자 코드

해결자는 응답자와 반대로 문제를 맞추는 경우라고 보면 됩니다. 즉 guess를 입력하고 결과로 알게되는 (num_str, num_bll)을 통해 답을 추론하는 알고리즘이죠. 일종의 탐색 알고리즘이며 결과를 8개로 구분이 가능하므로 브루타포스 알고리즘이라 보셔도 됩니다.

나올 수 있는 경우는 3S0B, 0S3B, 1S2B, 1S0B, 0S1B, 2S0B, 1S1B, 0S2B 입니다. (S는 스트라이크 개수, B은 볼의 개수 입니다.)

해결자 코드는 아래와 같이 작성 가능합니다.

numbers = [i for i in range(1, 10)]

while True:
    init_guess = np.random.choice(nubers, size = 3, replace = False)

    nubers.remove(init_guess[0])
    nubers.remove(init_guess[1])
    nubers.remove(init_guess[2])

    pirnt("guess:", "".join([str(n) for n in init_guess]))

    #human input
    n_stk = int(input("n strikes:"))
    n_bll = int(input("n balls :"))
    response = (n_stk, n_bll)

    if response == (3, 0) or reponse != (0, 0):
        break

    if response == (0, 3):
        guesser = Guesser_0S3B(init_guess)

    if response == (1, 2):
        guesser = Guesser_0S3B(init_guess)

    if response == (1, 0):
        guesser = Guesser_0S3B(init_guess)

    if response == (0, 1):
        guesser = Guesser_0S3B(init_guess)

    if response == (2, 0):
        guesser = Guesser_0S3B(init_guess)

    if response == (1, 1):
        guesser = Guesser_0S3B(init_guess)

    if response == (0, 2):
        guesser = Guesser_0S3B(init_guess)

1부터 9까지의 숫자중 3개를 골라 guess로 정하고 원래 1부터 9까지가 있는 number에서 guess로 고른 것들을 삭제합니다.

그 후 경우에 따라 나눠서 클래스를 실행시킵니다. 만약 (3, 0)인 경우 정답을 맞춘 것이기에 추측을 하지 않고 break를 통해 그만둡니다. (0, 0)인 경우 남은 number 중 다시 guess를 생성하여 탐색합니다.

위 예시를 통해 해결자 클래스를 작성 가능합니다. 코드가 거의 같고 길이가 길기에 코드는 생략하겠습니다.

추측기 클래스

추측기 클래스는 위 해결자 코드에서 guesser로 받는 클래스들이라 보시면 됩니다. 즉, 경우에 따라 추측기 클래스를 다르게 하여 정답 숫자를 추측을 하게 됩니다.

(3, 0)과 (0, 0)은 이 추측기 클래스가 필요 없으므로 이것들을 제외한 7개의 추측기 클래스가 있는데 전부 방법은 같기 때문에 2가지 경우만 코드를 통해 확인하겠습니다.

Guesser_0S3B 클래스

추측한 숫자가 abc라 하면 이 a, b, c 세개의 숫자 모두 정답 숫자이지만 자리만 전부 틀린 경우입니다. 즉 최대 다섯번의 시도로 정답을 찾을 수 있습니다.

코드는 다음과 같습니다.

class Guesser_0S3B():

    def __init__(self, init_guess):
        self.init_guess = init_guess
        self.branch_id = 1

    def make_guess(self, response = None):
        [a,b,c] = [self.init_guess[0],self.init_guess[1],self.init_guess[2])

        if self.branch_id == 1: next_guess = [a,c,b]
        if self.branch_id == 2: next_guess = [b,a,c]
        if self.branch_id == 3: next_guess = [c,a,b]
        if self.branch_id == 4: next_guess = [b,c,a]
        if self.branch_id == 5: next_guess = [c,b,a]

        self.branch_id += 1

        return next_guess

acb, bac, cab, bca, cba 순으로 최대 다섯번의 시도로 정답을 찾을 수 있다. branch_id로 추측과정을 기억하도록 하였다.

Guesser_2S0B 클래스

두 개의 숫자가 정답 숫자이며 자리까지 맞는 경우입니다.

위 표와 같이 경우가 나올 수 있는데 표를 해석하자면 위 첫째 줄은 ab, ac, bc가 정답 숫자일 경우를 뜻합니다. 그리고 왼쪽 경우들이 자리를 바꿨을 경우이고요.

즉 처음에 b와 c의 자리를 바꿨는데 0S2B가 되면 b와 c가 정답숫자입니다. 그 외에는 a, b 혹은 a, c이고요. 그후 cba순으로 guess로 하여 1S1B인 경우 a와 b가, 0S2B인 경우 a와 c가 정답 숫자입니다.

이걸 토대로 아래처럼 코드를 작성할 수 있습니다.

class Guesser_2S0B():
    def __init__(self, numbers, init_guess):
        self.numbers = numbers
        self.init_guess = init_guess
        self.branch_id = 1

    def make_guess(self, response=None):
        [a,b,c] = [self.init_guess[0],self.init_guess[1],slef.init_guess[2]]

        if self.branch_id == 1:
            next_guess[a,c,b]
            self.branch_id = 2
            return next_guess

        if self.branch_id == 2 and response == (0,2):
            self.branch_id = "xbc"

        if self.branch_id == 2 and response == (1,1):
             next_guess = [c,b,a]
             self.branch_id = 21
             return next_guess

         #--------------------------------------------

         if self.branch_id == 21 and response == (1,1):
             self.branch_id == "abx"

         if self.branch_id == 21 and response == (0,2):
             self.branch_id == "axc"

         #--------------------------------------------

         if self.branch_id == "xbc":
             x = self.numbers.pop()
            next_guess = [x,b,c]
            return next_guess

        if self.branch_id == "abx":
             x = self.numbers.pop()
            next_guess = [a,b,x]
            return next_guess

        if self.branch_id == "axc":
             x = self.numbers.pop()
            next_guess = [a,x,c]
            return next_guess

위 두 경우를 제외하고도 이와 같이 코드를 작성하면 됩니다.

🌈색 조합 맞추기 게임

위 예시와 비슷하게 색 조합 맞추기 게임 코드를 작성할 수도 있습니다.

   import numpy as np
from itertools import permutations

# 색상 후보
COLORS = ["red", "blue", "green", "yellow", "purple", "orange"]

# 사용자 입력
def get_secret_color_combination():
    while True:
        user_input = input(f"비밀 색 조합 3개를 입력하세요 (예: red blue green): ").split()
        if len(user_input) == 3 and len(set(user_input)) == 3 
        and all(c in COLORS for c in user_input):
            return user_input
        print("입력이 잘못되었습니다. 가능한 색상:", COLORS)

# 피드백 함수
def get_feedback(guess, answer):
    exact = sum([g == a for g, a in zip(guess, answer)])
    partial = sum([(g in answer) and (g != answer[i]) for i, g in enumerate(guess)])
    return exact, partial

# 추측 클래스
class ColorGuesser:
    def __init__(self):
        self.candidates = list(permutations(COLORS, 3))
        self.prev_guess = None
        self.first_guess_done = False

    def make_guess(self, feedback=None):
        if not self.first_guess_done:
            # 첫 추측은 np.random.choice로 무작위로 뽑기
            self.prev_guess = list(np.random.choice(COLORS, size=3, replace=False))
            self.first_guess_done = True
            return self.prev_guess
        else:
            # 이전 피드백과 일치하는 후보만 남기고 무작위 선택
            self.candidates = [
                c for c in self.candidates
                if get_feedback(list(c), self.prev_guess) == feedback
            ]
            if not self.candidates:
                raise ValueError("후보가 없습니다. 입력이 잘못되었을 수 있습니다.")
            idx = np.random.choice(len(self.candidates))
            self.prev_guess = list(self.candidates[idx])
            return self.prev_guess

# 게임 실행
def play_color_game():
    print("색 조합 추측 게임 - 컴퓨터가 맞춥니다!")
    secret = get_secret_color_combination()
    guesser = ColorGuesser()

    attempts = 0
    feedback = None

    while True:
        guess = guesser.make_guess(feedback)
        attempts += 1
        print(f"[{attempts}] 컴퓨터 추측: {guess}")

        feedback = get_feedback(guess, secret)
        print(f" → 정확: {feedback[0]}개, 색만 맞음: {feedback[1]}개")

        if feedback[0] == 3:
            print(f"\n 컴퓨터가 {attempts}번 만에 비밀 색 조합을 맞췄습니다!")
            break

# 실행
if __name__ == "__main__":
    play_color_game()

😊마무리

이때까지 배운 python과 numpy의 np.random을 이용하여 숫자야구 코드를 작성 가능하였습니다. 또한 비슷한 예제인 색 조합 맞추기 게임 또한 코드로 작성하였습니다. (색 조합 맞추기 게임은 교재에 없는 예제) 사실 여기서 numpy는 거의 안 쓰였기에 사실상 python으로 알고리즘 공부를 하였다고 봐도 될 듯 합니다.

지금까지 교재를 4장까지 하였습니다. 스터디를 1주차당 한 장씩 나가고 있으므로 당연하긴 합니다.

다음에 공부할 5장은 상태와 행동이라는 단원입니다. 6장과 7장은 각각 미니맥스와 몬테카를로 트리 탐색법에 대해 학습을 할 것인데 5장은 이에 기초가 되는 상태와 행동에 따른 상태의 변화를 알려줄 상태 클래스에 대해 학습할 것 같습니다.

이제부터 인공지능의 학습에 관한 알고리즘을 자세히 학습하게 될 것 같습니다. 내용도 점점 어려워 질것 같으니 열심히 해보아야 겠습니다. 요즘 날씨가 더워지고 있는데 이 글을 보시는 분들 모두 시원한 여름 되셨으면 좋겠습니다!

_ 번외로 메타몽 귀엽지 않나요? 메타몽은 사랑입니다💜_

저번주 스터디까지는 파이썬에 대해서 학습했습니다. 이젠 파이썬의 기능을 확장시켜 주는 패키지 중 하나인 넘파이를 학습합니다. 파이썬은 어느정도 지식이 있는 상태로 학습했지만 넘파이부터는 저도 처음인 부분이라 열심히 머리에 집어넣으려고 노력했습니다. 물론 쉽지는 않았습니다만 넘파이도 일종의 언어를 학습한다는 느낌으로 학습하니 어렵지는 않았던 것 같습니다.

▶️넘파이란

넘파이는 다차원 배열의 관리나 연산에 특화된 패키지입니다. 물론 기본적으로 파이썬에서도 리스트나 튜플등을 통해 배열관련 자료구조를 제공하지만, 대용량 또는 깊은 배열을 다루기에 불편하고 속도도 느리다는 단점이 있습니다. 넘파이는 이러한 단점을 상쇄시켜 줍니다.

넘파이는 관례적으로 np라는 이름으로 불러옵니다. 불러오는 방법은 다음과 같습니다. import numpy as np 위처럼 import를 통해 불러오면 됩니다.

🔑ndarray

ndarray란 : 넘파이에 존재하는 배열 자료형입니다. 쉽게 말하면 다차원 배열 객체라고 보면 됩니다. 파이썬의 기본 자료구조인 리스트와 비슷하지만 차이가 있습니다.

이 외에도 리스트보다 훨씬 빠르고 과학 계산이나 데이터 분석에 적합하다.

1. ndarray 생성하기

• array 함수를 이용하면 됩니다.
• array 함수는 리스트나 튜플을 ndarray로 바꿔줍니다. v=np.array([60,175,28], float)

위와 같으면 [60, 175, 28]을 요소들의 자료형을 float로 하여 ndarray를 생성하는 것입니다.

요소들의 데이터 타입을 알 수 있는 dtype함수를 사용하면

print(v.dtype)
>>>float64

위와 같이 float자료형이 나옵니다.

특별한 ndarray도 생성할 수 있습니다.

• np.zeros(size) : size 크기의 0으로만 이루어진 배열을 생성합니다. size = (2,3)이면 2행 3열인 2차원 크기의 0으로 이루어진 배열을 생성하는거죠.

• np.ones(size) : size 크기의 1으로만 이루어진 배열을 생성합니다.

• np.full(size, num, dtype = type) : size 크기의 type자료형의 num으로만 이루어진 배열을 생성합니다.

• np.empty(size, dtype = type) : size 크기의 type자료형들의 난수로 이루어진 배열을 생성합니다. 비어있는 배열이 아닌 난수로 요소가 채워집니다.

• 이 외에도 위 각각의 함수뒤 _like를 붙이면 size 대신 ndarray 객체가 들어가고 그 객체의 size만큼의 배열이 생성됩니다. 예를 들면 print(np.zeros_like(a)) #a는 (3,3)size배열을 실행하면 (3,3)크기의 0으로만 이루어진 2차원 배열이 출력될 것입니다.

• 추가로 np.diag(대각행렬), np.identity(항등행렬)이 있습니다.

  import numpy as np
  

d = np.array([1,2,3]) print(np.diag(d)) print(np.identity(3))

각각 아래와 같이 결과가 나올 겁니다.

[[1 0 0] [0 2 0] [0 0 3]]

[[1. 0. 0.] [0. 1. 0.] [0. 0. 1.]]

 diag는 그 뒤의 객체로 대각요소들을 구성하는 1차원 배열을 받고 
 identity는 항등행렬의 크기를 지정해 줍니다(항등행렬은 정사각행렬이기 때문에 수 하나만 넣으면 된다).

### 2. 축이란
축이란(axis) : ndarray의 단위라고 알면됩니다. ndarray는 행, 열, 높이가 아닌 축을 단위로 씁니다.

1차원에선 그 자체가 0번 축,
2차원에선 행이 0번 축, 열이 1번 축
3차원에선 높이가 0번 축, 행이 1번 축, 열이 2번 축
.
.
이렇게 n차원으로 확장하면 됩니다.
알기 쉽게 밑 사진을 참고합시다.
![](https://velog.velcdn.com/images/jae_red914/post/798fe041-46b3-45da-9c3e-31b852200d3e/image.png)
사진에 있는 shape메서드는 ndarray의 모양을 알려줍니다. 위 사진을 보면 ()로 둘러싸여 있는데 0번 축 부터 앞에 쓰인다고 알면 됩니다. 참고로 1차원 배열에서 ','를 빼먹지 않도록 주의합시다!

추가로 축에 대해 본인이 헷갈린 부분이 있었는데 n번축이 무엇을 의미하는지입니다. 위 예시들을 봐도 알겠지만 차원이 달라지면 n번축이 의미하는 것이 달라집니다. 2차원에선 0번 축이 행이지만 3차원에선 높이입니다.

이걸 알기 쉬운 방법은 상위배열이 몇개인지를 확인하는 것입니다. 위의 2차원 배열을 예로 들면 2차원 배열 안에 1차원 배열들이 있으므로 2차원 배열은 상위배열이 없습니다. 그러므로 0번 축입니다. 반대로 1차원 배열은 2차원 배열 하나라는 상위배열이 있으므로 1번 축입니다.

그리고 축의 방향은 그걸 확장하는 방향이라 생각하면 됩니다. 2차원배열을 확장하기 위해서는 1차원 배열을 추가해야 하는데 그 방향이 행입니다. 그래서 행방향이 0번축이라 생각하면 됩니다.

또 다른 알기 쉬운 방법은 가장 껍데기 배열을 0번 축이라 생각하면 됩니다. 위 2차원 배열을 예로 들면 [[1 2 3 4], [5 6 7 8]] 으로 표기되는데 가장 껍데기 대괄호가 가리키는 것이 0번 축이고 그다음 대괄호가 1번 축.. 이런식으로 생각하면 됩니다. 방향은 위와 동일한 방법으로 생각하면 됩니다.

### 3. 채널 처음 표기법 vs 채널 마지막 표기법
둘 다 이미지나 텐서 데이터를 다룰 때의 데이터 배열 형식을 의미합니다. 다만 표기방식의 순서가 다른 것 뿐입니다.

채널 처음 표기법(Channels first)는 HWC 혹은 NHWC로 표시되고 
채널 마지막 표기법은(Channels last) CHW 혹은 NCHW로 표시됩니다.

각각의 영어 대문자는 아래 표와 같이 의미합니다.

|글자|의미|
|---|----|
|N|Batch(크기)|
|H|Height(높이)|
|W|Width(넓이)|
|C|Channel(채널)|


Channels last 메모리 형식(memory format)은 차원 순서를 유지하면서 메모리 상의 NCHW 텐서(tensor)를 정렬하는 방식이라 생각하시면 되고 Channels first는 원래 배열을 표기하던 방식 그대로 표현했다고 생각하시면 됩니다.

혹여나 배열을 텐서플로나 파이토치 같은 프레임워크에 옮긴다면 NHWC나 NCHW같은 정해진 표기법으로 넘겨야 할 수 도 있습니다.

### 4. 배열 관련 메소드들
1. shape : 위에서 설명했으니 가볍게 넘어가겠습니다. 배열의 모양을 반환한다고 아시면 됩니다.

2. ndim : 차원의 수를 알려줍니다.
3. size : 요소들의 수를 알려줍니다.
4. dtype : 요소들의 데이터 타입을 알려줍니다.
5. astype : dtype의 속성을 변경합니다.
6. ravel : 다차원 배열을 일차원 배열로 평평하게 만듭니다.
7. reshape : 배열의 형태를 변경할 수 있습니다. 형태를 지정할때 '-1'로 지정하면 배열의 형태를 자동으로 결정하게 할 수 있습니다.
8. transpose : 행과 열을 바꿉니다(전치).
9. hstack, vstack : 각각 수평쌓기와 수직쌓기 입니다. 
10. column_stack : 수평쌓기 입니다. 위 hstack과의 차이점은 넘파이의 벡터가 행벡터이므로, 벡터를 수평으로 연결할때 더 유용합니다.
11. concatenate : vstack, hstack과 동일한 기능이지만 축을 지정할 수 있기 때문에 3차원 이상의 배열부터 유용성이 있습니다.
12. linspace : 요소를 등간격으로 나눕니다. 
예를 들어 `a = np.linspace(start = 0, stop =1, num = 101`이면 0부터 1까지를 101조각으로 나누어 a에 배열로 저장합니다. 이는 함수를 그릴때 유용하게 이용할 수 있습니다.

### 5. 배열 연산
1. '+', '-', '*' : 각각의 요소들을 합, 차, 곱하여 배열을 반환합니다.

2. '@', 'dot' : 점곱(내적)을 반환합니다.

3. '**', 'power' : 앞에서 부터 제곱, n제곱을 반환합니다. 이는 요소별 제곱, n제곱을 의미합니다.
추가로 AAA = A^3과 A@A@A는 서로 다른 것이니 주의해야 합니다.

4. exp, log, log10, log2, sqrt, round : 차례대로 e의 n승, 자연로그, 밑이 10인 로그, 밑이 2인 로그, 제곱, 반올림입니다.

5. sum, mean, var, std... : 차례대로 합, 평균, 분산, 표준편차 입니다. 이외에도 많은 통계량을 나타내는 메서드들이 있습니다.

6. 이 외에도 고유값, 벡터, 역행렬 등 선형대수 관련 메서드들도 있습니다.

### 6. 인덱싱 및 요소 값 찾기
1. ndarray도 슬라이싱, 인덱싱이 가능합니다. 

2. 넘파이 객체(ndarray)도 객체이기에 다른 변수라도 같은 값을 가리키면 동시에 요소가 바뀔 수 있습니다. 그래서 이를 피하는 방법은 저번주차에서 학습하였던 깊은 복사를 이용하면 됩니다.

3. argmax, argmin : 각각의 축에서 최대값 혹은 최소값 요소의 인덱스를 반환합니다.

4. where : where 뒤에 조건이 나오고 축별로 조건을 만족하는 요소의 인덱스를 반환합니다.

### 7. 브로드캐스팅
파이썬에서는 반복문을 사용해서 전체 데이터에 연산을 적용했던 것과는 달리 연산이 전체 데이터로 확장가능 합니다. 위 연산에서 '+', '-', '*' 등이 그 예시입니다.
스칼라도 적용 가능합니다.
```python
import numpy as np

a = np.array([[1, 2, 3], [4, 5, 6]])
print(a+3)

위 코드를 실행하면 [4 5 6] [7 8 9]로 결과가 나올 것 입니다.

이게 가능한 이유는 하나의 형태를 다른 하나의 형태로 확장시키는 브로드캐스팅이 일어나기 때문입니다.

🔢확률적 샘플링 및 난수 발생

1. np.random.choice(bases, size = n, p = probs) : 이 메서드는 bases들의 자료를 n크기만큼의 배열로 p의 확률분포로 요소를 샘플링 합니다.

2. 위 메서드에서 bases와 probs가 아닌 low[최소값], high[최대값]을 지정하여 정수를 무작위적으로 샘플링 가능합니다. 이때 최대값은 샘플링에서 제외됩니다.

3. 이 이외에도 binomial, poisson, gamma 등 다양한 확률분포로 샘플링이 가능합니다.

4. 난수 발생의 씨앗 지정 : np.random.seed(num)을 이용합니다. 이는 재현성 등을 보기위 한 이유로 난수가 발생하는 패턴을 고정시키기 위해 사용합니다. 이를 난ㅜ 발생의 씨앗이라고 합니다.

😊마무리

이번에 넘파이를 공부하며 느꼈던 것은 넘파이도 일종의 파이썬을 확장한 것이라 새로운 언어를 학습한다는 느낌으로 공부가 된 것 같았습니다. 또한 선형대수를 많이 까먹은 제게 선형대수를 공부하라는 느낌이 확 와닿았던것 같습니다..

다음 주차부턴 본격적으로 알고리즘에 대해 공부하게 될 것 같습니다. 난이도가 이제 올라가기 시작하겠군요..

아래 사진에서 해탈한이라는 귀여운(?) 친구가 말한 것과 같이 아무리 꼼수를 부려도 실력이 향상하기 위해서는 어려움을 감당해야 겠죠. 이제부터 어려운 시간이 될 수도 있겠지만 열심히 해봐야겠습니다😸😸

황금같던 연휴가 끝났습니다.. 그동안 나태하게 지내다 다시 스터디로 돌아왔습니다.. (내 연휴 😭😭)

다시 예전의 저로 돌아오길 기원하며 글을 작성해봅니다.

이번 스터디의 범위도 저번주와 같이 파이썬입니다. 다만 저번보다 조금 더 심화 내용이죠. 한번 내용들을 정리해 보겠습니다.

🔢함수

이번에 학습하는 함수는 내장 함수가 아니라 사용자 정의 함수 입니다. 사용자가 직접 함수를 만들어 사용하는 것이죠

def f(x):
    do_something
    ...
    y = ...
    return y

함수의 구조는 위와 같습니다. 참고로 함수는 영역 구분을 들여쓰기로 합니다. 파이썬은 들여쓰기로 칸을 나누는 경우가 거의 전부라 봐도 되니 알아두시는게 사실상 필수입니다. 함수 또한 객체입니다. 함수의 이름은 f, 매개변수는 x입니다. 그리고 반환하는 값은 y입니다. 차근차근 알아봅시다.

1. 매개변수

• 위 코드에서 매개변수는 x입니다. 쉽게 정리하면 함수로 입력되는 객체를 받아들이는 역할을 하는 변수라고 생각하시면 됩니다.
• 함수에서 매개변수가 필수요소는 아닙니다. 즉, 없어도 됩니다.
• c언어나 다른 언어와 달리 매개변수의 자료형을 정해주지 않아도 됩니다. 이것은 파이썬의 특징이라 생각하시면 됩니다.
• 매개변수는 함수 안에서만 사용됩니다. 즉 함수밖의 변수와 매개변수의 이름이 같더라도 서로 다른 변수입니다. 만약 같은 이름의 변수가 생긴다면 함수 안에서는 매개변수를 더 우선합니다.

2. 반환값

• 위 코드에서는 반환값이 y입니다.
• 함수가 입력을 매개변수로 받았다면 함수가 출력을 반환값으로 한다고 생각하면 됩니다.
• 반환값은 return 뒤에 값을 작성합니다.
• 반환값도 없을 수 있습니다. 그럴 경우 return None을 작성하거나 return 구문 자체를 작성하지 않으면 됩니다.
• 반환값이 여러개일 수 있는데 return 뒤에 반환할 요소들을 ','를 이용해 분리해서 반환하면 된다. (혹시 return이 여러개면 가장 처음의 반환값만 반환하니 여러개를 반환하고 싶다면 무조건 return은 하나만 쓰고 ','로 분리해서 반환시키자)

3. 위치인수와 키워드 인수, 기본값이 설정된 매개변수

   #위치인수
   def get_difference(a, b):
     diff = a - b
    return diff
   
   #키워드 인수
   def show_data(weight, height, age):
     print(weight)
    print(height)
    print(age)
   
   show_data(age = 33, weight = 77, height = 177)
   
   #기본값이 설정된 매개변수
   def get_add(a, b, c = 0):
     add = a + b + c
    return add

   • 함수의 매개변수가 여러개일 수 있습니다.

   • 그럴때 매개변수의 순서대로 전달되는 인수를 위치인수라 합니다. 위 코드를 참고하시길 바랍니다.

   • 위치인수 뿐 아니라 매개변수의 이름을 이용하여 인수를 전달할 수 있습니다. 그걸 키워드 인수라고 합니다.

   • 키워드 인수는 순서 상관없이 인수를 전달할 수 있습니다.

   • 만약 위치인수와 키워드 인수를 섞어서 쓸려면 항상 위치인수들 다음에 키워드 인수를 두어야 합니다.

   • 위 코드와 같이 어떤 매개변수는 미리 설정된 기본값을 인수로 사용할 수 있습니다.

   • 만약 위 예시로 설명하면 get_add(10, 20)은 a = 10, b = 20, c = 0이 전달된다 생각하시면 됩니다. 비슷하게 get_add(10, 20, 30)은 a = 10, b = 20, c = 30이 전달됩니다. 즉 전달할 인수값을 비우면 자동으로 기본값이 전달된다고 생각하시면 됩니다.

   4. 언패킹과 패킹

   • 인수들을 리스트[또는 튜플]나 딕셔너리에 모아서 다수의 인수들을 받으면 그걸 함수가 언패킹 할 수 있다. 반대로 함수의 매개변수에 나열된 인수들을 받을때 함수 내부에서 이들을 리스트나 딕셔너리의 요소처럼 다룰 수 있도록 패킹한다.

   • 언패킹은 함수에 전달할때 인수들 앞에 (리스트나 튜플), *(딕셔너리)를 붙여서 전달하면 되고 패킹을 하기위한 함수를 만들때는 매개변수 앞에 , *를 각각 붙이면 된다.

   5. 이름의 범위
   • 함수같은 경우는 함수 안에서 정의된 변수나 매개변수는 오직 함수 안에서만 정의 되어 있다. 즉 함수 밖에서는 사용하지 못한다. 이러한 변수를 지역변수라고 한다.
   • 반대로 함수 밖 메인코드에서 정의되는 변수를 전역변수라고 한다. 전역 변수는 함수 안에서도 사용할 수 있다.

📓클래스

클래스는 객체지향언어를 한번이라도 써봤스면 알 것이다. 파이썬도 객체지향언어 이므로 당연히 클래스가 쓰인다. 파이썬은 사실상 모든것이 객체라 생각하면 된다. 그 객체를 생성하는 것이 클래스이고 클래스로 객체를 생성하는 것을 구체화라고 한다. 그리고 클래스로부터 생성된 객체는 클래스의 인스턴스라 한다. 처음 접하면 용어가 많아 헷갈릴수 있을 테지만 쓰다보면 금방 익숙해질 것이다.

1. 클래스의 정의와 인스턴스 생성

   class StatCal():
   
    data = [1, 2, 3]
   
      def get_avg():
      avg = sum(data)/len(data)
      return avg
   
   stat_cal = StatCal()

   • 위의 예제를 보면 클래스를 정의하고 인스턴스를 생성한 것이다.
   • 클래스의 이름은 StatCal이다. 여기서 data와 같은 것들은 클래스 내부에서 사용되는 클래스 변수이며 다른말로는 속성이라는 말을 더욱 많이 사용한다.
   • 그 아래 함수는 클래스 내부에서 정의된 함수이고 메서드라고 한다.
   • 맨 아래 줄을 보면 클래스 StatCal을 통해 인스턴스인 stat_cal을 생성한 것이다.

print(stat_cal.data), print(stat_cal.get_avg())

• 위와 같이 '.'을 이용하면 인스턴스를 통해서 그 인스턴스의 속성, 메서드를 사용이 가능하다.
• 하지만 메서드를 불러오면 오류가 날것이다. 아무것도 입력하지 않았는데 무엇인가 하나가 메서드로 전달되었다는 오류가 말이다.
• 이 오류가 발생하는 이유는 메서드를 호출하면 자동으로 클래스 자신을 메서드 함수에 전달하여 자신이 가진 데이터를 메서드 함수가 사용하게끔 하기 때문이다.
• 그래서 클래스를 정의할 때 메서드 함수에 클래스 자신을 받아줄 매개변수를 가장 처음에 설정해야 한다. 그 매개변수는 self를쓴다. 즉 클래스 내부의 메서드를 def get_avg(self): 이런식으로 고쳐야 한다

2. 초기화 함수 init\ 앞 예와 달리 서로 다른 데이터를 사용하는 인스턴스를 만들어 보자

   class StatCal():
   
     def __init__(self, name, data):
           self.name = name
         self.data = data
   
     def get_avg(self):
         avg = sum(self.data)/len(self.data)
           return avg
   
   length = StatCal("sepal", [1,2,3])
   width = StatCal("petal", [2,3,4])

   • 위 코드를 보면 인스턴스를 length, width 2개 만들고 각각 다른 요소값을 넣었다.
   • init\는 생성자라고 한다. 인스턴스 생성 시 항상 자동적으로 실행되고 메서드는 아니다.
   • 위 코드 같은 경우는 init\를 통해 인스턴스 생성 시 name과 data 속성을 입력받도록 하였다.
   • name과 data처럼 인스턴스 별로 사용되는 변수를 인스턴스 변수라 한다.
   3. 클래스의 상속 기존의 클래스에 속성과 메서드를 추가하여 새로운 클래스를 만드는 것이다.

      class Avg():
      def __init__(self, data):
           self.data = data
      def get_avg(self):
         avg = sum(self.data)/len(self.data)
           return avg
      

   class AvgTimesX(Avg): def get_avg(self, x):

       avg = sum(self.data)/len(self.data)
     avg = avg*x
     return avg

   data = [1,2,3]

   avg_x = AvgTimesX(data) print(avg_x.get_avg(3))

   `6.0`
   
   - 위의 간단한 코드를 살펴보면 AvgTimesX클래스는 Avg클래스를 상속한 것이다.
   
   ## 🖨️복사
   만약 이름 a로 어떤 리스트 객체를 가리키고 b를 a로 정의 하면 두 이름은 동일한 리스트 객체를 가리키므로, a를 통해 리스트 객체의 요소를 변경하면 b가 가리키는 리스트의 객체에서도 변경된다고 하였다.
   
   이러한 문제를 피하기 위한 간단한 방법으로 리스트의 복사 메서드를 이용하는 것이 있다.
   
   ```python
   a = [1,2,3]
   
   b = a.copy()
   b[0] = "X"
   
   print(b)
   print(a)

   ['x',2,3][1,2,3]

   • 위와 같이 복사를 하면 b가 가리키는 객체와 a가 가리키는 객체가 달라져 한쪽을 수정해도 다른 한쪽이 수정되지 않는다.
   • 다만 중첩리스트에서는 복사 메서드로 문제가 해결되지 않는다.
   • 위와 같은 복사는 얕은 복사라고 한다. 요소 객체의 요소들까지 모두 복사하려면 얕은 복사 대신 깊은 복사를 해야한다.
   • 깊은 복사는 copy 모듈을 불러와서(import copy) copy.deepcopy(a)를 통해 실시 할 수 있다.

😊마무리

이제 파이썬 문법은 마무리 했습니다(교재 상으로는). 교재 내용중 필수적이거나 나중에 잠깐 찾아봐도 될 정도의 내용들은 굳이 작성하지 않았습니다.

다음주 스터디범위는 넘파이 기초 입니다. 파이썬 까지는 제가 해본 적이 있어 거의 알고 있던 내용이였는데 넘파이 부터는 완전 처음이라 하면서 머리가 깨질 수도 있을 것 같습니다. 다만 넘파이 까지는 쉽고 그 다음부터 어려워 보이긴 하더군요..

작성일 기준 다음날이 월요일 입니다.. 네, 오지 않았으면 좋겠군요.. 이 글을 읽으신 분들은 언제 읽으셨는지 모르겠지만.. 다들 하루하루 힘내시길 바랄게요! 시간은 흐릅니다!

뭐 풀지 하며 고민하다가 그냥 제목보고 끌리는 거 골랐습니다.. 근데 대충 리스트로 풀면 되겠다 하고 하다보니 알고보니 이문제 배열 큐로 풀면 정말 쉽게 풀릴거 같더라고요.. 그렇지만 코드 적어놨는데 중간에 지우긴 뭐 해서 그냥 리스트로 풀어봤습니다. (그러지 말았어야 했는데)

📓문제

🔑코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct stacknode {
    int data;
    struct stacknode* backlink;
    struct stacknode* frontlink;
}stacknode;

typedef struct stacktype {
    stacknode* head;
    stacknode* tail;
}stacktype;

stacknode* create_node(int item) {
    stacknode* s = (stacknode*)malloc(sizeof(stacknode));
    s->data = item;
    s->backlink = NULL;
    s->frontlink = NULL;
    return s;
}

stacknode* insert_node(stacktype* stack, int data) {
    stacknode* s = create_node(data);

    if (stack->head == NULL) {
        s->backlink = s;
        s->frontlink = s;
        stack->head = s;
        stack->tail = s;
    }
    else
    {    
        s->frontlink = stack->tail;
        s->backlink = stack->head;
        stack->tail->backlink = s;
        stack->head->frontlink = s;
        stack->tail = s;

    }
    return stack->head;
}

stacknode* drowcard(stacktype* s) {
    if (s->head == s->tail) return s->head;

    stacknode* to_delete = s->head;
    stacknode* newhead = s->head->backlink;

    s->tail->backlink = newhead;
    newhead->frontlink = s->tail;

    s->head = newhead;
    free(to_delete);
    return s->head;
}

stacknode* gotodown(stacktype* s) {
    if (s->head == s->tail) return s->head;

    s->tail = s->head;
    s->head = s->head->backlink;
    return s->head;
}

int main(void) {
    int n;
    scanf("%d", &n);

    stacktype* stack = (stacktype*)malloc(sizeof(stacktype));
    stack->head = NULL;
    stack->tail = NULL;

    for (int i = 1; i <= n; i++) {
        insert_node(stack, i);
    }

    while (stack->head != stack->tail) {
        drowcard(stack);
        if (stack->head == stack->tail) break;
        gotodown(stack);
    }

    printf("%d\n", stack->head->data);
    free(stack->head);
    free(stack);
    return 0;
}

우선 사과드립니다.. next랑 prev라는 단어가 왜인지 머리에서 안 떠올라 각각 backlink, frontlink로 작성했어요.. 보시는 분들 헷갈리실 텐데 미리 죄송함돠. (사실 중간에 단어가 떠오르긴 했는데 다 고치기 뭐해서 그대로 썼슴돠)

논리적으로 어려운 문제는 전혀 아니기에 코드설명을 간단히 하자면 일단 리스트를 구현 후 tail 뒤에 삽입하는 insert_node함수, 맨 윗장 카드를 버리는 것을 구현한 drowcard함수, 맨위 카드를 맨뒤로 보내는 gotodown함수로 구현하였습니다.

사실 이중원형리스트가 아닌 단일선형리스트로 처음에 작성했었는데 시간 초과가 뜸으로써 눈물을 머금고 이중원형리스트로 재구현했습니다. 이때 리스트로 하는 것을 포기하고 큐로 표현했으면 정말 쉬울거 같은데.. 시간이 아깝긴 했습니다.

🔎여담

이게 원래 실버 4난이도 였던걸로 기억하는데 리스트로 구현하자니 생각보다 빡세더군요. 물론 문제를 해결하기 위한 논리가 어렵진 않았습니다. 구현이 빡셌습니다. 그래서 gpt에게 리스트로 풀 시 난이도를 물어보았습니다.

엄.. 어쩐지 쉽진 않던데.. gpt피셜 이정도 난이도라네요. 물론 제가 c++이 아닌 C로 풀어서 더 어렵게 느꼈을 수도 있을것 같습니다. 별 차이 없을 수도 있겠지만..

그래도 딱 제 수준인 문제인 것 같았고 복잡한 코드 구현 연습을 해본 거 같아 나쁘진 않은 경험인것 같습니다. (근데 사실 시간은 많이 아깝긴 했어요..)

이번학기부터 입부하게 된 학교 동아리, 팜시스템. 그곳에서 같은 관심분야, 배우고 싶은 분야별로 팀이 이루어졌고 그렇게 스터디 팀이 결성되었다. 우리 모두 인공지능에 많은 지식이 부족한 이들이였기에 책하나를 정하고 차근차근 스터디를 진행하기로 결정하였다. 책은 '파이썬부터 시작하는 인공지능' 으로 정하였다.(광고 아닙니다) 모든 건 시작이 반이다. 스터디의 시작이니 열심히 해보겠다 다짐하고 시작해보자! (시작했으니 벌써 반은 했다)

🪄이번주차 학습목표

이번주차 스터디는 책의 1장인 파이썬 초급부분이다. 스터디원분들 중 파이썬을 조금만 알거나 모르는 분도 있고 이 스터디 자체가 초급적인 것부터 차근차근 학습하는 것이기에 인공지능하면 땔 수 없는 언어인 파이썬을 간단히 다루어보고 학습하는 것이 이번주차 목표이다.

▶️ 파이썬 시작하기

1. 파이썬 설치

• 홈페이지에서 설치하시면 됩니다.
• 파이썬 공식 홈페이지(https://www.python.org)*

2. 가상환경 생성 및 활성화

• 가상환경은 독립적이고 격리된 파이썬 실행환경을 뜻하며, 프로젝트 별로 다른 가상환경을 만들어 사용하면 패키지 버전 충돌문제를 방지할 수 있다는 장점이 있다.
• 가상환경 생성과 활성화는 운영체제에 따라 다르다. 본인의 OS가 윈도우 이므로 윈도우만 작성하겠다.
• 가상환경은 여러 종류가 있지만 venv으로 하겠다.

윈도우 운영체제에서 가상환경 생성 방법

1. 명령 프롬프트(CMD)를 실행

2. 프로젝트의 루트 디렉토리로 이동(cd를 활용)

예시) 처음 실행시 C:\users\사용자 이름> 으로 나올텐데 
cd <이동할 디렉토리> 를 통해 디렉토리로 이동하면 된다.

3. python -m venv 가상환경이름
위 처럼 작성한다.

• 가상환경을 생성하였으면 활성화를 하여야 사용할 수 있다.

  윈도우 운영체제에서 가상환경 활성화 방법

1. 생성한 가상환경폴더의 Scripts디렉터리로 이동한다.

2. activate.bat 명령어를 작성 후 실행

예시) cd C:\생성한가상환경폴더\Scripts
activate.bat

3. 혹은 call 생성한가상환경이름\Scripts\activate 로 작성하여도 된다.

4. 가상환경이 활성화 되면 커멘드라인 왼쪽에 (가상환경이름)이 추가된다. ```

5. IDLE

• 파이썬 설치시 같이 설치되며 IDLE(Integrated Development and Learning Environment)[통합개발학습환경]이다.
• 크게 셸 창과 에디터 창으로 나뉘는데 셸 창은 대화형 인터프리터이다. >>>뒤에 입력이나 명령을 입력시 실행된다.
• 에디터 창은 코드를 작성 후 실행하면 셸 창에서 실행된다.

4. 파이썬 IDE

• IDLE보다는 IDE가 실무적으로 많은 기능을 가졌기에 IDE를 추천한다. 1️⃣ 비주얼 스튜디오 코드(Visual Studio Code) - 파이썬 이용자들이 가장 많이 애용하는 IDE중 하나. - 본인은 가장 추천하는 IDE이다. 무료이기도 하고. 2️⃣ 파이참(PyCharm) - 현용 파이썬 개발 툴 중 가장 기능이 강력하고 완성도가 높다고 여겨진다. - 다만 유료이다.

5. 기본연산자

• 산술연산자(+, -, , /, *, //, %) : 순서대로 더하기, 빼기, 곱하기, 나누기, 제곱, 몫, 나머지 이다.
• 비교연산자(==, !=, <, <=, >, >=) : 순서대로 같다, 다르다, 작다, 작거나 같다, 크다, 크거나 같다 이다.
• 논리연산자(and, or, not) : 순서대로 논리합, 논리곱, 부정이다.
• 이 외에도 소속연산자, 신원연산자, 할당 연산자, 비트연산자가 있다.

6. 주석

-** #**을 통해 나타낸다.

🔑객체

변수란 정보가 저장될 메모리영역을 추상화 한 것이다. 일반적으로는 C언어와 같이 변수를 선언하면 변수를 어느 메모리영역에 영역을 확보하고 그곳에 정보를 할당한다. 하지만 파이썬에서는 a = 3이라 작성하면 3이라는 정수 객체를 생성하고 a가 객체를 가리키는 일종의 포인터역할을 한다. 모든 객체들은 메모리의 어디인가에 저장되며 각기 고유한 식별번호를 가진다.

 a=3
 b=3
 id(a)    #id함수는 객체의 식별번호를 출력하는 내장함수이다.
 id(b)

위 코드를 실행하면 a와 b가 같은 객체인 3을 가리키므로 같은 아이디값을 가지는 것을 알 수 있다.

🔢숫자와 문자열

1. 숫자

• 정수형 객체[int]와 실수형 객체[float]가 있다.
• 1과 1.0은 각각 식별번호가 다르다.
• 부동소수점 : 1보다 작은 숫자를 이진법으로 나타내기 어렵기에 0에 작은 수를 더하여 그 수에 아주 가까운수를 만든다. 그렇기에 작은 오차가 발생할 수 있다.
• 지수표현 : e를 이용한다. 여기서 e는 10의 몇승인지를 나타냄 ex) 1.23e-3 = 1.23 * 10^-3 = 0.00123

2. 문자열

• '이나 "으로 감싸면 문자열 객체가 생성된다.
• " "은 공백문자, ""은 비어있는 문자를 나타낸다.
• 이스케이프 코드는 아래와 같이 있다.

  \' 따옴표
  \" 큰따옴표
  \n 줄바꿈
  \t 탭
  \\ 백슬레쉬 개체

• 문자열 연결은 +로 문자열 반복은 *로 나타낼 수 있다.

  s1 = 'love'
  s2 = ' you'
  s3 = s1 + s2
  s4 = s1*3
  print(s3)
  print(s4) 

• 위 코드를 실행하면 s3는 love you로 s4는 lovelovelove로 출력된다. name = input("your name: ")
• 위 코드의 input은 큰 따움표 안의 문자열을 출력후 무언가를 입력받은 후 name이 그 입력받은 객체를 가리키도록 한다.
• 문자열은 순서가 있기에 특정한 위치의 문자를 반환할 수 있다. 이를 인덱싱이라 한다. s = 'abcdefg'
• 위 문자열이 있으면 아래와 같이 나타낼 수 있다.

  s[0]은 'a' #0번째(앞문자부터 0이다)
  s[3]은 'd' #3번째
  s[-1]은 'g' #뒤에서 첫번째(뒤에서부터 셀때는 1부터 시작한다. 0과 -0이 같기에)
  s[0:3]은 'abc' #0이상 3미만까지
  s[:3]은 'abc' #처음부터 3미만까지
  s[1:]은 'bcdefg' #1이상부터 끝까지
  s[:]은 'abcdefg' #전체

  • print("result : %s", %3) 이것과 같이 %s를 이용하여 출력할 문자열의 형식을 설정하는 것을 문자열 포맷팅이라 한다.

📓리스트, 튜플, 세트, 딕셔너리

1. 리스트

• 리스트는 요소 객체의 변경이 가능한 서열형 객체이다.
• 리스트는 대괄호([])로 묶여있고 생성함수 list를 사용하거나 직접 요소들을 대괄호로 묶어서 생성할 수 있다.
• 리스트도 문자열과 같이 연결(+), 반복(*),인덱싱, 슬라이싱을 할 수 있으며 요소값을 변경도 가능하다.
• 리스트 또한 객체이므로 요소값을 변경한다 하여도 id값은 변하지 않는다.

2. 튜플

• 리스트와 다른 것은 같지만 요소값을 변경하지 못한다는 차이만 있다.
• 리스트와 달리 소괄호"()"로 묶여있다.

3. 세트

• 집합과 같다.
• 서열형 객체가 아니기에 인덱싱을 할 수 없다.
• 중괄호({})를 이용하여 생성 가능하다.

4. 딕셔너리

• 키와 벨류 쌍으로 데이터를 관리하는 가변객체이다.
• 키를 인덱스처럼 사용하여 벨류를 얻을 수 있다.
• '키:벨류' 형식으로 요소객체 쌍을 구성한다.
• 중괄호로 묶여있다.
• 키에는 가변객체를 사용할 수 없다.

💻제어문

1. if 조건문

   number = 5
   

if number % 2 == 0: print("multiples of 2") elif number % 3 == 0: print("multiples of 3") elif number % 4 == 0: print("multiples of 4") else: print("none of above")

- 위 코드를 실행하면 none of above가 출력될 것이다.
- if 조건:
    실행할 코드
    이렇게 작성되는데 **실행할 코드는 들여쓰기 하여 if 블럭의 범위를 나타낸다.**
- **else if = elif** 이다. 즉 위 if조건이 아니라 elif의 조건이라면 elif의 실행코드가 실행된다.
- if문 안의 if문 같이 **중첩 if문**도 가능하다.

2. for 반복문
- 리스트나 튜플 같은 **서열형 객체**를 이용할 시

for item in items: do_something

     그 서열형 객체들의 요소들 전체를 차례대로 하여 무언가를 실행할 수 있다.

```python
>>> a = range(0,8,2)
>>> list(a)

• 위와 같이 실행하면 list는 [0, 2, 4, 6]으로 생성된다.
• range의 괄호 안 첫번째는 시작정수, 두번째는 끝정수(미포함), 세번째는 간격을 나타낸다.
• 즉 위의 예시는 0이상 8미만까지 2의 간격으로를 의미한다.
• 간격이 음수면 간격만큼 감소하도록 한다.
• 간격을 지정하지 않으면 기본값이 1이고, 초기값을 지정하지 않으면 기본값이 처음이다. 끝값은 무조건 지정해야 한다.
• 중첩 for문도 가능하다.
• break는 반복문을 빠져나가게 하고, continue는 이후의 코드를 실행하지 않고 다음 반복 차수를 수행하고, pass는 아무작업도 하지 않겠다는 뜻이다.

3. while 반복문

• while은 주어진 조건이 참인 동안 계속해서 루프를 순환시킨다.

  i = 0
  while i<3:
    print(i)
    i += 1

• 위 코드를 실행시키면 0, 1, 2가 차례되로 출력된다.
• while문 또한 중첩이 가능하며 break를 통해서 탈출할 수도 있다.