이아손의 아르고호

1. 탄생배경 연결리스트에 대한 첫 언급은 1955-1956년에 개발된 IPL이라는 언어의 기본 자료구조로 등장한다. 이 IPL은 복잡한 수식을 증명하는 용도로 개발이 되었는데 간단히 설명하자면 이 언어에서 사용되는 변수들의 계층을 나누기 위해서 사용된 것으로 보인다. 어떤 변수들은 그 스코프가 전역적이고 또 어떤 특정 변수들은 스코프가 내부적으로 이루어져 있는데 이 각 값들을 어떤 변수의 이름으로 접근할 수 있도록 연결 리스트가 사용되었다고 한다. 2. 연결 리스트란 무엇인가? 정의: 한 줄로 연결되어 있는 방식으로 어떤 데이터 덩어리(이하 노드Node)를 저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장한다. 즉 리스트의 순서가 메모리에서의 실제 저장 위치에서는 ..

1. 탄생 배경 배열은 가장 오래된 자료구조 중 하나로써 특정 탄생 시기나 배경에 대한 정확한 기록을 찾기 어려웠다. 추정컨대 배열이라는 개념을 어느 시점에 누가 처음으로 만들어내서 지금까지 쓰고 있다기 보다는 이전부터 일렬로 데이터를 저장해서 읽고 쓰는 것이 매우 기초적인 행위이기 때문에 배경을 찾는 의미가 없는 건 아닐까 싶다. 저장장치가 생기기 전의 컴퓨터에서 사용한 테이프 (magnetic tape나 구멍 뚫린 종이 테이프)도 아주 넓은 의미에서 배열의 범주 안에 들어간다고도 할 수 있지 않을까? 그만큼 일렬로 데이터를 저장하는 방식은 매우 보편적인 아이디어 같다. 다만 direct access가 가능한 배열은 컴퓨터 하드웨어에 내장 메모리가 등장하기 시작하면서 우리가 현재 아는 배열의 개념이 정..

1. 탄생 배경 Trie는 1959년 René de la Briandais의 라는 논문에서 처음으로 등장하였다. (Trie라는 단어 자체는 2년 후에 만들어졌지만 Trie의 기본 알고리즘은 이 논문이 최초라고 한다) 논문의 내용을 정말 간단하게 요약하자면, 모든 Search의 성능은 주어진 데이터의 크기 (N)가 가장 큰 결정 요소인데 이것을 해결하기 위해 고안된 자료구조이다. 즉, Search 연산에 대한 전체 복잡도를 주어진 데이터 크기와 최대한 상관이 없도록 만들어진 것이다. 하지만 이러한 문제점을 극복하기 위해 HashTable이라는 자료구조도 나오지 않았는가? 그러나 당시 컴퓨터들에게는 Hash 방식을 비롯한 기존 방식들이 가지고 있는 몇 몇 문제점들이 있었다. 1) Hashing의 문제점 Tr..