컴공과고씨

https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제 정리 강의를 녹화해야함. 강의 수 N개, M개의 블루레이에 저장. 이때 강의마다 시간이 주어지는데 강의는 순서대로 녹화해야함. 또한 강의 중간에 끊겨서 녹화하면 안됨. -> 한 강의는 한 블루레이에 끊어지지 않고 있어야함. 이때 블루레이의 크기를 구하는데 최소 크기를 구해야함. 문제 해결 방법 하나하나 크기를 정해서 비교하면 시간이 굉장히 오래 걸리게 됩니다. 그러므로 이분탐색을 이용하여서 시간 단..

https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 문제 간단 정리 돈을 통장에서 인출하는 횟수를 정해놓고 씀. 인출한 금액에서 하루 하루 금액을 정해놓고 사용. 인출한 금액을 쓰다가 모자른 경우 남은 금액 통장에 넣고 다시 아까 정해놓은 인출 금액을 꺼내서 씀. 이때 인출하는 금액을 최소가 되도록 구해라. 인출하는 횟수가 문제에서 주어진 횟수보다 크면 안됨. 하지만 인출하는 횟수가 적은 것은 상관없음 이유는 문제에서 인출하는 횟수를 맞추기 위해서 금액..

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) 이 필터가 가장 좋은 효과를 냅니다..