반응형 프로그래밍/알고리즘 프로그래밍/알고리즘 2021. 1. 23. DFS - 깊이 우선 탐색 (C#으로 길 찾기 구현) - Depth First Search의 약자 - 현재 정점(노드)에서 간선으로 연결된 정점중 가장 깊은 정점까지 탐색하고 목표 정점이 없으면 이전 정점으로 돌아가 간선으로 연결된 다른 정점으로 또다시 탐색한다. - 위 방법을 반복하면서 정점들을 순회하게 된다. - DFS와 대조되는 BFS (너비 우선 탐색)도 있다. - 일반적으로 재귀호출로 구현하는 방법과 스택으로 구현하는 방법이 있다. using System; using System.Collections.Generic; class Program { static void Main(string[] args) { MapController mapController = new MapController(); // 길 체크 플래그를 초기화해준다. mapContro.. 프로그래밍/알고리즘 2021. 1. 22. BFS - 너비 우선 탐색 (C#으로 길 찾기 구현) - Breadth-First Search의 약자 - 루트 노드에서 인접한 노드를 탐색하며 순회하는 탐색 방법 - BFS와 대조되는 DFS (깊이 우선 탐색)도 있다. - Queue를 이용하여 구현하는게 일반적이다. - Queue가 모두 소진될 때까지 루프하며 인접 노드들을 검색한다. using System; using System.Collections.Generic; class Program { static void Main(string[] args) { MapController mapController = new MapController(); // 시작 좌표와 목적지 좌표를 매개변수로 넘겨준다. mapController.BFS(0, 0, 5, 3); } } public class MapControlle.. 프로그래밍/알고리즘 2020. 12. 7. AStar Algorithm (에이스타 알고리즘) 길 찾기에서 흔히 사용되는 AStar 알고리즘 입니다. 간단히 요약해보자면 용어 설명 openList = 갈 수 있는 길 closeList = 이미 지나간 길 current = 현재 위치 NeighborNode = 탐색한 길 이동비용 = 도착지점까지의 거리라고 생각하면 된다. 가중치 = 일반적으로 직선 : 10, 대각선 : 14 1. CreateNode : 맵을 만든다. 2. SetTargetLocation : 시작지점과 도착지점을 구한다. 3. PathFinding : 길 찾기 알고리즘을 한다. - 시작지점을 openList에 담는다. - openList 중에 이동 비용이 낮은 길을 찾아 current에 담는다. - current를 openList에서 지우고 closeList에 담는다. - curren.. 프로그래밍/알고리즘 2020. 5. 12. Optimal BST (최적 이진 탐색 트리) - 각 노드의 검색 빈도가 주어질 때, 검색 비용의 기댓값이 가장 작은 이진 검색 트리 예시) 입력이 5,4,6,3,2,8,7 순일 경우 균형적인 트리 입력이 1,2,3,4,5 순일 경우 불균형적인 트리 위처럼 1,2,3,4,5 순으로 입력이 있을 경우 입력이 있을때마다 트리를 최적화하여 아래와 같이 만든다. 이리하여 이진 탐색 트리 중에서 평균 검색 시간이 가장 낮은 효율적인 트리가 된다. 참고 출처 RememberCook 9월 28일 정식 출시! 두번째 게임인 RememberCook이 출시되었습니다. 귀여운 캐릭터들이 나오는 간단한 게임이며 플레이어의 공간인지능력을 테스트하는 게임입니다. 아래 링크를 통해 다운 받으실 수 있으니 많은 관�� chipmunk-plump-plump... 프로그래밍/알고리즘 2020. 5. 11. binary search tree (이진 탐색 트리) - 이진 트리에 4가지 조건을 더 갖는 트리구조 - 데이터의 삽입, 삭제, 탐색 등이 자주 발생하는 경우에 효율적인 구조다. - 루트를 기준으로 루트보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 정해져 있다. 4가지 조건 1. 모든 노드는 다른 값을 갖는다. 2. 왼쪽 서브 트리의 데이터 값은 부모 노드의 데이터 값보다 작은 값을 갖는다. 3. 오른쪽 서브 트리의 데이터 값은 부모 노드의 데이터 값보다 큰 값을 갖는다. 4. 왼쪽, 오른쪽 서브트리도 이진 탐색 트리다. 아래와 같은 이진 트리에서 12를 검색하고자 할 때 (출처 네이버 백과) 1. 루트 노드의 값(8)보다 찾으려는 값(12)이 클 경우 오른쪽 서브트리에서 탐색한다. 2. 다음 루트(10)의 값보다 찾으려는 값(12)이 클 경우 오른.. 프로그래밍/알고리즘 2020. 4. 20. Heap Sort (힙 정렬) 개념 - 힙 트리의 특징을 이용하여 정렬 (힙 트리에 원소들을 전부 삽입 후 힙의 루트에 있는 값을 이용하여 정렬) - 힙 트리는 완전이진트리구조를 가진 자료구조 - 추가적인 메모리를 전혀 필요로 하지 않음 - 항상 O(nLogn)정렬의 성능 - 선택정렬과 비슷 (매번 원소를 순환하면서 정렬하느냐 아니냐의 차이) * 힙트리는 첫번째 출처, 힙정렬은 두번째 출처에 알기쉽게 설명되어 있다. 원소 (16,14,10,8,7,9,3,2,4,1)를 정렬할 경우 (최대힙 기준) 힙트리에 삽입 1. 최상위 루트인 16을 추출 2. 추출되어 비어진 최상위 루트에 마지막 노드 1로 채움 3. 최대힙 특성에 맞춰 힙 트리를 재정렬 4. 재정렬 후 최상위 루트가 된 14를 추출 더이상 트리에 값이 남아있지 않을때까지 .. 프로그래밍/알고리즘 2020. 4. 20. Merge Sort (병합정렬) 개념 - 분할 정복 알고리즘을 응용한 정렬 (분할 정복이란 문제를 나눌 수 없을 때까지 나누어서 각각을 풀고 다시 합병하는 과정을 거쳐 문제의 답을 얻는 알고리즘을 말한다.) - 퀵 정렬보다 전반적으로 속도가 느림 - 데이터 크기만한 메모리가 더 필요 - 데이터의 상태에 영향을 받지 않음 (힙, 퀵 정렬은 같은 값의 데이터가 있으면 순서가 뒤바뀔 수도 있다. 정수형 배열[0] = 100, 배열[10] = 100을 정렬할 때 배열[10]이 배열[0]보다 앞에 오는 경우가 생일 수 있다. 그러나 병합 정렬은 위와 같은 상황이 발생하지 않는다.) 정수형 배열 A[9]가 있고 [0]번부터 순서대로 (5,3,1,9,4,2,8,7,6)이 있다고 가정하자. 배열 A의 값들을 정렬하려고 할 경우 (5,3,1,9,4.. 프로그래밍/알고리즘 2020. 4. 20. Quick Sort (퀵 정렬) 개념 - 분할해서 정렬 - 주어진 값에서 기준이 될 값을 정하고 기준이 되는 값보다 작은 값은 왼쪽, 높은 값은 오른쪽으로 우선 정렬한다. 이후 왼쪽은 왼쪽대로 정렬하고, 오른쪽은 오른쪽대로 정렬한다. - 랜덤 배열에서 빠름 - 순열이나 역순의 경우 매우 느림 (기준값을 선정하는 방법에 따라 속도가 다름) 1. 최소 값이나 최대 값으로 할 경우 2. 이미 정렬된 배열을 정렬할 경우 - 재귀함수 기반으로 구현할 경우 복잡해질 수 있다. 기준값이 3라고 정했을 경우 (5,4,'3',2,1) -> (2,1,'3',5,4) 왼쪽 값 정렬 : (2,1) -> (1,2) 오른쪽 값 정렬 (5,4) -> (4,5) 최종적으로 (1,2,3,4,5)로 정렬 된다. 퀵정렬의 단점을 보안하기 위해 여러 기법들이 .. 이전 1 2 다음 반응형
