For job interview, about Data Structure 면접 공부하기-자료구조

1. Linked List vs Array

1. Array 배열

• 같은 자료형을 갖는 데이터의 집합으로 연속적인 데이터를 저장한다.
• 생성할 때 데이터를 저장하는 데 필요한 모든 메모리를 한 번에 확보해 사용할 수 있게 해주므로 프로그램이 실행되는 중간에 배열의 크기를 바꿀 수가 없다.
• 따라서 새로운 배열을 생성해서 데이터를 복사하는 작업이 필요하다.
• 실행속도를 향상시키기 위해서는 충분히 큰 크기의 배열을 생성해야하고 메모리가 낭비된다.
• 논리적 저장 순서와 물리적 저장 순서가 일치하므로 인덱스 값을 알면 O(1)로 해당 원소에 접근 가능하다.
• 삽입, 삭제 시 빈 공간을 shift해야 하므로 O(n)이다.

2. Linked List 연결 리스트

• 연속적이지 않는 데이터들을 링크로 서로의 순서만을 기억하며 연결하므로 삽입/삭제 시 O(1)이다.
• 즉, 논리적 저장 순서와 물리적 저장 순서가 일치하지 않으므로 원하는 데이터를 찾거나 원하는 곳에 삽입 시 O(n)이다.
• 중간 노드의 연결이 끊기면 다음 노드 찾기가 어렵다.
• 이동뱡향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전요소에 대한 접근은 어렵다. -> Double linked list 이중 연결리스트 등장
  cf. Array List : 저장 순서가 유지되고 중복 허용이 된다. 데이터 저장 공간으로 배열을 사용한다. 인덱스로 접근 시 O(1). 순차적으로 데이터를 추가/삭제 시 링크드 리스트보다 빠르다.

2. Stack, Queue, Deque, Heap

1. Stack 스택

• LIFO (Last In First Out)
• 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조이다.
• 스택이 꽉 찬 상태를 overflow 오버플로우 라고 한다.
• 스택이 텅 빈 상태를 underflow 언더플로우 라고 한다.
• Usage 용도 : 인터럽트가 발생하여/부프로그램 호출시 복귀 주소 저장할 때, 함수 호출의/재귀 프로그램의 순서 제어, 후위표기법 산술 연산할 때, 컴파일러를 이용한 언어 번역할 때, …

2. Queue 큐

• FIFO (First In First Out)
• 한쪽에서는 삭제 작업이 이루어지고 다른 한쪽에서는 삽입 작업이 이루어지도록 구성한 자료 구조이다.
• 두 개의 포인터 front/head, rear/tail이 있다.
• Usage 용도 : 작업 스케줄링과 같이 순서를 기다리는 등의 대기 행렬의 처리에 사용한다.

3. Deque (Double Ended Queue) 덱

• 스택과 큐의 장점만 따서 구성 (삽입과 삭제가 양쪽 끝에서 모두 발생할 수 있다.)
• 입력 제한 : 입력이 한쪽에서만 발생하고 출력은 양쪽에서 일어날 수 있다.
• 출력 제한 : 입력이 양쪽에서 일어나고 출력은 한쪽에서만 이루어진다.

4. Heap 힙

• 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기반으로 한 자료 구조이다.
• property 속성 : A가 B의 부모 노드이면, A의 키값과 B의 키값 사이에는 대소관계가 성립한다.
• Max Heap 최대 히프 : 최대 트리이면서 완전 이진 트리 (각 노드의 값이 그 자식의 키 값보다 작지 않은 트리 - 루트 노드가 최대값)
• Min Heap 최소 히피 : 최소 트리이면서 완전 이진 트리 (각 노드의 값이 그 자식의 키 값보다 크지 않은 트리 - 루트 노드가 최소값)

3. HashMap

1. HashMap 해시맵

• key 키와 value 값을 쌍으로 저장 (cf. keySet(), entrySet(), values())
• 키는 검색에 사용되기 때문에 유일해야하지만 값은 중복이 허용된다.
• hashing 해싱을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다.
• 배열과 연결이 결합된 형태. 추가/삭제/검색/접근성이 모두 뛰어남. 검색에는 최고성능을 보인다. (해시 함수를 이용하여 저장할 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다.)

