728x90 c언어 알고리즘3 c언어 - 퀵 정렬 (QuickSort) 퀵 정렬은 이름처럼 빠른 정렬이다. 퀵 정렬은 적절한 하나의 기준(피벗)을 잡고 피벗을 기준으로 삼아 값들을 정렬해나간다. 피벗(pivot)을 어떻게 설정하느냐에 따라 정렬 시간에 큰 영향을 준다. 그래서 최악의 경우 O(n^2)의 시간이 걸릴 수 있다. 피벗을 기준으로 작은 값은 왼쪽 큰 값은 오른쪽으로 보내면서 정렬해간다. 정렬할 리스트가 1~0일때 까지 반복하는 정렬이다. 글로 설명하는건 쉬우나 코딩할때 조금 꼬일수있으니 주의하면서 코딩해보자. low, high 을 좌표로 잡고 피벗과 비교하면서 low 는 피벗보다 큰 수를 high 는 피벗보다 작은수를 서로 교환한다. low 와 high가 교차하는 순간 low 와 피벗을 교체한다. 그리고 피벗을 기준으로 -1, +1 한 값을 재귀함수를 이용하여 퀵.. 2020. 12. 25. C언어 - 조합 알고리즘 [nCr] 경우의 수 순열을 프로그래밍화 (나열, 카운팅) 조합이란? - 서로 다른 n개에서 순서를 고려하지 않고 r개를 선택하는 방법의 수 구현 방향 - n의 원소의 갯수가 늘어날 수록 for문의 중첩이 계속 늘어나야 한다. - for문으로 구현할 경우 중첩이 많아질경우 효율이 떨어지고 n과 r의 값이 변할때마다 코드를 수정해줘야한다. - 재귀함수를 사용해서 문제를 풀어보도록 하자. 코드 #include int arr[] = {1,2,3,4,5}; //전역 변수로 선언 int Copy[5]; //arr배열을 복사하기 위한 배열 void print_Comb(int count); void Combination(int n,int r,int c); void print_Comb(int count){ for(int i=0;i 2020. 7. 10. C언어 - 순열 알고리즘 [nPr] 경우의 수 순열을 프로그래밍화 (나열, 카운팅) 순열이란? - 서로다른 n개에서 중복 없이 r개를 택하여 나열하는것을 순열이라 한다. nPr (Permutation) 구현 방향 - n의 원소의 갯수가 늘어날 수록 for문의 중첩이 계속 늘어나야 한다. - for문으로 구현할 경우 중첩이 많아질경우 효율이 떨어지고 n과 r의 값이 변할때마다 코드를 수정해줘야한다. - 재귀함수를 사용해서 문제를 풀어보도록 하자. 코드 #include int arr[] = {1,2,3,4}; //전역 변수로선언. 동적 할당이 효율적임 void swap(int *a, int *b ){ //값을 이동하기 위한 함수 int tmp; tmp = *a; *a = *b; *b = tmp; } void print_arr(int size).. 2020. 7. 3. 이전 1 다음 728x90
