개발하는 리프터 꽃게맨입니다.

개요 위 그림과 같은 임의의 미로가 있고 플레이어와 도착지의 위치가 정해져 있을 때, 플레이어는 도착지를 어떻게 찾을 수 있을까요? 그리고 어떻게 해야 최단 경로로 도착지에 도달할 수 있을까요? 그에 대한 알고리즘을 소개해보겠습니다. 미로 찾기 베이스 미로 찾기 알고리즘을 개발하기 위한 베이스입니다. 이 파트는 넘어가셔도 상관없다만, 몇 가지만 확인해 주시면 해당 포스트를 이해하는데 도움이 될 것입니다. (포스팅을 위해 하나의 파일로 만들었습니다.) 1. 2차원 좌표값은 Pos 클래스를 사용합니다. Pos(y, x)로 나타내며 y는 y축 값, x는 x축 값을 나타냅니다. 연산자 오버로딩을 해주었기에, 자유롭게 연산이 가능합니다. 2. 미로는 NxM 사이즈의 bool 형 2차원 배열입니다. 0(false)..

(참고: 기본적인 구현인 '인접 행렬'을 사용해서 구현했습니다.) 서론 탐색은 우리가 관리하는 자료구조의 전체를 순회하거나 원하는 자료를 찾고자 하는 것을 뜻합니다. 자료구조를 다루는 시점에서 '탐색'은 필수적이죠. 그런데, 그래프 구조는 복잡하기에 단순하게 순회하는 것조차 힘듭니다. 일반적으로 탐색의 방법은 '깊이 우선 탐색 DFS' '너비 우선 탐색 BFS' 2가지가 존재합니다. 깊이 우선 탐색 1. 개요 깊이 우선 탐색은 말 그대로 출발점에서 가장 멀리 있는 노드(가장 깊이 있는 노드)를 도달하고자 하는 탐색방법입니다. A에서 가장 멀리 있는 노드는 F죠 그래서 A -> D -> F를 먼저 탐색하고 나머지 노드를 탐색합니다. 이런 식으로 탐색하는 이유는 '스택'의 특성 때문에 그렇습니다. 알고리즘의..

개요 그래프(Graph)는 '정점(vertex, node)'과 '간선(edge, adjacent, link)'의 집합으로 이루어진 자료구조입니다. 어떻게 보면, 하나의 노드를 가리키는 '연결리스트' 다수의 노드를 한 방향으로 가리키는 '트리'의 확장된 버전으로 이해할 수 있습니다. (문서를 찾다보면 정점 = Node = Vertex 등 용어가 혼용되고, 간선 = edge = adjacent = link 용어가 혼용됩니다. 다 알아두시길 바랍니다.) 이런 식으로 노드와 노드는 간선으로 연결됩니다. 트리, 연결리스트에 비해 현실 상황을 잘 재현하는 자료구조라고 여겨집니다. 어떻게 보면 지하철 노선도와 같은 형태를 띠고 있으며 이렇게 정보를 가지고 있는 '노드'를 간선으로 직관적으로 연결하고 '복잡한 관계'에..

📕 개요그리디 알고리즘은 '욕심쟁이 알고리즘'이라는 별칭을 가지고 있습니다. 이는 '지금 이 순간 최적의 답을 선택하여, 전체 문제를 해결하자!'라는 아이디어로부터 출발합니다. 간단한 예시를 들어보겠습니다. 서울에서 부산으로 가고자 하는데, 무조건 대전, 대구를 경유해서 가야 한다고 가정해 보겠습니다. 어떻게 해야 가장 빠르게 부산에 도착할 수 있을까요? 서울 ~ 대전까지 가장 빠르게 도달하는 시간 + 대전 ~ 대구까지 가장 빠르게 도달하는 시간 + 대구 ~ 부산까지 가장 빠르게 도달하는 시간 = 서울 ~ 부산까지 가장 빠르게 도달하는 시간 일 겁니다. 그때그때 최적의 답을 선택하고, 그것을 모아서 전체 문제에 대한 해답을 찾고자 합니다. 그러나, 그리디 알고리즘이 항상 최적의 결과를 도출하는 것은 아닙..

참고: https://powerclabman.tistory.com/13 [C++/알고리즘] 퀵 정렬 (Quick Sort) 참고: https://powerclabman.tistory.com/12 [C++/알고리즘] 분할정복 (Divide and Conquer) + 병합정렬 (Merge Sort) 📕 개요 '분할 정복 알고리즘'이란, 엄청나게 크고 방대한 문제를 해결할 수 있는 단위까지 쪼개서 powerclabman.tistory.com 이번 글은 퀵정렬을 모르면 이해하기 힘듭니다. 📕 문제 N 사이즈의 정수배열 arr 이 존재할 때 배열 arr에서 k번 째로 작은 수를 선택해라 예시) N = 7 arr = {5, 9, 3, 7, 11, 2, 0} k = 4 일 때, 결과값은 5 설명) arr을 오름차순 ..