Coding StudyRoom

보호되어 있는 글입니다.

문제 설명 : 숫자를 담은 벡터를 input 값 으로 받는다. 벡터에서 연속된 숫자 부분은 한번만 저장되도록 바꾼다. ex) [1,1,1,3,3,0,1,1] >> [1,3,0,1] 간단하게 짧은 line으로 푼 풀이가 있어서 작성한다. #include #include #include using namespace std; vector solution(vector arr) { arr.erase(unique(arr.begin(), arr.end()),arr.end()); vector answer = arr; return answer; } C++ vector의 erase 멤버 함수 iterator erase (const_iterator position); iterator erase (const_iterator ..

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..

cuRAND 라이브러리 : pseudorandom number(무작위 난수) 와 quasirandom number(준 난수) 생성을 위한 라이브러리 cuRAND 라이브러는 library on the host(CPU)와 device(GPU) 헤더 파일 두 가지로 구성 1. host에서 라이브러리 함수 호출 시 device global memory에 난수가 저장되고, 이를 host memory로 복사해 와서 사용할 수 있다. 2. device 헤더 파일은 random number generator(난수 생성기) state 세팅하기 위한 device 함수와, sequences of random numbers를 생성하는 것이 정의됨. 즉, host code에서 host library를 사용해서 device에서 ..

Nonserial Polyadic DP : next level의 optimal solution 계산을 위해 바로 이전 level의 optimal subsolution 이외에 다른 것도 필요할 수 있으며 + functional equation에 재귀 식이 여러 개 인 경우. 예제 문제1) Optimal Matrix-Parenthesization Problem (Matrix Chain Multiplication) 문제 설명 : - A1, A2 ... Ai matrix 가 존재하고 순서대로 곱했을 때 행렬 곱 연산이 가능 (row와 columm 크기가 매칭된다는 의미) 이 때 행렬 곱을 위해 행렬을 괄호로 묶었을 때 최소 연산 횟수를 찾는다. functional equation C[i, j] : A i 행렬부..

Serial Polyadic DP : next level의 optimal solution 계산을 위해 이전 level의 optimal subsolution을 사용하고, functional equation에 여러 재귀 함수가 필요한 경우. 예제 문제1) Floyd's All-Pairs Shortest-Paths Algorithm 문제 설명 : 모든 노드 간의 쌍에 대해서 최단 거리를 구하는 문제. >> 결과는 행렬로 나오고 0번 노드부터 n번 노드까지 각 노드까지 경유를 고려했을 때 최단거리를 계산해 나가면서 계산한다. functional equation 좌항 : k는 노드 번호, 0번 노드 부터 k - 1 노드 까지 고려해서 경유한 경우 최단 거리를 저장하고 있다. (각 level 마다 n^2 계산이 필..

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]

Stack (스택) : LIFO (Last In First Out) 특징 - 나중에 들어온 값이 먼저 나온다 >> 마지막에 들어온 원소가 제인 먼저 나갈 수 있도록 하는 자료 구조. #include : stack 라이브러리 전처리 필요 stack 변수명 : stack 생성 멤버함수 push(데이터) : 데이터 삽입 (top에 원소 추가) size() : 현재 스택에 저장되어 있는 데이터의 갯수를 반환 top() : 현재 스택 최상위의 데이터를 반환 (데이터를 제거하지는 않는다) pop() : 현재 스택 최상위의 데이터를 제거 (top에 있는 원소를 삭제) >> 반환값 x (void) empty() : 현재 스택이 비었으면 true, 아니면 false 반환 ※ C++ explicit 키워드 : 컴파일러에 ..