자료구조 (4) 썸네일형 리스트형 알고리즘 <삽입 정렬(Insertion Sort)> 개요 및 정의하기 이번 포스팅에서는 기본 정렬 알고리즘인 삽입정렬에 대해 다룹니다. 삽입정렬(Insertion Sort) 삽입 정렬은 정렬이 필요한 모든 요소들 처음부터 시작하여 이미 정렬된 배열부분 중 정렬이 필요한 요소의 위치를 찾아 삽입하여 정렬하는 방식입니다. 설명하기 삽입 정렬이 어떤 방식으로 정렬 되는지 직접 사진으로 분석해보겠습니다. 3,7,2,5,1,4 라는 값을 정렬하려합니다. 맨 처음 3은 정렬되어있다고 가정하고 7 부터 검사합니다. 7이 3보다 작은지 검사하고 그렇지 않은경우 다음 인덱스로 이동합니다. 이제 3과 7까지 정렬되어있다고 가정하고 2의 값의 위치를 찾아갑니다. 2는 7보다 작기에 한칸 앞으로 당깁니다. 마찬가지로 2가 3보다도 작으므로 한칸 더 앞으로 당기면 (c) 와 같.. 자료구조 <행동 트리(Behavior Tree) 기반의 AI 구현하기> 행동트리(Behavior Tree) 정의하기 행동트리(Behavior Tree)란? 트리 기반의 모델로 게임 내에서 AI 혹은 대화 시스템 등 다양한 분야에서 사용이 가능합니다. 행동 트리를 이루는 노드는 루트 노드를 제외하고 셀렉터(Selector), 시퀀스(Sequence), 액션(Action) 세 종류의 노드들로 구성되어 있으며 각 노드들은 저마다의 규칙을 가지고 있습니다. 또한 가장 왼쪽노드를 우선으로 처리합니다. 세 종류의 노드는 공통적으로 성공, 실패, 진행중 상태를 갖습니다. 그리고 행동의 결과가 어떤 상태인지 평가하여 반환하는 메서드가 존재합니다. Action 노드 : Excution 노드 라고도 하며 리프 노드로 자식을 가지지 않습니다. Aciont 노드는 행동 트리에서 해당 행동에 대한.. 자료구조 <이진 트리(Binary Tree) 데이터 순회> 개요 트리의 순회는 말그대로 데이터를 순회하는 방식을 말합니다. 크게 세 종류이며 각각 전위 순회( preorder traverse ), 중위 순회( inorder traverse ), 후위 순회( postorder traverse ) 라고 불립니다. 본문 먼저 전위, 중위, 후위 순회의 방법부터 살펴보겠습니다. 전위 순회 : 부모 => 왼쪽 => 오른쪽 순으로 순회합니다. 중위 순회 : 왼쪽 => 부모 => 오른쪽 순으로 순회합니다. 후위 순회 : 왼쪽 => 오른쪽 => 부모 순으로 순회합니다. 전위 순회로 순회 : 8 > 5 > 3 > 6 > 2 > 4 > 9 중위 순회로 순회 : 3 > 5 > 6 > 8 > 4 > 2 > 9 후위 순회로 순회 : 3 > 6 > 5 > 4 > 9 > 2 > 8 순회 .. 자료구조 <트리(Tree), 이진 트리(Binary tree), 이진 탐색 트리(Binary Search Tree)> 개요 및 정의 오늘은 자료구조 중 하나인 트리에 대해 다루어 보려합니다. 트리는 그래프의 일종으로 큐, 스택, 리스트 같은 선형 구조와는 달리 비선형 구조로 되어있으며 계층적 특징을 가지고있습니다. 또한 트리는 순환 구조를 가지지 않습니다. 여기서 순환 구조란, 노드의 연결 방향이 서로 순환하는 구조를 말합니다. 위 사진에서 만약에, H 노드와 I 노드가 서로 연결되어있다면 D노드, H노드, I노드는 순환구조입니다. 트리구조의 기본 용어 루트(Root) : 트리에서 가장 꼭대기에 위치한 노드 간선(Edge) : 노드와 노드를 잇는 연결선 단말 노드(Leaf) : 아래로 또 다른 노드가 연결되어 있지 않은 노드 내부 노드 : 단말 노드를 제외한 모든 노드 부모 노드 : 세 노드가 트리구조일 때 상단에 위치.. 이전 1 다음
