전체 글
-
qsort() in Cps 2024. 8. 28. 10:37
#include void qsort( void *base, size_t number, size_t width, int (__cdecl *compare )(const void *, const void *));base : 정렬할 것number : 정렬 요소의 수width : 정렬 요소의 크기compare() : 비교 기준 함수 (오름차순 기준으로 a>b이면 1 , a 사용 예제qsort(arr, n, sizeof(Pos), compare) // quick sort 관련 문제BOJ 11650 좌표 정렬하기#include #include typedef struct _pos{ int x; int y;} Pos;int compare(const void *a, const void *b){..
-
Counting sortps 2024. 8. 26. 10:40
$$ O(n) $$ 입력 값의 범위가 작은 경우 유용하게 쓰이는 알고리즘 1. arr1 에서 각 값이 등장하는 횟수를 countfor(int i=0; i 2. count 한 값을 누적합 계산for(int i=1; i 3. arr2[누적합-1]에 arr1 값 inputfor(int i=n; i>0; i++) arr2[--count[arr[i]]] = arr1[i] arr1 : 기존 데이터arr2 : 정렬된 데이터 관련 문제BOJ 10989 수 정렬하기 3입력 범위$$ 1 \leq n \leq 10,000,000 $$ $$ 1 \leq num \leq 10,000 $$#include int main(){ int n, num; int count[10000] = {0}; scanf("%d"..
-
시간복잡도2 BOJ 24267ps 2024. 8. 19. 11:18
MenOfPassion(A[], n) { sum 나의 풀이$$ \sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1}\sum_{k=j+1}^{n}1 $$ $$ =\sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1}(n-j) =\sum_{i=1}^{n-2}\left\{\sum_{j=i+1}^{n-1}n-\left ( \sum_{j=1}^{n-1}j-\sum_{j=1}^{i}j \right )\right\} $$$$ =\frac{(n-2)(n-1)n}{6} $$ 다른 풀이$$ _nC_3 = \frac{n!}{(n-3)!3!} $$ 입력값 n개 숫자 중에서 3중 for loop에서 선정될 3개의 값을 순차적으로 ((i
-
시간초과 feat.O(1)ps 2024. 8. 8. 10:37
BOJ 2869번 문제 시간제한 0.25초 for loop 1억번당 대략 1초라고 한다입력 범위가 10억까지이니 아래와 같은 코드는 시간제한이 발생할 수 있다 while(1) { day++; sum += a; if(sum >= v) break; sum -= b; } printf("%d", day); for loop가 아닌 O(1)로 계산할 수 있는 방법을 찾아야 한다방법은 아래와 같다 day = (v-a) / (a-b); mod = (v-a) % (a-b); if(mod == 0) day++; else day = day + 2; printf("%d", d..
-