데이터 구조

배열(Array)

• 배열은 많은 수의 항목을 메모리에 저장할 때 사용할 수 있는 방법 가운데 가장 단순하고 기본적인 방법이다.
• 배열은 메모리에 연속적인 공간을 할당하여 만든다.
• 배열 속에 저장하려는 항목은 그 메모리 공간 속에 순차적으로 기록한다.
• 장점 - 프로그래밍하기 쉽고 접근시간이 상수 시간이다.
• 단점 - 연속적으로 이어진 메모리 공간에만 저장할 수 있다. 중간 항목을 제거하려면 제거하는 항목 이후의 모든 항목을 한 칸씩 앞으로 당기거나 죽은 공간으로 표시해야 한다.

연결 리스트(linked list)

• 저장한 칸들을 쇠사슬처럼 연결한 구조이다.
• 장점 - 배열과 달리 연속적인 메모리 주소로 구성될 필요가 없다. 처음부터 필요한 모든 메모리를 할당해 둘 필요가 없다. 리스트 중간에 추가, 삭제가 간단하다.
• 단점 - 배열과 달리 n번째 항목을 상수 시간에 가져오지 못한다. 어느 한 칸의 주소만 가지고 해당 항목을 삭제하거나 앞쪽으로 옮기기 어렵다.(각 칸은 다음 칸의 주소만 알고 있어, 이전 칸의 주소를 구할 수 없기 때문에)

이중 연결 리스트(double linked list)

• 각 칸이 갖는 포인터를 2개로 늘려, 각각 이전 다음 칸을 가리키도록 한 것
• 연결 리스트의 장점을 그대로 가진다.
• 단점 - n번째 항목에 상수 시간 접근 불가. 2개의 포인터로 인해 코드 복잡 데이터 저장하는데 메모리 늘어남.

배열 VS 리스트

- 연결 리스트를 사용해야 하는 경우

• 리스트에서 항목의 추가, 제거가 아주 빠르게 수행되어야 한다.
• 데이터에 순차적으로만 접근한다.
• 리스트의 중간에 항목의 추가, 제거를 수행해야 한다.
• 리스트의 정확한 크기를 계산할 수 없다(실행 도중에 리스트가 확대, 축소되어야 한다.)

- 배열을 사용해야 하는 경우

• 데이터의 임의의 지점으로 상수 시간에 접근해야 하는 경우가 잦다.
• 항목에 아주 빨리 접근해야 한다.
• 실행 도중에 항목 개수가 변하지 않으므로 컴퓨터 메모리 공간을 연속적으로 할당하기 쉽다.

트리(tree)

• 연속적인 물리적 메모리가 필요 없다.
• 다른 칸을 향한 포인터를 가짐.
• 계층형 구조이다.

트리 종류 

- 이진 탐색 트리(binary search tree)

• 효율적인 탐색을 지원하는 트리
• 각 노드가 자식을 2개까지만 가질 수 있음.
• 노드의 위치는 노드의 키-값에 의해 결정된다. 부모 노드의 왼쪽 자식 노드는 부모 정점보다 키-값의 크기가 작아야 하고 오른쪽은 커야 함.

* 이진 탐색 트리에 정점을 너무 많이 추가하면, 자식이 하나뿐인 정점이 많이 생기면서 트리의 높이가 터무니없이 높아진다.(연결 리스트에 가까운 형태) 따라서, 재배열해야 하는데 이를 '트리 균형 잡기'라 한다.

* n개의 균형 잡힌 이진 탐색 트리를 탐색하는 시간 복잡도는 O(logn)이다.

* 트리에 항목이 추가, 제거될 때마다 균형을 새로 잡는다면 성능이 크게 떨어지므로 대개 여러 번의 추가, 제거 연산이 일어난 후에 균형을 잡는다.

 

- 자가 균형 이진 탐색 트리 : 레드 블랙 트리(red-black tree)

• 정점들을 레드 또는 블랙으로 칠함으로써 균형을 유지.
• 맵을 구현 하는데 자주 사용된다. 맵의 빈번한 수정을 효율적으로 처리.
• 자가 균형을 통해 키로 항목을 구하는 작업 빠름.

- 자가 균형 이진 탐색 트리 : AVL tree

• 레드 블랙트리에 비해 항목 추가 제거 시간이 조금 더듬 대신 균형을 더 잘 잡는 경향이 있음 즉 항목의 조회 속도가 빠름.
• 읽기 작업이 매우 높은 빈도로 일어나는 상황에 성능 최적화.

- 이진트리 : B트리

• 각정점이 하나 이상의 항목 저장 자식도 둘 이상씩 연결 따라서 큰 덩어리의 데이터 효율적 처리.
• 데이터베이스 시스템에 보편적 사용.

- 이진 탐색 트리 : 이진 힙(binary heap) 

• 최대(최소) 항목을 즉시 구할 수 있는 특별한 이진 탐색 트리. 특히 우선순위 큐를 구현할 때 유용.
• 최대(최소) 구하는 비용은 O(1), 노드의 탐색 추가 비용은 O(logn).
• 힙의 노드 배치 규칙은 이진 탐색 트리와 동일하나 제약이 하나 추가됨.
• 제약 : 부모 노드가 반드시 두 자식 노드보다 커야(또는 작아야) 한다.

그래프

• 트리와 유사한 데이터 구조. 다른 점이라면 자식, 부모 노드가 없음.
• 정점과 간선으로 자유롭게 배열될 수 있음.
• 네트워크 연결망을 다루어야 한다면 그래프!

그래프 탐색

