altair의 프로젝트 일기

학기 중에 DFS를 사용하여 주어진 미로의 최단 경로를 탐색하는 과제를 한 적이 있었다. 그리고 학기의 마지막 즈음에 다익스트라 알고리즘으로 그래프의 최단 경로를 탐색하는 것도 구현했었다. 그러다가 든 의문이 "다익스트라 알고리즘이 그래프에서 최단거리를 찾을 수 있다면 미로에서도 찾을 수 있을까?"였다. 이번 글에서는 여러 최단 경로 탐색 알고리즘으로 미로의 최단 경로를 구하고 알고리즘들을 비교해볼 것이다. 모든 코드는 Clion을 사용해 C++로 작성되었으며 개발환경은 macOS Big Sur 11.4 이고, 실행 환경은 라즈베리파이 OS와 g++ 8.3이 설치된 라즈베리파이 4B이다. 미로와 다익스트라 다익스트라는 기본적으로 "음이 아닌 가중치를 가진 간선들과 정점들로 구성된 그래프"에서 특정 정점에..

학기 중에 미로 탐색 과제를 했었다. 주어진 미로의 최단경로와 그 개수를 탐색하는 DFS 알고리즘을 만들었다. 스택을 사용하여 길이 막힐 때마다 갈림길로 돌아오고, 도착점에 이르렀을 경우 다시 이전 갈림길로 돌아가 다른 길이 존재하는지, 존재한다면 이전의 경로보다 짧은지 탐색하는 알고리즘이었다. 더 이상 찾아볼 경로가 존재하지 않을 때 이 알고리즘은 종료된다. 결과적으로 알고리즘은 잘 작동했다. 하지만 내가 만족스럽지 못했던 점은 알고리즘을 테스트할 수 있는 환경이 미리 주어진 미로 밖에 없었다는 점이다. 물론 미로를 약간 수정하여 입력할 수 있었지만 어디까지나 약간의 수정에 불과했고 더 큰 미로에서 얼마나 이 알고리즘이 잘 작동하는지 알고 싶었다. 그런 의미에서 완전히 무작위적인 미로를 만드는 방법을 ..

정렬 알고리즘을 살펴보다보면 C언어에서 라이브러리에 퀵 정렬 함수가 있다는 것을 알게 된다. 이번에 정렬 알고리즘을 배우면서 qsort 함수를 실행하고 내가 직접 구현한 퀵 정렬과 그 실행시간을 비교할 기회가 있었다. 가장 간단한 퀵 정렬 알고리즘은 최악의 경우 \(O(n^2)\) 의 시간 복잡도를 갖는다. 정렬되지 않은 배열을 정렬할 때 $$log_{2}n$$의 재귀 단계를 가지지만, 피벗을 기준으로 파티션이 극단적으로 나뉠 때는 $$n^2$$의 단계를 갖는다. 많이 쓰이는 힙 정렬은 비록 퀵 정렬보다 살짝 느리지만 이런 최악의 경우를 갖지 않고 항상 안정적인 시간 복잡도를 갖는다는 장점이 있다. 이번 프로젝트에서 확인했던 일반적인 퀵 정렬 알고리즘의 실행시간은 다음과 같다. 데이터 개수는 5만개로 하..