반응형 정렬3 [C] 백준 3273번: 두 수의 합 문제에 탐색, 정렬 알고리즘을 바로바로 적용시키는 연습을 한창 하고있다. 안한지 꽤 오래돼서 파악하는데 좀 걸린다. 이번 문제 역시 문제는 쉽지만 제한시간을 맞춰야하기 때문에 정렬과 탐색을 적절히 사용해야 한다. 나는 시간복잡도 O(n * log n)으로 했다. 입출력 예시 정답코드 #include #include void quickSort(int *, int, int); int inPlacePartition(int *, int, int, int); int search(int *, int, int); int main() { int n; int x; int *arr; int i; int tmp; int count = 0; scanf("%d", &n); arr = (int *)malloc(sizeof(int.. 2018. 10. 28. [C] 단일연결리스트 합병정렬 (singly linked list merge sort) 합병정렬에 관한 포스팅은 따로 알고리즘 창고에 하겠습니다. 보통 배열로 이루어진 정렬만 해서 애를 먹었습니다. 특히 분할하는 부분에서 힘들었는데, 그래도 깔끔한 방법을 찾아내 만들었습니다. 구조체 및 함수설명 NODE : 단일연결리스트를 구성하는 노드 구조체 TMP : partition 함수를 위한 구조체. 두 개의 반환값을 받아내기 위함 NODE* addNode(int n) : 노드를 추가하는 함수. 단일연결리스트 끝부분에 계속 붙여나가므로 새 노드 값의 next는 항상 NULL이다. void mergeSort(NODE **L, int k) : 합병정렬함수. 재귀방식으로 구성돼있다. L은 리스트의 시작 주소, k는 리스트의 크기이다. NODE* merge(NODE *L1, NODE *L2) : 합병함수.. 2018. 10. 14. [C] 버블 정렬 (bubble sort) 가장 짧고 간단한 코드로 나타낼 수 있는 정렬 알고리즘이다. 하지만 이러한 알고리즘이 다 그렇듯 단점은 거의 모든 상황에서 최악의 성능을 보인다는 점이다. 시간 복잡도는 O(n^2)이다. 적은 양의 데이터에서는 굳이 다른 정렬법을 쓰지 않아도 되는 성능을 발휘하지만, 현업에서는 방대한 양의 데이터를 관리하기 떄문에 버블정렬은 웬만해서는 안쓴다고 한다. 버블 정렬은 1번째와 2번째, 2번째와 3번쨰 .... n-1번째와 n번째를 비교하여 정렬하고 그 다음엔 n-2, n-1번째 까지, 그 다음엔 n-3, n-2번째 까지 하나씩 줄여가면서 정렬한다. #include #include #include const int MAX_NUM = 100; void swap(int *a, int *b) { int tmp = .. 2018. 7. 12. 이전 1 다음 반응형
