A. 자료구조
1. 선형과 비선형
a. 선형구조
🌟 자료를 순차적으로 나열한 형태
- 배열
- 연결리스트
- 스택 / 큐
👉 대부분의 경우 이 선형구조를 사용함
b. 비선형 구조
🌟 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태
- 트리
- 그래프
2. 선형 자료구조 (배열 vs 동적배열 vs 연결리스트)
a. 배열
🌟 사용할 방 개수를 고정해서 계약 (절대 변경 불가)
연속된 방으로 배정받아 사용
👍 장점
연속된 방
👎 단점
방을 추가 / 축소 불가
👉 사용하는 경우 : 맵, 커스터마이징, 인벤토리 등 절대 변하지 않는 경우
하지만 동적배열과 크게 구조상 다를게 없기 때문에 동적배열로 생성해도 상관 없음
b. 동적배열
🌟 사용할 방 개수를 유동적으로 계약
연속된 방으로 배정받아 사용, 가장 많이 사용된다
데이터를 이동해야 한다면 이사 비용이 생겨 횟수를 최소화 해야 함
👉 할당 정책 : 실제로 사용할 방보다 많이 여유분까지 (최대 2배) 예약
👍 장점
유동적인 계약이 가능 (방 여유분 추가 예약으로 이사 횟수 최소화)
연결리스트보다 속도가 빠름
👎 단점
중간 삽입 / 삭제 불가
👉 사용하는 경우 : 거의 대부분의 상황에 사용됨
🧡 C#과 C++의 차이점C#에서는 list가 vector!
c. 연결리스트
🌟 연속되지 않은 방을 사용
👍 장점
중간 삽입 / 삭제 가능
👎 단점
n번째 방을 바로 찾을 수 없음 (임의 접근 Random Access 불가)
👉 사용하는 경우 : 대기열일때 중간에 누군가가 빠져야 할 때
🧡 임의 접근
N번째 방이 몇번 방인지 바로 찾을 수 있는지 알려주는 것Sorting하다보면 임의 접근이 필요한 부분임
3. 시간 복잡도에 따른 동적 배열과 연결리스트
👉 시간 복잡도란?
[게임 프로그래머 입문 올인원] 선형 자료구조 : 시간복잡도 (49강)
A. 시간복잡도 1. BIG-O 표기법 알고리즘의 효율을 객관적으로 측정하기 위해 사용 a. 대략적인 계산 b. BIG-O 표기법의 규칙 c. BIG-O 표기법의 의의 d. Log 함수 출처 : https://www.inflearn.com/course/%EA%B2%8C%EC%
monamu.tistory.com
✒ 47, 48강을 공부하고 와야 이해할 수 있음
[게임 프로그래머 입문 올인원] 선형 자료구조 1 : 연결 리스트 (47강)
B. 선형 자료구조 1. 연결 리스트 a. 노드 🌟 리스트를 구현할 때 가장 핵심 46강에서 설명한 것 처럼, 101호 방 자체(데이터 공간)를 노드로 표현한다 b. 노드로 연결리스트 생성 (단방향) c. 단방향
monamu.tistory.com
[게임 프로그래머 입문 올인원] 선형 자료구조 2 : 동적배열 (48강)
B. 선형 자료구조 2. 배열 a. Array 생성하기 STL에서 array라는 클래스를 만들어 사용하길 권장 기본적인 틀인 버퍼, 사이즈, 용량을 작성해줌 b. 생성/소멸자 만들기 버퍼는 용량에 따라 생성 explicit
monamu.tistory.com
데이터의 삽입/삭제에 따른 시간 복잡도 분석할 것임
a. 동적 배열 (vector)
1) 시작 0(N)
중간과 다를게 없다
2) 중간 0(N)
1 / 2 / 3 / 4 / N / 5 / 6 / 7 ➡ 이런식으로 데이터가 들어가야 한다면
N/2로 위치를 찾아야 함
3) 끝 0(1)
push_back : 데이터를 증설하는 작업은 어느 시점부터는 안정화가 되기 때문에 1이 됨
4) 임의접근 0(1)
operator[] 는 아무때나 접근 가능하니 1
b. 연결 리스트 (List)
1) 시작 0(1)
head 부분에 연결하면 됨
2) 중간 0(1)
중간에 데이터를 넣는게 1인 이유는 위치를 기억하고 있을 때에만 빠름
심지어 단방향일 경우엔 전/후 데이터를 둘 다 알아야 연결 가능하지만
양방향일 경우엔 삭제할 데이터의 전후 데이터가 있기 때문에 빠르다
3) 끝 0(1)
tail 부분에 연결하면 됨
4) 임의의 인덱스 접근 0(N)
하나하나 찾아봐야 하니까 N
[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버 -
어디부터 시작할지 막막한 게임 프로그래밍 입문자를 위한 All-In-One 커리큘럼입니다. C++, 자료구조/알고리즘, STL, 게임 수학, Windows API, 게임 서버 입문으로 이어지는 알찬 커리큘럼으로 게임 프
www.inflearn.com
'자료구조와 알고리즘 > Data Structure' 카테고리의 다른 글
| [게임 프로그래머 입문 올인원] 선형 자료구조 3 : 스택 & 큐 (53강) (1) | 2024.02.15 |
|---|---|
| [게임 프로그래머 입문 올인원] 선형 자료구조 실습 2 : 플레이어 이동하기(51강) (0) | 2024.02.15 |
| [게임 프로그래머 입문 올인원] 선형 자료구조 실습 1 : 미로 맵 만들기(50강) (0) | 2024.02.14 |
| [게임 프로그래머 입문 올인원] 선형 자료구조 2 : 동적배열 (48강) (0) | 2024.01.23 |
| [게임 프로그래머 입문 올인원] 선형 자료구조 1 : 연결 리스트 (47강) (2) | 2024.01.23 |