본문 바로가기

개발/기본) 알고리즘16

알고리즘)Decision Trees Algorithm(의사 결정 알고리즘) 보호되어 있는 글 입니다. 2024. 3. 8.

알고리즘) Given When Then Pattern ( 테스트 케이스 작성 기법 ) Given When Then Pattern ( 테스트 케이스 작성 기법 ) 주로 테스트 케이스를 작성하거나 스펙을 정의할때 사용하는 패턴으로 이 패턴은 테스트 케이스의 구조를 명확하게 만들고 테스트의 목적을 명시적으로 표현하는데 도움이 된다. 주로 BDD(Behavior-Driven Developement), TDD(Test Driven Development)에서 사용한다. 테스트를 시작하기 전에 시스템이 특정 상태어야 하는 전제 조건이다. 이미 주어진 환경, 혹은 필요한 환경도 포함된다. 어떤 조건이나 특정한 상황을 설정하는 부분으로 특정한 행동이나 이벤트를 트리거하너 전제 조건을 설정한다. When에서 설정한 조건에 대한 기대 결과 혹은 예.. 2024. 1. 31.

알고리즘) WayPoint Algorithm(길찾기 알고리즘) WayPoint Algorithm(길찾기 알고리즘) Waypoint Algorithm은 주로 로봇 탐색, 자동차 경로 설정, 비행기 경로 계획 등의 분야에서 사용되는 알고리즘입니다. 이 알고리즘은 시작점에서 목적지까지의 경로를 설정하는 데 사용되며, 이 경로는 일련의 웨이포인트(Waypoint)로 구성됩니다. 웨이포인트는 각각의 위치를 나타내며, 이들 사이의 경로는 로봇이나 차량이 이동할 수 있는 최적의 경로를 찾는 데 사용됩니다. Waypoint Algorithm의 기본적인 동작 방식은 다음과 같습니다: 동작 순서 설명 1 시작점과 목적지를 설정한다. 2 시작점과 목적지까지의 경로를 설정하기 위해서 웨이포인트(Waypoint)를 설정한다. (이때 웨이 포인트는 일반적으로 일정 간격을 기준으로 생성되며 .. 2023. 11. 21.

알고리즘) SOLID 원칙 (솔리드 패턴) SOLID 원칙 (솔리드 패턴) SOLID은 다섯 가지 기본 설계 원칙을 나타냅니다. 이 원칙들은 소프트웨어 디자인을 더 견고하고 유지보수하기 쉽게 만들기 위한 패턴으로 의미에 대해서 알고있으면 좋다. 실제 구현 방식에 대해서는 간략하게 정리한다. 클래스는 단 하나의 책임만을 가져야 합니다. 여러가지 책임이 생기게되면 더 많은 기능이 추가되는 경우에는 해당 클래스를 확장해서 더 넓은 의미의 클래스로 재작성 및 리팩토링이 필요하다. (독립성) 소프트웨어 엔터티(클래스, 모듈, 함수 등)는 확장에는 열려 있어야 하고 변경에는 닫혀 있어야 한다.. 2023. 10. 19.

알고리즘) 매치 메이킹 (Matching Algorithms) 매치 메이킹 (Matching Algorithms) 매치 메이킹이라는건 경쟁 게임에서 대결 상대를 선택하는 알고리즘으로 매치 메이킹으로 많은 알고리즘이 존재한다. 상황에 맞게 적절한 알고리즘을 선택해서 개발 하는것을 추천한다. 원래 체스용으로 개발된 이 시스템은 다른 플레이어와의 상대적인 성과를 기준으로 플레이어에게 숫자 점수를 할당해서 점수를 기반으로 매칭하는 알고리즘으로 . 두 플레이어의 점수 차이를 기반으로 경기 결과를 예측합니다. 모든 유저그룹에 대한 매칭을 진행하는 안정적인 매칭 알고리즘으로 많이 사용한다. 홀수 길이 주기가 포함된 그래프에 특히 유용하다고 한다. 블라섬 알고리즘은 1965년 Jack Edmonds에 의해 발명되었으며 특히 네트워크 설계, 노동 시장 매칭, 컴퓨터 비전 등에 적용.. 2023. 9. 4.

