선형대수 공부

• 지피티의 도움을 잔뜩받아서 선형대수 공부를 하고 있었다.

• 목차는 다음과 같다.

  1. 벡터와 행렬의 기초
  2. 벡터공간과 부분공간
  3. 선형변환과 행렬
  4. 고윳값과 고유벡터
  5. 직교성과 정사영
  6. 특이값 분해 (SVD)

• 각 파트 별로 배운 것들을 정리해보자.

  1. 벡터와 행렬의 기초
     • 알고 있던 내용이라 쉽게 넘어갔다.
  2. 벡터공간과 부분공간
     • 벡터공간의 조건은 그냥 넘어갔다. 엄밀하게는 다음에 살펴보기로.
     • 부분공간의 조건 : (1) 영벡터 포함 (2) 덧셈 닫힘성 (3) 스칼라곱 닫힘성
     • 생성_span은 주어진 벡터들을 선형결합하여 만들 수 있는 모든 벡터의 집합
     • 벡터의 집합이 주어질 때, 어떤 한 벡터가 다른 벡터들의 선형결합으로 만들어질 수 있으면 선형종속, 아니면 선형독립이다.
     • 기저는 어떤 공간을 생성할 수 있는 가장 적은 수의 벡터의 집합
     • 차원 = 기저의 개수
  3. 선형변환과 행렬
     • 선형변환은 벡터공간을 다른 공간으로 보내는 함수 중 덧셈과 스칼라곱을 보존하는 함수.
     • 모든 선형변환은 행렬로 표현할 수 있다.
     • 행렬의 곱 = 선형변환의 합성
  4. 고윳값과 고유벡터
     • 고유벡터_eigenvector는 선형변환을 거쳐도 그 방향이 바뀌지 않는 벡터이다. 고윳값_eigenvalue은 선형변환을 거칠 때 변하는 크기의 배율.
     • 즉, 다음과 같은 식으로 표현할 수 있다.
     • 위에서 의 식을 얻을 수 있다.
       • 가 영벡터가 아닌 비자명근을 얻으려면 역행렬이 존재하지 않아야 한다. (역행렬이 존재하면 양변에 역행렬을 적용하여 자명근만 얻을 수 있기 때문)
       • 따라서 이어야 한다.
     • 대각화는 행렬 를 다음과 같이 표현하는 것.
       • 는 의 고유벡터로 구성된 고유기저_eigenbasis다.
       • 는 고유값으로 구성된 대각행렬이다.
       • 를 계산하는 것은...
         • 로 표준기저의 를 고유기저로 옮겨놓고,
         • 로 그 고유기저에서 스칼라곱만 하는 선형변환을 해두고,
         • 로 다시 고유기저에서 표준기저로 돌려놓는 것이다.
       • 어떻게 되는지 이해는 했는데, 내부 원리까지 이해하진 못했다. 다시 돌아오도록 하자.
     • 정사각행렬 가 서로 다른 개의 고윳값을 가짐 ⇒ 개의 선형독립 고유벡터를 가짐 ⇒ 는 대각화가능_{diagonalizable}하다.

• 나머지는 나중에... 기회가 된다면 Gilbert Strang textbook으로 다시 보고 싶다.

BOJ 1655 : 가운데를 말해요 (Gold 2)

• multiset의 iterator를 이용하여 해결했다.

#include <bits/stdc++.h>

using namespace std;

const int INF = numeric_limits<int>::max();

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  multiset<int> ms;

  auto med = ms.begin();
  int off = 0;
  for (int i=0;i<n;i++) {
    int x; cin >> x;
    ms.insert(x);
    if (i == 0) {
      med = ms.begin();
      cout << x << '\n';
      continue;
    }
    if (x >= *med) {
      off++;
    } else {
      off--;
    }
    if (off > 1) {
      off -= 2;
      med++;
    } else if (off < 0) {
      off += 2;
      med--;
    }
    cout << *med << '\n';
  }
}

BOJ 16234 : 인구 이동 (Gold 4)

• Disjoint set으로 해결했다.

#include <bits/stdc++.h>

using namespace std;

using vi=vector<int>;

struct DisjointSet {
  vi parent, rank, sum;
  int max_rank=1;

  DisjointSet(int n, const vi &mat) {
    parent.resize(n);
    rank.resize(n, 1);
    sum = mat;
    for (int i=0;i<n;i++)
      parent[i]=i;
  }

  int find(int x) {
    if (parent[x]==x) return x;
    return parent[x]=find(parent[x]);
  }

  void merge(int x, int y) {
    x=find(x),y=find(y);
    if (x==y) return;
    if (rank[x] > rank[y]) swap(x, y);
    parent[x]=y;
    rank[y]+=rank[x];
    sum[y]+=sum[x];
    max_rank=max(max_rank, rank[y]);
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, l, r;
  cin >> n >> l >> r;

  vi mat(n*n);
  for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
      cin >> mat[i*n+j];

  int res=0;
  for (;res<=2000;res++) {
    DisjointSet ds(n*n, mat);
    for (int i=0;i<n;i++){
      for (int j=0;j<n;j++) {
        int cur = mat[i*n+j];
        if (i > 0 && l <= abs(cur - mat[(i-1)*n+j]) && abs(cur - mat[(i-1)*n+j]) <= r)
          ds.merge(i*n+j, (i-1)*n+j);
        if (j > 0 && l <= abs(cur - mat[i*n+j-1]) && abs(cur - mat[i*n+j-1]) <= r)
          ds.merge(i*n+j, i*n+j-1);
      }
    }

    if (ds.max_rank == 1) break;

    for (int i=0;i<n;i++) {
      for (int j=0;j<n;j++) {
        int par = ds.find(i*n+j);
        int cnt = ds.rank[par];
        int sum = ds.sum[par];
        mat[i*n+j] = sum / cnt;
      }
    }
  }
  cout << res;
}