컴공과고씨

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 이 문제는 DFS와 백트래킹을 사용하는 문제입니다. 문제 정리 사다리 타기를 하는데 1번 위치가 사다리를 타면 1번 위치로 내려가고 2번은 2번 위치, 즉, i번이 사다리를 탔을 때 결과가 i번이도록 사다리에 가로선을 추가하는 것입니다. 가로선은 최대 3까지 가능하며 가로선을 최소로 하는 사다리를 만드는 것입니다. 문제 해결 방법 사다리 표시 방법 부터 정해야 합니다. 배열로 정의를 할 것이고 ..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제를 읽어보면 탐색 문제인 것을 알 수 있습니다. BFS를 사용해서 풀었습니다. 전체적인 문제 해결 방법은 수빈이의 위치와 동생의 위치를 확인 후 같지 않다면 수빈이의 위치를 이동시킨 후 큐에 넣어줍니다. 큐가 빌 때까지 반복 해 주면 됩니다. 그러다 처음으로 위치가 같아지면 이제까지 걸린 시간을 저장해줍니다. 그 후 위치가 같고 그 전에 저장해둔 걸린 시간..

Determinant |A| or det A A가 n by n 행렬일 때 det A라는 것은 벡터들이 만드는 볼륨을 이야기 합니다. 예를 들면 det A의 특징은 det A = det AT detAB = detA detB det A = 0 A singular => 역행렬 존재하지 않음 det A-1 = 1/detA Eigenvector & Eigenvalue 고유벡터와 고유값에 대해서 알아보겠습니다. A라는 square 벡터가 주어졌을 때 어떤 x라는 벡터와 곱을 했을 때 x 벡터의 스칼라배 벡터가 만들어진다고 하자. 이것을 식으로 나타내면 Ax = λx , x not 0 이 때 λ가 고유값이고 Ax를 했을 때 스칼라배 된 벡터를 고유 벡터라고 합니다. 고유벡터를 구하는 법은 | A - λI | = 0 ..

Norm norm이라는 것은 벡터의 크기를 말합니다. || x || 이런 식으로 표기를 해줍니다. || x - y || 이것은 무엇일까요? x-y는 저런 벡터가 됩니다. 그러면 저것의 크기는 결국 x 벡터와 y 벡터 사이의 거리가 되는 것 입니다. p-Norms에는 종류가 있습니다. 먼저 엘투 norms을 보면 우리가 흔히 알고 있는 피타고라스 정리를 통해서 구한 거리를 말합니다. 각 길이를 제곱후에 더해주고 루트를 취해주면 됩니다. 엘원 놈은 멘하튼 norm이라고도 불립니다. 이유는 멘하튼이 이제 네모네모 형태로 되어있는데 그림에서 보시다시피 대각선으로는 못가고 왼쪽 오른쪽 위 아래로만 갈 수 있기 때문에 그 거리를 측정한 것을 말합니다. 그래서 각 벡터의 크기를 더해주기만 하면 됩니다. 나머지는 그림..

본격적으로 머신러닝을 공부하기 앞서 머신러닝에 필요한 선형대수에 대해서 먼저 간단히 공부하고 머신러닝에 대해서 공부해 보겠습니다. 벡터를 기본적으로 표현하는 방법입니다. x 밑에 - 를 적어주면 기본적으로 벡터라는 뜻인데 생략하기도 합니다. 열과 행을 모으면 행렬이 되는데 이 행렬은 두 가지로 나타낼 수 있는 모습을 볼 수 있습니다. 하나는 열벡터들의 모음 다른 하는 행 벡터들의 모음 이런식으로 표현할 수 있습니다. Dot product & Outer product 이제 내적과 외적에 대해서 간단히 보겠습니다. 먼저 내적, inner product or dot product라고 합니다. 보시면 내적을 표현하는 방법은 3가지가 있습니다. 기본적으로 x 벡터라고 하면 행벡터를 나타내기 때문에 트랜스포스(T)..

