알고리즘 - (2) 자료구조/알고리즘 이론 (2)
3. Linked List 심화
3.1. 개요
- 일단 선결론은 게임 개발에서 자주 쓰이는 것은 아니다.
- 값들을 선형적으로 나열하는 구조인데 반드시 연속된 곳에 배치하진 않는다.
- 그래서 자료 구조상에서 상당히 중요하다.
- 진짜 의미를 이해해야 한다.
- 이것도 직접 구현하는 것도 언젠가 해야 할 것.
3.2. 사용
- 가령 쪽지는 다음과 같이 구성되었다 가정한다.

<김플레티넘수, 김다이아수...김철수...>
- 이전에 누구고 다음은 누군지 알고 있었고 이것을 선형적으로 나열할 수 있고 다음 원소에 대한 참조를 통해 element를 이어줌으로써 이뤄진다.
- 이전 것이 없으면 처음, 다음것이 null이면 끝이라는 것이다.
- 중간에 끼어들고 싶다면

- 이런 식으로 끼워넣는 방식.
- 연산상 참조를 걸어주는 것이 얼마 걸리지도 않는다. 그래서 이 방식자체가 빠를 수 밖에 없다.
3.3. 도식화
- 그렇지만 이런 구조라면?

- index에 무엇이 있는지 알고 있음에도 next를 통해 들어갈 수 밖에 없는 구조이다.
- 따라서 게임에서는 잘 안쓰게 되는 것.
- 이런 구조를 기반으로 게임 시스템을 만들수도 있는 것.
- 특정 스탭을 가야 하는 flow가 있는 경우에는 쓸 수 있을 것.
- 연결 List는 하나의 데이터 단위를 머리 속에 가장 먼저 떠올리면 문제될 것은 없다.
- 데이터 덩어리 하나 단위를 node라고 표현한다.
- 이 자료구조의 형식은 노드에 따라 다를 수는 있다.
- 이 도식화는 생각보다 많을 것.
3.4. 종류
- 이 노드에서 다음 노드에 대한 참조를 가지고 있고 이전 데이터의 참조를 가지고 있으며 맨 끝에 것에 대한 것이 처음 노드 참조를 가지는 형태 등 생긴 모양에 따라 단일, 이중, 원형 연결 리스트로 나누게 되는 것.
- 아예 섞어서도 있다.
- 그래서 명칭보단 그림을 떠올리는 것이 가장 좋을 것.
- 클래스 같은 것에서 참조 타입 대입을 통해 서로 이어주는 것이 가능했다.
- 그래서 화살표로 표현했지만 다음 노드에 대한 참조를 가지게 되는 것.
- 메모리 연속된 위치에 할당이 안된다.
- 각 노드는 다음 노드나 이전 노드의 참조를 저장한다.
- 삽입 삭제가 효율적이다
- 흔하진 않지만 중간에 삽입 삭제가 활발해야 하나 index가 아닌 순회를 한다면 연결 리스트가 정답일 수 있다.
- 읽기와 검색의 경우는 연결 리스트에서는 O(n)일수밖에 없다. 단, 추가 삭제는 O(1)을 지님.
- 정확히 List 때와는 반대.
- Linked List도 다양한 기능을 제공한다.

- C# Linked List는 이중 연결 리스트로 구현이 되어 있다.
- 그래서 Linked List는 직접 써봐야 한다. 처음 쓸 때가 어렵다. 특정 노드 정보를 알아야 할 때도 있기 때문.
3.5. 내부 구조
- 예를 들어, 다음과 같은 상황이 있다고 가정한다.

- 새로운 데이터를 끼워 넣은 다음에 이전에 대한 참조가 없으므로 참조를 이어주고 다음 것에 대한 참조를 이어주며 추가된 것을 First라고 하면 끝난다.

- 이게 개념적으로는 쉽지만 코드적 처음 접근은 어려운 것이 중간에 데이터를 추가하고 싶다고 가정을 한다면

- 이 위치에 추가하고 싶으면 순회를 돌다가 특정 위치가 나오면 추가, 그 사이에 참조를 이어준다 이 두가지가 존재.
- 적재적소에 참조를 들고 있는 것이 중요할 수 있다.
- 기준이 있다고 한다면

- 이 노드를 기준으로 AddAfter()를 이용하면

