BOJ 5622 다이얼

문제에서 주어진대로 문자 -> 숫자를 메핑시킨후 그대로 더해주면 된다. 기본적으로 1칸은 기본적으로 움직인다는 조건을 생각해야한다. #include <cstdio> #include <cstdlib> #include <iostream> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <vector> #include <queue> #include <stack> #include <deque> ...

더보기

BOJ 1865 웜홀

문제에서 말하는 ‘돌아오는데 시간이 줄어드는’ 을 컴공스럽게 번역하면 ‘음수 사이클이 존재하면’ 이라고 번역할 수 있다. 따라서 벨만-포드 알고리즘의 음수 사이클 체크를 통해서 이 문제를 풀 수 있다. #include <cstdio> #include <cstdlib> #include <iostream> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <vector> #include <queue> #include &...

더보기

BOJ 12851 숨바꼭질2

BFS 를 이용하여 문제를 풀면 된다. 시간은 1 씩 늘어나고, 이동 거리가 -1, +1, *2 를 갈 수 있을때 queue 에 넣어주면 된다. queue 에서 뺀 후, check 를 했을때, 현재 위치가 목적지 이면서 현재의 min value 보다 작거나 같을 경우 결과 배열에 해당 시간에 경우의수 + 1 을 해주고 min value 를 갱신해주면 된다. 최종 결과는 min value 와 minvalue 가 얼마나 나왔는지 위의 결과 배열에서 res[min value]를 확인하면 된다. #include <cstdio> #include <cstdlib> #include <iost...

더보기

BOJ 1004 어린왕자

원에 걸치는 경우가 없다고 문제에서 말했으니, 두 점이 새로 나오는 원의 내부에 있는지, 외부에 있는지 거리를 통해서 구하고, 두 점이 서로 다른 상태 라면 무조건 한번은 해당 원의 경계를 지나게 되므로 count ++ 을 해준다. #include <cstdio> #include <cstdlib> #include <iostream> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <vector> #include <qu...

더보기

cs231n 정리 Lecture 3 Loss Functions and Optimization

Wx+b 를 학습하면서, model 이 학습하는 paremeter인 W 와 b 는 어떻게 학습되는걸까? 일단 W 와 b 가 현재 상황에서 얼마나 나쁜지 좋은지에 대한 기준을 내릴 수 있어야 할 것이다. 따라서 ‘얼마나 실제와 다른지, 나쁜지’ 를 구하는 함수가 바로 ‘Loss function’ 이 된다. 여기서는 W,b 를 사용하여 예측된 결과와 실제 값의 Loss 를 모두 더해 평균을 내는것으로 Loss function 을 정의했다. Loss 를 측정하는데는 여러가지 방법이 있다. 그 중 한가지 방법으로 SVM Loss 가 있다. s_j 는 다른 레이블에 대한 점수, 즉 잘못된 정도에 대한 점수, ...

더보기

cs231n 정리 Lecture 3 -2

이전 시간에서, 우리가 열심히 구한 Loss 가 있는데, Loss 를 어떻게 써먹을까? 에 대한 방안이 없었다. 자 이제 Optimization 이라는 기법으로 위의 Loss 를 사용해보자. 우리가 가지고 있는 데이터에 W를 최적화 시키기 위해서 가장 간단한 방법은 뭘까? 그냥 W 를 랜덤하게 계속 바꿔가면서 하나씩 고르는것이 가장 간단할 것이다. 근데 이건 거의 암호를 푸는 수준으로 시간이 기하급수적으로 올라가니, 다른 방법을 써야 한다. 조금 더 수학적이고 현실적인 방법을 찾아보자. 두 번쨰 방법은 기울기를 이용하는것이다. W를 구하기 위해서, 점점 ‘기울기’ 를 타고 잔걸음으로 이동한다. ...

더보기

BOJ 10159 저울

a > b 가 정의되어있다면, a 는 b 를 타고 계속 접근할 수 있게된다. 이는 경로로 생각할수 있는데, 모든 node 에서 모든 node 로 가는 경로를 찾으면 되므로 플로이드 와샬 알고리즘을 사용하여 모든 경로를 구한다. 여기서 자기 자신으로 가는 경로와 갈수 있는 경로를 제외한 나머지 node 가 접근 불가 node 라고 생각할 수 있다. 하지만 한가지 문제가 발생하는데, logic 상에서 ‘접근 불가’ 의 의미가 ‘단방향’ 으로 계산했는데 문제에서 원하는 ‘비교 가능’ 은 양방향이다. 따라서 단방향으로 접근가능한 경로를 구한후, 최종적으로 접근불가능한 node 를 카운팅할때는 양방...

