Python
Training , Test 선택 가우시안 모델 구현하기
이번엔 Training, Test 케이스를 나누어서 가우시안 회귀를 적용해 보자. 예를들어 25개의 데이터가 있다고 생각해보자. 만약 이 25개의 데이터를 이용해 저번 글에서 사용한 가우시안 함수를 이용한 모델을 만들면 어떻게 될까? K의 값이 높아질수록 이 25개의 데이터에 알맞아지는 함수가 나올 것이다. 그렇다면 이 함수가 정말 뛰어난 인공지능이라고 말할 수 있을까? 정답은 그렇지 않다. 이를 생각하기위해 25개의 데이터를 20개의 데이터와 5개의 데이터를 가지고 봐보자. 학습을 20개의 데이터만 가지고 학습을 시키고 5개의 데이터를 실전 데이터라고 생각해보자. MSE는 손실율 즉, 높을수록 정확도가 떨어진다고 생각하면 될 것 같다. K의 값이 일정 수순을 넘어가면 실전 데이터에선 오히려 오차가 증가..
11700_플로이드2
https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 해당 유형의 문제는 역시 다익스트라 알고리즘을 활용하고 최단거리 역추적을 이용하면 꽤나 쉽게 풀 수 있다. import sys import heapq input = sys.stdin.readline INF = int(1e9) n= int(input()) m = int(input()) graph = [ [] for _ in range(n+1)] for _ in range(m): s,e,v = m..
11779_최소비용 구하기 2
https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 이전의 다익스트라 알고리즘을 활용하면 풀 수 있다. 이전과 다른점은 어디를 방문했는지 기록을 해둬야 할것이다. 그래서 visited란 배열을 하나 만든 후에, 새로운 노드에 값을 기록할때마다 어느 노드에서 왔는지 기록하도록 하였다. import sys import heapq input = sys.stdin.readline INF = int(1e9) n = int(i..
9019_DSLR
https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net bfs를 활용하면 되는 문제이다. 결국 이전 숨바꼭질 문제들과 비슷하게 풀 수 있다. D,S,L,R 연산을 한번씩 한 후에 dp에 넣어주면서 풀면 된다. 만약 어떠한 연산으로 200이란 수가 나왔다면 그 다음에 200이 나온 경우에는 queue에 추가하지 않는 방식으로 문제를 풀면 될 것이다. 이때 역추적또한 해야하는데, 이전의 데이터를 굳이 넣진 않고 큐 구조에 답을 저장하는 공간을..
13913_숨바꼭질
https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질의 연장선 문제이다. bfs를 통해서 카운트를 통해 몇초가 걸리는지 걸리는건 해볼 수 있다. 이때 0~100000까지의 배열을 만들어두고 해당하는 초를 새기면서 카운팅을 한다. 그렇다면 이 배열을 기록해나갈때 어느 점에서 나왔는지도 기록을 하면 쉽게 역추적을 할 수 있다. 이배열의 이름을 cnt라고 해보자 예를 들어 5 17인경우 5 10 9 18 17 5..
9252_LCS2
https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이전에 LCS문제를 풀어봤다면 비슷하게 풀 수 있다. 해당 예제를 dp에 넣을때 위처럼 쌓여지게 된다. 첫째줄부터 살펴보면 C를 가지고 A, AC , ACA, ACAY, ACAYK, ACAYKP 랑 순서대로 비교하면서 배열을 찾는 것이다. 두번재줄은 A,C를 가지고 A, AC , ACA, ACAY, ACAYK, ACAYKP 랑 비교하면서 길이를 찾는..