알고리즘) 게일- 섀플리 알고리즘(Gale-Shapley Algorithm) 게일- 섀플리 알고리즘(Gale-Shapley Algorithm) 서로에 대해 선호를 가진 지단 간 안정적 매칭을 찾아내는 알고리즘이다. 안정적 매칭은 두 집단에 속하는 사람들이 빠짐없이 모두 매칭에 성공하였으며, 매칭된 결과에 모든 사람이 만족하고 있는 상태를 말한다. 절차는 다음과 같다. 1. 초기화 2. 제안단계 3 수락 단계 4 반복 5 종료 간단하게 결혼상대를 찾는 매칭을 게일 -섀플리 알고리즘을 통해서 구현한다고 치면 다음과 같다. 간단하게 남성4명과 여성4명을 매칭시키는 알고리즘을 구현하면 다음과 같다. using System; using System.Collections.Generic; class Man { public string Name { get; set; } public List P.. 2023. 7. 31.

알고리즘) Procedural Dungeon Generation Algorithm(절차적 던전 생성) Procedural Dungeon Generation Algorithm(절차적 던전 생성) 이리저리 포럼을 찾다가 절차적 던전 생성 알고리즘이라는 소스코드와 자료를 보게 되어서 포스팅하게 되었다. 간단하게 절차적 던전 생성은 임의의 크기인 생성될 오브젝트를 생성하고 난 이후에 겹치지 않도록 공간을 비집고 해당 공간을 연결해주는 방식으로 재조립하는 알고리즘이었다. 테스트해본 소스코드로 영상은 다음과 같다. 던전을 생성하는 여러가지 방법이 있을 텐데 이런 방식이 있다는 것에 대해서 알게 되어서 재미있다고 생각했다. Unity 코드로는 룰에 의거한 임의의 DungeonRoom을 생성하고 그 이후에 FixedUpdate를 통해서 겹치지 않는 방으로 해당 방을 이동시키는 방식을 사용한다. 이후.. 2021. 12. 30.

알고리즘) 동적 계획법 (Dynamic Programmi 동적 계획법 (Dynamic Programming) 어떤 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(Sub Problem)로 나누어서 푼 다음에 그걸 결합해서 최종적인 목적에 도달하는 것이다. 복잡한 문제를 처음부터 풀기보다는 조금씩 조금씩 만들어서 풀면 쉽게 풀리기도 한다. 동적 계획 알고리즘은 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다. 이것은 동적 계획법은 문제를 해결하기 위한 모든 방법을 검토하고, 그중에서 최적을 풀이법을 찾아내기 때문이다. 1. 전체 문제를 작은 문제로 단순화한다. 2. 재귀적인 구조를 활용할 수 있는 점화식을 만든다. 3. 작은 문제를 해결한 방법들을 결합한다. 4. 문제를 해결.. 2020. 8. 22.

알고리즘) 탐욕 알고리즘(Greedy Algorithm) 탐욕 알고리즘(Greedy Algorithm) 탐욕 알고리즘은 '미래를 생각하지 않고 현 상황에서 가장 최선의 선택을 하는 알고리즘'으로 그 선택이 탐욕스럽다고 해서 붙여진 알고리즘입니다. 현 상태에서는 최선의 선택을 하지만 각 단계를 거치고 나면 최선의 선택을 하지 못하는 경우가 많습니다. 미래에 대한 분기가 생기게 되면 최선의 선택을 하지 않습니다. 예시로 지금 선택하면 1개를 주는데 다음에 선택하면 3개를 주는 상황을 가정을 하면 다음 단계에서 받으면 3개를 받을수 있지만. 탐욕 알고리즘으로는 1개를 선택합니다. 많이들 예시로 작업한 동전을 거슬러주는 상황으로 테스트 코드를 작성합니다. 대체적으로 동전은 불편하기 때문에 최소의 동전으로 거슬러주는 상황이 거슬러 받는 사람에게는 좋다는 가정입니다. p.. 2020. 6. 22.

알고리즘) 트리(Tree)의 종류 트리(Tree)의 종류 트리구조(하위에 자식이 추가되는 구조)에서 이진트리는 하위에 2개까지 붙을 수 있는 트리를 이진트리(Binary Tree)라고 한다. 그 외 하위에 여러 가지 붙는 변형 형태의 트리도 많다. 그중에서 많이 쓰이고 대표적인 트리에 대해서 알아보자. 이진 탐색트리는 이진트리 + 정렬의 개념이 추가된 형태로 탐색하는 과정에서 많이 사용하는 탐색 구조이다. 트리에서 밸런스(Balance)에 대한 표현이 나오는데 이는 지나치게 치우치게 되면 탐색하는 과정(비용)이 많이 들기 때문에 트리를 구성하는 과정에서 밸런스에 대한 처리도 고려를 해야 한다. 밸런스가 고려된 트리의 종류는 다음과 같다. Red-Black Tree AVL Tree 완전 이진트리(Complete Binary Tree) - .. 2020. 6. 18.

