[게임 프로그래머 입문 올인원] 비선형 자료구조 1 : 재귀함수와 트리 기초(54, 55강)

C. 비선형 자료구조

최종 목표는 A*를 공부하는 것

 

근데 A*를 공부하려면 이렇게 많은 내용을 알아야 함 (순차적으로 공부할 예정)

 

1. 재귀함수

a. 재귀함수란?

🌟 자기 자신을 호출하는 함수

 

똑같은 함수를 재사용하면 그 상황을 묘사하는게 쉽기 때문에 사용함

 

🧡 스택 오버플로우

스택 프레임을 초과해서 사용하기 때문에 나타남
함수가 종료될 때 스택 프레임을 회수해야 하는데 계속 사용하기 때문에 
처음에 할당된 스택 메모리가 고갈되어 에러가 생김

 

b. 재귀함수 예제

1) n!

 

2) 유클리드 호제법

 

두 숫자에 대한 최대공약수를 구하는 알고리즘 

 

👉 여기에 잘 설명되어있음

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

면접때 나올 수 있음

 

 

2. 트리

a. 트리의 개념

🌟 계층적인 구조를 갖는 데이터를 표현하기 위한 자료구조

 

• 선형 자료구조로는 많은 노드들이랑 연결되어 있는 상황을 표현하기 어려워 트리를 사용
• 트리는 구조적으로 1에서 배운 재귀함수랑 많은 연관이 있음

 

 

트리의 예시

 

b. 트리의 사용

👉 우선순위 큐 레드블랙 트리로 서칭 정도를 위해 사용됨

 

즉, 개발시 만들일이 많이 없음. 특성 트리(게임 개발), 고급 기법의 베이스정도 

공부할 떄 필수적인 내용이지만 자주 활용되지는 않는다

 

c. 트리 관련 용어

• 부모노드
• 자식노드
• 형제노드
• 선조노드
• 자손노드
• 루트(최고 조상)
• 잎(제일 손자)
• 깊이(얼마나 내려가야 하는지)
• 높이(얼마나 올라가야 하는지) : 트리에선 제일 깊은 자식부터 높이를 잰다
• 트리의 재귀적 속성 및 서브트리

 

d. 트리의 구현

별도의 클래스를 제공하지 않기 떄문에 기존 클래스로 구현해야 함

 

리스트를 사용한 것 처럼 노드라는 개념으로 데이터가 생성,

데이터는 동적으로 늘어날 수 있음 ➡ 벡터를 사용

 

👉 표준 벡터를 사용해 구현해볼 것임

 

📄 main()함수가 있는 cpp파일

 

표준 벡터를 받아주고

 

벡터를 자식으로 하는 노드를 생성

 

그 노드를 사용해 트리 구조를 생성해준다 (접힌부분 동일)

 

메인에서 실행해주면 이렇게 트리구조로 생성되어있다

 

e. 트리 출력

위에서 생성한 root를 재귀함수를 사용해서 트리의 내용을 출력하자

 

1. 루트의 데이터 먼저 출력
2. 루트의 자식 개수를 센다음
3. 자식들만큼 재귀함수를 돌려줌 

잘나온다

 

f. 트리의 깊이와 높이

1) 깊이

 

루트에 있는 모든 데이터를 출력하려면 depth 변수를 사용해 출력함

 

위 코드에서 빨간줄 추가하고 실행하면

 

계층구조가 잘 나타난다

 

2) 높이

 

트리구조에서 높이는 가장 깊은 자식을 기준으로 잡음

 

높이를 출력하려면 자식들간의 높이를 비교한 후 가장 높은걸 출력함

 

넥슨 면접에 나온 문제!

 

 

 

---

출처 : https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss#curriculum

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버 -