Go Gradually - Repository

691. Stickers to Spell Word - Streak 3

내 풀이 접근설명이 복잡하지만, 읽어보면 결국 가장 작은 수 안에 target 문자들 전부 포함시키는 최소 단어 수를 구하는 문제이다.이는 최단거리 문제와 유사하다.BFSDP조건에서 추가로 최적화할 부분이 없나 탐색해보자.target.length 16^50너무 크다.가장 부족한 단어부터 그리디하게 탐색하는 것이 최적해를 보장하나? -> Xtarget.length 중복조합 수식 (64 15)이것도 너무 크다.그래프를 target에서 시작하면 어떨까?깊이 16선택지 50가지가 맞나? 8가지여도 안되는데...(2^32)결국 중요한건 남은 문자열 정보이다. 이를 활용해보자.이를 2^15로 표현하면?32768그래서 이걸 어떻게 활용하느냐...여기서 차도가 없어 풀이를 봤습니다.정해백트래킹이었습니다~핵심 아이디어 ..

[강화학습] Policy Gradient Method

우리가 기존에 알고있던 DQN은 Q 함수를 하나의 신경망으로 근사하는 "정책 외 알고리즘"이다.즉, DQN은 행동을 했을 때 얻을 수 있는 기대 보상을 기준으로 판단하는 알고리즘이다.QN이 예측한 Q value들은 특정 정책에 따라 다음 동작을 선택하는데 쓰인다.동작을 선택하는 정책은 다양한데, 현재 우리는 입실론-그리디 정책 정도만 학습했다.그 외에도 Q value들에 소프트맥스 층을 적용해서 하나의 동작을 선택하는 등 다양한 정책이 가능하다. 그런데 신경망과 정책을 따로 두고 동작을 선택하는 대신, 신경망이 직접 동작을 선택하도록 훈련하면 어떨까?이 경우 신경망은 정책 함수(policy function)의 역할을 한다.이런 신경망을 정책 신경망, 줄여서 정책망(policy network)이라고 부른다..

295. Find Median from Data Stream - Streak 2

