알고리즘
알고리즘이란?
문제를 해결하기 위한 명확하고 체계적인 단계별 절차 또는 명령어들의 집합
알고리즘 설계 과정
- 문제 이해
- 당연하지만, 문제에 대한 이해가 되지 않는다면 제대로된 알고리즘을 구현할 수 없다.
- 예시/테스트 케이스
- 입력과 출력에 대한 예상을 할 수 있어야 한다.
- 설계
- 최우선은 정확도. 그 다음 효율성을 고려해야 한다.
- 구현/검증
- 이미 제작한 테스트 케이스를 이용하여 정상적으로 동작하는지 확인한다.
- 분석/개선
- 완성한 알고리즘을 분석하여 Big-O 기반 개선점을 확인한다.
알고리즘은
정확성과 이를 검증할검증 방법이 아주 중요하다!
대표적인 알고리즘
정렬 알고리즘 - 1
버블 정렬
BigO: O(n^2)- 우리가 일반적으로 사용하는 정렬 방식이다.
코드 예시
public static int[] BubbleSort(int[] arr)
{
int temp;
for (var i = 0; i < arr.Length; i++)
{
for (var j = 0; j < arr.Length - 1; j++)
{
if (arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}실행 예제
// 참고:아래 데이터 표기 및 실행 횟수는 이해를 위해 임의로 코드 추가 후 실행하였음.
[-2][-8][7][3][-10][4][8][1]
[-8][-2][3][-10][4][7][1][8]
[-8][-2][-10][3][4][1][7][8]
[-8][-10][-2][3][1][4][7][8]
[-10][-8][-2][1][3][4][7][8]
실행 횟수: 35선택 정렬
BigO: O(n^2)- 주어진 리스트에서 맨 앞부터 리스트내 최소값을 선택하여 앞에 놓고, Index 를 뒤로 밀으며 같은 방식을 취한다.
- 즉, 정렬된 앞쪽과 정렬되지 않은 뒤쪽이 존재하게 되며, 정렬되지 않은 쪽 기준으로 위 내용을 반복하게 된다.
코드 예시
public static int[] SelectionSort(int[] arr)
{
int temp;
int minIndex;
for (int i = 0; i < arr.Length - 1; i++)
{
minIndex = i;
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] < arr[minIndex])
minIndex = j; // index 를 ovvrriding 하며 가장 작은 것을 찾는다
}
// 가장 작은 값의 위치를 변경한다.
temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
return arr;
}실행 예시
// 참고:아래 데이터 표기 및 실행 횟수는 이해를 위해 임의로 코드 추가 후 실행하였음.
[-2][-8][7][3][-10][4][8][1]
[-10][-8][7][3][-2][4][8][1]
[-10][-8][7][3][-2][4][8][1]
[-10][-8][-2][3][7][4][8][1]
[-10][-8][-2][1][7][4][8][3]
[-10][-8][-2][1][3][4][8][7]
[-10][-8][-2][1][3][4][7][8]
실행 횟수: 28삽입 정렬
BigO: O(n^2)- Index를 뒤로 밀어가며 선택된 값을 앞으로 다시 보내며 앞 값이 선택한 값보다 작아지기 전까지 반복하게 된다.
코드 예시
public static int[] InsertionSort(int[] arr)
{
int key;
int j;
for (int i = 1; i < arr.Length; i++)
{
key = arr[i]; // 대상 값. Index 를 뒤로 밀어가면서 확인
j = i - 1;
while (j >= 0 && arr[j] > key) // 앞값이 작을때까지 반복
{
arr[j + 1] = arr[j]; // 기존 값을 뒤로 미루기
j--; // Index 앞으로 이동
}
arr[j + 1] = key; // 마지막 위치에 값 삽입
}
return arr;
}실행 예시
// 참고:아래 데이터 표기 및 실행 횟수는 이해를 위해 임의로 코드 추가 후 실행하였음.
[-2][-8][7][3][-10][4][8][1]
[-8][-2][7][3][-10][4][8][1]
[-8][-2][7][3][-10][4][8][1]
[-8][-2][3][7][-10][4][8][1]
[-10][-8][-2][3][7][4][8][1]
[-10][-8][-2][3][4][7][8][1]
[-10][-8][-2][3][4][7][8][1]
[-10][-8][-2][1][3][4][7][8]
실행 횟수: 11길 찾기 알고리즘 - 1
선형 탐색
일반적인 for문을 이용해 순서대로 찾는 방법.
코드 예시
public static void Main(string[] args) {
int[] arr = {7, 5, 3, 4, 1, 2, 6};
Console.WriteLine(LinearSearch(arr, 5)) // true
Console.WriteLine(LinearSearch(arr, 10)) // false
}
public static bool LinearSearch(int[] arr, int target)
{
// 그냥 한칸씩 뒤로 가며 찾게 된다.
for (int i = 0; i < arr.Length; i++) {
if (target == arr[i]) return true;
}
return false;
}실행 결과
// 아래 출력물은 이해를 돕기 위해 임의로 코드를 추가했던 출력로그 입니다.
List Length: 1000000
Processing Count: 534277
GivenData:215652 vs FoundData:215652이진 탐색
정렬되어 있는 데이터중 중간 값을 찾아 이보다 큰지 작은지 확인하는 방법.
코드 예시
public static void Main(string[] args) {
List<int> list = MakeData(1_000_000)
BinarySearch(list, list[65535])
}
public static List<int> MakeData(int size) {
List<int> list = new List<int>();
Random random = new Random();
if (!list.Contains(i))
{
list.Add(random.Next(0, size));
}
return list;
}
public static int BinarySearch(List<int> list, int target)
{
list.Sort();
int start = 0;
int end = list.Count - 1;
int pivot = 0;
for (int i = 0; i < end; i++)
{
if (list[start + pivot] == target)
{
return start + pivot;
}
pivot = (end - start) / 2;
if (list[start + pivot] < target)
{
start += pivot;
}
else
{
end -= pivot;
}
}
return -1;
}실행 결과
// 아래 출력물은 이해를 돕기 위해 임의로 코드를 추가했던 출력로그 입니다.
List Length: 1000000
- s: Start Index
- e: End Index
- p: Pivot value
- d: CurrentData:TargetData
s:0 e:999999 p:0 d:0:602352
s:499999 e:999999 p:499999 d:999998:602352
s:499999 e:749999 p:250000 d:749675:602352
s:499999 e:624999 p:125000 d:624606:602352
s:562499 e:624999 p:62500 d:624606:602352
s:593749 e:624999 p:31250 d:624606:602352
s:593749 e:609374 p:15625 d:609245:602352
s:601561 e:609374 p:7812 d:609243:602352
s:601561 e:605468 p:3906 d:605381:602352
s:601561 e:603515 p:1953 d:603461:602352
s:601561 e:602538 p:977 d:602468:602352
s:602049 e:602538 p:488 d:602467:602352
s:602293 e:602538 p:244 d:602467:602352
s:602293 e:602416 p:122 d:602352:602352
Processing Count: 13
GivenData:602352 vs FoundData:602352재귀 함수
재귀 함수란?
함수가 자기 자신을 호출하는 프로그래밍 기법
- ⚠️주의! 재귀 호출을 멈추는 조건이 필요하다 (기저조건) -> 그렇지 않으면 Stack Overflow 발생!
분할 정보법
- 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄어가는 방식. 나무위키
function F(x):
if F(x)가 간단 then:
return F(x)를 계산한 값
else:
x 를 x1, x2로 분할
F(x1)과 F(x2)를 호출
return F(x1), F(x2)로 F(x)를 구한 값
Python Dev with Infra -> Game Programmer