CS231n Lecture 4-1: Backpropagation

빠르고 정확한 Analytic gradient를 유도하고 사용하는 방법에 대해 배워보자. 계산 그래프 (Computational graph) 복잡한 형태의 함수를 나타내기 위해 계산 그래프(computational graph)를 사용할 것이다. 기본적으로 계산 그래프를 통해 어떤 함수든 표현 가능하다. 다음 예시는 $W$, $x$를 입력으로 받는 ...

CS231n Lecture 3-3: Image Features

Feature vector 이전에 간단한 형태의 inear classifier를 소개할 때, 이미지를 픽셀 그대로 입력 받는 방식을 소개했다. 그리고 아주 안 좋은 방법이라는 것을 알 수 있었다. 그래서 딥러닝 이전에는 두 가지 스테이지를 통해 입력을 변환한다. 먼저, 이미지에 대한 여러가지 특징(feature)들을 계산한다. 특징은 이미지의 ...

CS231n Lecture 3-2: Optimization

파라미터 $W$를 산과 계곡같은 풍경으로 비유하면 우리는 이 골짜기를 돌아다니는 사람과 같다. 이때 내가 있는 곳의 높이가 Loss인 셈이다. Loss는 $W$에 따라 변하고 이를 최소로 만드는 골짜기의 밑바닥에 해당하는 $W$를 찾는 것이 목표다. 이 과정을 해결하기 위한 방법들을 최적화(Optimization)이라고 한다. 손실 함수(Loss f...

CS231n Lecture 3-1: Loss Function and Regularization

앞서 배운 Linear Classifier는 Parametric model의 일종이었다. Prametric Model은 학습 데이터의 정보가 파라미터인 행렬 $W$로 요약되는 것을 말한다. 이번 강의에서 가장 좋은 행렬 $W$를 구하기 위해 학습 데이터를 어떻게 활용하는지 알아보자. 손실 함수 (Loss Function) 좋은 $W$를 구하는 방법...

CS231n Lecture 2-3: Linear Classifier

Linear Classifier(선형 분류기) Linear classifier(선형 분류기)는 간단하지만 중요하고 신경망과 CNN의 기반이 되는 알고리즘이다. 신경망을 레고블럭에 비유하기도 하는데, 다양한 컴포넌트들을 모아서 CNN이라는 타워를 짓는 셈이다. 앞으로 보게될 다양한 딥러닝 알고리즘의 가장 기본이 되는 블럭 중 하나가 Linear cla...

CS231n Lecture 2-2: K-Nearest Neighbor Classifier and Hyerparameter

최근접 이웃 분류기(Nearest Neighbor Classifier) 최근접 이웃 분류기(nearest neighbor classifier)는 아주 단순한 분류기가 있다. 학습 단계에서는 아무 일도 하지 않고, 모든 학습 데이터를 저장만 한다. 그리고 예측 단계에서 새로운 이미지가 오면 기존 학습 데이터들과 비교해서 가장 유사한 이미지를 찾는다. ...

CS231n Lecture 2-1: Image Classification

컴퓨터 비전(computer vision)에서 가장 핵심적인 task인 이미지 분류(image classification)에 대해 소개한다. 이미지 분류(Image Classificaion) 이미지 분류란 입력 이미지를 받아 미리 정해놓은 카테고리(category)들 중에서 속하는 하나의 레이블(label)을 찾는 문제다. 문제의 정의는 간단하지만...

CS231n Lecture 1: Introduction

Stanford의 CS231n은 컴퓨터 비전(computer vision) 분야에서에서 가장 인기있는 강의 중 하나다. 그 중에서도 신경망(neural network), 특히 CNN과 관련된 부분에 초점을 맞추고 있다. 감사하게도 강의 녹화본이 공개되어 있다. 이번에 강의를 들어보면서 컴퓨터 비전으로서의 딥러닝에 대한 깊은 이해를 해보려고 한다. 순...

Ubuntu 서버에 Docker로 Tensorflow 개발 환경 구축하기

Ubuntu 서버에 Tensorflow 개발 환경을 구축할 일이 생겼다. 다양한 환경의 여러 오픈 소스들을 돌려보기도 해야하고, 혼자 쓰는 서버가 아니기 때문에 Docker를 활용하기로 했다. 하지만 세팅하는 과정이 생각보다 어려워서 이렇게 따로 정리해두려고 한다. 1. 서버 GPU 확인 서버에는 NVIDIA GPU가 장착되어 있고 이를 지원하기 ...

Kickstart 2021 Round G 개인 풀이

학교 K관 랩실에서 대회에 참가했는데 중간에 랩실을 닫는 바람에 끝까지 할 수 없었다. A, B번까지 해결했을 때 등수가 괜찮았고 지하철에서 C번을 해결하면서 D번 풀이까지 세웠으나 대회가 끝나버렸다. 결과는 아쉽지만 풀이가 맞았다는 것과 시간이 있었으면 모두 해결할 수 있었다는 것에 의의를 두려고 한다. A. Dogs and Cats 개 사료가 ...

프로그래머스 월간 코드 챌린지 시즌3 9월

참가후기 전체 6등을 했다. 참 괜찮은 국내 알고리즘 대회 중 하나이지만 플랫폼의 단점이 많다. 테스트 케이스를 추가하는 과정이 번거롭고, 디버깅용 출력을 너무 많이 하면 또 실행이 안된다. 무엇보다도 대회 종료 전에 코드를 따로 백업해두지 않으면 작성한 코드가 모두 날아가는 것이 가장 불편하다. 깜박하고 코드를 백업해두지 않아서 이번에는 코드...

접미사 배열과 LCP 배열(Suffix Array and LCP Array)

접미사(Suffix) 문자열 $s$의 $i$번째 접미사란, $s$의 $i$번째 글자부터 마지막 글자까지 포함하는 부분문자열을 뜻합니다. 예를 들어, $s=\mathsf{GATAGACA}$의 접미사를 순서대로 나타내면 다음과 같습니다. [\begin{array}{ c c } ...

각도 정렬 알고리즘(Sort by Angular)

2차원 좌표평면 상의 점들을 기준점에 대해 반시계 방향 순서로 정렬하는 방법에 대해 알아보겠습니다. 외적을 이용한 방향성 판별 세 점 $O$, $A$, $B$의 방향성은 외적을 통해 판단할 수 있습니다. 외적 $\overrightarrow{OA} \times \overrightarrow{OB}$의 외적이 0보다 크면 반시계 방향(Counter Cl...

프로그래머스 월간 코드 챌린지 시즌2 4월

참가후기 전체 8등을 했다. 지문이 간단하고 명확했고 무려 한국어였다(…). 항상 영어 지문을 잘못 해석해서 고생했던 나한테 유리했다. 국내에도 이렇게 좋은 대회가 생기다니 앞으로도 자주 참가해야겠다. A. 음양 더하기 몇 개의 정수들이 있다. 이 정수의 절대값을 나타내는 수열과 부호를 나타내는 boolean 배열이 주어진다. 이 때, 모든 ...

Kickstart 2021 Round A 개인 풀이

A. K-Goodness String 문자열 절반을 기준으로 서로 대칭이 아닌 쌍의 개수를 정확히 $K$개로 만들기 위해 최소 몇 개의 문자를 바꿔야하는지 출력하는 문제다. 현재 문자열에서 대칭이 아닌 쌍의 개수를 구하고, $K$와 얼마나 차이나는지 출력했다. 배열 크기를 잘못잡아서 한 번 틀렸다. 1 2 3 4 5 6 7 8 9 10 11 1...

스턴 브로콧 트리(Stern Brocot tree)

먼저, 모든 양의 분수를 나열하는 방법에 대해 알아봅시다. 다음 두 분수가 있습니다. [\dfrac{0}{1}, \dfrac{1}{0}] 두 번째는 엄밀히 분수는 아니지만, 무한대를 나타내는 기약분수로 해석합시다. 매 반복마다, 모든 인접한 분수 $\dfrac{a}{b}$ 와 $\dfrac{c}{d}$ 사이에 mediant인 $\dfrac{a+c...

IOI 2011 풀이 (International Olympiad in Informatics 2011)

작성일 기준 BOJ에서 채점 가능한 문제만 풀어보았습니다. 1번. BOJ 5819 열대 식물원 제 풀이는 $O(N + M \log M + Q)$이지만 공식 풀이는 $O(QN)$입니다.  각 연못을 node로 하고 각 산책로에 대해 아름다운 정도를 가중치로 갖는 edge로 directed graph를 구성합니다. 철수가 한 연못에서 다음 연못으...

ACM-ICPC Seoul Nationalwide Internet Competition 2018

https://www.acmicpc.net/category/detail/1935 A. BOJ 16282 Black Chain 첫 번째 접근법은 ‘n개의 고리가 연결된 체인에서 m개의 고리를 풀 때 1g부터 ng까지 모든 무게를 생성할 수 있는지’ 여부를 판단하는 함수 f를 만들어 풀어야 할 고리의 최소값을 binary search로 찾는 것이었습니...

COCI 2009/2010 contest #2 개인 풀이

COCI(Croatian Open Competition in Informatics) 2009/2010 contest #2 https://www.acmicpc.net/category/detail/84 1. BOJ 2914 저작권 앨범의 수록곡의 개수 A와 수록곡 당 멜로디의 개수의 평균값 I가 주어질 때, 적어도 몇 개의 멜로디가 있는지 묻는다. ...

Mapping Permutation to Integer

원문 : https://stackoverflow.com/questions/1506078 permutation of n elements가 있을 때, integer로 mapping하는 방법에 대해 설명한다. n!의 permutation이 있을 수 있고, 이를 n!가지의 정수에 1:1 mapping하는 것이 목적이다. n개의 원소로 이루어진 permut...

COCI 2009/2010 contest #1 개인 풀이

COCI(Croatian Open Competition in Informatics) 2009/2010 contest #1 https://www.acmicpc.net/category/detail/83 1. BOJ 2920 음계 음계가 1 2 3 4 5 6 7 8이면 ascending, 8 7 6 5 4 3 2 1이면 descending을 출력하고,...

[MacOS] 맥 터미널에서 bits/stdc++.h 헤더 사용하기

bits/stdc++.h는 표준 라이브러리 전체를 모두 포함시키는 헤더입니다. 그래서 complie time에는 상당히 안 좋습니다. 반면에 헤더 하나만 포함하면 되기 때문에 빠르고 간결한 코드 작성이 가능합니다. 알고리즘 대회에서 중요한 것은 빠르고 정확한 코드작성, 실행 시간이기 때문에  채점서버가 이 기능을 지원하는 g++ 컴파일러를 쓴다면...

Segment Tree (+ Lazy Propagation) 코드 최적화

원문 : https://codeforces.com/blog/entry/18051 Segment tree with single elment modifications Segment tree는 한 배열에서 몇 번의 변경이나 연속된 부분에 대한 query들을 처리할 때 사용한다. 첫번째 예로 다음 두 명령어를 생각해두자.  배열에 있는 한...

Range Queries와 Modifications over Array의 Non-recursive 구현

양의 정수 $N$이 2의 지수라고 하자. 길이가 $N$인 배열 $a$의 각 원소를 $a_i$라고 하자$(i \in [0, N-1])$. 어떤 원소 $a_i$를 수정하는 규칙이 있을 때, 이것을 $a_x$와 $a_y$ 사이 모든 원소들에 적용시킨다고 생각하자. 이것을 Range modification이라고 부를 것이다.  결합법칙(Associative...

COCI 2006/2007 contest #1 개인 풀이

1. BOJ 2052 나머지 각 나머지에 대해 marking 해놓는다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include<cstdio> bool chk[42]; int main(){ for(int i=0;i<10;++i){ int t; scanf("%d...