생각정리
밑바닥부터 시작하는 딥러닝①: 손실함수와 정확도 미분
모델의 평가방법으로 정확도가 아닌 손실함수를 사용 하는 이유에 대해 내가 이해한 대로 써보려 한다. 정확도가 아닌 손실함수를 평가요소로 사용하는 이유는 두가지가 있다. ① 정확도는 매개변수의 변화에 민감하게 반응하지 않고, 값이 불연속적이다. ② 정확도는 매개변수의 미분값이 대부분 0이여서 매개변수 갱신이 되지 않는다. 정확히는 ①이 ②의 원인이다. 먼저 정확도 그래프를 보자. 값이 불연속적으로 변하는 것을 볼 수 있다. 왜냐하면 정답 갯수는 값이 1개, 2개..등으로 셀 수 있는 정수, 즉 불연속적인 값이기 때문이다. 이 정확도 함수는 미분을 하여도 구간별로 상수이기때문에 미분값이 0이 될것이고, 따라서 역전파를 통한 최적화시에 매개변수 값을 바꿀 수 없다. 왜냐하면 0은 더하거나 곱해도 0이기 때문이..
밑바닥 부터 시작하는 딥러닝① 요약
딥러닝을 공부한지 두달정도가 지났고 딥러닝계의 바이블로 불리는 '밑바닥부터 시작하는 딥러닝①'로 시작하였다. 신경망(ANN)의 기초와 평가방법, 최적화 그리고 합성곱계층(CNN), 오버피팅 방지 등에 대해 배우는 책이였다. 책을 공부하며 정리한 요약본을 남겨본다. 책을 읽으며 생긴 의문점과 그에 대한 답은 후속 포스트에 남겨놓았다. 신경망에 대해 처음 배우는 장이다. ANN, 완전연결계층과 입력(label)을 이용해 머신러닝의 기초에 대하여 배웠다. ANN은 입력층, 은닉층, 출력층으로 나눌 수 있었고 층의 깊이를 깊게 할때는 은닉층을 깊게 쌓았다. 입력층에 데이터를 바로 입력하지 않고 데이터의 특성들을 고려하여 전처리 후, 입력하면 정확도를 더 높힐수 있었다. 모델을 평가할 때는 정확도와 손실함수라는 ..
백준 17135번: 캐슬 디펜스 (파이썬, 완전탐색, 구현)
정말 어려운 문제였다. 처음 문제를 봤을때 완전탐색 혹은 DP중에 고민했는데 시간복잡도가 M개 중에 3 개를 뽑는 조합 mC3 = m(m-1)(m-2)/6, 적들이 N번 움직이므로 반복문 O(N), 사정거리 D만큼, M열에 대해 거리를 탐색해야 하니 O(N^2)으로 M= 15, N = 15일 때 455*15*15*10= 10^6으로 시간제한인 1초에 넉넉하게 맞출 수 있어 완전탐색으로 풀어야 겠다고 생각할 수 있었다. 그러나 구현 문제를 거의 처음 풀어봐서 시간이 오래 걸렸는데 반복문이 많이 중첩되다 보니 순서나 반복값에 있어서 헷갈림이 많았다. 알고리즘은 간단하다. 먼저 조합으로 [0:M]에 대해 3개를 뽑는다. 이때 궁수의 위치는 N행에 고정이므로 열의 크기에 대해서 조합을 뽑아야 한다. 그다음 적과..
백준 17070번: 파이프 옮기기 1 (파이썬, DFS, DP)
멘탈이 나간 문제이다. 골드V에서 이정도로 헤멘건 처음이다.. 삼성 A형 기출문제중 하나인데 2차원 배열이 주어지길래 당연히 dfs, bfs로 접근하려 했다. 나는 bfs로 접근하였는데 파이프가 가로인지, 세로인지, 대각선인지 판단을 해야해서 queue에 두 점의 좌표를 튜플과 리스트로 감싸 넣었다. 대각선일땐 세점이 방문 불가하고 파이프의 왼쪽은 파이프가 옮겨질 때 옮겨지기 전 파이프 오른쪽의 좌표로 옮겨진다는 두 포인트를 잡고 코드를 짰다. import sys from collections import deque def bfs(n): global cnt queue = deque(n) while queue: now = queue.popleft() if now[0][0] - now[1][0] == 0: ..
백준 2623번: 음악프로그램 (파이썬, 위상정렬, Cycle)
유향그래프를 정렬하는 문제이고 사이클이 없으므로 위상정렬을 이용하여 풀었다. 앞서 푼 '2252번: 줄세우기' 문제와 사이클이 존재할 때와 존재 안할 때를 판별하는 것이 차이점이 였다. 위상 정렬을 하기 위해서는 사이클이 없어야 하므로 문제의 조건을 하나 추가한 것 같다. 위상정렬은 DFS로 그래프를 정렬 후 뒤짚는 방식으로 구현하였다. 사이클 판별은 두가지로 해보았다. 첫번째 방법은 노드 수 N과 크기가 같은 boolean 배열을 하나 만들어서 V의 종단노드부터 boolean 배열의 원소 값을 True로 한다. 그 후 종단노드의 부모노드 순으로 boolean 배열의 원소 값을 True로 한다. 이때 부모노드의 boolean 배열의 원소값이 False라면 Cycle이 존재한다고 판별하는 방법이다. 왜냐하..
백준 13565번: 침투 (파이썬, DFS)
전류가 통하는 격자는 0, 통하지 않는 격자는 1이다. outder side에서 inner side로 침투하면 성공이므로, 첫번째 행의 원소들에 대해서만 DFS를 하면 된다. 마지막 행에 도달했다는것을 알기 위해 방문을 확인하는 배열을 따로 만들었다. outer side에서만 DFS를 하므로(방문), inner side에 방문을 했다면 침투에 성공한 것이기 때문이다. 여담으로 출력을 Yes로 했다가 계속 틀려서 머리가 터지는 줄 알았는데 대소문자 구별을 잘해야 하고 문제 조건을 꼼꼼히 읽어야 한다.. import sys sys.setrecursionlimit(10**9) dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] def dfs(x, y): visited[x][y] = True f..
백준 2468번: 안전영역 (파이썬, DFS)
문제 자체는 기본적인 DFS의 구현이였으나 안전한 영역의 최대 개수를 구하기 위해 한번의 과정이 더 필요하였다. 2차원 배열이기 때문에 각 배열의 원소들에 접근하기 위해서는 2중 반복문이 필수이다. 이때 높이는 1이상 100이하 정수이고 N은 100보다 작으므로 3중 반복문이라 하더라도 100^3=10^6, 시간복잡도는 O(N^3)으로 시간초과에 걸리지는 않는다. 따라서 입력되는 배열들 각각에 max함수를 적용후, 그 값들에 다시 max함수를 적용하여 반복문의 최대 range를 정하고 dfs를 적용하면 된다. import sys sys.setrecursionlimit(1000000) dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def dfs(x, y): visited[x][y] =..
백준 2667번: 단지번호 붙이기 (파이썬, BFS)
BFS로 푸는 문제이다. 아파트가 있는곳은 1, 아파트가 없는곳은 0으로 표시되기 때문에(이진법) 방문여부를 확인하는 배열을 따로 만들지 않고 방문 시 배열값을 0으로 함으로써 다시 방문할 일이 없게 하였다. 근소한 차이긴 하지만 실행시간을 약간이라도 줄이는 것을 확인하였다. import sys from collections import deque dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def bfs(x, y): global cnt graph[x][y] = 0 q = deque([(x, y)]) while q: now = q.popleft() for i in range(4): nx = now[0] + dx[i] ny = now[1] + dy[i] if 0