머신러닝을 공부하기 앞서 AI와 머신러닝의 관계를 한번 살펴보도록 하겠습니다. 먼저 AI의 초창기는 지식 기반 방식이 주류였습니다. - 예를 들면 가운데 구멍이 한 개 있고 둥근 모양이면 반지이다. 하지만 누가봐도 가운데 구멍이 한 개 있고 둥근 모양이라고 모든 것이 반지는 아닙니다. 즉, 지식 기반에는 한계점이 많습니다. 그래서 사람들은 지식 기반에서 데이터 중심으로 접근 방식을 달리 합니다. 이것이 바로 ML(머신러닝)입니다. 간단히 정의 하면 인공지능이 큰 의미이고 그 안에 머신러닝이 있다고 보면 됩니다.

요즘 핫한 머신러닝에 대해서 쭉 공부를 할 것인데 먼저 머신러닝이 무엇인지에 대해서 간단히 알아보도록 하겠습니다. 1. 머신러닝이란? 먼저 머신러닝을 간단한 도식으로 표현해 본다면 바로 이러한 그림이 될 것입니다. 자 이 그림이 의미하는 바는 무엇이냐? 예를 들어서 포탄을 날린다고 하면 이 때 포탄의 도착지점을 결정하는 지점의 요인에는 날리는 세기, 바람의 방향, 포탄의 크기, 각도 등이 있을 것입니다. 자 이것을 input이고 우리는 수학적 이론에 따라 계산을 하면 도착 지점이 나오겠죠. 이때 black box는 수학적 모델이 될 것입니다. 그런데 만약 우리가 수학적 공식을 모른다면? 직접 포탄을 쏘면 output을 알 수 있겠죠? 그럼 바람의 세기, 각도 등을 무수하게 바꾸면서 포탄을 쏘면 각각 다른..

앞쪽에서 필터링하는 과정을 보았다면 이번에는 어떤 필터들이 있는지 살펴 보도록 하겠습니다. 먼저 Low pass 필터부터 보겠습니다. 이유는 Low pass 필터를 알면 high pass는 자동으로 알 수 있습니다. 1. Ideal Lowpass Filters (ILPF) 보면 일정한 우리가 정한 주파수 전까지는 1이고 나머지는 다 0으로 만드는 필터입니다. 이 모양의 필터를 IDFT를 해주면 sinc function 처럼 되는데 문제는 저렇게 쭉 잔상이 이어집니다. 그렇기 때무노에 ILPF를 거치면 ringing artifact가 발생합니다. 2. Gaussian Lowpass Filters(GLPF) 3. Butterworth Lowpass Filters(BLPF) 이 필터가 가장 좋은 효과를 냅니다..

이제 주파수 영역에서 필터링을 공부해 보겠습니다. 어떤 이미지에 주기성이 있는 노이즈가 섞여있다고 할 때 정말 유용합니다. 위 처럼 노이즈가 주기성이 있는 경우 주파수 도메인으로 변경해주면 노이즈가 보일 것입니다. 앞에서 배웠듯이 주기가 큰 (width) 다른 도메인은 반비례하게 나타나기 때문에 저렇게 나오게 되고 또한 크기는 같고 반대쪽에도 생기기 때문에 노이즈에 대한 것이 2개 찍혀있는 것을 볼 수 있습니다. 우리는 주파수를 분석해서 노이즈 주파수만 0인 필터를 만들고 두 개를 곱해주면 노이즈가 제거된 이미지를 볼 수 있을 것입니다. 하지만 이 방법은 많은 문제를 야기 합니다. 그래서 더 자세히 배워보도록 하겠습니다. 문제1. discrete 도메인에서 푸리에 변환을 하다 보면 오차가 발생하게 됩니다..

앞에 푸리에 변환에 대해서 깊게 배운 이유는 바로 주파수 도메인에서 이미지에 무언가를 조작하기 위해서 입니다. 그래서 이제는 주파수 도메인 필터링을 공부할 것인데 그전에 디지털 이미지에서의 2-D DFT에 대한 특성들을 이해하고 넘어가려고 합니다. 앞에 푸리에 변환을 잘 이해했다면 비슷비슷해서 이해하기 쉬울 것입니다. Periodity 2-D DFT의 공식은 1-D하고 거의 비슷하구요 중요한건 주기성을 가진다. 앞에서도 말했듯이 주기반복된 신호를 DFT를 한 것이기 때문에 항상 주기반복 된 결과에서 N - Point를 뽑아 낸 것이기 때문에 N마다 주기반복이 되고 있다고 생각해주어야합니다. 그래서 M과 N을 주기로 하고 있기 때문에 저런 주기성을 가진 특성을 가집니다. Magnitude & Phase 크..