전체 글
-
백준 17780번 새로운 게임PS 2020. 1. 29. 23:56
https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 www.acmicpc.net 말이 겹치는 상황에서 말을 관리하려면 2차원배열의 벡터가 필요합니다. 말이 4개 이상 쌓이면 게임을 종료하는 것입니다. 딱 4개가 ..
-
오차역전파법 - Softmax-with-Loss계층 구현하기딥러닝 2020. 1. 28. 17:35
잠시 앞의 내용복습을 하겠습니다! 신경망은 그림1과 같은 층들이 여러 개 있는 것입니다. (그림이 조금 엉망이네요...ㅎㅎ) 이때 그림1의 h() 함수를 활성화 함수라고 하죠. 활성화 함수에는 계단, 시그모이드, ReLu 등 이 있습니다. 출력층의 활성화 함수는 항등함수와 소프트맥스 함수가 있습니다. 이제는 각 층을 하나의 클래스로 구현한다고 했습니다. (그림2) 그래서 이제는 소프트맥스함수를 구현해봅시다. 학습과정이므로 손실함수가 필수입니다. 그러므로 손실 구현도 같이 하겠습니다. ! 신경망에서 수행하는 작업은 학습과 추론 두 가지입니다. 추론에서 답을 하나만 낼 때는 소프트맥스 함수가 필요없습니다. 소프트맥스 함수는 입력값을 출력의 합이 1이 되도록 정규화하는 함수이기 때문입니다. (입력값과 출력값이..
-
백준 15898번 피아의 아틀리에 ~신비한 대회의 연금술사~PS 2020. 1. 28. 16:48
https://www.acmicpc.net/problem/15898 15898번: 피아의 아틀리에 ~신비한 대회의 연금술사~ "피아의 아틀리에 ~신비한 대회의 연금술사~"는 가난한 연금술사 피아의 성장스토리를 담은 게임이다. 이 게임의 가장 중요한 부분은 "대회"인데, 연금술로 높은 품질의 물건을 만들어 상금을 타야만 피아가 먹고 살 수 있기 때문이다. 스토리는 매우 길지만 여백이 없어 생략하기로 하고, 여러분은 이 게임의 대회 기능을 확인해달라는 요청을 받았다. 여러분이 확인해야 하는 대회는 다음과 같다. 여러분은 5×5 격자 모양 가마에 서로 다른 재료 3개를 순서대로 넣어 www.acmicpc.net 처음에는 dfs0 기저에서 dfs1 호출, dfs1 기저에서 dfs2 호출, dfs2 기저에서 계산..
-
오차역전파법 - 덧셈 계층, 곱셈 계층딥러닝 2020. 1. 27. 00:39
덧셈 계층과 곱셈 계층을 구현해봅시다. 각각 순전파와 역전파 모두 구현해야겠죠. 우선 덧셈 계층부터 봅시다. 순전파는 그냥 덧셈해주면 됩니다. 역전파는 각 입력에 대해 미분을 해주고 그 값을 곱해주면 됩니다.(합성함수 미분의 원리) 두 개 모두 미분값이 1이군요. 구현해봅시다. class AddLayer: def __init__(self): pass #순전파 def forward(self, x, y): return x + y #역전파 def backward(self, dout): dx = dout * 1 dy = dout * 1 return dx, dy 덧셈 계층은 역전파에서 순전파의 값을 이용하지 않습니다. 그래서 초기화가 필요없습니다.(pass : 아무것도 하지 말라) 곱셈 계층을 봅시다. 순전파는 ..
-
오차역전파법 - 계산 그래프딥러닝 2020. 1. 27. 00:11
왜 오차역전파법을 배우나? 오차역전파법은 가중치 매개변수의 기울기를 계산하는 방법입니다. 굳이 수치미분 대신 사용하는 이유는 오차역전파법이 빠르기 때문입니다. 많은 양의 데이터를 다뤄야하므로 조금이라도 빠른 것이 좋겠죠. 오차역전파법은 계산 그래프를 활용하여 구현되어집니다. 그럼 계산 그래프는 무엇일까요? 요런 것입니다. 저 f의 자리에는 +, -, *, exp(x) 등이 들어갈 수 있겠군요! 사용예시를 봅시다. 화살표의 방향으로 진행하는 것이 순전파입니다. 이 계산 그래프의 특징은 뭘까요? 분할정복처럼 국소적 계산을 전파함으로써 최종결과를 얻을 수 있다는 것입니다. 그렇다면 역전파는 순전파의 역방향일 것이고.. 구하고자 하는 것은 기울기이니.. 계산 그래프의 저런 특징이 기울기 또한 구하기 쉽게 만드는..
-
알고스팟 QuantizationPS 2020. 1. 24. 04:57
https://algospot.com/judge/problem/read/QUANTIZE algospot.com :: QUANTIZE Quantization 문제 정보 문제 Quantization (양자화) 과정은, 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현함으로써 자료를 손실 압축하는 과정을 말한다. 예를 들어 16비트 JPG 파일을 4컬러 GIF 파일로 변환하는 것은 RGB 색 공간의 색들을 4컬러 중의 하나로 양자화하는 것이고, 키가 161, 164, 170, 178 인 학생 넷을 '160대 둘, 170대 둘' 이라고 축약해 표현하는 것 또한 양자화라고 할 algospot.com 완탐으로는 도저히 풀 수 없음은 조금만 생각해보면 알 수 있다. 그럼 어떻게 할까? 일단 관찰을 해..
-
알고스팟 원주율 외우기 PIPS 2020. 1. 22. 20:58
https://algospot.com/judge/problem/read/PI algospot.com :: PI 원주율 외우기 문제 정보 문제 (주의: 이 문제는 TopCoder 의 번역 문제입니다.) 가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다. 이 때, 각 조각들의 난이 algospot.com 딱 봐도 dp문제인 것을 알 수 있습니다. 길이가 3, 4, 5 방법이 1, 2, 3, 4, 5 인 것을 메모이제이션 ..