Let's Girin!

1) 자료 구조 형태 중 트리 구조에 대한 설명트리(Tree) 구조는 계층적인 관계를 표현할 수 있는 자료 구조이다. 기본 단위는 노드이며, 각 노드는 데이터를 가지고 있고 다른 노드들과 연결될 수 있다. 가장 상위 노드를 루트 노드라고 하며, 그 아래에는 부모 노드와 자식 노드의 관계로 이어진다.가장 대표적인 트리 구조는 이진 트리로, 하나의 부모 노드가 최대 두 개의 자식 노드를 가지는 형태이다. 이진 트리는 탐색, 정렬, 계층적 구조 표현에 자주 사용된다. 2) 트리 구조를 사용하는 이유트리 구조는 탐색과 정렬에서 매우 효율적이기 때문에 사용된다. 특히 이진 탐색 트리(Binary Search Tree)는 정렬된 데이터를 다룰 때 탐색, 삽입, 삭제 연산의 시간 복잡도가 평균적으로 O(log N)..

🗂 목차1. 트리란?2. 이진 트리란?3. 이진 탐색 트리란?4. 힙이란?5. DFS vs BFS6. 시간 복잡도7. 게임 속 트리 구조1.  트리(Tree)란? 트리는 계층적 자료를 표현하기 좋은 비선형 자료구조이다. 트리는 루트(Root) 노드에서 시작하여 여러 자식 노드를 가질 수 있으며, 대표적인 예는 씬 그래프, UI 계층 구조, FSM(Finite State Machine) 등이 있다. • 노드(Node): 트리의 구성 요소 • 간선(Edge): 노드를 연결하는 선 • 루트(Root): 최상위 노드 • 리프(Leaf): 자식이 없는 노드class TreeNode { public int Value; public List Children = new();} 2. 이진 트리 (Binary..

1. 퀵 정렬퀵 정렬(Quick Sort)은 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복하여 정렬하는 알고리즘으로서, 분할 정복(divide-and-conquer) 방식을 사용한다.  1.1 분할배열을 두 개의 하위 배열로 분할하기 위해 피벗 요소를 선택하고, 피벗보다 작은 요소들은 왼쪽 하위 배열로, 피벗보다 큰 요소들은 오른쪽 하위 배열로 이동시킨다.1.2 정복각 하위 배열에 대해 퀵 정렬을 재귀적으로 호출하여 정렬한다.퀵 정렬은 추가적인 메모리를 사용하지 않고 주어진 데이터 구조 내에서 작업을 수행하도록 동작하므로 병합 과정이 필요 없다.2. 시간 복잡도퀵 정렬의 평균 시간 복잡도는  O(nlog⁡n)이다. 최악의 경우는 이미 정렬된 배열에서 피벗을 항상 최솟값이나 최..

1. 버블 정렬버블 정렬은 인접한 두 요소를 비교하여 필요에 따라 서로 위치를 바꾸는 방식이다. 이 알고리즘은 주어진 배열을 처음부터 끝까지 반복하여 정렬을 수행하며, 각 반복마다 가장 큰 (또는 작은) 요소가 배열의 맨 끝으로 이동하고, 이 과정을 배열이 정렬될 때까지 반복한다. 시간복잡도는 O(n^2)으로 다른 알고리즘보다 속도가 느리다.  2. 구현 방식데이터의 인접 요소끼리 비교하고, swap 연산을 수행하여 진행한다. 만약 특정한 루프의 전체 영역에서 swap이 한번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도 된다.  3. 문제 예제3.1 백준 1377번https://www.acmicpc.net/problem/1377   3.1.1 구현 방식1)..

1. 선택 정렬선택 정렬은 리스트를 순차적으로 탐색하여 가장 작은 또는 가장 큰 요소를 선택하고, 이를 정렬되지 않은 부분의 첫 번째 요소와 교환하는 과정을 반복한다. 이렇게 하면 리스트의 정렬되지 않은 부분이 점점 줄어들고, 결국 리스트 전체가 정렬된다. 선택 정렬의 시간 복잡도는 O(n^2)이다. 이는 두 개의 중첩된 반복문으로 인해 발생하는데 첫 번째 반복문은 리스트의 모든 요소를 반복하며, 두 번째 반복문은 나머지 요소들 중에서 최소값을 찾는다. 선택 정렬은 정렬된 상태와 상관없이 항상 동일한 시간 복잡도를 가지므로, 데이터의 초기 상태에 크게 영향을 받지 않는다. 2. 구현 방식2.1 주어진 리스트에서 최소값을 찾습니다.2.2 그 최소값을 리스트의 첫 번째 요소와 교환합니다.2.3 리스트의 첫 ..

1. 트리의 기본 개념 1.1 노드(Node) 트리는 노드들로 구성되어 있다. 각 노드는 데이터와 부모-자식 관계를 나타내는 링크(포인터)로 이루어져 있다. * 노드(node) : 데이터가 저장된 부분 * 엣지(edge) : 노드와 노드 사이를 잇는 선 트리는 노드와 노드 사이를 연결하는 엣지를 이용하여 계층을 구성한다. 트리의 계층 구조를 도식적으로 표현하면 나무 형태로 나타낼 수 있으며 이때 엣지는 나뭇가지처럼 표현된다. 트리의 중심이 되는 노드를 루트 노드라고 하며, 보통 가장 맨 위에 나타낸다. public class TreeNode { public T Data { get; set; } public List Children { get; set; } public TreeNode(T data) { D..

1. DFS(Depth First Search) 알고리즘 ● DFS 알고리즘은 깊이 우선 탐색 알고리즘으로, 트리나 그래프 자료구조에서 사용되는 탐색 알고리즘이다. ● 일반적으로 Stack 자료구조 또는 재귀 함수를 사용하여 구현할 수 있으며, 모든 노드 혹은 특정 조건의 노드를 찾는데 활용된다. ● 가능한 깊이 들어가면서 탐색하고 해당 노드의 방문 여부를 저장해 무한 루프를 방지하며 방문한 노드는 다시 방문하지 않는다. 2. 유니티 DFS 코드 구현 무한 루프를 방지하기 위해 탐색 중에 방문한 노드를 저장하고 적절한 종료 조건을 설정한다. public Class DFSClass { //시작 노드. public GameObject objStartNode = null; //방문 노드 저장. private ..