개발 블로그

병합 정렬이란 전화번호부를 반씩 나누어 간다는 것과 비슷하다. 원소가 한 개가 될 때까지 계속 반으로 나누다가 다시 합쳐나가며 정렬하는 방식이다. ①최소 단위로 나눈 다음, ②나눈 곳 기준 왼쪽을 정렬한다. ③나눈 곳 기준 오른쪽을 정렬한다. ④위에서 정렬한 것을 병합한 후 오름차순으로 정렬한다. 이 과정을 계속 반복한다. 예시) 7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 → 가장 작은 부분(숫자 1개)으로 나눈다. 4 7 | 2 5 | 3 6 | 1 8 → 숫자 1개씩을 정렬하여 병합한다. 2 4 5 7 | 1 3 6 8 → 숫자 2개씩을 정렬하여 병합한다. 1 2 3 4 5 6 7 8 → 마지막으로 숫자 4개씩을 정렬하여 병합한다. 알고리즘에서 무언가를 계속 절반으로 나눈다면 이것은 로그 ..

재귀(Recursion)란 함수 자기 자신을 스스로 호출하는 프로그래밍 기법이다. 아래와 같이 중첩 루프를 쓰지 않고 #include #include void draw(int h); int main(void) { // 사용자로부터 피라미드의 높이를 입력 받아 저장 int height = get_int("Height: "); // 피라미드 그리기 draw(height); } void draw(int h) { // 높이가 h인 피라미드 그리기 for (int i = 1; i

지금까지의 선형 검색, 이진 검색, 버블 정렬, 선택 정렬의 실행시간은 다음과 같다. 실행시간의 상한 O(n^2): 선택 정렬, 버블 정렬 O(n log n) O(n): 선형 검색 O(log n): 이진 검색 O(1) 실행시간의 하한 Ω(n^2): 선택 정렬, 버블 정렬 Ω(n log n) Ω(n) Ω(log n) Ω(1): 선형 검색, 이진 검색 만약 이미 정렬이 되어 있는 배열이 주어진다면, 아래와 같이 바깥 루프를 '교환이 일어나지 않을 때'까지만 수행하도록 하여 버블 정렬을 좀 더 효율적으로 실행할 수 있을 것이다. Repeat until no swaps For i from 0 to n–2 If i'th and i+1'th elements out of order Swap them 따라서 최종적인 ..

선택정렬은 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환하는 방식의 정렬이다. 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다. 선택정렬의 예시 정렬되지 않은 숫자들을 오름차순 정렬한다고 하자. 프로그램은 배열 속 다른 값을 전부 보기 전 까지는 알 수 없기 때문에, ①첫 번째 값을 제일 작은 숫자로 기억하고 다음 값을 탐색한다. ②탐색하다가 현재 기억하는 숫자보다 작은 값이 발견되면 발견된 값으로 다시 기억한다. ③배열을 다 탐색하고 나면 기억한 숫자를 맨 앞으로 정렬한다. ④정렬한 숫자를 제외하고 두 번째 숫자부터 시작해서 똑같이 탐색한다. ⑤또 가장 작은 값을 찾았으면 정렬된 숫자를 제외하고 맨 앞에 정렬한다. 이를 ..

버블 정렬은 정렬 알고리즘 중의 하나로, 두 개의 인접한 자료값을 비교하면서 위치를 바꾸는 방식으로 정렬하는 방법이다. 마치 거품이 터지면서 위로 올라가는(옆으로 이동하는) 방식이기 때문에 붙여진 이름이다. 버블 정렬은 아래와 같은 의사코드로 나타낸다. Repeat n–1 times For i from 0 to n–2 If i'th and i+1'th elements out of order Swap them 중첩 루프를 돌며, n개의 값이 주어졌을 때, 루프가 각각 n-1, n-2번 반복되므로 (n−1)∗(n−2) = n^2​^2​^22−3n+2 번의 비교 및 교환이 필요하다. 여기서 가장 크기가 큰 것은 n^2이므로 버블 정렬 실행 시간의 상한은 O(n^2)이다. 버블정렬은 이미 정렬이 되어 있어도 정..

선형 검색은 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색한다. 즉 모든 자료를 확인해야 하므로 정확하지만 효율적이지 못한 방법이다. 따라서 자료가 정렬되어 있지 않거나 아무 정보도 없이 하나씩 찾아야 하는 경우에 유용하다. 선형 검색의 예시 아래 코드는 배열의 크기만큼 반복하고 인덱스를 차례로 확인하며 50을 찾는다. #include #include int main(void) { // numbers 배열 정의 및 값 입력 int numbers[] = {4, 8, 15, 16, 23, 42}; // 값 50 검색 for (int i = 0; i < 6; i++) { if (numbers[i] == 50) { printf("Found\n"); return 0; } } printf("N..

Big O Big O는 실행시간의 상한(최악)을 나타낸다. 아래 차트는 알고리즘을 실행하는데 걸리는 시간을 표현한 것이다. 이 차트를 공식으로 표기한 것이 Big O 표기법이다. Big O의 O는 on the order of의 약자로, 쉽게 생각하면 '~만큼의 정도로 커진다'라는 뜻이다. 따라서 O(n)은 n만큼 커진다는 것을 의미하고 n이 늘어날수록 선형적으로 증가하게 된다. O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 그냥 O(n)과 같다. 아래의 표기가 실행시간을 나타내기 위해 많이 사용된다. O(n^2) O(n log n) O(n) - 선형 검색 O(log n) - 이진 검색 O(1) Big Ω(오메가) Big Ω는 실행시간의 하한(최선)을 나타낸다. 아래의 표기가 실행시간..

아래는 배열의 값에 접근하기 위한 방법들이다. 1. 선형검색(Linear Search) 배열을 앞에서부터 차례대로 하나씩 확인해보면서 검사하는 방법 For i from 0 to n–1 If i'th element is 50 Return true Return false 2. 이진검색(Binary Search) 배열이 정렬되어 있다고 가정하고 배열의 중간 인덱스부터 확인해서 찾는 값이 없으면 작은 인덱스 또는 큰 인덱스로 이동을 반복하는 방법 If no items Return false If middle item is 50 Return true Else if 50 middle item Search right half 출처: www..