[자료구조 기초] Data Structure 1
1. 자료구조(Data Structure)란?
말그대로 컴퓨터에서 메모리상에 저장되는 데이터들의 순서나 위치관계 등의 구조를 정의하는 것입니다. 각 상황에 따른 데이터에 대한 효율적인 접근과 수정을 위해 여러 자료구조를 공부하고 적용해야 합니다.
또한 컴퓨터가 하는 작업, 계산들을 효율적으로 정리한 것이 알고리즘이면
이런 컴퓨터 작업들은 결과적으로 데이터들을 저장하고 조작하고 관리하는 것이 목표기 때문에,
잘 선택된 자료구조는 그 위에서 행해지는 알고리즘의 효율성을 높이며 이 둘은 긴밀한 관계를 갖습니다.
메모리상의 데이터는 기본 1차원적 구조를 취하지만 도구 등을 통해 복잡한 형태로 구조화도 가능합니다.
2. Array (배열)
배열은 메모리상 데이터를 순서대로 일렬로 나열한 데이터 구조입니다. 배열이름[index]의 형태로 0부터 시작하는 배열의 요소 번호를 가리키는 index(첨자)가 있기 때문에, index(와 데이터 요소들의 크기)를 알면 요소의 메모리 바로 주소를 알 수 있습니다. (Random Access)
찾고자 하는 데이터의 index를 알 때의 데이터 접근 시간 : O(1) (상수시간)
이처럼 Random Access(임의접근)으로 데이터를 접근 및 수정 배열의 최후미부터 데이터를 추가,삭제 해나가는 작업의 경우 빠른 작업속도를 보이지만…
배열의 중간부터 데이터 요소를 추가, 삭제하는 경우 해당 영역의 공간을 확보하거나 메꾸기 위하여 뒷부분의 요소들을 순차적으로 하나씩 이동해나가야 하기 때문에 작업시간이 꽤 소요됩니다.
사이즈가 n인 배열 중간에 데이터 요소 추가, 삭제 시간 : O(n)
그리고 Java와 같은 경우의 배열객체는 처음 지정한 배열의 사이즈를 변경하지 못하므로 초기화 시 지정한 배열의 크기를 넘는 추가 작업이 발생할 경우 새로운 배열을 생성하여 기존 배열의 내용을 순차적으로 복사하는 작업(O(n))이 발생합니다.
물론 초기화 시 넉넉히 배열의 사이즈를 지정해도 되지만 메모리 낭비가 생길 수 있습니다.
따라서 배열은 요소의 추가, 삭제가 거의 없는 비교적 고정된 데이터 집합의 조회에 적합한 자료구조이며,
특히 찾고자 하는 요소의 index를 알 경우 매우 뛰어난 효율을 보여줍니다.
3. List (Java의 경우 LinkedList)
리스트는 데이터가 일직선으로 나열된 형태지만 실제 메모리상에 각 요소 배치는 산개할 수 있습니다.
하지만 각 요소에는 다음 요소의 주소값을 가리키는 포인터(Java에서는 변수node)가 있어 연속된 위치에
데이터가 없더라도 다음 요소들을 찾아나갈 수 있습니다.
보통 메모리상에 산개해 있어 포인터를 따라 순차적으로 데이터에 접근하게 되므로(Sequential Access)
n개의 요소를 가진리스트의 데이터 접근시간 (순차접근, Sequential Access) : O(n)
직접 주소계산이 가능한 index를 알고 있는 배열의 임의접근(O(1))보다 시간이 걸립니다.
(물론 배열도 접근하고자 하는 요소의 index를 몰라 임의접근이 아닌 순차접근을 하면 O(n)입니다.)
하지만 요소의 추가,삭제를 하는 경우 어느 위치든 해당 요소 앞뒤의 포인터를 수정하기만 하면 되므로
리스트의 데이터 요소 추가 및 삭제 시간 : O(1)
위와 같은 빠른 계산 효율을 보입니다.
(물론 그 이전, 해당 위치에 접근해야하는 전제가 있지만 이는 배열도 마찬입니다.)
참고로 각 추가와 삭제에 따라 변경해야할 포인터는 다음과 같습니다.
* 추가 : 추가할 위치의 앞(추가 요소를 가리키게) + 추가요소의 포인터가 뒤를 가리키게함
* A -> C 에서 A -> B(추가요소) -> C
* 삭제 : 삭제하고자 하는 요소의 앞 요소가 삭제요소의 뒷 요소를 가리키게함
* A -> B -> C 에서 A -> C (B->C) 는 결국 A -> C
위 삭제 예시에서 B는 A와의 연결이 끊겨 접근이 불가능하므로 이후 메모리에서 덮어씌어지는 등의 방법으로 사라집니다.
리스트는 배열과 반대로 순차접근 밖에 가능하지 않지만 포인터라는 특성으로 인해,
조회보다는 데이터의 수정과 삭제의 변동이 자주 일어나는 데이터 집합에 어울리는 자료구조입니다.
추가적으로 리스트는 응용된 형태로서,
후미 요소의 포인터를 선두에 연결해 앞뒤 개념을 없앤 ‘순환(원형)리스트’,
각 요소의 뒤를 가리키는 포인터를 추가해 데이터 크기와 추가,삭제 번거로움이 조금 늘어나더라도 전후
이동이 가능한 ‘양방향 리스트’ 등이 존재해 필요에 따라 접근효율을 높일 수 있습니다.
또한 이런 리스트 자료구조의 포인터를 이용하는 특성은 후에 그래프 형태 기반의 자료구조를 구현할 때,
실제 프로그래밍에서 기반이 되는 형태로도 사용됩니다.
(Java에서는 이진트리를 구현에서 각 요소의 자식요소를 연결하기 위해 node변수를 두개 씩 취합니다.)
(그래프에서 각 정점요소를 ‘노드’라고 부르나 내부 변수와 헷갈릴까 위에서 요소라고 했습니다.)
4. 해시 함수와 Hash Table
해시테이블은 key-value 구조를 취하는 데이터들의 자료구조입니다. (Java에서는 HashMap의 전신) key는 (보통 중복이 허용되지 않는) 각 데이터의 식별자이며 value는 데이터의 실제 내용이 됩니다.
해시 테이블은 특정 데이터의 빠른 접근을 위해 key와 해시 함수를 이용하므로 우선 해시 함수에 대해 이야기하도록 하겠습니다.
해시 함수는 내부 알고리즘에 따라 주어진 데이터를 고정길이의 불규칙한 숫자로 변환하는 함수입니다.
사용되는 알고리즘은 MD5(Message Digest Algorithm)이나 SHA(Secure Hash Algorithm)-1 등이
있으며, 보통 보안상 MD5, SHA-1가 아닌 SHA-2가 사용됩니다.
(프로젝트 경험상 실제 패스워드+salt 암호화 등으로 보안기능 구현시 SHA-256 등이 사용됩니다.)
해시 함수로 계산해 변환된 결과(해시값)는 보통 16진수로 표현되며 다음과 같은 특징이 있습니다.
* 주어진 데이터가 어떤 크기를 갖던 해시값의 길이는 같음. (고정길이)
* 주어진 입력 데이터가 같으면 같은 해시값을 가짐. (사용 알고리즘이 같다는 전제)
* 비슷한 데이터지만 1비트라도 다르면 해시값이 크게 달라짐 (아래와 함께 보안성 기여)
* 해시값으로부터 원래 데이터가 무엇인지 역산이 사실상 불가능 (단방향성)
* 극히 드문 확률로 전혀 다른 데이터임에도 같은 해시값이 나올 수 있음 (해시값 충돌)
이런 해시 함수는 흔히 믹서기에 비유하여 설명하는 경우가 많은데 다음과 같이 비유가 됩니다.
* 딸기를 믹서기에 갈면 항상 딸기주스가 나옴 (같은 입력에 같은 해시값)
* 딸기주스만 보고서는 실제 딸기가 어떤 모양일지는 추측이 불가능함 (단방향성)
이제 다시 해시 테이블로 돌아와서 이 자료구조는 보통 다음과 같은 과정을 통해 구현됩니다.
1. 데이터(key-value)를 저장할 배열를 생성합니다.
2. key의 해시값을 배열의 사이즈로 나머지를 구하는 mod연산을 합니다.
3. mod연산의 결과로 나온 index에 데이터를 저장합니다.
(index 범위 : 0 ~ 배열크기-1 vs 위 mod 결과 범위 : 0 ~ 배열크기-1)
4. mod연산 결과가 같아 index가 겹치는 경우(충돌) 리스트 구조로 연결합니다.(Chaining)
참고로 Chaining(연쇄법)에는 리스트를 사용하는 방법 외에도 다음 후보지 주소를 구하는 알고리즘으로
비어있는 메모리 주소가 나올 때까지 찾는 ‘개방 주소법’과 같은 방법 등의 여러가지가 존재합니다.
이렇게 구현된 해시 테이블에서는 key의 값만 알면 해시 함수와 mod연산을 통해 빠른 임의접근이 가능하며
(물론 충돌된 부분은 리스트의 순차접근이 이뤄집니다),
위와 같은 저장 방식과 충돌시 연쇄법을 통해 데이터의 추가, 삭제에도 유연합니다.
물론 배열의 크기가 작아 겹치는 mod 연산 결과가 많으면 순차접근이 많아져 조회능력이 떨어지고, 배열이 너무 크면 배당되지 않은 index가 생길 확률이 높아져 메모리 낭비가 생깁니다.
해시 테이블은 key-value 형태의 데이터를 key값, 해시 함수, mod연산, 연쇄법 등을 이용하여 저장하기에
데이터 변동에 유연하고 효율적인 조회 성능을 보여줍니다.
하지만 바탕이 되는 배열의 크기와 데이터 양에 따라 조회 성능과 메모리 효율이 바뀌므로 주의해야합니다.
언제나 읽어주셔서 감사합니다.^^
개인 공부용 블로그입니다.
잘못된 부분에 언제든지 댓글이나 메일로 지적해주시면 감사하겠습니다.
Leave a comment