전체 글
-
종만북 dp 개론 미완PS 2020. 1. 14. 21:03
문제를 쪼개어 부분 문제로 나누고, 이 답들로부터 원래 문제에 대한 답을 계산하는 알고리즘 이 때, 중복된 부분 문제에 대해서는 메모이제이션을 해서 계산 시간을 줄인다. 두 개의 차이점 : 문제를 나누는 방식 p208 그림8.1 (존재하는 부분 문제의 수) * (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수) dp문제를 푸는 첫 단계는 해당 문제를 재귀적으로 해결하는 완전 탐색 알고리즘을 만드는 것이다. int cache[50][50]; int dp(int a, int b){ //기저사례 if(...) return ...; //중복방문 int &res = cache[a][b]; if(res != -1) return res; //답 계산 ... return res; } int main(){ memset..
-
3층 신경망 구현해보기딥러닝 2020. 1. 10. 17:15
import numpy as np def sigmoid(x): return 1/(1+np.exp(-x)) def identy_function(x): return x def init_network(): network = {} network['W1'] = np.array([[0.1, 0.3, 0.5], [0.2, 0.4, 0.6]]) network['b1'] = np.array([0.1, 0.2, 0.3]) network['W2'] = np.array([[0.1, 0.4], [0.2, 0.5], [0.3, 0.6]]) network['b2'] = np.array([0.1, 0.2]) network['W3'] = np.array([[0.1, 0.3], [0.2, 0.4]]) network['b3'] = np...
-
활성화함수딥러닝 2020. 1. 10. 17:08
활성화함수란 입력 신호의 총합을 출력 신호로 변환하는 함수입니다. 입력 신호의 총합이 활성화를 일으키는지를 정하는 역할을 합니다. h가 활성화 함수 입니다. 입력 신호의 총합인 a를 입력값으로 가지고 y를 출력하네요. y = h(b + x1w1 + x2w2) 위 식의 활성화 함수는 임계값을 경계로 출력이 바뀝니다. 활성화 함수가 계단함수인 것입니다. 퍼셉트론이 예시가 되겠네요. 이 활성화 함수를 다른 함수로 바꾸면 신경망을 만들 수 있습니다. 그럼 활성화 함수의 종류를 알아봅시다. 종류 계단 함수, 시그모이드 함수, ReLU 함수 등이 있습니다. 시그모이드 함수는 신경망에서 자주 사용합니다. 입력을 넣으면 값이 작아져서 나옵니다. 그래서 계단함수와는 다르게 곡선입니다. (h(1.0) -> 0.7..., ..
-
알고스팟 울타리 잘라내기PS 2020. 1. 9. 23:20
https://algospot.com/judge/problem/read/FENCE algospot.com :: FENCE 울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 algospot.com 하나하나 비교하는 방법은 n의 크기를 고려했을 때, 당연히 안된다고 생각했다. 그래서 반띵을 해가며 풀어야겠다..
-
알고스팟 소풍PS 2020. 1. 9. 21:26
https://algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다. 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요 algospot.com n이 매우 작기 때문에 완전탐색으로 풀 수 있겠다고 생각했다. 단, 중복을 없애고 고르는 것이 관건이라고..
-
퍼셉트론딥러닝 2020. 1. 9. 14:37
'밑바닥부터 시작하는 딥러닝' 이라는 책을 참고하여 작성하였습니다. 퍼셉트론은 다수의 신호를 입력받아서 하나의 신호를 출력하는 것 입력이 2개인 퍼셉트론을 보도록 하자 x는 입력값, w는 가중치, b는 편향이라고 할 때 y = x1*w1 + x2*w2 + b y의 값이 1을 넘으면 1을 출력. 못넘으면 0을 출력 편향과 가중치는 다르다. 가중치는 각 입력 신호가 결과에 영향력을 조절하는 매개변수이고 편향은 뉴련이 얼마나 쉽게 활성화되는지 결정한다. 논리게이트 AND, NAND, OR, XOR를 구현해보도록 하자. import numpy as np import matplotlib.pyplot as plt def AND(x1, x2): x = np.array([x1, x2]) w = np.array([0.5..
-
알고스팟 쿼드 트리 뒤집기PS 2020. 1. 7. 20:21
https://algospot.com/judge/problem/read/QUADTREE algospot.com :: QUADTREE 쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N × 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다. 이 그림의 모든 algospot.com 압축을 풀어서 뒤집고 다시 압축하는 방법은 불가능하다. 그림의 최대 크기가 2^20 * 2^20 ..
-
알고스팟 Traveling Salesman Problem 1PS 2020. 1. 7. 17:49
https://algospot.com/judge/problem/read/TSP1 algospot.com :: TSP1 Traveling Salesman Problem 1 문제 정보 문제 NP-Complete 문제의 가장 유명한 예 중 하나인 여행하는 외판원 문제 (Traveling Salesman Problem) 은, 여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를 정확히 한 번씩 방문하는 가장 짧은 경로를 찾는 문제이다. 이 문제를 다항 시간에 해결할 수 있는 방법은 현재까지는 존재하지 않지만, 도시의 숫자가 작은 경우에는 비교적 사용 가능한 시간 안에 algospot.com n의 크기에 따라 풀이법을 달리해야 하는 유명한 문제라고 한다. 이 문제는 n이 8로 매우 작으므로 완전탐색으로..