분류 전체보기 (15) 썸네일형 리스트형 알고리즘 < 버블 정렬(Bubble Sort)> 버블 정렬 개요 버블정렬은 정렬알고리즘 중에서 비교적 쉬운 정렬 알고리즘으로 구현이 쉽고 간편하게 사용할 수 있지만 성능면에서는 다소 아쉬운 알고리즘입니다. 이번 포스팅에서는 버블정렬이 무엇인지 그 원리를 이해하고 직접 코드로 구현해보는 과정까지 작성해보겠습니다. 버블정렬의 원리 배열에 왼쪽부터 차례대로 3, 2, 4, 1 이란 정수가 담겨있다고 가정합니다. 이를 오름차순으로 정렬하면 1, 2, 3, 4 가 될 것입니다. 버블 정렬은 쉽게 말해 현재 값과 다음 값을 비교하며 정렬하는 방식이라 볼 수 있습니다. Current 는 현재 인덱스이며 Next 는 현재 인덱스의 바로 다음 인덱스입니다. 오름차순으로 정렬할 것이므로 두 값을 비교하여 더 작은 값을 앞에 배치해야합니다. 위의 예시대로라면 두 값을 서.. 알고리즘 <이진 탐색 알고리즘 시간 복잡도 계산하기> 보호되어 있는 글입니다. C++ <가상 함수의 동작 원리> V-Table & V-Pointer 가상 함수의 동작 원리를 이해하기 위해 꼭 필요한 개념인 V-Table와 V-Pointer에 대해 먼저 알아봅시다. V-Table 란? - 하나 이상의 가상 함수를 가진 클래스에 대해서 컴파일러에서 만들며 바이너리 'rdata' 영역에 기록되는 테이블 - Key 와 Value 로 구성되어 있으며 Key 를 통해 Value 에 접근하는 방식으로 Key 에는 함수 식별자, Value 에는 함수의 주소 정보가 저장됨. V-Pointer 란? - V-Table 의 주소를 참조하는 포인터 변수로 가상 함수를 가진 클래스로 객체를 생성했을 때 그 생성된 각각의 객체가 V-Pointer 를 갖고있음. V-Table 생성 원리 AAA 라는 클래스가 존재하고 BBB 클래스가 이를 상속.. Unity <스크립터블오브젝트(ScriptableObject) 사용하여 몬스터의 아이템 드랍 구현하기> 직렬화, 역직렬화 개념 이해하기 직렬화란 데이터 구조, 오브젝트 상태를 동일하게 하여 어디서든 읽을 수 있도록 변환하는 과정입니다. 직렬화가 되는 방식에는 문자열(string)형식 혹은 바이너리(binary)형식이 있습니다. 반대로, 역직렬화란 직렬화가 되어있는 데이터로부터 그 구조를 추출하는 과정을 말합니다. 기본적으로 유니티 인스펙터창에는 직렬화가 가능한 혹은 직렬화가 되어있는 데이터들만 표시될 수 있습니다. 예를 들어, 플레이어의 능력치를 저장해둘 클래스를 만들고 플레이어가 이를 참조하는 형태를 만들어보겠습니다. public class PlayerStats { public int currentHealth; public int maxHealth; public int attackPower; } publ.. 디자인 패턴 <상태 패턴(State Pattern) #2> StateMachine 클래스 개요 지난 포스팅에서 Player 클래스가 State 변수를 가지고 있도록 하여 상태 패턴을 구현했었습니다. 하지만, 이렇게 구현할 시 상태가 전환 될 때 마다 힙 영역에 클래스가 할당된다는 단점이 있었습니다. 이를 보완하고자 StateMachine 클래스를 새로 만들어 상태 패턴을 재구성 해보겠습니다. StateMachine 클래스 소개 using System.Collections; using System.Collections.Generic; using UnityEngine; public class StateMachine { Dictionary stateDic; // 상태들을 저장할 딕셔너리 public BasicState curState; // 현재 상태 변수 publi.. 디자인 패턴 <상태 패턴(State Pattern) #1> 유한 상태 머신(FSM) 개요 상태 패턴은 유한 상태 머신(Finite state Machine)을 객체 지향 방식으로 구현하는 디자인 패턴입니다. 그래서 상태 패턴에 대해 이해하기 위해서는 유한 상태 머신에 대해 알 필요가 있습니다. 유한 상태 머신이란 유한한 개수의 상태를 가질 수 있는 도구로서 한 객체가 한 번에 오로지 하나의 상태만을 가지게되며 어떠한 이벤트가 발생했을 때 한 상태에서 다른 상태로 전환할 수 있습니다. Swich-case 문을 활용하여 FSM 구현하기 Player 객체가 있다고 가정해 봅시다. Player 객체는 Idle(대기), Walk(걷기), Run(뛰기) 상태를 가지고 있습니다. 이 상태들을 나타낼 STATE_TYPE 열거형부터 정의해 보겠습니다. public enum ST.. 알고리즘 <BFS, DFS 활용하여 경로 탐색 구현하기> BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 정의하기 너비 우선 탐색(BFS)이란 : 루트 노드를 시작으로 인접한 노드부터 차례로 탐색하는 방법 시작 정점으로부터 가장 가까운 노드를 시작으로 순차적으로 검색하는 방법. 왼쪽부터 차례로 탐색한다. 깊이 우선 탐색(DFS)이란 : 루트 노드를 시작으로 다음 가지로 넘어가기 전에 해당 분기를 전부 탐색하는 방법. 만약, 어느 한 분기의 깊이가 무한하면 다음 분기로 넘어갈 방법이 없기때문에 깊이를 제한한다. 깊이 제한에 도달하였는데도 목표 노드가 발견되지 않으면 해당 노드의 부모 노드로 되돌아 오는데, 이를 백 트래킹(BackTracking) 이라 한다. 경로 탐색 구현작업 세팅하기 작업은 Unity C# 으로 진행하였습니다. 먼저, 경로 탐색을 본격적으.. 알고리즘 <삽입 정렬(Insertion Sort)> 개요 및 정의하기 이번 포스팅에서는 기본 정렬 알고리즘인 삽입정렬에 대해 다룹니다. 삽입정렬(Insertion Sort) 삽입 정렬은 정렬이 필요한 모든 요소들 처음부터 시작하여 이미 정렬된 배열부분 중 정렬이 필요한 요소의 위치를 찾아 삽입하여 정렬하는 방식입니다. 설명하기 삽입 정렬이 어떤 방식으로 정렬 되는지 직접 사진으로 분석해보겠습니다. 3,7,2,5,1,4 라는 값을 정렬하려합니다. 맨 처음 3은 정렬되어있다고 가정하고 7 부터 검사합니다. 7이 3보다 작은지 검사하고 그렇지 않은경우 다음 인덱스로 이동합니다. 이제 3과 7까지 정렬되어있다고 가정하고 2의 값의 위치를 찾아갑니다. 2는 7보다 작기에 한칸 앞으로 당깁니다. 마찬가지로 2가 3보다도 작으므로 한칸 더 앞으로 당기면 (c) 와 같.. 이전 1 2 다음
