Coding StudyRoom

Device API Overview : user kernel 작성 시 kernel에서 난수 생성 후 사용하기 위함 #include "curand_kernel.h" 필요 curand_init()으로 generator state initialize 후, curand() 사용 시 무작위 난수 반환. 같은 generator state에서 curand()를 호출하면 같은 값을 반환. >> thread 당 device global memory에 generator state 값을 저장하는 변수를 할당하여 난수 생성이 끝난 후 state 값을 저장해야 해당 thread 에서 다음 호출 시 해당 state 부터 난수값 반환 가능 한 것 같다 . 즉, 겹치지 않게 생성 XORWOW generator가 defalut gen..

NonSerial Monadic DP : next level의 optimal solution을 계산하기 위해서 바로 이전 level의 optimal subsolution이 아닌 다른 것을 사용 + functional equation에 재귀 식이 한번 사용되는 경우. 예제 문제1) Longest-Common-Subsequence 문제 설명 : 두 문자열의 최장 공통 부분수열을 찾는다. >> 문자열 같은 부분 건너뛰기 가능 fuctional equation F[i, j] : 한 문자열의 i index 까지, 다른 문자열의 j index 까지의 최장 공통 부분수열의 길이를 저장. * Table entries are computed in a diagonal sweep from top-left to the bot..

Serial Monadic DP : next solution의 최적 해를 구하기 위해 바로 이전 level의 subproblem의 최적 해의 값이 사용되고, 이러한 DP 식에서 재귀식이 한 개인 경우. 예제 1) The Shortest-Path Problem (최단 경로 문제) : 시작 노드(S)에서 끝 노드(R) 까지의 최단 경로를 구하는 문제이다. 문제설명 : - weighted multistage graph(다단계 그래프) 이고 r + 1 개의 levels로 구성되었다. 예시 그림) - level i의 모든 노드들은 level i + 1 의 모든 노드들과 연결되어 있다. (그림과는 다름) - level 0 은 시작 노드(S), level r 은 끝 노드(R)로 노드가 1개 뿐이다. functiona..

Dynamic Programming : Discrete optimization(이산 최적화) 문제들을 풀기 위해 일반적으로 사용됨. >> Discrete optimization : 문제의 해가 연속적이지 않다. 즉, 이산적이다. ex) 해 = [1, 2, 3, 4]