Tech.log/알고리즘8 [강화학습]Marcov Process 1️⃣강화학습 최종목표 환경(Environment)과 상호작용하는 Agent를 학습 시키는 것. Agent : 상태(State)라는 상황 안에서 행동(Action)을 취하며 조금씩 학습해 나아간다. action에 의해 양이나 음의 보상(Reward)를 돌려받는다. 정책(Policy) : Agent가 학습을 통해 제공하는 최적의 의사결정 전략 예를 들어 미로탈출 게임이 있다면, (사진하나 넣자~!) Action = 위,아래, 오른쪽, 왼쪽 reward 양(+) = 아이템을 얻은 경우 음(-) = 함정에 빠지거나 죽는 경우 0 = 아무것도 하지않고 돌아다니는 경우 ("특별하지 않은" 보상이 0인 행동이 반드시 필요함 → why? 이를 통해서 실제로 보상 발생시, 어떻게 발생시켰는지를 찾아내기 위해 필요) 직.. 2021. 7. 6. [최소 신장 트리(MST, Minimum Spanning Tree)] 신장트리(Minimum Spanning Tree, MST) 그래프가 모든 노드를 포함하고 모든 노드가 연결 되어있으며 Tree의 속성을 만족하는 그래프를 말한다. 최소신장트리(Minimum Spanning Tree, MST) 신장트리 가운데 가중치의 합이 최소인 경우를 신장 트리라고 한다. 이런 MST를 찾아내는 기법이 크게 두 가지가 있다. 크루스칼 알고리즘(Kruskal’s algorithm) 간선을 오름차순으로 정렬하여, 사이클이 만들어 질 경우를 제외하고 추가하는 방식 디스조인트 셋(disjoint set)을 기본 자료구조로 활용한다. 크루스칼 알고리즘의 시간 복잡도는 O(ElogV)이다. 디스조인트 셋(disjoint set)관련해서는 다음 포스팅에서 기재하겠다. 프림 알고리즘(Prim Algo.. 2021. 5. 30. [Fibonacci에서의 세 가지(Recursion, Dynamic Programming,Bottom-Up Approach] Fibonacci를 구하는 방법은 총 3가지가 있다. Recursion int Fibo(int num) { if(num == 1) return 1; else if( num ==2 ) return 1; else return Fibo(num-1)+Fibo(num-2); } 재귀방식으로 짜는 방식은 이와 같이 반복이 일어난다. fibo(3)이 좌우로 두번 반복하는 낭비가 발생한다. 해당 방식은 시간복잡도가 O(2^n)으로 나타난다. Dynamic Programming(Memoization) 이와 같은 반복되는 낭비를 막기 위해 Memoization 방식을 사용한다. 즉 위에 fibo(3),fibo(2) fibo(1) fibo(0)의 값을 저장해 놓은 뒤에 재 사용하는 것이다. int Fibo(int num) .. 2021. 5. 30. [DFS와 BFS의 차이] DFS(깊이 우선 탐색) 인접하는 한 정점에서 갈곳이 없을 때 까지 탐색하고 되돌아와 다음 정점을 탐색하는 방법 대표적으로 백트래킹에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. //인접 행렬로 구현 void dfs(int x) { check[x] = true; for(int i = 1; i 2021. 5. 30. 이전 1 2 다음