더보기

cs231n - Lecture 1 and 2

1강 이미지 처리란 매우 복잡하다. 하지만 이 이미지를 매우 잘 처리하고있는게 바로 ‘동물’ 과 ‘사물’ 이다. 동물, 사람은 이미지를 아래와 같은 방식으로 이해한다고 한다. 복잡한 이미지를 나누어서 처리하기. 복잡한 물체를 단순한 물체의 결합으로 이해하기 feature 를 중심으로 이해하기 이러한 ‘이미지’ 들에 대한 정보들이 있어야 컴퓨터가 우리가 어떤방식으로 이해하는지 알려줄 수 있을것이다. ‘Data driven Learning’ 으로, 수많은 데이터들이 있어야 한다. 최근에 딥러닝이 다시 각광받기 시작하고, 성능이 좋아진 이유도 이 데이터가 풍부해 졌고, 컴퓨팅...

더보기

BOJ 5719 거의 최단경로

푸는대 2시간은 걸린거같다. 문제는 최단경로를 제거하고 그 다음의 최단경로 즉 ‘2번째 최단경로’ 를 구하는것이다. 조건은, 최단경로에 사용되는 경로를 사용하면 안되는 2번째 최단경로를 구하는것이다. 이 문제는 조건이 큰 힌트가 되었다. ‘최단 경로에서 사용되는 경로를 사용하면 안된다’ 라는 것은 곧 최단 경로를 구하고, 최단경로에 해당하는 모든 Edge 를 지우고 다시 최단경로를 구하면 되기 때문이다. 하지만 여기서 문제가 생긴다. 바로 ‘최단경로가 여러가지 일때’ 이다. 이 문제를 해결하기 위해서, BFS 를 사용한다. 다익스트라의 결과는 결국 ‘출발 노드에서 모든 노드까지의 최단 경로...

더보기

BOJ 3780 네트워크 연결

간단히 Disjoint set 으로 풀면 된다. Disjoint set 에서 달라지는점이 2가지 있는데, 문제에서 가장 중요한 length 와 연결 방향이 주어진다는것이다. length 계산을 위해서 length 배열을 만든다. 여기서 lenght 란, 현재 노드에서 최신 상태의 root 까지의 거리인데, 초기 상태에서 root 는 자기 자신이므로 lenght 는 0이다. 하지만 각 노드가 합쳐지는 merge 연산이 발생하면 root <> root 사이에 I – J (mod 1000) 만큼의 길이가 생긴다. 따라서 merge 할...

더보기

BOJ 14940 쉬운 최단거리

오랜만에 알고리즘 문제를 풀어서 그런지 문제를 제대로 안읽어서 엄청 틀렸다 n m 입력 받고 습관적으로 정사각형인줄알고 nn 인줄알고 풀어서 엄청 틀렸다 문제 읽기도 매우 중요하다. 문제 풀이는 간단하게 BFS 를 사용하여 풀면 끝난다. 엄청 긴 if 문을 나누자니 tap 이 엄청 많아지고, 이어쓰자니 엄청 길어져서 읽기 불편했는데, 번뜩 아래와 같이 가독성 좋고 짧은 코드를 써보니 매우 좋았다. 역시 continue 는 마법인거같다. // 1번 안 if(1 <= cx && cx <= n && 1 <= cy && cy <= m &&a...

더보기

Batch Normalization. Accelerating Deep Network Training by Reducing Internal Covariate Shift

ICML 2015 Sergey Ioffe, Christian Szegedy Google Inc. Keywords Batch Normalization, mini-batch, internal covariate shift Contribution gradient vanishing/exploding problem이 발생하지 않으면서 learning late을 크게 설정할수 있어 학습 속도가 빠르다. 각 layer 에서 input distribution 에 따라 training 되는 데이터가 달라서 학습이 불안정하다. 이 문제를 정규화를 통해 푼다. 자체적으로 regularization 효과도 있다....

더보기