기록하지 않았다면 잃어버릴 시간들

새로운 것을 배우는게 즐거운 개발자입니다.

알고리즘/이론

위상정렬 방향성을 가진 비순환 그래프에서만 사용이 가능 특정한 순서로 실행이 되어야하는 상황에 사용이 적합 위상정렬은 위에서 간단하게 설명한 것 처럼 특정한 순서로 실행이 되어야하는 상황에서 사용을 할때 사용을 하게 됩니다. 게임에서 예를 들어 보겠습니다. 요즘 유명한 게임이죠 리그오브 레전드라는 게임에서 피바라기 라는 아이템을 구매하기 위해 필요한 아이템 목록입니다. BF 대검 + 롱소드 + 흡혈의 낫을 그래프로 나타내면 다음과 같이 나타낼 수 있게 됩니다. B.F 대검과 롱소드 그리고 흡혈의 낫은 피바라기를 가르키고 있고 롱소드는 흡혈의 낫을 가리키고 있습니다. 그 이유는 각각의 아이템들은 피바라기의 선행조건이 되기 때문입니다. 그리고 피바라기를 구매후에는 다시 각각의 아이템으로 바꿀 수 없게 됩니다..

2022. 1. 3.

알고리즘/이론

BFS (Breath First Search) 그래프 탐색 알고리즘으로, 그래프탐색이란 한 정점에서 시작하여 탐색 조건에 맞는 노드를 찾을때까지 모든 노드를 방문하는 방법입니다. 너비 우선 탐색으로 모든 Branch의 같은 깊이의 노드들을 번갈아 가며 탐색을 하게 됩니다. FIFO구조인 큐로 구현 가능합니다. 장점 장점 단순검색 속도가 DFS에 비해 빠른편입니다. 깊이에 관계없이 최단 경로를 찾을 수 있습니다. 단점 다음에 탐색할 노드들을 모두 큐에 담아 두기 위해서는 자원이 많이 필요합니다. 과정 ※다음과 같은 그래프의 정점 1에서 모든 노드를 탐색 스택을 이용한 BFS를 하는 과정이고, 한번 방문한 노드는 방문처리가 되어 다시 방문 할 수 없다고 가정합니다. 아래쪽의 큐의 변화와 함께 보시면 이해가 ..

2021. 12. 30.

알고리즘/이론

DFS(Depth First Search) 그래프 탐색 알고리즘으로, 그래프탐색이란 한 정점에서 시작하여 탐색 조건에 맞는 노드를 찾을때까지 모든 노드를 방문하는 방법입니다. 깊이 우선탐색으로 한 정점에서 탐색을 시작할때 하나의 Branch를 완전히 탐색 한 후 다음 Branch를 탐색하게 됩니다. 스택과 재귀로 구현이 가능합니다. 장점 단지 현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적습니다. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있습니다. 단점 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제로는 미리 지정한 임의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있습니다. 얻어진 해가 최단 경로가 된다는 보장..

2021. 12. 30.

알고리즘/이론

안녕하세요. 최근 PS 관련 풀이를 하던도중 다익스트라 알고리즘에 대해 접하게 되었는데요. 사실 학부시절때 이론은 수업을 들어서 알고 있었지만 깊게 공부해보지 않아서 코드로 적용하기가 힘들더라구요... 그래서 이번 기회에 조금 깊게 공부해본 내용을 설명 하게 되었습니다. ●다익스트라 알고리즘 요약 1956년에 에즈허르 데이크스트라가 고안 다익스트라 알고리즘은 두 꼭지점 사이의 최단 경로 거리를 구하는 알고리즘 방향성 그래프와 무방향성 그래프 모두에 적용가능 가중치가 음수이면 사용 불가능 현제 길찾기 알고리즘의 기초가 되는 알고리즘 최초의 다익스트라는 출발노드를 기준으로 최소비용 그래프를 저장하여 방문하지 않은 노드 중 가장 가까운 거리에 있는 노드를 먼저 방문을 한 후 또 다른 노드를 방문하게 될 때 기..

2021. 8. 8.