들어가기 앞서
알고리즘은 C#문법의 거의 최종 기법이며 자료구조를 얼마나 잘 사용해서 만들러낸 로직같은 존재
Big-O 표기법
● 컴퓨터에서 알고리즘과 자료구조의 평가는 시간과 공간 두 자원을 얼마나 소모하는지가 효율성의 중점으로 두는데 그걸 나타내는 표기법인 Big-O표기법을 알아보도록 하자
- 시간복잡도 : 알고리즘의 시간적 자원 소모량
- 공간복잡도 : 알고리즘의 공간적 자원 소모량
● 대부분 자료구조에 상관되어 표기되는데 (n)일경우는 1<n 이렇게 되는것으로 1보단 효율이 떨어진다
=> 자료구조별 설명은 https://passingwolf.tistory.com/11 해당 블로그의 해당 게시물을 확인해보길 바란다
정렬 알고리즘
| 선택정렬(Selection Sort) |
| ● 선택 정렬은 배열에서 최소값(또는 최대값)을 찾아 맨 앞(또는 맨 뒤)와 교환하는 방법입니다. ● 시간 복잡도: 최악의 경우와 평균적인 경우 모두 O(n^2) ● 공간 복잡도: O(1) (상수 크기의 추가 공간이 필요하지 않음) |
| 삽입 정렬(Insertion Sort) |
| ● 삽입 정렬은 정렬되지 않은 부분에서 요소를 가져와 정렬된 부분에 적절한 위치에 삽입하는 방법입니다. ● 시간 복잡도: 최악의 경우 O(n^2), 하지만 정렬되어 있는 경우에는 O(n) ● 공간 복잡도: O(1) (상수 크기의 추가 공간이 필요하지 않음) |
| 퀵 정렬 ( Quick Sort ) |
| ● 퀵 정렬은 피벗을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 분할하고 이를 재귀적으로 정렬하는 방법입니다. ● 시간 복잡도: 최악의 경우 O(n^2), 하지만 평균적으로 O(n log n) ● 공간 복잡도: 평균적으로 O(log n), 최악의 경우 O(n) (재귀 호출에 필요한 스택 공간) |
| 병합 정렬 (Merge Sort) |
| ● 병합 정렬은 배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후, 병합하는 방법입니다. ● 시간 복잡도: 모든 경우에 대해 O(n log n) ● 공간 복잡도: O(n) (정렬을 위한 임시 배열이 필요함) |
탐색 알고리즘
| 선형 탐색 (Linear Search) |
| ● 선형 탐색은 가장 단순한 탐색 알고리즘입니다. ● 배열의 각 요소를 하나씩 차례대로 검사하여 원하는 항목을 찾습니다. ● 시간 복잡도: 최악의 경우 O(n) |
| 이진 탐색 (Binary Search) |
| ● 이진 탐색은 정렬된 배열에서 빠르게 원하는 항목을 찾는 방법입니다. ● 중간 요소와 찾고자 하는 항목을 비교하여 대상이 중간 요소보다 작으면 왼쪽을, 크면 오른쪽을 탐색합니다. ● 시간 복잡도: 최악의 경우 O(log n) |
그래프 (Graph)
| 깊이 우선 탐색 (Depth-First Search, DFS) |
| ● 그래프의 분기를 만났을 때 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 다음 분기를 탐색 ● 스택구조의 함수재귀호출구조로 탐색을 쓴다 ● 시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수) |
| 너비 우선 탐색 (Breadth-First Search, BFS) |
| ● 그래프의 분기를 만났을 때 모든 분기를 저장한 뒤, 저장한 분기를 하나씩 탐색 ● 큐를 이용해 탐색을하는게 대부분이다. ● 시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수) |
| 최단 경로 알고리즘 (Shortest path problem) |
| ● 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구함 ● 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 후, 해당 노드를 거쳐 다른 노드로 가는 비용 계산 ● 방문(탐색)하지 않은 정점 중 가장 가까운 정점부터 탐색 ● 직접연결된 거리보다 거친거리가 더 짧아진다면 갱신. |
| A* 알고리즘 (A-star Algorithm) |
| ● 다익스트라 알고리즘을 확장하여 만든 최단경로 탐색알고리즘 ● 경로 탐색의 우선순위를 두고 유망한 해부터 우선적으로 탐색 ● 목적지의 방향이 정해진 다면 반대방향의 노드들은 나중에 선택하고 목적지 방향 노드(유망한 노드)를 우선선택하는 식으로 탐색을 진행한다. |
| 휴리스틱 (Heuristic) |
| ● 최상의 경로를 추정하는 순위값, 휴리스틱에 의해 경로탐색 효율이 결정됨 ● 맨해튼 거리 : 직선을 통해 이동하는 거리 ● 유클리드 거리 : 대각선을 통해 이동하는 거리 ● 타일맵용 유클리드 거리 : 직선과 대각선을 통해 이동하는 거리 |
해당사이트에서 탐색알고리즘 관련해서 시뮬레이션 가능함
https://qiao.github.io/PathFinding.js/visual/
마치며.
이번엔 잠시 쉬어가면서 각종 알고리즘에 대해서 알아보도록 했다
이 다음에는 유니티관련 해서 탐색하고 연구하면서 디자인패턴들에 대해서 알아가보고 싶다
'유니티개발 TIL' 카테고리의 다른 글
| 4주차 3일 TIL_유니티 입문(유사 2D메타버스 만들기_캐릭터 이동+추가편) (3) | 2025.07.24 |
|---|---|
| 4주차 2일 TIL_유니티 입문(유사 2D메타버스 만들기) (4) | 2025.07.22 |
| 3주차 5일 TIL_TextRPG심화(+추가 : 회피기능) (6) | 2025.07.18 |
| 3주차 4일 TIL_TextRPG심화(추가기능 및 버그수정) (1) | 2025.07.17 |
| 3주차 3일 TIL_TextRPG심화(상태패턴) (0) | 2025.07.16 |