알고리즘의 설계 방법
실험적 분석방법
- 직접 실행해보며 분석해보는 방법
- 실험은 제한된 테스트 입력값을 가지기 때문에 정확한 측정이 어렵다.
- 두 개의 서로 다른 형태의 알고리즘의 동작시간을 구분하기 어렵다.
- 알고리즘을 완전히 구현해야 합니다. (학술적인 이유)
이론적 분석방법
- 의사 코드를 작성해 분석해보는 방법
- 모든 입력가능한 데이터들에 대해 분석할 수 있습니다.
- 고수준 언어의 분석으로 실제 구현과 실험 결과를 미리 분석할 수 있습니다.
분석에 앞서 생각해야 하는 것
- 대부분의 알고리즘은 입력된 객체를 출력 객체로 변환합니다.
- 알고리즘의 동작시간은 일반적으로 입력 데이터의 크기에 비례해 증가합니다.
- 평균 동작시간의 측정은 대다수가 매우 어렵습니다.
- 따라서 Worst-case Running time에 초점을 두어야 합니다.
다음 작업들은 동작시간을 1로 가정합니다.
- 변수할당
- 함수(메소드) 호출
- 사칙연산
- 비교
- 배열 접근
- 포인터 추적
- 메소드 동작 종료 후 반환
의사 코드(Psesude code)
어떠한 알고리즘(동작)의 상위 언어 표현
- 영어의 형태보단 구조적입니다.
- 실제 프로그램 코드에 비해 상세하지 않습니다.
- 알고리즘의 구동 방식을 정리하는데 사용됩니다.
- 실제 프로그래밍에 들어가는 여러가지 트릭이나 기타 사항들을 무시할 수 있습니다.
아래는 알고리즘 동작시간 분석을 위해 꼭 필요한 7개의 기본 함수 그래프입니다.
....
정렬 알고리즘
정렬 알고리즘의 종류
비교 정렬 알고리즘
- 선형(삽입 선택 버블), 분할(퀵 분열 합병), 셀 등
비교하지 않는 알고리즘
- 비둘기집 정렬, 버킷 정렬, LSD기수 정렬 등이 있다.
기타 정렬 알고리즘
- 스파게티 정렬, 바이토닉 정렬 등이 있다.
선택 정렬
현재 위치에 들어갈 값을 찾아 정렬하는 배열이다.
현재 저장될 값의 크기가 크냐 작냐에 따라 최대 선택 정렬과 최소 선택 정렬로 구분할 수 있다.
최소 선택 정렬은 오름차순, 최대 선택 정렬은 내림차순이다.
기본 로직
- 정렬되지 않은 인덱스의 맨 앞에서 부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아간다.
- 가장 작은 값을 찾으면 그 값을 현재 인덱스의 값과 바꿔준다.
- 다음 인덱스에서 위의 과정을 반복한다.
public static void SelectionSort(ref int[] values, bool flag = true)
{
int count = values.Length;
int tmp;
if (flag == true)
{
//오름차순
for (int i = 0; i < count; i++)
{
for(int j = i + 1; j < count; j++)
{
if (values[i] > values[j])
{
tmp = values[i];
values[i] = values[j];
values[j] = tmp;
}
}
}
return;
}
//내름차순
for (int i = 0; i < count; i++)
{
for (int j = i + 1; j < count; j++)
{
if (values[i] < values[j])
{
tmp = values[i];
values[i] = values[j];
values[j] = tmp;
}
}
}
return;
}삽입정렬
현재 위치에서 그 이하의 배열들읠 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 정렬 알고리즘이다.
기본 로직
- 삽입 정렬은 두번째 인덱스부터 시작한다.
- 현재 인덱스는 별도의 변수에 저장해주고, 비교 인덱스를 현재 인덱스-1로 잡는다.
- 별도로 저장해둔 삽입을 위한 변수와 비교 인덱스의 배열 값을 비교한다.
- 삽입 변수의 값이 더 작으면(오름차순일 때) 현재 인덱스로 비교 인덱스의 값을 저장해주고, 비교 인덱스를 -1 하여 비교를 반복한다.
- 만약 삽입 변수가 더 크면 비교 인덱스 + 1에 삽입 변수를 저장한다.
public static void InsertionSort(ref int[] values, bool flag = true)
{
if (flag == true)
{
int count = values.Length;
int i, j;
int tmp;
for(i = 1; i < count; i++)
{
tmp = values[i];
for (j = i - 1; j >= 0; j--)
{
if (tmp < values[j])
{
values[i] = values[j];
values[j] = tmp;
i--;
}
}
}
return;
}
else
{
int count = values.Length;
int i, j;
int tmp;
for (i = 1; i < count; i++)
{
tmp = values[i];
for (j = i - 1; j >= 0; j--)
{
if (tmp > values[j])
{
values[i] = values[j];
values[j] = tmp;
i--;
}
}
}
return;
}
} 버블 정렬
매번 연속된 두 개의 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬한다.
기본 로직
- 두번째 인덱스부터 시작한다.
- 현재 인덱스와 바로 전 인덱스를 비교한다.
- 이전 인덱스가 더 크면 현재 인덱스와 바꿔준다.
- 현재 인덱스가 더 크면, 교환하지 않고 다음 두 연속된 배열값을 비교한다.
- 위의 순서를 (전체 배열 크기 - 현재까지 순환한 바퀴 수) 만큼 반복
public static void BubbleSort(ref int[] values, bool flag = true)
{
int count = values.Length;
int i, j;
int tmp;
if(flag == true)
{
for (i = 1; count - i > 0; i++)
{
for (j = 1; j < count; j++)
{
tmp = values[j];
if (tmp < values[j - 1])
{
values[j] = values[j - 1];
values[j - 1] = tmp;
}
}
}
return;
}
for (i = 1; count - i > 0; i++)
{
for (j = 1; j < count; j++)
{
tmp = values[j];
if (tmp > values[j - 1])
{
values[j] = values[j - 1];
values[j - 1] = tmp;
}
}
}
return;
}
} 분할 합병 정렬 (Merge Sort)
분할 합병 방식으로 설계된 알고리즘으로 큰 문제를 반으로 쪼개 문제를 해결해 나가는 방식
분할은 배열의 크기가 1보다 작거나 같을 때까지 반복한다.
합병은 두 개의 배열을 비교하여 기준에 맞는 값을 다른 배열에 저장해 나간다.
이 정렬 알고리즘은 분할 과정과 합병 과정이 나뉘어진다.
분할 과정 기본 로직
- 현재 배열을 반으로 쪼갠다. 배열의 시작 위치와 종료 위치를 입력받아 둘을 더한 후 2를 나눠 그 위치를 기준으로 나눈다.
- 쪼갠 배열의 크기가 0이거나 1일때 까지 반복한다.
합병 과정 기본 로직
- 두 배열 A, B의 크기를 비교한다. 각각의 배열의 현재 인덱스를 n, m으로 가정하자
- n에는 A배열의 시작 인덱스를 저장하고, m에는 B배열의 시작 인덱스를 저장한다.
- A[n]과 B[m]을 비교한다. 오름차순의 경우 이 중에 작은 값을 새 배열 C에 저장한다. B[m]이 더 크다면 A[n]의 값을 배열 C에 저장하고 n의 값을 하나 증가시켜준다.
- 이를 n이나 m 둘중 하나가 각자 배열의 끝에 도달할 때 까지 반복
- 끝까지 저장을 못한 배열의 값을 순서대로 전부 C에 저장한다.
- C 배열을 원래의 배열에 저장해준다.
게임 개발자 지망생, 유니티 공부중!