알고리즘) A* Algorithm A* Algorithm 가장 대표적인 길찾기 알고리즘이다. 가중치를 기준으로 길을 찾는다. 알고리즘의 원리는 다음과 같다. 찾을 영역(Grid)를 만든다. 현재 경로에 대한 8방향(주위) 경로에 대한 가중치(비용)을 계산한다. 이때 경로를 계산하는 비용은 (F = G + H) 로 가정한다. G = 시작점 으로부터 종료점까지 이동하는데 소요되는 비용 H = 현재 사각형에서 종료점까지의 예상 이동비용(이때는 방해물에 대한 계산을 처리하지 않고 가로세로만 계산한다.) F = 현재까지 이동한 총 비용 ( G + H ) 이동은 가로세로만 가능한것을 기준으로 설명한다. 현재 위치를 기준으로 가중치에 대한 처리를 한다. 시작점을 기준으로 오른쪽의 사각영역에 대한 계산을 하면 다음과 같다. F = 40 ( 총합) G .. 2020. 4. 19.

알고리즘) 영향도 알고리즘(Influence Map Algorithm) 영향도 알고리즘(Influence Map Algorithm) 영향도 알고리즘은 어떤 선택을 하는 과정에서 많은 선택지 중에서 가장 좋은 선택을 할 수 있는 알고리즘이다. 여러 가지 다중 조건의 결과를 격자의 그리드인 영역에 가중치를 계속 추가하고 난 이후에 가중치를 기준으로 원하는 선택을 한다. 원리는 map에 가중치에 대한 값을 계속 누적하는 것으로 가중치에 대한 계산을 한다. 격자의 맵이 있는 상황에서 다중 조건에 의한 선택을 할 때 사용한다. Unity 에서 간단하게 원형으로 영향도에 대한걸 처리해보자. 먼저 영향도에 대한 체크를할 기준이 되는 오브젝트를 생성하고 기준이 되는 오브젝트의 주위 반경에 영향도 가중치를 추가한다. 오브젝트와 근접한 위치의 큐브는 좀더 영향도 있는 것을 나타내기 위해서 R.. 2020. 1. 22.

알고리즘) 플러드 필 (Flood Fill) 플러드 필 (Flood Fill) 플러드 필이라는 알고리즘은 다차원 배열(2차원 이상)에서 화면을 격자(Grid)로 분할하거나 체우는과정에서 사용되는 알고리즘이다. 이번에 필자는 특정 맵을 포인트화하는 과정에서 해당 알고리즘을 사용했다. 타일맵으로 만드는 과정에서 굉장히 많이 사용한다. 구현방법은 다음과 같다. 특정 기준이되는 좌표를 정한다. 기준좌표의 방향(4방향 , 8방향)에 대한 확장형 로직을 작성한다. 해당 로직을 재귀처리한다. 재귀처리를 하는과정에서 해당 조건이 맞지 않으면 종료한다. (조건은 맵의 크기 or 갈수없는 영역 등등) 작업된 코드는 다음과 같다. private void GetGridPoint(int _x, int _z){ SceneInGame scene = SceneManager.I.. 2020. 1. 14.

알고리즘) Flocking Algorithm (군중이동 알고리즘) Flocking Algorithm (군중 이동 알고리즘) 군중 이동에 대한 알고리즘으로 많이 쓰이고 대중적인 알고리즘이다. 새 떼라던지 물고기들의 움직임 등 여러 집단이 함께 움직이는 모습을 구현한 알고리즘이다. FSM!= Flocking Alogrithm (상태 머신이 없다) Emergent Behavior (임기응변적인 행동) 개별적인 정보로 행동!= 집단의 움직임 특징은 다음과 같다. 예전부터 한 번쯤은 구현해보려고 했던 Flocking Alogrithm을 구현을 했다. 처음부터 내가 구성해서 작업한 건 아니고 다른 코드를 많이 참고했다. Flock에서는 각 가중치에 의거해서 회피, 집합, 정렬에 대한 처리를 하게 되고 집합 그룹이 되면 움직임에 대해서 평균 처리를 하게 된다. .. 2019. 12. 26.

알고리즘) 알고리즘 깊이우선 탐색 (Depth-First Search) 알고리즘 깊이우선 탐색 (Depth-First Search) 깊이 우선 탐색(DFS, Depth-First Search) 깊이 우선 탐색은 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다. 사용하는 경우는 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.(전체 검색) 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다. 단순 검색 속도 자체는.. 2019. 10. 31.

이전 1 2 다음

티스토리툴바