[멋쟁이사자처럼 부트캠프 TIL회고] Unity 게임개발 3기 19일차

목표 : 배우던 중, 헷갈리거나 모르는 개념 복습, 프로그래머스 코테 최대한 많이 풀어보기.

 

자료구조와 알고리즘

자료구조(Data Sturcture)

• 데이터를 효율적으로 저장하고 관리하기 위한 '방법이나 구조'
• List, Array, Stack, Queue, Tree, Graph 등이 있음
• 프로그램의 성능과 메모리 사용 효율을 개선하는데 중요한 역할

알고리즘(Algorithm)

• 문제를 해결하거나 특정 작업을 수행하기 위한 절차나 규칙의 집합
• 효율성과 정확성이 중요
• 정렬, 탐색, 최적화

유니티 c#에서 자주 쓰이는 자료구조와 알고리즘 

 

자료구조

• 리스트(List) : 다수의 동적 오브젝트들을 동적으로 저장하고 관리하는데 이용 ( 인벤토리, 적 스폰 목록 등)
• 딕셔너리(Dictionary) : 키-값 쌍을 이용해 빠른 검색이 필요할 때 사용 ( 게임 내 설정 데이터 매핑 등)
• Queue : FIFO 방식 ( Al 행동 큐나, 이벤트 처리 // 우리가 배운 우선순위 큐를 생각해 볼 것)
• Stack : LIFO 방식 ( 뒤로 가기 기능)
• Graph : 노드 기반의 데이터 연결 구조 (길찾기 등)
• Tree : 계층 구조를 표현 할 때 사용( 씬 계층 구조, 상태 트리, UI 계층 관리,퀘스트 또는 대화 트리)

알고리즘

• 길찾기 알고리즘
• 정렬 알고리즘
• 물리 계산
• 상태 관련 알고리즘
• LOD 알고리즘

알고리즘 관련해서는 아직 배우지 않았기 때문에 자세하게 적지 않았다. 

주말에 공부하고 놀 때 하나 둘 씩 영상 찾아보자.

 

 

 

개념 복습

배열 (Array)

 배열

• 가장 기본적이고 널리 사용되는 자료구조
• 동일한 데이터 타입 요소들을 '연속된' 메모리 공간에 저장
• 인덱스를 통해 빠르게 개별 요소에 접근 가능

장점

• 빠른 요소 접근 : O(1) 시간 복잡도
• 메모리 효율성  : 연속된 메모리 할당  -> 캐시 효율성 
• 간단한 구현     
• 다차원 데이터 표현  : 행렬, 이미지 등에 적합

단점

• 고정된 크기 : 동적 크기 조절 불가
• 삽입/삭제  비효율성 : O(n) 시간 복잡도
• 메모리 낭비 가능성 : 선언된 크기만큼 메모리 차지
• 연고나 데이터 저장 어려움 : 다른 자료구조에 비해 복잡한 데이터 구조 표현이 어려움

https://learn.microsoft.com/ko-kr/dotnet/api/system.array?view=net-8.0

Array 클래스 (System)

 

 

 

Collection

• 하나의 이름 아래 여러개의 데이터를 묶어서 관리하는 것
• 크기가 정해져 있지 않음 (배열과 다른점)
• Dictionary, List, Queue, SortedLsit, Stack, ArrayList, Hashtable 등이 있음

리스트 (List)

List

•  배열을 기반으로 구현된 자료구조
•  데이터가 연속된 메모리 공간에 저장
•  인덱스를 통해 데이터 즉시 접근 가능(O(1))
•  배열 크기의 리사이징이 필요한 경우가 있음

장점

• 데이터 접근 속도가 빠름(O(1))
• 크기가 자동으로 조절, 고정된 크기 배열보다 유연

단점

• 삽입/삭제 시 데이터 이동이 필요하여 성능이 저하될 수 있음

 

https://learn.microsoft.com/ko-kr/dotnet/api/system.collections.generic.list-1?view=net-8.0

List<T> 클래스 (System.Collections.Generic)

 

 

 

연결 리스트 (Linked List)

Linked List

• 데이터의 요소(노드)가 다른 노드와 포인터로 연결된 구조
• 메모리 상에서 연속적이지 않은 위치에 저장 가능

종류

• 단일 연결 리스트(Singly Linked List)
• 이중 연결 리스트(Doubly Linked List)
• 원형 연결 리스트(Circular Linked List)

장점

• 동적 크기 : 필요에 따라 크기 조절 가능
• 삽입/삭제 효율성 : 포인터만 변결하면 되므로 O(1)의 시간 복잡도(앞뒤만)
• 메모리 효율 : 필요한 만큼만 메모리 사용
• 데이터 재구성 용이 : 노드의 연결만 변겅하면 재구성 가능

단점

• 임의 접근의 비효율성 : 특정 위치 접근시 O(n) 시간 복잡도
• 추가 메모리 사용 : 포인터를 저장하기 위한 메모리 필요
• 캐시 비효율 : 메모리상 연속적이지 않아 캐시 활용도가 낮음
• 역방향 탐색 어려움(단일의 경우)

실제 사용

1.  웹 브라우져의 앞/뒤 탐색 기능
2.  음악 플레이어 재생 목록
3.  운영체제의 프로세스 관리
4.  메모리 관리: 가용 메모리 블록 연결
5.  다항식의 표현과 계산
6.  큰 숫자의 표현과 계산( 각 자릿수를 노드로)

https://learn.microsoft.com/ko-kr/dotnet/api/system.collections.generic.linkedlist-1?view=net-8.0

LinkedList<T> 클래스 (System.Collections.Generic)

 

 스택 (Stack)

Stack

• 간단한 LIFO(Last In First Out) 방식을 따르는 선형 자료구조
• 배열 또는 연결 리스트로 구현 가능
•  일반적으로 메모리에서 연속된 공간을 차지하며, 동적 크기 조정 가능
•  배열 기반과 연결 리스트 기반이 차이가 있다. 

장점

•  간단한 구현 : 동작 원리가 단순하고 구현이 쉬움
•  효율적인 연산 : 삽입(Push)와 삭제(Pop)가 O(1) 시간 복잡도를 가짐
•  함수 호출 관리 : 함수 호출 스택 등 메모리 관리에서 활용

단점

• 크기 제한(배열 기반) : 초기 크기가 고정되어 크기를 초과하면 재 할당 필요
• 선형 데이터 : 계층적 관계를 표현하는데 부적합
• 임의 접근 불가 : 특정 요소에 접근하려면 순차적으로 접근해야 함

실제 사용

• 재귀 함수 호출 관리
• 문자열 역순 출력 : 어 이걸로 코테 입문 문제 풀었으면 엄청 쉬웠겠다.. 다시 풀어봐야지
• 괄호 검증  // 직접 해본 경우, 15일자 자료에 보면 있다
• 탐색 알고리즘 : DFS(Depth First Search)에서 스택 사용
• Undo/Redo 기능 : 게임에서의 이전/다음 상태를 저장.

https://learn.microsoft.com/ko-kr/dotnet/api/system.collections.stack?view=net-8.0

Stack 클래스 (System.Collections)

  큐(Queue)

Queue

• 선입선출(FIFO, First In First Out) 원칙을 따르는 선형 자료구조
• 배열이나 연결 리스트로 구현 가능
• 고정 크기(배열) / 동적 크기 (링크드 리스트 키반) 두 방식으로 동작

종류

• 기본 큐(Simple Queue) : FIFO의 기본 형태
• 원형 큐(Circular Queue) : 배열 기반 큐에서 빈 공간을 줄이기 위해 끝에서 처음으로 연결
• 우선순위 큐(Priority Queue) : 데이터에 우선순위를 부여해, 높은 우선순위 데이터 먼저 처리
• 양방향 큐(Deque, Double-Ended Queue) : 삽입/삭제를 양쪽에서 모두 가능하게 한 큐

장점

• 순차적 데이터 처리 
• 효율적인 데이터 흐름 관리 : 삽입과 삭제가 빠르게 수행됨 (O(1), 연결 리스트 기반 시)
• 다양한 응용 : 작업 예약, 데이터 흐름 처리, 탐색 알고리즘 등에 사용

단점

• 임의 접근 불가 : 특정 요소에 접근할 시 순차 탐색(O(n)) 필요
• 고정 크기 문제(배열 기반 큐) : 크기 초과 시 재할당
• 메모리 낭비 가능성 (원형 큐가 아닌 배열 기반 큐) : 사용되지 않는 공간이 있을 수 있음

실제 사용

1. 적 스폰 시스템
2. AI 행동 관리
3. 이펙트 관리(풀링 시스템) //만들어 봤음
4. 이벤트 처리
5. 경로 찾기 (BFS) : 알고리즘에서 큐를 사용해 탐색 노드를 관리

https://learn.microsoft.com/ko-kr/dotnet/api/system.collections.queue?view=net-8.0

Queue 클래스 (System.Collections)

 

  힙(Heap)

Heap

• 트리 구조 : 완전 이진 트리 구조
• 최대 힙/최소 힙이 존재 ( 최대 힙 : 부모 노드 값>= 자식 노드 값 최소 힙 부모 노드 값<= 자식 노드 값 )
• 배열 혹은 리스트로 구현

장점

• 우선순위 관리 : 최대값/최솟값을 빠르게 찾고 처리 가능
• 효율성 : 삽입 및 삭제가 O(log n)으로 빠름
• 동적 크기 : 배열 기반 힙은 크기가 유동적

단점

• 임의 접근 불가 :순차 탐색이 필요
• 구조 유지 비용 : 삽입/삭제 시 힙 속성을 유지하기 위해 추가적인 연산(Heapify)가 필요

실제 사용

1.  우선순위 큐  : 작업을 우선순위에 따라 정렬하여 처리. // 만들어봤음
2.  이벤트 처리 시스템 : 중요한 이벤트를 먼저 처리
3.  스케줄링 시스템 : 타이머 또는 작업 우선순위 관리

개념 복습은 오늘 간단하게 이정도로 하고, 남는 시간에는 프로그래머스 코테 입문 문제 정복을 위한 시간 !

내일은 몰랐던 개념들이나 헷갈렸던 개념 (LINQ, 프로퍼티 등) 을 알아보고 공부해보자.