말로만하는 - 자료구조(for 기술면접)

면접에서 자료구조는 기본 질문 사항이다. 배열, 연결리스트, 스택/큐, 트리 등등을 공부하지 않은 사람은 없을것이다. 공부를 할 때는 코드도 있고 그림도 있어서 직관적으로 이해할 수 있다. 그러나 면접에서는 이것들을 말로 표현할 줄 알아야 한다(중요성은 굳이 이야기하지 않아도 알 것이다..) 이 글에서는 자료구조를 ‘말’로만 표현할 수 있도록 정리해보았다. 예전에 사수님께서 기술을 설명할 때 ‘정의’와 ‘특징’을 나눠보라고 하셨다. 지금도 정리할 때에 종종 사용하는 방법인데, 간단 명료하면서 기술을 가장 잘 설명할 수 있는 방안이리라 확신한다.

자료구조의 분류

자료구조는 성격에 따라 아래와 같이 분류할 수 있다.

배열

연속적인 공간에 동일한 성질을 가지는 데이터를 저장하는 자료구조.
인덱스와 인덱스에 해당하는 데이터로 이루어진 자료구조.
An array is a simple data structure in which each element can be accessed directly.

• 특정 위치의 원소에 인덱스를 통해 즉시 접근 가능.

• 데이터를 담을 공간을 미리 메모리에 할당해야 함.

• 원하는 위치로의 삽입/삭제를 하려면 기존 값들을 한 칸씩 미뤄줘야 함.

리스트

불연속적인 메모리 공간에 데이터를 저장하는 선형 자료구조.
데이터를 저장할 때에 다음 데이터가 있는 공간의 주소를 가리키는 포인터도 같이 저장하여 자료를 이어준다.

• 필요할 때마다 메모리 공간을 할당받는다.

• 원하는 위치에 노드를 추가/삭제하기 용이하다.

• 단, 원하는 위치에 접근하려면 처음부터 탐방해야한다.

• 삽입과 삭제가 잦은 경우에 배열보다 효율적

• 인덱스를 통한 참조가 많을 경우에는 배열이 더 효율적

스택

데이터를 한 쪽 끝에서 삽입하고 삭제하는 자료구조. LIFO(Last In Fist Out), 나중에 들어간 것이 먼저 나온다.
A stack is a sequentially ordered data structure that uses the LIFO.

• push/pop으로 이루어져 있다.

• 연결리스트/배열을 통해 구현 가능하다.

• 배열을 통해 구현하면 스택의 Max Size가 고정되고, 현재 Stack의 최상단 위치를 기억하는 Stack pointer가 필요하다.

• 메소드 실행, 연산 등에 사용된다.

큐

데이터를 한쪽 끝으로 삽입하고 반대쪽 끝에서부터 삭제하는 자료구조. FIFO(First In First Out), 먼저 들어간 것이 먼저 나온다.
A queue is a sequentially ordered data structure that uses the FIFO.

• stack과 마찬가지로 push/pop으로 이루어져 있다.

• 연결리스트 또는 배열로 구현할 수 있다.

• 배열을 통해 구현하면 큐의의 Max Size가 고정되고, 현재 큐의 최상단과 최하단 위치를 기억하는 head와 tail용 pointer가 필요하다.

• CPU 스케쥴링 등에 사용된다.

트리

데이터 간의 계층 관계를 표현하는 비선형 구조의 자료구조이다. 시각적으로 표현했을 때에 나무를 뒤집어 놓은 모양을 하고 있어 tree라고 한다.
A tree is a data structure that can be used to represent data hierarchically. Data values in a tree are linked through parent-child relationship.

• 트리는 특수한 형태의 그래프로서, 두 노드 사이에는 사이클이 없어야 하며, 두 노드 사이의 경로는 오직 하나이다. 즉, 단방향 그래프라고 할 수 있다.

이진트리

트리의 한 종류로 각 노드의 차수(자식노드의 개수)가 2이하인 트리이다.

이진탐색트리

이진트리 중 부모노드를 기준으로 왼쪽 자식노드의 값은 부모노드의 값보다 작고, 오른쪽 자식노드의 값은 부모노드의 값보다 크다는 규칙을 만족시키는 자료구조이다.

해쉬

해쉬함수는 input값을 특정 연산을 하여 고정된 길이의 데이터로 리턴해준다.
해쉬테이블은 key:value형태의 데이터를 저장할 때, key를 해쉬함수의 input으로 넣고 output을 인덱스삼아 데이터를 저장하는 자료구조이다.

• 고정된 길이의 값(hash value)을 테이블의 인덱스/주소로 삼아 데이터를 저장하면 메모리 상에서 데이터를 바로 불러올 수 있다.

• 자료를 꺼낼 때에도 key를 해쉬함수에 넣어 자료가 저장된 주소를 반환받고 해당 주소에 있는 value를 꺼내오면 된다.

• 해쉬함수의 경우 서로 다른 key값을 넣었을 때 동일한 해쉬값을 반환하는 경우가 있는데, 이를 해쉬충돌이라 한다.