작은 메모장

Goal Merge Sort란? Merge Sort 구현 Merge Sort 시간복잡도, 공간복잡도 계산 Merge Sort란? Merge Sort는 분할 정복(Divide and Conquer) 방법 중 하나의 방법으로, 주어진 문제를 작은 문제로 분할하고 각 문제를 해결한 다음, 결과를 모아서 문제를 해결하는 방식이다. 평균적으로 매우 빠른 수행 속도를 보여주는 정렬 방법이고 안정 정렬에 속하나, 정렬해야하는 데이터만큼 메모리를 추가적으로 더 사용한다는 점이 단점이다. 과정은 아래와 같다. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 리스트로 나눈다. 리스트의 길이가 0 혹은 1이라면 이미 정렬된 것으로 보고, 그렇지 않으면 계속 절반으로 나눈다. 각 부분의 리스트를 합병 정렬을 통해 재귀..

Goal Insertion Sort란? Insertion Sort 구현 Insertion Sort 시간복잡도, 공간복잡도 계산 Insertion Sort란? 손 안의 카드를 정렬하듯이, 2번째 원소부터 시작하여 마지막 원소까지, 앞의 원소들과 비교 후 조건에 부합하지 않을 때 까지 교환하는 방식이다. 대략적인 과정은 아래를 따른다. 2번째 위치의 원소를 임시공간에 집어넣는다. 선택한 자리부터 시작하여 앞으로 진행하며 계속 교환하면서, 조건에 주합하지 않을 때 까지 반복한다. 정렬이 끝날 때 까지 위 과정을 반복한다. Selection Sort 구현 #include #include #include #define MAX_SIZE 10000 int mknum() { int random = (rand() % 1..

Goal Selection Sort란? Selection Sort 구현 Selection Sort 시간복잡도, 공간복잡도 계산 Selection Sort란? 순서에 맞게 자리를 정하고, 조건에 맞는 원소를 선택 후 교환하며 정렬하는 알고리즘. 대략적인 과정은 아래를 따른다. 교환할 자리를 정하고, 배열 중 최소값을 찾는다. 선택한 자리와 최소값을 교환한다. 선택했던 자리를 제외하고 나머지 배열을 위 방법으로 진행한다. Selection Sort 구현 #include #include #include #define MAX_SIZE 10000 int mknum() { int random = (rand() % 100) + 1; return random; } void selection_sort(int list[]..

Goal Bubble Sort란? Bubble Sort 구현 Bubble Sort 시간복잡도, 공간복잡도 계산 Bubble Sort란? 서로 인접한 원소의 대소를 비교하고, 조건에 맞게 자리를 교환하며 정렬하는 알고리즘. 대략적인 과정은 아래를 따른다. 1번째 원소와 2번째 원소를 비교하고 정렬하고, 2번째와 3번째, ... n-1번째와 n번째를 정렬한다. 1회차가 끝나면, 처음부터 다시 시작하여 n-2번째와 n-1번째를 정렬할 때 까지 진행한다. 위 과정을 정렬이 끝날 때 까지 반복한다. Bubble Sort 구현 #include #include #include #define MAX_SIZE 10000 int mknum() { int random = (rand() % 100) + 1; return ra..

알고리즘 문제는 컴퓨터 분야에서 중요하게 여기는 문제 중 하나로, 여러 데이터들이 주어졌을 때 "최적의" 자원으로 이를 나열하는 문제다. 정렬의 기준은 숫자의 크기가 될 수도 있고, 문자의 순서도 될 수가 있으며, 이런 다양한 상황을 얼마나 효과적으로 해결할 수 있느냐가 문제의 핵심이다. 왜 정렬을 해야할까? 그 이유는 탐색을 위해서다. 수백만, 수천만 개가 넘어가는 데이터중 원하는 데이터를 효과적으로 찾는 강력한 탐색 알고리즘인 이진 탐색은 데이터가 정렬이 되어있는 조건 하에 동작한다. 정렬된 데이터의 특징은 특정 값의 오른쪽은 무조건 크거나 같은 값이 있으며, 왼쪽에는 작거나 같은 값이 있다. 때문에 한 번의 탐색으로 데이터의 절반을 추려낼 수 있고, 이는 탐색시간의 감소로 이어진다. 이러한 이유로 ..