Go Gradually - Repository

410. Split Array Largest Sum - Streak 17

이분탐색 문제이다.너무 이분탐색이라 설명을 건너뛰고 주석으로 설명한다.class Solution { public int splitArray(int[] nums, int k) { int lo = 0; for(int i = 0; i upperbound){ now = 0; nowSubArrCnt++; // 배열의 수가 k개보다 많아지면 실패 if(nowSubArrCnt == k) return false; } now += nums[i]; } return true; }}

84. Largest Rectangle in Histogram - Streak 16

그리디하게 스위핑하는 아이디어가 떠오른다. 스택으로 높은 박스를 추가하면서, 계속 세지 말고, 스택에서 pop할때만 넓이를 계산하면 된다. 그렇다면 왼쪽 끝의 기준을 어떻게 잡아야 할까? 이런 경우, 전체 조건 내의 부분집합을 모두 포함했는지 검사해보면 디버깅하기 용이하다.즉, 누락된 조건이 없는지 체크해보는 것이 좋다.왼쪽에 나보다 큰 수가 있었으면 -> 거기도 내 넓이에 포함됨왼쪽에 나보다 작은 수밖에 없으면 -> 지금 내 자리부터 넓이에 포함임class Solution { public int largestRectangleArea(int[] heights) { int n = heights.length; Deque s = new ArrayDeque(); int..

DRL 환경 - 전이 함수의 설계

DRL을 이용하여 새로운 문제를 해결하려면 일단 환경이 존재해야 한다.환경의 구현을 위해 디지털 트윈(Digital Twin)과 같은 환경을 구성하는 다양한 방식들이 논의되고 있지만, 그 모든 환경의 구현 이전에는 문제의 모델링이 우선되어야 한다. 강화학습의 문제 모델링에 대해서는 다음 네 가지를 고려해야 한다.상태행동보상전이함수이번 글에서는 이 중 전이 함수에 집중해서 알아볼 것이다.이번 내용은 다음과 같은 순서로 진행할 것이다.먼저, 전이 함수로 구현할 수 있는지 여부를 파악한다.이후, 전이 함수의 형태를 결정한다.마지막으로, 구현한 전이 함수가 현실을 충분히 반영하고 있는지 확인한다.실현 가능성 확인전이 함수가 P(s_t+1|s_t, a_t)로 정의된다는 사실을 다시 떠올려보자.전이 함수는 마르코프..

DRL 환경 - 보상의 설계

DRL을 이용하여 새로운 문제를 해결하려면 일단 환경이 존재해야 한다.환경의 구현을 위해 디지털 트윈(Digital Twin)과 같은 환경을 구성하는 다양한 방식들이 논의되고 있지만, 그 모든 환경의 구현 이전에는 문제의 모델링이 우선되어야 한다. 강화학습의 문제 모델링에 대해서는 다음 네 가지를 고려해야 한다.상태행동보상전이함수이번 글에서는 이 중 보상에 집중해서 알아볼 것이다.보상의 역할보상 신호는 에이전트가 최대화해야 하는 목적 함수(objective function)를 정의한다.보상 설계는 강화학습의 근본적인 문제 중 하나이고, 환경에 대한 깊은 지식이 필요한 영역이며, 여러 가지 이유로 인해 해결하기 어려운 문제로 알려져 있다.보상이 양의 부호인가? 음의 부호인가? 혹은 0인가?보상의 크기(스칼..

DRL 환경 - 행동의 설계

DRL을 이용하여 새로운 문제를 해결하려면 일단 환경이 존재해야 한다.환경의 구현을 위해 디지털 트윈(Digital Twin)과 같은 환경을 구성하는 다양한 방식들이 논의되고 있지만, 그 모든 환경의 구현 이전에는 문제의 모델링이 우선되어야 한다. 강화학습의 문제 모델링에 대해서는 다음 네 가지를 고려해야 한다.상태행동보상전이함수이번 글에서는 이 중 행동에 집중해서 알아볼 것이다.행동을 구현하는 데에는 다음 두가지를 고려해야 한다.행동의 완결성(completeness)원하는 모든 것을 제어할 수 있게 해주는가?행동의 복잡성(complexity)행동의 최소 단위를 어느정도의 수준으로 둘 것인가?우선, 행동의 설계를 몇 가지 확인하고, 각 질문에 대한 상세한 정보를 알아보자.행동의 설계행동의 표현행동은 보통..

DRL 환경 - 상태의 설계

DRL을 이용하여 새로운 문제를 해결하려면 일단 환경이 존재해야 한다.환경의 구현을 위해 디지털 트윈(Digital Twin)과 같은 환경을 구성하는 다양한 방식들이 논의되고 있지만, 그 모든 환경의 구현 이전에는 문제의 모델링이 우선되어야 한다. 강화학습의 문제 모델링에 대해서는 다음 네 가지를 고려해야 한다.상태행동보상전이함수이번 글에서는 이 중 상태에 집중해서 알아볼 것이다. 상태를 구현하는 데에는 다음 세가지를 고려해야 한다.상태의 완결성(completeness)상태의 표현이 세상이 제공하는 정보가 충분히 포함되어 있어서 문제를 해결하는 데 무리가 없는가?상태의 복잡성(complexity)상태의 표현이 얼마나 효과적이고 상태의 표현을 위해 요구되는 계산량은 얼마인가?상태 정보 손실(informat..

212. Word Search II - Streak 15

보드의 크기는 최대 12x12로, 순수하게 DFS를 수행한다면 4^144의 시간복잡도가 된다. 하지만 문제의 제약조건을 잘 살펴보면, 단어의 길이가 최대 10자인 것을 확인할 수 있고, 즉 우리는 최대 10개의 글자만 살펴보면 된다. 이는 DFS의 과정이 O(4^10) 으로 제한됨을 의미한다.이를 보드의 각 칸(144개의 칸)에 수행해보면 된다. 그렇다면 이제 각 단어가 실제로 존재하는지를 매칭해보면 되는데, 확인해봐야 하는 단어는 총 3만개이다.이를 일일히 매칭해보는 것은 당연히 시간초과일 것이다. 그래서 word를 해시맵으로 바꾸는 것도 생각해볼 수 있다.하지만 이번엔 단순히 Trie를 이용하는 방식을 선택했다.트라이를 사용하게 되면, 해시맵을 이용한 완전탐색과 달리 트라이 아래에 더이상 노드가 존재..

MountainCar - Policy Gradient Methods, 그리고 회귀

다양한 알고리즘의 고민이전 글에서 이것 저것 수행해보고 난 뒤, 좀 더 다양한 기법들에 대해 트레이드오프를 이해할 필요성을 느낀 나는 다양한 알고리즘을 공부했다. 하지만 이번 MountainCar 환경에서는, 결국 DQN으로 다시 회귀할 수밖에 없었다.그 근거는 다음과 같다.나는 최근 다양한 정책 경사 알고리즘들을 공부해왔는데, 각 알고리즘은 해결하고자 하는 문제가 현재 MountainCar 의 상황과 맞지 않았다.하이퍼파라미터 튜닝은 예술의 영역이고, 숙련자들 또한 기존에 푼 문제와 논문에 존재하는 하이퍼파라미터를 참고하여 하이퍼파라미터를 설정한다는 것을 확인했다. REINFORCEREINFORCE는 가장 기초적인 Policy Gradient Method로, 다음과 같은 이점과 한계를 갖고 있다.이점정..

강화학습의 신경망 선택 방법

모든 DRL 환경은 순차적 데이터를 생성하는 것으로 해석될 수 있다.RNN이 이러한 유형의 입력을 다루는 데 특화되어 있다고 알고있는데, 그렇다면 DRL은 왜 항상 RNN이나 CNN-RNN구조를 사용하지 않을까? 이에 대한 제대로된 이해를 위해선 우선 MDP와 POMDP의 차이에 대해 이해할 필요가 있다. 환경의 두 가지 특성얼마나 관측 가능한가상태 공간의 특성이 무엇인가MDP와 POMDPMDPMDP는 의사결정을 모델링하는 수학적 프레임워크다. MDP의 핵심은 상태 s_t가 다음 상태 s_t+1로 전이하는 방법을 모델링하는 전이 함수이다.MDP 전이 함수는 다음 식으로 표현될 수 있다.전이 함수는 마르코프 특성을 갖는다.즉, s_t+1로의 전이는 전적으로 현재 상태와 행동 (s_t, a_t)에 의해 결정..

DRL에서의 디버깅 방법, 하이퍼파라미터 설정

사실 DRL은 디버깅 과정이 과학이라기보다는 예술에 더 가깝다.디버깅을 잘하려면 딥 러닝 소프트웨어의 특이한 점들과 수치 계산, 그리고 하드웨어에 대해 직접 무언가를 해보면서 경험을 많이 해볼 필요가 있다.난이도가 높은 프로젝트에서는 언제나 그렇듯이, DRL을 작동시키려면 엄청난 끈기가 필요하다. 디버깅의 주요 목적은 실패의 근본적인 원인 탐색이다.디버깅 과정은 본질적으로 문제 해결의 과정이며 오류가 의심되는 다양한 부분을 체계적으로 확인하면서 오류를 찾아내는 과정이다.여기서 중요한 것은 체계적으로 한다는 것이다. 오류라고 추측되는 의심스러운 부분들을 오류 가능성이 높은 순으로 나열해 놓고, 가능하면 독립적으로 하나씩 테스트해야 한다.테스트가 실패할 때마다 오류 의심 항목을 하나씩 지우면서 다음 항목을 ..