안녕

강화 학습을 잘 모를 수 있지만, 알파고를 모를 수는 없습니다. 알파고는 강화 학습을 통해 학습된 모델입니다. 이처럼 강화학습은 요즘 가장 흥미진진한 분야이자 가장 오래된 분야 중 하나입니다. 사람은 주위를 센싱하고 인식하여 적절한 행위를 통해 환경과 상호작용합니다. 인공지능 제품도 비슷한 과정을 수행해야 쓸모가 있습니다. 1. 에이전트 (Agent) 일상생활에서 에이전트 (Agent)란 특정한 일을 대행해주는 사람을 뜻합니다. 강화 학습에서의 에이전트는 관측을 하고 주어진 환경에서 행동을 합니다. 그리고 그 결과로 보상을 받습니다. 에이전트의 목적은 보상의 장기간 기대치를 최대로 만드는 행동을 학습하는 것입니다. 목적지에 도착하면 양의 보상을 받고, 시간을 낭비하거나 잘못된 방향으로 향하면 음의 보상을..

1. 시계열 데이터 시계열 데이터란 시간, 순서 정보가 들어 있는 데이터를 말합니다. 문장이 있다면 단어가 나타나는 순서가 중요합니다. 또한 일별 온도를 기록한 데이터가 있다면 날짜의 순서가 중요합니다. 이처럼 데이터에 순서나 시간이 들어가 있는 데이터를 시계열 데이터(time series data)라고 합니다. 시계열 데이터의 독특한 특성에 대해 알아보겠습니다. 요소의 순서가 중요 "세상에는 시계열 데이터가 참 많다"를 "시계열 참 데이터가 많다 세상에는"으로 바꾸면 의미가 훼손됩니다. 샘플의 길이가 다름 짧은 발음 "인공지능"과 긴 발음 "인 ~공~~~지능"이 다름 문맥 의존성 "시계열은 앞에서 말한 바와 ... 특성이 있다"에서 "시계열은"과 "특성이 있다"는 밀접한 관련성이 있음 계절성 미세먼지 ..

https://algospot.com/judge/problem/read/JUMPGAME algospot.com :: JUMPGAME 외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상 algospot.com import sys input = sys.stdin.readline testcase = int(input()) # 테스트 케이스의 수 def func(start, end): W[start][end] = [0, 0] # 0, 0은 0, 0으로 초기화 C[start][end] = 0 # 0, 0의 count는 0 for i in range(start, n): # ..

https://www.acmicpc.net/problem/1931 import sys input = sys.stdin.readline def func(case): i = 1 solved = True while solved: # 더 이상 들어갈 수 없다면 False임 solved = False case.append((s[i], e[i])) # i가 1로 시작하고, 나중에는 아래의 조건에 맞는 회의가 들어감 for j in range(i + 1, n + 1): if s[j] >= e[i]: # j번째 회의의 시작 시간이 i번째 회의의 끝나는 시간 이후라면 i = j # 해당 회의를 넣고 끝내버림 solved = True break n = int(input()) # 회의의 개수 s = [0] # 회의의 시작 ..

문제)

다익스트라 알고리즘은 단일 출발점에서의 최단 경로의 문제를 푸는 알고리즘입니다. 앞선 DP 알고리즘에서 Floyd's Algorithm을 이용해서 모든 출발점에서의 최단 경로의 문제를 풀었습니다. 하지만 하나의 특정 vertex에서 다른 모든 vertex로 가는 최단 경로만 알고 싶다면 프로이드의 알고리즘은 너무 과합니다. 시작하기에 앞서 프로이드의 알고리즘은 n^3인 것에 반해, 다익스트라 알고리즘은 n^2입니다. 다익스트라 알고리즘은 Prim's Algorithm과 매우 흡사합니다. 집합 Y를 최단 경로를 구하려고 하는 vertex만 포함한다. (v_1이라고 함) 그리고 F는 공집합으로 초기화한다. v_1과 가장 가까운 vertex를 찾아서, 이 vertex를 Y에 포함하고, edge를 F에 포함한다..

앞서 보았듯이 시간 복잡도는 다음과 같습니다. Prim's Algorithm : \(T(n)\,\epsilon\,\theta(n^2)\) Kruskal's Algorithm : \(W(m, n)\,\epsilon\,\theta(mlgm) \, or \, \theta(n^2lgn)\) 또한 \(n-1 \leq m \leq \frac{n(n-1)}{2}\)이 성립합니다. 따라서 프림 알고리즘과 크루스칼의 알고리즘은 다음과 같은 상황에서 비교할 수 있습니다. For a Sparse Graph edge의 개수인 m이 n-1과 가까운 희소 행렬의 경우에는 Kruskal's Algorithm is \(\theta(nlgn)\)이므로, Prim's Algorithm 보다 빠릅니다. For a Dense Graph e..

문제)

최소 비용 신장 트리를 풀기 위한 또 다른 알고리즘은 크루스칼 알고리즘입니다. 크루스칼 알고리즘은 각 vertex마다 본인만 포함하는 서로소 집합 (disjoint set)을 만드는 것부터 시작합니다. 이후, 가중치가 작은 것부터 차례대로 edge를 검사합니다. 만약 edge가 서로소 부분 집합들에 있는 두 개의 vertex를 연결한다면 edge를 추가하고, 두 개의 부분 집합을 하나의 집합으로 합칩니다. 이 반복은 모든 disjoint set이 하나의 set이 될 때까지 반복합니다. 슈도 코드로 작성하면 다음과 같습니다. F = 0 create disjoint set of V sort the edges in E in nondecreasing order while the instance is not so..

문제)