- 추가가 된다
- 이전이면 AddBefore()를 사용한다.
3.6. 사용
- 순회 순서는 맨 끝인지 맨 앞인지 선택이다.
- 중간에 데이터가 추가되는 것들을 염두했다보니 추가한 기능들이 다양함.
- 노드라는 단위 역시 그대로 구현이 되어 있다.
- 노드에서는 자기가 가져야 하는 값들과 이전, 이후의 참조를 가진다는 것.
- 내가 가질 값, 이전 것이 무엇인지 참조, 이후가 무엇인지 참조.
- 프로퍼티들과 함수들이 상당히 직관적인 구성을 지닌다.
- 이제 사용을 해볼 것이다. 스크립트를 하나 만들어 준비. 그리고 할당까지 해둘 것.

- Start에 로그로 할당해본다.

- 문제는 null 상태라 터진다.

- 여기에서 다음과 같이 진행.다음과 같이 하나만 출력되었는데

- 현재 이런 상태이다.
- LinkedList에는 데이터가 하나인데 First인데 마지막일 수 있다.
- 이유는 하나만 들어있기 때문.

- 여기에 AddFirst를 추가하면?

- 이러면 다음과 같이 된다.


- 91이 First, 58이 라스트가 된다.
- 추가로 데이터를 넣는다.

- 네번째 줄에서는

- 다음과 같이 진행된다.
- 그래서 이것을 로그를 조금 다르게 가져가보면

- 순서대로 로그가 나옴을 볼 수 있다.

- 그래서 이런 상황인데 구도는 다음과 같다.
[33] [91] [58] [75]
- 이젠 특정 노드를 기준으로 추가를 해볼 것이다.

- 변수형에 담아볼 것이다.
- LL 추가하는 함수는 LinkedList 노드를 반환하는 경우가 많다.
- 그림 상으로는

- 58 노드에 대한 참조를 가지게 된다.
- 이 상황에서

- 위 기준으로 잡았을 경우, 현 상태에서 이어져 있었는데

- 타겟 이전에 추가한다고 했으므로 참조가 한 번 끊기고 노드가 비집고 들어가면서 참조를 다시 이어주고 이와 같은 형식을 보여준다.


- 의도대로라면 이렇게 나와야 할 것이고 잘 나온다.
- 이제 아까본 바로는 Next라고 하여 다음 노드에 대한 참조를 가지고 이전의 참조 Previous를 가졌다.
- 예를 들어 다음과 같이 진행.

- 이 경우에는, 이렇게 될 것이다.


- 그러니까 .을 찍고 타고 들어가는 것이다.
- 약속을 외운다기 보다는 반환받은 형식에서 무언가이다.

- 정말 이런 형식까지도 가능은 하지만 하지 말 것.
- 또 다르게는

- 이러한 케이스는 터지는 경우
- 차라리 참조를 보관하는 방식을 택하는 것이 정공한 방법이다.
- 내부적으로 극적인 변화는 없고 조정하여 정렬하는 것이다.
- 이것을 어디에 쓸건가 생각해보면 순서대로 흘러가는 것.
- 단방향 원형 연결 리스트면 턴제 구현이 가능할 것이다.
- 또는 인터페이스를 가져가도 될 것이다.
- 한 노드에 갔을 때 수행해야 하는 것을 적고 다음 노드 참조
- 죽는다면 연결 리스트에서 뺄 순 있고.
- 하지만 게임에서 사용될 경우는 드물다고 알 것.
- 주로 사용할 method는 이렇다.

- 실습하면서 써보면 될 일이다.
- Monster라는 스크립트에서 이런식의 플롯이 있다고 해보자.


- 컴포넌트에 추가

- Test에는 다음과 같이.

- 그 다음에 초기화와 동시에 호출.

- 다음, Update에서 배열을 받지만 한 번에 스캔해서 전투에 추가해야 하면 연결 리스트에 추가하면 될 일이다.
- 시행을 하면


- 지금의 경우는 C# LL는 기본적으로 이중 연결로 되어 있다.
- 그래서 턴 웨이브를 잘 구현하기 힘든데 TurnFlow에 해당하는 자료구조를 만들 때 원형 연결리스트로 만든 다음에 처음으로 돌아가게끔 해야 한다.
- 대신 전투가 끝나는지 조건에 대해 잘 잡아줘야 한다.
- 어쨋든 턴의 흐름은 LL을 통해 쉽게 접근이 가능해진다.
- 그리고 추가적으로 Monster 기준이 아닌 인터페이스로 빼거나 전투에 참가할 수 있다는 인터페이스를 정의하고 플레이어든 NPC든 몬스터든 그 턴 안에서 진행될 것이며 세부적 구현은 클래스에서 진행.




