목록2024/01 (48)
개발하는 리프터 꽃게맨입니다.
(참고: 기본적인 구현인 '인접 행렬'을 사용해서 구현했습니다.) 서론 탐색은 우리가 관리하는 자료구조의 전체를 순회하거나 원하는 자료를 찾고자 하는 것을 뜻합니다. 자료구조를 다루는 시점에서 '탐색'은 필수적이죠. 그런데, 그래프 구조는 복잡하기에 단순하게 순회하는 것조차 힘듭니다. 일반적으로 탐색의 방법은 '깊이 우선 탐색 DFS' '너비 우선 탐색 BFS' 2가지가 존재합니다. 깊이 우선 탐색 1. 개요 깊이 우선 탐색은 말 그대로 출발점에서 가장 멀리 있는 노드(가장 깊이 있는 노드)를 도달하고자 하는 탐색방법입니다. A에서 가장 멀리 있는 노드는 F죠 그래서 A -> D -> F를 먼저 탐색하고 나머지 노드를 탐색합니다. 이런 식으로 탐색하는 이유는 '스택'의 특성 때문에 그렇습니다. 알고리즘의..
개요 그래프(Graph)는 '정점(vertex, node)'과 '간선(edge, adjacent, link)'의 집합으로 이루어진 자료구조입니다. 어떻게 보면, 하나의 노드를 가리키는 '연결리스트' 다수의 노드를 한 방향으로 가리키는 '트리'의 확장된 버전으로 이해할 수 있습니다. (문서를 찾다보면 정점 = Node = Vertex 등 용어가 혼용되고, 간선 = edge = adjacent = link 용어가 혼용됩니다. 다 알아두시길 바랍니다.) 이런 식으로 노드와 노드는 간선으로 연결됩니다. 트리, 연결리스트에 비해 현실 상황을 잘 재현하는 자료구조라고 여겨집니다. 어떻게 보면 지하철 노선도와 같은 형태를 띠고 있으며 이렇게 정보를 가지고 있는 '노드'를 간선으로 직관적으로 연결하고 '복잡한 관계'에..
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 처음으로 문제 풀이를 하는 포스팅을 작성했는데.. 날아가니까 의지가 팍 꺾이네요 ㅎㅎ 해당 문제는 그래프 탐색 알고리즘을 통해 풀 수 있는 문제입니다. 꽤나 좋은 문제에요 백트래킹, 너비 우선 탐색 둘 다 사용할 수 있으니 시간있으면 도전해보는 것을 추천합니다.