• 깊이 우선 방식(DFS, depth-frist search) - 스택 사용. 구현 쉬움 메모리 적게 사용.
• 너비 우선 방식(BFS, breadth-frist seaarch) - 큐를 사용. 구현 어려움. 많은 메모리 사용.
• 탐색하려는 정점이 출발점에서 몇 단계밖에 떨어지지 않았다고 예상되는 상황에서는 너비 우선 탐색 아니면 깊이 우선 탐색.
• 다익스트라 알고리즘(Dijkstra algorithm) - 그래프 최단경로 탐색 알고리즘(GPS 내비게이션 시스템). 큐 대신 우선순위 큐 사용. 하지만 음의 폐로(negative cycle)가 발생할 수 있음. 간선에 0보다 작은 가중치가 존재해 출발점과 도착점이 서로 연결되는 순환 경로가 생길 수 있음. 음의 폐로에서는 같은 경로를 계속 되돌기 때문에 목적지에 도달 불가능 그러므로 음의 가중치를 갖는 간선이 있다면 주의가 필요하다.
• 양방향 탐색 기법 - 탐색하려는 그래프가 매우 방대할 때 사용. 출발점과 도착점에서 탐색을 동시에 시작하여 두 탐색 범위가 겹친다면 완료.
• 페이지 랭크(OageRank algorithm) - 구글 검색 알고리즘. 어떤 페이지가 다른 중요한 페이지로부터 많이 링크된다면 링크된 페이지 역시 중요한 페이지이다. 이 알고리즘은 페이지를 그래프로 나타내고 여러 라운드에 걸쳐 페이지의 점수 평가. 처음에는 모든 페이지가 동일한 점수를 가지만 라운드가 진행될 때마다 페이지들은 자신이 획득한 점수를 자신이 링크하는 페이지에 나누어줌. 이 분배과정에서 점수가 안정화될 때까지 계속 반복.

해시 테이블(hash taable)

• 탐색을 O(1) 비용으로 수행할 수 있는 데이터 구조.
• 대량의 연속적 메모리를 미리 할당 하지만 배열과 다르게 항목을 순차적을 저장하지 않음.
• 해시함수에 의해 정해짐.
• 맵과 집합을 구현하는데 자주 사용.
• 장점 - 항목의 추가 제거가 트리 기반의 데이터 구조에 비해 빠름.
• 단점 - 올바르게 동작하기 위해 대량의 연속적 메모리 공간 필요.

해시 함수 

• 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
• 같은 입력값에 대해서 같은 출력값이 보장된다.
• 서로 다른 입력값으로부터 동일한 출력값이 나올 가능성이 희박해 입력값에 대한 무결성이 보장
• 일방향성을 갖는다. (출력값으로 입력값을 추론 불가)
• 좋은 해시 함수의 조건 : 계산이 간단해야 한다. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다.

* 해시 함수의 대표 - SHA(Secure Hash Algorithm)

• NSA에 의해 1993년 처음 개발된 해시 알고리즘
• 현재 주로 사용되는 것은  SHA-2 함수 군으로, SHA-256, SHA-512으로 나뉜다.
• SHA-256, SHA-512는 해시 충돌성이 사실상 0에 수렴.(해싱을 하면 2^256개의 해시값 중 하나가 나옴)
• 무결성 검사, 파일 다운로드, 데이터베이스에 비밀번호 저장, 블록체인,  GIT등에 활용됨

해시 충돌

• 우연히 두 개의 입력값에 동일한 해시값이 나옴
• 해시함수가 내어놓는 값의 범위(해시 테이블에 할당된 메모리의 크기)가 넓을수록 데이터가 분포될 수 있는 범위가 더 많아지고 해시 충돌이 일어날 가능성도 줄어듦. 따라서 해시 테이블의 최소 공간을 50%는 남겨 두어야 함. 그렇지 않으면 충돌이 너무 자주 발생해 해시 테이블의 성능이 심각하게 떨어짐
• 해시 함수는 일반적으로 다양한 크기의 데이터를 입력받아 일정한 크기의 값을 출력. 서로 다른 데이터로 해시 함수를 적용해도 결과가 동일할 수 있음

해시 충돌 해결 방법

1. 체이닝(chaining) 

• 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트에 매달아서 관리한다.
• 원소를 검색할 때는 해당 연결 리스트의 원소들을 차례로 지나가면서 탐색한다.

2. 개방 주소 방법(open addressing)

•  체이닝과 달리 어떻게든 주어진 테이블 공간에서 해결한다.
• 따라서 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장한다는 보장이 없다.
• 선형 조사(linear probing), 이차원 조사(quadratic probing),  더블 해싱(double hashing)

2-1. 선형 조사(linear probing)

• 가장 간단한 충돌 해결 방법
• 충돌이 일어난 자리에서 일차 함수의 보폭으로 점프한다.
• 테이블의 경계를 넘어갈 경우에는 맨 앞으로 돌아간다.

2-2. 이차원 조사(quadratic probing)

• 바로 뒷자리를 보는 대신 보폭을 이차 함수로 넓혀가면서 본다.

2-3. 더블 해싱(double hashing)

• 두 개의 함수를 사용한다.
• 하나의 함수는 초초의 해시값을 얻을 때, 다른 하나의 함수는 해시 충돌이 일어났을 때 이동할 폭을 얻을 때 사용
• 두 원소의 첫 번째 해시값이 같더라도 두 번째 해시값까지 같을 확률은 매우 희박하므로 서로 다른 보폭으로 점프

 

출처 - 한 권으로 그리는 컴퓨터 과학 로드맵 / 블라드 스톤 페헤이라 필루