jusang blog

SIMD(Single Instruction Multiple Data) SIMD란 병렬 컴퓨팅의 한 종류로, 하나의 명령어로 여러 개의 값을 동시에 계산하는 방식이다. 변수형 typedef union __declspec (intrin_type) __declspec (align( 16 )) __m128i { __int8 m128i_i8[ 16 ]; __int16 m128i_i16[ 8 ]; __int32 m128i_i32[ 4 ]; __int64 m128i_i64[ 2 ]; unsigned __int8 m128i_u8[ 16 ]; unsigned __int16 m128i_u16[ 8 ]; unsigned __int32 m128i_u32[ 4 ]; unsigned __int64 m128i_u64[ 2 ]; } __m128i ; 사용법 __declspec(align __declspec (align( 32 )) struct s1 { int a, b, c, d; // sizeof(struct s1)는 32. 16바이트가 덧붙여진다. }; __declspec (align( 8 )) struct s2 { int a, b, c, d; // sizeof(struct s2)는 16. }; __mm_loadu_si128 __m128i a; // 128bit aligned 자료형 __declspec (align( 16 )) short v1[ 6 ] = { 1 , 2 , 3 , 4 , 5 , 6 }; //short 단위로 채움 a = _mm_loadu_si128(( __m128i *)v1);   _mm_set1_epi32 __m128i b; // 128bit aligned 자료형 b = _mm_set1_epi32(( int ) 5 ); //in...

문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요. 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42840 문제 풀이 소스코드: #include <string> #include <vector> #include <iostream> #include <functional> using namespace std; template < typename T> class MaxHeap { vector<pair< int , T>> array; public: MaxHeap() {} void insert( int x, T item) { array.push_back(pair< int , T>(x, item)); int target = array.size(); while ( target > 1 && x > array[(target/ 2 )- 1 ].first) { array[target- 1 ].first = array[(target/ 2 )- 1 ].first; array[target- ...

  문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42746 문제 풀이 소스코드: #include <functional> #include <iostream> #include <vector> #include <string> using namespace std; template < typename T> class MaxHeap { private : vector<T> array; // c style //bool (*compare)(...); function< bool (T first, T second)> compare; static bool dcompare (T first, T second) { return first > second; } public: MaxHeap() { compare = this ->dcompare; } MaxHeap(function< bool (T first, T second)> usercompare) { compare = usercompare; } void insert(T x) { array.push_back(x); int target = array.size(); while ( target > 1 &...

문제 설명 각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다) 문제 링크 :  https://programmers.co.kr/learn/courses/30/lessons/42627 문제 풀이 ※ 참고 : 2차원 Minheap class https://github.com/juwith/jsutilspp/blob/master/sort-heap-2d/src/heapsort2d.cpp 소스코드 (CPP) #include <string> #include <vector> #include <iostream> using namespace std; template < typename T> class MinHeap { vector<pair< int , T>> array; public: MinHeap() {} void insert( int x, T item) { array.push_back(pair< int , T>(x, item)); int target = array.size(); while ( target > 1 && x < array[(target/ 2 )- 1 ].first) { array[target- 1 ].first = array[(target/ 2 )- 1 ].first; array[target- 1 ].second = array[(target/ 2 )- 1 ].second; //cout << "target = " << target << ", target/2 = " << ...

문제 설명 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요. https://programmers.co.kr/learn/courses/30/lessons/42626 소스코드(CPP) : #include <string> #include <vector> #include <iostream> using namespace std; class MinHeap { vector< int > array; public: MinHeap() {} void insert( int x) { array.push_back(x); int target = array.size(); while ( target > 1 && x < array[(target/ 2 )- 1 ]) { array[target- 1 ] = array[(target/ 2 )- 1 ]; //cout << "target = " << target << ", target/2 = " << target/2 << endl; ...

heap sort란? 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법입니다. 시간 복잡도는 n log(n) 입니다. 전체 소스 코드 :  https://github.com/juwith/jsutilspp/blob/master/sort-heap/src/heapsort.cpp Max heap - insert 아래와 같은 tree에 280을 추가한다고 가정해봅시다. 먼저 가장 끝 node에 index를 추가합니다. 새로운 노드와 부모노드를 비교하여 새로운 노드가 더 크다면 현재 노드를 부모노드랑 같은 값으로 만듭니다. 같은 과정을 최상위 노드까지 반복합니다. 최상위 노드까지 새로운 노드가 비교할 노드보다 크거나, 또는 새로운 노드가 부모노드보다 작다면 해당 노드를 새로운 노드로 설정합니다. 소스코드 void insert ( int x) { array.push_back(x); int target = array.size(); while ( target > 1 && x > array[(target/ 2 )- 1 ]) { array[target- 1 ] = array[(target/ 2 )- 1 ]; //cout << "target = " << target << ", target/2 = " << target/2 << endl; target /= 2 ; //cout << "target:" << target << endl; } //cout << "======end target========target:" << target << endl; array[target- 1 ] = x; } Max heap - pop max(delete) max heap은 항상 최상위 노드가 최대값이므로 최상위 노드를...

tree란? tree란 아래와 같은 구조로 여러 node가 한 node를 가르킬 수 없는 구조입니다. 다중트리 2진 트리 LCMS 구조 LCMS는 다중 트리의 구현 중 하나의 알고리즘 입니다. 다중트리 구현은 코드상 구현이 복잡하기 때문에 LCMS와 같이 2진 트리 형태로 구현을 하면 코드 복잡도를 줄일 수 있습니다. LCMS는 말 그대로 왼쪽 노드에 자식을 추가하고 오른쪽 노드에는 같은 레벨의 형제를 추가합니다. 다중트리는 아래와 같이 자식이 여러개가 될 수 있습니다. LCMS구조로 왼쪽 노드로는 자식, 오른쪽 노드는 형제를 추가하면 아래와 같습니다. 위의 그림은 어디서 본것같은 그림이지 않나요? 그림을 조금 바꿔서 그려보면 2진트리와 완벽하게 동일합니다. 즉 다중 트리를 2진화해서 단순하게 사용할 수 있는 방식이 LCMS라 할 수 있습니다. code 구현 C++ Add 노드를 2개 생성한 뒤 부모,자식을 연결해서 add합니다. 동일 부모로 노드를 생성한 뒤 add할 수 있습니다.   동일 노드로 생성되었다면 같은 부모를 갖는 두 노드는 오른쪽으로 이어지며 형제 관계입니다. void LCRS_tree::addNode(lcrs* parent, lcrs* child) { if (mlcrs == NULL ) { mlcrs = child; cout << "create root" << endl; return ; } if (parent->leftchild == NULL ) { parent->leftchild = child; //cout << "add left" << endl; } else { lcrs* mchild = parent->leftchild; while (mchild->rightsibling != NULL ) { mchild = mchild->rightsibling; } mchild->ri...