오리는 오늘도 꽥꽥

quick sort | 퀵 정렬

이 글은 python3를 기준으로 작성했다. 더보기 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. 퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 또한 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비..
코딩/자료구조 2020. 12. 4. 01:39

merge sort | 합병정렬

해당 글은 python3을 기준으로 작성하였다. merge sort는 divide and conquer 방법을 사용한 정렬. divide and conquer 더보기 비유를 해보자. A회사는 하나의 큰 프로젝트를 반으로 쪼갠 후, B, C 두 회사에 하청을 맡겼다. 그리고 B,C 회사는 하청받은 프로젝트를 또 반으로 쪼개 B는 D, E회사에 C는 F,G 회사에 하청을 맡겼다. D와 E는 프로젝트를 끝내 B에 보내고, F와 G도 결과물을 C에 보냈다. B와 C는 하청업체로부터 받은 결과물을 합쳐 A로 보냈다. A는 B와 C로부터 받은 결과물을 합쳐 큰 프로젝트를 완수했다. merge sort는 다음과 같이 작동한다. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 분할(divi..
코딩/자료구조 2020. 12. 2. 03:16

[C언어][자료구조] 선형 큐(Linear Queue)

※ 이 글은 C언어 기준으로 작성하였습니다. 큐 저번 글에서 큐는 줄서기와 같다고 했습니다. 먼저 입력된 데이터가 먼저 출력되는 FIFO 구조를 가지고 있습니다. 큐가 스택과 구조적으로 다른 점은 스택은 삽입과 삭제가 같은 쪽(top)에서 일어나는 반면, 큐에서는 삽입(rear)과 삭제(front)가 다른 쪽에서 일어납니다. 데이터 삽입은 rear에서 일어나고 삭제는 front에서 일어납니다. 이번 글에서는 선형큐를 구현해보겠습니다. code #include #include #define MAX_QUEUE_SIZE 5 typedef int element; typedef struct { int front; int rear; element data[MAX_QUEUE_SIZE]; } Queue; void er..
코딩/자료구조 2020. 6. 7. 18:19

[C언어][자료구조] 스택(Stack)

※ 이 글은 C언어 기준으로 작성하였습니다. FIFO, LIFO 스택과 큐에 대해 알아보기 전에 FIFO와 LIFO에 대해 알아봅시다. FIFO(First In, First Out, 선입선출)란 먼저 입력된 원소가 우선적으로 출력되는 기법입니다. 대표적인 예시로 Queue가 있습니다. 반대로 LIFO(Last In, First Out, 후입선출)은 가장 최근에 입력된 원소가 우선적으로 출력되는 기법입니다. 대표적인 예시로 Stack이 있습니다. 스택(Stack), 큐(Queue) 큐는 줄서기를 하는 것과 같습니다. 왼쪽에 줄을 선 사람들이 있습니다. 저들이 새치기를 하지 않는 이상 먼저 온 사람(First In)부터 게이트를 통과(First Out)하게 됩니다. 사람들을 원소로 바꾸게 되면 큐가 됩니다...
코딩/자료구조 2020. 6. 7. 17:06

[C언어][자료구조] 순환(recursion)

※ 이 글은 C언어 기준으로 작성하였습니다. 순환(recursion)이란... 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법입니다. '재귀'라고도 부릅니다. 러시아 인형 '마트료시카'를 아신다면 그것 또한 좋은 예라고 할 수 있겠습니다. void example() { . . . . return example(); //자기자신을 출력 } recursion을 구성할 때는 무한반복이 일어날 수 있기 때문에 매개변수를 바꾸고 조건문을 사용하여 반복을 제한합니다. 몇 가지 예시를 통해 알아봅시다. factorial(팩토리얼) #include int factorial(int n) { if(n
코딩/자료구조 2020. 6. 6. 15:15
◀ 1 ▶

티스토리툴바