이번 문제는 다음 자료구조를 완성하라는 문제였다. 이런 유형의 문제는 릿코드만의 독특한 알고리즘 문제로, 라이브코테에서 만날 법한 문제였다. 가장 먼저 든 생각은 "중간을 찾는 자료구조"를 만드는 것이었다.두개의 스택을 이용해 큐를 만드는 것처럼,두 개의 우선순위 큐를 이용해 중간값을 유지하는 MedianFinder 클래스를 구현했다.class MedianFinder { PriorityQueue high = new PriorityQueue(); PriorityQueue low = new PriorityQueue(Collections.reverseOrder()); int count = 0; public MedianFinder() { } public void addNum(in..

188. Best Time to Buy and Sell Stock IV - Streak 1

내 풀이 접근현재 인덱스까지 구할 수 있는 최대 수익을 계산하려면이전 인덱스에 담겨 있는 최대 수익과, 그 인덱스부터 지금까지의 1회 최대 수익을 알고 있어야 한다.이는 카데인 알고리즘과 굉장히 유사하다고 판단했다. 따라서 DP를 이용해 현재 인덱스까지 가장 최적의 이익을 찾도록 했다.class Solution { public int maxProfit(int k, int[] prices) { int[][] dp = new int[prices.length + 1][k+1]; int ret = 0; for(int kk = 1; kk이래도 통과는 한다.하지만, 조건이 빡빡하다면 통과하지 못했을 것이다.좀 더 효율적인 해이전에 구할 수 있는 최대 이익을, 0~i까지 전..

지금 할 수 있으면 해라.지금 할 수 없으면 하지마라.지금 해야하면 해라.이번주에 한 것OpenAI Gym - MountainCar 학습 시도학습이 잘 이루어지지 않음좀 더 다른 기법들을 학습해볼 필요성을 느낌항암치료 보조카카오 공채 내용 살펴보기RabbitMQ Java/Spring AMQP 클라이언트 학습카페 알바 이번주에 하지 못한 것코틀린 코루틴 학습 할 일이 너무 많으니, 매일 우선순위 결정하는데 머리가 복잡해진다.조금 단순화할 필요성 느낌 다음주에 할 수 있는 것심층강화학습 인 액션리액트 튜토리얼핀잇 기능 요구사항 도출 & 백엔드 설계파드셉 분석다음주에 할 수 없는 것코틀린 코루틴 학습쿠팡커피 원두 종류 및 맛 분석(블렌딩 or 싱글오리진) 다음주에 해야하는 것USACO Gold - DP 번역..

지금까지 우리는 Gridworld 게임을 플레이하도록 심층 강화학습 알고리즘을 훈련하는 데 성공했다.하지만 두 모드의 경우 가능한 4x4 게임판 구성이 아주 많지는 않으므로, 그냥 가능한 모든 게임판 구성을 암기했을 가능성도 있다. 따라서 게임을 이기려면 알고리즘은 게임 플레이 방법을 실제로 배워야 한다.그러나 앞에서 본 잡음이 많은 손실 그래프가 말해 주듯이, 현재 우리의 심층 강화학습 모형은 Gridworld의 무작위 모드를 그리 잘 학습하지 못한다. 그럼 가치 갱신량들을 좀 더 고르게 만드는 또다른 기법을 살펴보자.학습 불안정성DQN 논문에서 딥마인드 팀은 개별 동작마다 QN의 매개변수들을 갱신하다보면 학습이 불안정해질 수 있음을 지적했다.Girdworld 게임처럼 보상이 희소한 환경, 즉 게임..

본 내용은 심층강화학습 인 액션 도서를 참고하여 작성되었습니다. 심층 강화학습 인 액션 - 예스24프로젝트로 배우는 심층 강화학습의 이론과 실제!이 책 『심층 강화학습 인 액션』은 환경이 제공하는 직접적인 피드백에 기반해서 환경에 적응하고 자신을 개선해 나가는 에이전트의 구현 방www.yes24.com 우리는 이전 글에서 Gridworld를 학습시켰고, 무사히 학습에 성공한?것을 알 수 있었다.하지만 이것은 게임의 '정적' 모드, 즉 가장 쉬운 버전이었다.mode='random'으로 다시 실험해보면 실망스러운 결과가 나온다.실망스럽지만 흥미로운 결과이다.이 결과를 자세히 살펴보면, 단순히 정적 모드에서의 움직임을 암기했다고 보는게 정확한 수준으로 그대로 움직인다. 학습 또한 'random' 모드로 수행..

본 내용은 심층강화학습 인 액션 도서를 참고하여 작성되었습니다. 심층 강화학습 인 액션 - 예스24프로젝트로 배우는 심층 강화학습의 이론과 실제!이 책 『심층 강화학습 인 액션』은 환경이 제공하는 직접적인 피드백에 기반해서 환경에 적응하고 자신을 개선해 나가는 에이전트의 구현 방www.yes24.com 과거에도 Q함수를 신경망으로 표현하려던 시도는 있었지만, 이는 다음과 같은 문제가 있어 해결하지 못했다.신경망 학습 연산의 비용이 감당 불가능했다.catastrophic forgetting 문제가 있었다. - ER(Experience Replay)신경망 자체의 편향을 제거하기가 어려웠다. - Target Network시대가 변화하며 GPU의 병렬 연산의 성능이 대폭 향상되었고,구글 딥마인드에서 2013년에..

배낭(knapsack) 문제는 보통 제한된 용량의 컨테이너에 물건들의 부분집합을 넣되, 물건과 관련된 어떤 양을 세거나(카운트) 최적화하는 문제를 다룬다.거의 항상 각 물건은 양의 무게를 가지며, 우리가 선택한 물건들의 총 무게는 어떤 수로 주어지는 컨테이너의 용량을 초과해서는 안 된다. 배낭 유형 문제의 변형으로는 다음과 같은 것들이 있다.0/1 배낭 문제: 물건들의 부분집합을 골라 총 가치를 최대화하되, 총 무게가 컨테이너의 용량을 넘지 않도록 한다.가능한 총 무게 찾기: 컨테이너 용량을 넘지 않게 임의의 부분집합으로 만들 수 있는 모든 총 무게를 구한다.정확히 채우는 경우의 수 세기: 총 무게가 정확히 컨테이너 용량이 되도록 하는 물건의 순서열이 몇 개인지 센다(순서가 중요할 수도 있고 중요하지 않..

RabbitMQ는 메시지를 수신하고 전달하는 메시지 브로커이다.이 글은 다음 RabbitMQ 튜토리얼을 Java 버전으로 따라가 본 상태라고 가정합니다.따라서, 주요 API의 스프링에서의 사용법을 언급하며,스프링부트의 org.springframework.boot:spring-boot-starter-amqp를 사용하고 있다고 가정합니다.만약 RabbitMQ가 처음이시라면, 다음 글을 순서대로 따라가보며 내부 원리를 이해해보시길 권장드립니다.[RabbitMQ Java] 가장 간단한 프로듀서-컨슈머 사용해보기 [RabbitMQ Java] 가장 간단한 프로듀서-컨슈머 사용해보기원래 RabbitMQ 는 할 생각이 없었고, Kafka를 해보려고 했는데Kafka Definitive Guide의 내용이 너무 방대해서 ..