[멋쟁이사자처럼 유니티 TIL] 2024_12_11(수) 강의 요약 및 정리

프로그래밍 언어에서의 알고리즘이란

알고리즘은 프로그래밍에서 문제를 해결하기 위한 단계적인 절차나 방법을 의미.

이는 특정 작업을 수행하거나 결과를 얻기 위해 컴퓨터가 따라야 할 명확하고 정확한 지시사항의 집합.

 

알고리즘의 종류

알고리즘은 다양한 유형으로 분류될 수 있습니다. 주요 알고리즘 종류는 다음과 같습니다:

• 정렬 알고리즘: 버블 정렬, 퀵 정렬, 병합 정렬 등
• 검색 알고리즘: 선형 검색, 이진 검색 등
• 그래프 알고리즘: 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS), 다익스트라 알고리즘 등
• 동적 프로그래밍: 최적화 문제를 해결하는 데 사용되는 기법
• 분할 정복 알고리즘: 문제를 작은 부분으로 나누어 해결하는 방식
• 그리디 알고리즘: 각 단계에서 최적의 선택을 하는 방식

이러한 알고리즘들은 각각 특정 문제 유형에 적합하며, 효율성과 복잡성 면에서 차이가 있습니다.

프로그래머는 문제의 특성에 따라 적절한 알고리즘을 선택하고 적용해야 함.

1. 버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 원소를 비교하여 정렬하는 간단한 알고리즘.

 

Bubble sort with Hungarian, folk dance

 

 { 7, 3, 2, 41, 1, 4, 66, 5 } 일경우 하기와 같이 실행됨

 int n = arr.Length=7 

i=0 j=0                                           i=0 j=4

= 3, 7, 2, 41, 1, 4, 66, 5                 = 3, 2, 7, 1, 4, 41, 66, 5

i=0 j=1                                           i=0 j=5

= 3, 2, 7, 41, 1, 4, 66, 5                = 3, 2, 7, 1, 4, 41, 66, 5

i=0 j=2                                            i=0 j=6

= 3, 2, 7, 41, 1, 4, 66, 5                = 3, 2, 7, 1, 4, 41, 5, 66

i=0 j=3

= 3, 2, 7, 1, 41, 4, 66, 5

 

해당 과정을 7번 반복(i = 6 까지)하다 보면 작은 숫자가 왼쪽으로, 큰숫자가 오른쪽으로 이동

하면서 배열이 정리됨

 

2. 퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복 방법을 통해 리스트를 정렬합니다.

 

퀵소트 / 퀵정렬 5분만에 이해하기 - Gunny

 

 

{ 7, 3, 2, 41, 1, 4, 66, 5 }

QuickSort(arr, 0, arr.Length - 1);

일경우 하기와 같이 실행됨

 

QuickSort(arr, 0, 7);

if (low < high) = true

int pi = Partition(arr,0,7) 을 실행

 

 

 

여기까지 진행하면 i의 4번째에 있는 5 를 기준으로 왼쪽배열은 5보다 작은수

오른쪽 배열은 5보다 큰수로 정리됨.

 

해당 과정을 if (low < high) = false 즉, high가 0 이 될때까지 반복하다보면

작은 숫자가 왼쪽으로, 큰숫자가 오른쪽으로 이동하면서 배열이 정리됨.

 

월드좌표와 그리드 좌표

월드좌표 (World Coordinates)

게임 세계 전체를 기준으로 한 절대적인 좌표 체계

월드 좌표는 글로벌 좌표로도 불리며, (0, 0, 0)은 씬의 중심(월드 원점)을 의미

 

사용처:

NPC나 캐릭터의 이동 경로를 계산

객체를 게임 씬 내 특정 위치에 배치할 때 사용.

 

월드좌표 -> 그리드 좌표 구하는 공식

 

 

그리드 좌표 (Grid Coordinates)

일정한 간격으로 나뉜 셀(Grid)을 기준으로 객체의 위치를 정의하는 체계

 

사용처:

주로 2D 또는 타일 기반 게임 또는

전략 게임이나 퍼즐 게임에서 좌표 기반 논리를 구현할 떄 사용

 

그리드 좌표 -> 월드 좌표 구하는 공식