자료구조

이번에 살펴볼 부분은 스택과 큐이다. 스택 스택(Stack)은 후입선출(Last In First Out: LIFO)의 선형 자료구조이다. 데이터를 쌓아 올린다는 의미에서 더미(stack)라는 이름이 붙었다. 입력은 push, 출력은 pop, 그리고 가장 위에 있는 데이터를 확인하는 방법은 peek라고 한다. 바닥이 막힌 상자라고 이해하면 쉬운데, 그렇기 때문에 나중에 넣은 물건이 위에 있으므로 먼저 꺼낼 수 밖에 없다. 스택을 구현하는 방법을 살펴보자. 스택에서 필요한 함수는 위에서 언급한 push, pop, peek 그리고 하나를 더 추가한다면 스택이 비었는지 아닌지를 확인하는 isEmpty 함수 정도가 될 것 같다. 배열과 다르게 스택은 한 번에 i(인덱스)번째 데이터에 접근할 수는 없다. 다만 삽입..

두 번째로 자료구조에서 살펴 볼 내용은 연결 리스트(LinkedList)이다. 연결 리스트 연결 리스트는 어떤 데이터 덩어리(이를 노드라고 표현)를 저장할 때, 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장하는 자료구조이다. 따라서 각각의 노드들은 자기 자신 다음에 어떤 노드가 오는지를 기억하고 있다. 배열이 가지고 있는 단점들을 해결하기 위해서 만든 자료구조이다. 예를 들면 배열에서는 하나의 값을 삭제하고 추가하는 데에 시간복잡도가 O(n)이었다면, 연결 리스트에서는 삭제시에 하나의 노드를 빼 주고 나서 삭제된 노드 이전의 노드가 삭제된 노드 이후의 노드를 바로 참조할 수 있게 연결해 주면 되기 때문에 시간복잡도가 O(1)이고 삽입도 비슷한 이유로 O(1)이다. 연결리스트..

SW엔지니어로서 면접을 준비하면서 기본적인 컴퓨터 사이언스 지식을 복습하는 의미에서 이렇게 블로그에 정리를 하고자 한다. 가장 먼저 복습할 과목은 자료구조이다. 이번 글에서는 배열, 그리고 해시테이블에 대해서 복습해 보려 한다. 먼저 배열부터 살펴보자. 배열 배열(array)은 연관된 데이터를 모아서 한 번에 관리하기 위해 사용하는 데이터 타입이다. 배열은 논리적인 저장순서와 물리적인 저장순서가 일치한다. 따라서 인덱스(index)를 사용하여 해당 원소에 접근할 수가 있다. 인덱스를 알고 있다면 각각의 원소를 바로 찾아갈 수 있게 되므로 원소를 찾는데 걸리는 시간복잡도는 O(1) 이라고 볼 수 있고, 이를 임의 접근(random access)이 가능하다고 말한다. 반면에 새로운 데이터를 삭제하거나 삽입을..