티스토리

Coding StudyRoom

검색하기

블로그 홈

Coding StudyRoom

jeus5771.tistory.com/m

1minair 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

머신러닝 개요 및 Supervised Machine Learning 보호되어 있는 글입니다. 공감수 0 댓글수 0 2023. 6. 26.
내가 보는 프로그래머스 벡터 중복 요소 제거 문제 문제 설명 : 숫자를 담은 벡터를 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 .. 공감수 0 댓글수 0 2022. 12. 30.
pseudorandom number(무작위 난수) 생성을 위한 NVIDIA cuRAND 라이브러리 - 2 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.. 공감수 0 댓글수 0 2022. 12. 28.
pseudorandom number(무작위 난수) 생성을 위한 NVIDIA cuRAND 라이브러리 - 1 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에서 .. 공감수 0 댓글수 0 2022. 12. 28.
Parallel computing (Dynamic Programming) - 5 / Nonserial Polyadic DP 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 행렬부.. 공감수 0 댓글수 0 2022. 12. 27.
Parallel computing (Dynamic Programming) - 4 / Serial Polyadic DP 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 계산이 필.. 공감수 0 댓글수 0 2022. 12. 26.
Parallel computing (Dynamic Programming) - 3 / NonSerial Monadic DP 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.. 공감수 0 댓글수 0 2022. 12. 26.
Parallel computing (Dynamic Programming) - 2 / Serial Monadic DP 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.. 공감수 0 댓글수 0 2022. 12. 26.
Parallel computing (Dynamic Programming) - 1 Dynamic Programming : Discrete optimization(이산 최적화) 문제들을 풀기 위해 일반적으로 사용됨. >> Discrete optimization : 문제의 해가 연속적이지 않다. 즉, 이산적이다. ex) 해 = [1, 2, 3, 4] 공감수 0 댓글수 0 2022. 12. 26.
C++ Stack(스택) STL Stack (스택) : LIFO (Last In First Out) 특징 - 나중에 들어온 값이 먼저 나온다 >> 마지막에 들어온 원소가 제인 먼저 나갈 수 있도록 하는 자료 구조. #include : stack 라이브러리 전처리 필요 stack 변수명 : stack 생성 멤버함수 push(데이터) : 데이터 삽입 (top에 원소 추가) size() : 현재 스택에 저장되어 있는 데이터의 갯수를 반환 top() : 현재 스택 최상위의 데이터를 반환 (데이터를 제거하지는 않는다) pop() : 현재 스택 최상위의 데이터를 제거 (top에 있는 원소를 삭제) >> 반환값 x (void) empty() : 현재 스택이 비었으면 true, 아니면 false 반환 ※ C++ explicit 키워드 : 컴파일러에 .. 공감수 0 댓글수 0 2022. 12. 9.
C++ < unordered_map> 사용법 C++ 에서 제공하는 map은 데이터를 정렬하여 저장. unordered_map은 정렬을 하지 않고 저장. unordered_map의 자료구조는 "해시 테이블"이다. : 좋은 경우 탐색 시간복잡도 O(1)이다. hash_function("key") : 해시함수에 key값을 대입하면 해시 테이블의 인덱스를 반환해줌 -> 이러한 인덱스를 가지고 배열로 구성된 hash table의 value 값에 상수시간 내에 접근가능. #include 선언 C++ STL 이기 때문에 using namespace std; 생성 unordered_map 변수명; ex) unordered_map um; 1. 삽입 insert( {key, value} ) , insert(make_pair(.. 공감수 0 댓글수 0 2022. 11. 20.
[C++] vector 주로 사용하는 것 정리 [C++] vector란? : 동적으로 메모리가 할당되는 배열. 컴퓨터에서 벡터란 1차원 배열의 데이터를 뜻한다. ★ 대부분의 STL 이 그렇듯. template을 사용하기 때문에 데이터 타입은 지정 가능하다. 헤더파일을 추가해야함 >> #include 선언 : vector 변수명 ex. vector v1; vector v2; vector의 멤버 함수 v.push_back(value) : 마지막 원소 뒤에 value값 삽입 v.insert(2, 3, 4) 2번째 위치에 3개의 4값을 삽입 (뒤엣값들은 뒤로 밀린다.) v.insert(2, 3) 2번째 위치에 3의 값을 삽입 v.pop_back() : 마지막 원소 제거 v.clear() : 모든 원소 제거 원소만 제거하고 메모리는 남아있다(size만 줄어들.. 공감수 0 댓글수 0 2022. 11. 13.
단백질 발현 최대 서열 찾는 MOABC 기반 유전 알고리즘 정리 MOABC (Multi-Objective Artificial Bee Colony) 알고리즘 : 같은 단백질 인코딩을 위한 여러 유전자 조합을 찾기 위해서 합성 생물학에서 단백질 발현을 향상하는 것이 중요한 목표이다. 방법으로 숙주(단백질 생산하는 개체)에게 해당 단백질을 인코딩하는 여러 유전자를 통합하는 것이다. ex) 하나의 단백질을 인코딩 하는 유전자를 n개를 통합하면? >> 이론상 n배로 단백질이 발현된다는 뜻. 여러 유전자를 숙주 게놈에 통합하는 것이 cost가 높기 때문에, 해결 방안으로 여러 유전자를 최대한 가까이 붙여서 숙주 게놈에 통합한다. 하지만, 약점이 있는데 CDS간에 염기 서열이 비슷하면 homologous recombination이 발생할 확률이 커지는데 이는 유전자들의 reduc.. 공감수 0 댓글수 0 2022. 11. 9.
유전 알고리즘 개요 최적화 문제를 해결하는 기법 중 하나이다. - 다윈의 적자생존 이론을 기본으로 한다. (좋은 것은 남고 안 좋은 것은 사라짐) 유전 알고리즘 : 문제에 가능한 해들을 정해진 형태의 자료구조(유전자)로 표현한 다음, 이들을 점차적으로 변형함으로써 점점 더 좋은 해들을 만들어 나가는 과정 해집단 설정(랜덤) >> 적합도 기반 선택 >> 교차 >> 변이 >> 대치(더 좋은 것으로 바꾼다) ○ 조건 - 해를 유전자 형식으로 표현하기 - 해가 얼마나 적합한지를 판단할 수 있어야 한다. (적합도 계산 필요) 1. 선택 : 교차에 쓰이는 두개의 부모해를 고르기 위한 연산 >> 우수한 해(적합도가 높은 것)일 수록 선택될 확률이 높아야 한다. 1. 1 토너먼트 선택 파라미터 T 설정 (사용자가 설정 하는 값) 두 개의.. 공감수 0 댓글수 0 2022. 11. 8.
HashTable, 해시 테이블 (내가 보기 위한 정리) HashTable이란? - >> Key값과 Value 값으로 데이터를 저장하는 자료구조. 내부적으로 배열을 이용하여 구현하기 때문에 빠른다. (상수 시간내에 찾을 수 있다.) Key 값을 해시 함수에 매개변수로 입력하여 Value 값이 저장된 배열의 인덱스 값을 찾는다. ex) hash_function(Key) --> return index array[index] = Value 해시 함수에서 중요한것! 고유한 인덱스 값을 설정하는 것이 매우 중요 즉, 해시 함수 구현이 중요하다. - 해시 함수는 주로 해시 테이블의 크기로 모듈로(%) 연산을 사용한다. 이 외에도 다양한 방법 가능. ** 해시 값이 충돌하는 경우 ** 해시 값이 충돌할 때 해결 방안 Separate Chaining 버킷에 Value만 저장.. 공감수 0 댓글수 0 2022. 11. 7.
KMP 알고리즘 (패턴 찾기) 시간복잡도 : O(N + M) N : 텍스트 길이 M : 패턴(탐색 문자열)의 길이 KMP 알고리짐에서 prefix(접두사) suffix(접미사)란? : 문자열에서 맨앞과 맨 뒤에어서 같은 문자열이 나오는 경우 ex) ABCAB -> 접두사 : AB, 접미사 : AB 핵심 아이디어 : 문자열이 불일치 할 때 앞서 탐색했던 정보를 이용하여 몇 칸 정도는 건너 뛴 후 탐색하겠다! Simple 비교할 문자열의 인덱스는 계속 증가한다!다만 패턴의 인덱스가 pi 배열의 접두사 접미사가 일치하는 정보를 기반으로 비교하는 패턴의 인덱스가 변하는 것이다.! 이동했을 때 또한 다르면 당시의 pi배열 접두사 접미사의 정보를 가지고 또 건너 뛸 수 있다! 건너 뛴 후 preifx와 suffix가 일치해야한다는 전제 조건이 .. 공감수 0 댓글수 0 2022. 11. 3.
내가 보기 위한 OpenMP 사용법 #pragma -> 컴파일러에게 뒤에 오는 내용에 따라 어떤 일을 하라는 전처리명령 1. pragma omp parallel (option) : 구문을 병렬로 실행한다. thread 수만큼 실행된다. >> 여러 thread에서 병렬로 실행할 코드인 병렬 영역을 정의한다. #pragma omp parallel // 병렬처리 할 한줄 #pragma omp parallel { // 병렬처리 할 여러줄 } - Option ▣ if(조건) : 조건이 true일 때만 병렬처리 한다. ▣ num_threads(n) : n개의 thread로만 병렬처리 한다. ▣ private(var) : 변수 var를 각각 copy 해서 사용. 병렬처리 지역 이전의 초기화가 무의미함. >> 병렬처리 지역 내부에서 초기화 필요! 각 쓰.. 공감수 0 댓글수 0 2022. 10. 27.
Visual Studio 디버깅 단축키 F9: 중단점 지정 / 해제 F10 : 프로시저 단위 코드 실행 -> 함수 단위 코드 실행 F11 : 한 단계씩 코드 실행 Shift + F11 : 함수 외부로 탈출 F5 : 계속 실행 ( 다음 중단점 위치 까지 실행) / 디버그 실행 모드 Shift + F5 : 디버그 실행 중지 조사식 -> 원하는 식을 입력하여 값을 확인해 볼 수 있다. 공감수 0 댓글수 0 2022. 10. 27.
Visual studio 단축키 정리 ctrl + f: 찾기 (enter 아래로 검색 shift + enter 위로 검색) alt + shift + enter: 전체화면 ctrl + tab: 창 선택 shift + esc: 창 닫기, ctrl + F4: 문서내 창 닫기 ctrl + alt + L: 솔루션 탐색기 창 F4: 속성창 공감수 3 댓글수 1 2022. 10. 5.
NP 정의 보호되어 있는 글입니다. 공감수 0 댓글수 0 2022. 6. 3.
Union, Find 보호되어 있는 글입니다. 공감수 0 댓글수 0 2022. 6. 2.
CNN (Convolutional Neural Network) CNN: computer vision에서 많이 사용됨(이미지 처리) 이미지의 공간 정보를 유지한 상태로 학습이 가능한 모델 이미지의 특징을 추출하는 부분 + 클래스를 분류하는 부분 특징 추출 영역: Convolution Layer와 Pooling Layer(optional)를 여러 겹 쌓는 형태로 구성됨. CNN 마지막 부분에는 이미지 분류를 위한 Fully Connected Layer가 추가된다. Convoution(합성곱) Layer? 이미지 --> 3D tensor로 표현 가능. 위치값(height, width) + 색(channel) Filter 적용 하나의 convolution layer에는 입력되는 이미지의 채널 개수만큼 필터가 존재 -> 각 채널에 할당된 필터를 적용함으로서 convoluti.. 공감수 0 댓글수 0 2022. 5. 29.
NP 도입부 보호되어 있는 글입니다. 공감수 0 댓글수 0 2022. 5. 29.
Finding the Lower Bound 보호되어 있는 글입니다. 공감수 0 댓글수 0 2022. 5. 29.
8-Puzzle Problem (Branch & Bound) 보호되어 있는 글입니다. 공감수 0 댓글수 0 2022. 5. 23.
TSP Traveling Salesman Problem(Traveling Sales-Person Problem) minimization optimization 조합 최적화 문제 택배 배달 시스템. 1,000개 boxes -> 가장 먼저 퇴근경로? h-value estimation in TSP Minimization Optimization: h = under-estimate -> TSP : under-estimation ==> 실수 X. incorrect prune X. -> 0 h = h* - alpha(smaller) #include using namespace std; const int N = 4;// 노드 수 int final_path[N + 1];// 경로 저장 .. 공감수 0 댓글수 0 2022. 5. 20.
0/1 Knapsack Example 0/1 Knapsack Example using Branch&Bound #include #include #include using namespace std; struct Item { double weight; // 무게 int value; // 가치 }; struct Node { int level, profit, bound; double weight; }; bool cmp(Item a, Item b) { double r1 = a.value / a.weight; double r2 = b.value / b.weight; return r1 > r2; } // bounding function int bound(Node u, int n, int W, Item arr[]) { if (u.weight >= W) re.. 공감수 0 댓글수 0 2022. 5. 12.
Branch & Bound 알고리즘 Backtracking = DFS visit + bound function --> DFS를 BFS visit으로 전환하면? --> Branch and Bound. Backtracking = DFS + bound function Branch&Bound = BFS + bound function --> 차이는 DFS vs BFS. Q1. DFS vs BFS 장단점을 논하시오. --> in practice, Branch&Bound >> Backtracking. --> BFS: 신뢰성이 더 좋음 Q2. f = g + h tree traverse(child visit)순서에 따라, g value, h value는 update 차이 발생 ** 미.. 공감수 0 댓글수 0 2022. 5. 11.
Knapsack 보호되어 있는 글입니다. 공감수 0 댓글수 0 2022. 5. 11.
N Queen Problem #include #define N 4 using namespace std; void printSolution(int board[N][N]) { for (int i = 0; i = 0 && i = N) return true; for (int i = 0; i .. 공감수 0 댓글수 0 2022. 5. 10.

728x90

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.