알고리즘(7)
-
DQN, A3C
DQN (Deep Q Network) DQN is learning using deep learning neural networks such as CNN. Method of storing samples obtained from each time step, randomly selecting these samples to configure and update them into mini-batches. Existing RL, once it start learning in a bad way, it continue learning in a bad way. The problem is solved by randomly extracting and breaking the correlation between samples...
2021.11.23 -
[BOJ] Greedy Algorithm / 16단계
1 11047 동전 0 동전의 조건이 특별해서 동적 프로그래밍보다 빠르게 답을 찾을 수 있는 문제 import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException{ BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer bd = new StringTokenizer(bfr.readLine()); int T = Integer.parseInt(bd.nextToken()); int money = Integer.parseInt(bd.nextT..
2021.05.24 -
[BOJ] dynamic programming / 14단계
1 1003 피보나치 함수 단순 재귀로 피보나치 수를 구하면 왜 느릴까요? 함수 호출의 개수가 기하급수적으로 늘어나기 때문입니다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(bfr.readLine()); for(int i=0; i
2021.03.19 -
[BOJ] 15단계 / Greedy Algorithms
1 11047 동전 0 동전의 조건이 특별해서 동적 프로그래밍보다 빠르게 답을 찾을 수 있는 문제 import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException{ BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer bd = new StringTokenizer(bfr.readLine()); int T = Integer.parseInt(bd.nextToken()); int money = Integer.parseInt(bd.nextT..
2021.03.14 -
동적계획법(Dynamic Programming) / Memoization
-동적계획법 (dynamic programming) 복잡한 문제를 간단한 여러개의 문제로 나누어서 푸는 방법. 부분문제반복과 최적부분구조를 가지고있는 알고리즘을 일반적인 방법보다 더 적은 시간내에 풀 때 사용. 문제를 여러개의 하위 문제(subproblem)로 나누어 품. 이 하위문제들을 결합하여 최종적인 문제에 도달하는 것. 메모이제이션(memoization) 컴퓨터 프로그램이 동일한 계산을 반복할 때, 이전에 계산한 값은 메모리에 저장해서 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술. 동적 계획법의 핵심 기술. 처음 방문하는 재귀문제면 계산을 통해 얻은 값을 메모리에 저장, 이 후 재방문을 하면 계산하지 않고 저장 된 값 사용. ex) import java.util.Sc..
2021.03.05 -
Backtracking
백트래킹(=퇴각검색) , 일종의 트리 탐색 알고리즘.해를 찾아가는 중에 막히면 다시 이전으로 돌아가서 해를 찾아가는 기법으로, 최적화 문제와 결정 문제를 풀 때 사용. 더보기- 깊이우선탐색 (Depth First Search, DFS)- 너비우선탐색 (Breadth First Search, BFS) - 최선우선탐색 (Best First Search/Heuristic Search) 모든 경우의 수를 검색 > DFS.트리의 깊이가 무한대이면 BFS DFS는 가능한 모든 경로를 탐색함. 일일이 하나씩 체크해보면서 노가다하는 탐색임.백트래킹은 DFS 방식과 비슷한데, DFS처럼 해를 찾아가는 중에, 다음에 갈 경로로 하면 해가 절대 안나올것 같으면 그 경로는 가지않고 되돌아감.이렇게 조건을 설정해서 안가는 경로..
2021.02.19 -
[백준] 11단계 문제 모음
11 브루트 포스 가장 간단한 알고리즘인, 모든 경우의 수를 검사하는 브루트 포스 알고리즘을 배워 봅시다. 1 2798 블랙잭 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scan = new Scanner(System.in); int T = scan.nextInt(); int Max = scan.nextInt(); int n[] = new int [T]; for(int i = 0; i
2021.02.07