2. Hashing 해싱

• 해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법
• 해싱은 하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것이다.
• 해시함수는 데이터가 저장되어 있는 곳을 알려 주기 때문에 순차 검색에 비해 다량의 데이터 중에서 원하는 데이터를 빠르게 찾을 수 있다.

@ 해시 함수 종류 : MD5, SHA-1, SHA 224, HAS-160 등

3. Hash Collision 해시 충돌

• 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값(= key 키)을 내는 상황을 의미한다.
• 해시 함수의 입력값은 무한하지만, 출력값의 가짓수는 유한하므로 해시 충돌은 반드시 발생한다.
• 충돌 해결 방법
  • Chaining 체이닝 : 각각의 해시 테이블 인덱스에 해당하는 자료구조를 연결 리스트로 만들어 데이터를 삽입하다가 해시 충돌이 발생하면 연결 리스트로 데이터를 연결하는 방법이다. 복잡한 계산식을 사용할 필요가 개방 주소법에 비해 적다. 단, 검색 시 시간복잡도는 O(n)이다.
  • Open addressing 개방 주소법 : 해시 테이블 인덱스 중 비어있는 공간을 할당하는 방법으로 데이터의 주소값이 변한다. 삽입/삭제 시 오버헤드가 적고 저장할 데이터가 적을 때 유리하다.
    • Linear Probing 선형 탐색 : 해시 충돌 시 다음 bucket 버킷(해시 주소 하나에 할당 된 전체 메모리 공간) 혹은 몇 개를 건너 뛴 버킷에 데이터를 삽입한다.
    • Quadratic Probing 제곱 탐색 : 해시 충돌 시 제곱만큼 건너 뛴 버킷에 데이터를 삽입한다.
    • Double Probing/Rehashing 이중 해시/리해싱 : 해시 충돌 시 다른 해시 함수를 한 번 더 적용한 결과를 이용한다.
  • 두 방식 모두 최악의 경우 O(n)이다. 하지만 개방 주소법은 연속된 공간에 데이터를 저장하기 때문에 체이닝에 비해 캐시 효율이 높다. 반면, 개방 주소법은 버킷을 계속 사용하기 때문에 테이블 확장을 늦출 수 있다는 점에서 체이닝 방식이 낫다.

4. 깊이 우선 탐색 DFS와 너비 우선 탐색 BFS

1. DFS

• 그래프 상에 존재하는 임의의 한 정점으로부터 최대한 왼쪽으로 깊게 정점을 탐색하는 알고리즘이다.
• 자식이 없는 정점까지 탐색한 후 가장 가까운 탐색이 끝나지 않은 정점으로 돌아와 탐색을 계속 진행한다.
• 스택 또는 재귀 함수를 사용해 구현한다. 시간 복잡도는 O(정점 개수 + 간선 개수)이다.
• 모든 경로를 탐색하고 결과를 확인해야 하는 경우, 문자열 등을 탐색할 때 ‘사전 순서로 앞에 오는 것’처럼 앞부터 검색해서 찾는 것이 빠를 경우 사용되는 알고리즘이다.

2. BFS

• 그래프 상에 존재하는 임의의 한 정점으로부터 깊이가 얕은 순서로 왼쪽부터 차근차근 정점을 탐색하는 알고리즘이다.
• 자식이 없는 정점까지 탐색한 후 가장 가까운 탐색이 끝나지 않은 정점으로 돌아와 탐색을 계속 진행한다.
• 큐, 리스트, 배열을 사용해 구현한다. 시간 복잡도는 O(정점 개수 + 간선 개수)이다.
• 최단 경로 문제 등에 자주 사용되는 알고리즘이다.

※ 참고 : https://en.wikipedia.org/wiki/Heap_(data_structure), https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#array-vs-linkedlist, https://preamtree.tistory.com/20, 시나공 정보처리기사, Java의 정석(남궁성 지음), TopCoder 알고리즘 트레이닝(타카하시 나오히로 지음)