자료구조에 대한 기본적인 이해

오른쪽 사진의 분석결과를 토대로 
데이터의 수가 적은 경우에는 알고리즘 B가 빠르고

데이터가 수가 많은 경우에는 알고리즘 A가 빠르다.

하지만 데이터의 수가 적은 경우 속도 차는 크게 나지 않는다.

즉 상황에 맞게 알고리즘을 사용하는것이 중요하다.

 

 

 

 

올해 초반에 길찾기 알고리즘을 구현한 적이 있었다. 

BFS, DFS, A* 알고리즘을 공부했었는데 그때는 각 알고리즘에 대하여 자세하게 이해하지 못했을 뿐더러,

길찾기 알고리즘에서 A* 가 좋다고 하여 무작정 A*로 실행을 했었다.

 

하지만 위 그림과 같이 보드에서 길찾기 알고리즘을 적용했을 때 DFS가 빠른 경우가 있고 A*가 빠른 경우가 생겼다.

그 이유는 탐색해야할 경로도 많지 않고 맵 하단과 맵 우측에는 직선방향으로 길을 뚫어놓은 단순한 구조로 미로를 구현했기 때문이다.

그렇기 때문에 각 노드를 방문할때 복잡함 계산을 사용하지 않고, 시작점과 목적지까지 비교적 직선 경로라
깊이 우선 탐색인 DFS가 가장 빠르게 나올때가 있는 것이다.
반면 A*는 항상 최적의 경로를 찾으려하기 때문에 더 많은 이동옵션을 고려해야해서 연상량이 증가할 수 있는것이다.
BFS는 모든 방향을 균등하게 탐색하므로 불필요한 영역까지 탐색해 DFS랑 A*에 비해 속도가 느리긴하다.

복잡한 맵이나 최적의 경로가 중요한 상황에서는 A*가 적합하지만, 내 코드에는 DFS가 A*보다 더 빠르게 연산되는 횟수가 많긴했다.

이 코드를 구현할때는 상황에 따른 최적의 알고리즘을 구분해서 사용하는 것에 대해 크게 이해를 못했었다. 

사실 지금도 내 코드에 맞는 알고리즘으로는 무엇을 써야하는지 정확한 판단은 서지 않는다. 속도가 차이가 크게 나는것도 아니고, A*를 써서 꼭 대각선으로 이동할 필요는 없기 때문이다. 단순히 길찾기 알고리즘을 통해 시작 지점에서 목표지점까지 적을 랜덤으로 움직이게 하는것에 목적을 두었기 때문이다. 그래도 DFS, BFS, A*를 공부했었다는 것에 의의를 두고 있다.
이를 통해 자료구조를 공부하면서 구현보다 중요한 것은 상황에 따라 사고하고 판단하는게 중요하다는 것을 과거의 경험으로 인해 확실하게 깨달을 수 있었다.