altair의 프로젝트 일기

학기 중에 미로를 저장하고 최단 경로를 탐색하는 과제가 있었다. 당시에는 스택까지만 배운 상태여서 배열에 미로를 저장하였다. 하지만 이번에 미로를 생성하는 알고리즘을 구현하면서 더 이용하기 편한 형태로 미로를 저장할 기회가 있었다. 바로 그래프의 형태로 구현하는 것이다. 이에 대하여 설명하고자 한다. 지나갈 수 있는 칸과 그렇지 않은 칸들로 이루어진 형태의 미로는 다루지 않겠다. 배열로 저장하기 인간이 바라보는 미로 자체에는 크게 복잡한 정보가 존재하지는 않는다. 단 두가지, 지나갈 수 있는 통로와 지나갈 수 없는 벽이 존재할 뿐이다. 칸을 모두 저장하면서 각 칸의 네 벽에 대한 정보를 저장하는 것은 분명 낭비가 있어보인다. 인접한 두 칸에서 저장한 정보가 겹치기 때문이다. 같은 값을 두 칸이 모두 저장..

연결 리스트는 간단하게는 선형 연결 리스트에서부터 복잡하게는 여러 트리까지 많은 곳에서 사용하는 자료 구조이다. C와 같은 로우레벨에서 자료들을 저장하고 삭제하는데 효과적이다. C에서 기본으로 제공하는 배열은 삽입과 삭제의 비용이 크지만 연결 리스트는 그렇지 않고 그 구조도 배열처럼 선형으로 구성하지 않고 다른 여러 방식으로 구성할 수 있다. 하지만 C에서 연결 리스트를 직접 구현해보면 치명적인 단점을 발견하게 되는데, 기본적인 선형 연결 리스트에서 특정 노드를 탐색하는 방법은 순차 탐색 밖에 없다는 것이다. 중간에 있는 노드들을 곧바로 접근하지 못하니 이진 탐색은 그 비용이 너무 크다. 이런 점을 극복하기 위해 선형 연결 리스트가 아닌 트리로 구조를 바꾸면 탐색이 훨씬 빨라지지만, 일단은 선형 연결 리..

2023-03-30 수정 알다시피 트리의 높이는 곧 트리의 탐색시간을 결정한다. 이미 어떤 규칙에 의해 자식들로 나뉘는 트리에서 원하는 노드의 탐색 시간은 곧 일반적인 삽입과 삭제 시간 또한 결정한다. 따라서 트리가 어느 정도 편향되어 있는지, 자식 노드는 몇 개로 어떻게 구성되는지 같은 요소들은 트리의 전체적인 성능을 크게 좌우한다. 자료구조의 시간적 복잡도를 고려하는 과정에서 최악의 경우를 고려하지 않을 수 없다. 가장 안 좋은 트리는 모든 노드가 형제를 갖지 않고 연결된 경우일 것이다. 극단적으로 편향된 이런 트리는 연결리스트와 거의 다를바 없다. 성능 또한 마찬가지일 것이다. 다수의 데이터를 저장하기 위해 만들어진 자료구조인 만큼 이런 최악의 경우뿐만 아니라 '어느 정도 나쁜' 경우도 고려를 해야..

개요 학기 중에 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만개로 하..