altair의 프로젝트 일기

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

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

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