알고리즘

비교 방법 1. 각각 1000, 10000, 100000 크기의 배열 A, B에 0 ~ 999 사이의 난수를 채운다. (단, 동일한 난수로 채운다.) 2. 정렬 안된 상태, 정렬된 상태, 역순 정렬된 상태에서 선택 정렬과 삽입 정렬을 하여 시간을 비교한다. 사용 코드 #include #include #include #include void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void bubble(int *L, int n) { for (int i = 0; i < n - 1; i++) for (int j = 0; j < n - 1 - i; j++) if (L[j] < L[j + 1]) swap(&L[j], &L[j + 1]); } voi..

Memoization(메모이제이션)이란 동적 계획법(dynamic programming)의 핵심 기술로 동일한 계산을 반복해야 할 때, 이전에 계산한 값들을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 방법이다. 보통 예시로 피보나치 수열을 사용한다. 피보나치 수열 피보나치 수열(Fibonacci sequence)은 제0항을 0, 제1항을 1로 두고, 제2항부터는 바로 앞의 두 수를 더한 수로 놓는다. 제0항부터 제10항까지 표현하면 다음과 같다. $$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 $$ 이는 C 언어에서 재귀 함수를 사용해서 다음과 같이 구현할 수 있다. int fibonacci(int n) { if (n == 0) ret..

시간 복잡도 자료구조나 알고리즘을 배우면 기본적으로 시간 복잡도라는 개념이 나온다. 시간 복잡도는 컴퓨터 프로그램의 입력 값과 연산 수행 시간의 상관관계를 나타내는 척도이다. 주로 빅-오 표기법을 사용하는데 O(n), O(n^2), O(n^3) 등이 있다. 예를 들어, 만약 크기 n의 모든 입력에 대해 알고리즘에 필요한 시간이 최대 5n^2 + 3n의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(n^2)이다. 이런 시간 복잡도를 가지는 프로그램을 구현해서 직접 실행 시간을 확인해보고, 측정하는 방법도 알아보자. C 언어를 통해 구현하고, 구현에 필요한 난수 발생 함수와 시간 측정 함수도 같이 작성할 예정이다. 난수 발생 함수 C 언어에서는 시스템 라이브러리를 통해 난수 발생 함수를 제공한다. ..

소개 Selection sort(선택 정렬)는 제자리 정렬 알고리즘의 하나로 가장 작은(혹은 가장 큰) 원소를 찾아서 교체하는 알고리즘이다. 말 그대로 원소를 선택해서 정렬한다. 정렬 과정 다음과 같이 다섯 개의 정수가 주어졌을 때, Selection sort로 오름 차순으로 정렬해보겠다. +-----+-----+-----+-----+-----+ | 5 | 4 | 1 | 3 | 2 | +-----+-----+-----+-----+-----+ 우선 인덱스 0을 가장 작은 값을 가진 인덱스라고 가정하고, 인덱스 1부터 원소 끝까지 순회하면서 가장 작은 원소를 찾는다. 그리고 찾은 원소를 가장 처음 원소와 교체한다. +-----+-----+-----+-----+-----+ | 1 | 4 | 5 | 3 | 2 ..

소개 Cocktail shaker sort(칵테일 셰이커 정렬)는 거품 정렬에서 파생된 정렬 알고리즘이다. 양방향 거품 정렬 혹은 셰이커 정렬 등으로 불린다. 시간 복잡도가 O(n^2)으로 거품 정렬과 비슷하다. 정렬하는 게 마치 칵테일을 위아래로 흔드는 모습과 비슷하다 하여 이런 이름이 붙었다. 정렬 과정 다음과 같이 다섯 개의 정수가 주어졌을 때, Cocktail shaker sort로 오름 차순으로 정렬해보겠다. +-----+-----+-----+-----+-----+ | 5 | 4 | 1 | 3 | 2 | +-----+-----+-----+-----+-----+ 거품 정렬처럼 인덱스 0의 값과 인덱스 1의 값을 비교하는걸 시작으로 인덱스 3의 값과 인덱스 4의 값까지 비교한다. +-----+---..

소개 Bubble sort(거품 정렬)는 인접한 두 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순해서 자주 사용된다. 이름의 유래는 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다. 정렬 과정 다음과 같이 다섯 개의 정수가 주어졌을 때, Bubble sort로 오름 차순으로 정렬해보겠다. +-----+-----+-----+-----+-----+ | 5 | 4 | 1 | 3 | 2 | +-----+-----+-----+-----+-----+ 우선 인덱스 0의 값과 인덱스 1의 값을 비교하면, 인덱스 0의 값이 더 크기 때문에 두 값이 서로 교체된다. +-----+-----+-----+-----+-----+ | 4 | 5 | 1 | ..