본문 바로가기

::public265

기수 정렬(Radix Sort) 버킷 정렬(bucket sort)라고도 함. 먼저 들어간 숫자들이 먼저 나와야함.(queue) 숫자의 자릿수 값을 비교하는 정렬. LSD(least significant digit) ;가장 낮은 자릿수부터 MSD(most significant digit) ;가장 높은 자릿수부터 시간복잡도 k개의 자릿수를 가지기에 O(kn) 이지만 일반적으로 O(n) 로 표현. #include #define BUCKETS 10 // 10진수 #define DIGITS 4 // 4자릿수 테스트 void radizSort(int arr[], int n) { queue que[BUCKETS]; int factor = 1; for (int d = 0; d 2019. 9. 6.
스킬트리 *스킬트리 선행 스킬 순서를 지켜야 하고 배운 순서가 뒤바뀌면 사용 불가능. 이전 스킬을 배워야 이후 스킬을 배움. 안배우면 사용 불가능. #include #include #include using namespace std; int solution(string skill, vector skill_trees) { int answer = 0; vector learned; for (int i = 0; i 2019. 9. 5.
평균 구하기 *평균 구하기. 정수를 담고 있는 배열 arr의 평균값을 리턴. #include #include #include using namespace std; double solution(vector arr) { double answer = accumulate(arr.begin(), arr.end(), 0); return answer / arr.size(); } Colored by Color Scriptercs 2019. 9. 5.
제일 작은 수 제거하기 *제일 작은 수 제거하기. 가장 작은 수를 제거. 빈 배열이면 -1을 채워 리턴. #include #include #include using namespace std; vector solution(vector arr) { vector answer; vector::iterator iter; iter = min_element(arr.begin(), arr.end()); arr.erase(iter); if(arr.size() == 0) arr.push_back(-1); answer = arr; return answer; } Colored by Color Scriptercs 2019. 9. 5.
정수 제곱근 판별 *정수 제곱근 판별 임의의 정수 n에 대해 어떤 정수 x의 제곱인지 아닌지 판단. n이 x의 제곱이면 x+1의 제곱 리턴. 아니면 -1 리턴. #include #include using namespace std; long long solution(long long n) { long long answer = 0; double d = sqrt(n); int i = sqrt(n); if(d - i == 0) answer = pow(i + 1, 2); else answer = -1; return answer; } Colored by Color Scriptercs 2019. 9. 5.
체육복 *체육복(탐욕법 Greedy) 전체 학생의 수 n, 체육복을 도난당한 학생 lost[], 여분 학생 reserve[] reserve[] +1, -1 번호 학생에게 빌려줄수 있음. 수업을 들을 수 있는 학생의 최대값 #include #include #include using namespace std; int solution(int n, vector lost, vector reserve) { int answer = 0; vector in; in.assign(n + 2, 1); for(int i = 0; i 2019. 9. 5.

티스토리툴바