선형대수 공부

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

• 목차는 다음과 같다.

  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';
  }
}