자료구조

자료구조

배열과 연결리스트

자료구조에서 배열과 연결리스트는 레퍼런스 타입의 변수이고, 각 변수들은 배열및 리스트의 시작지점의 메모리 주소를 가리키고 있다는 점에서는 동일하다.

하지만 중대한 차이가 존재하는데,

배열은 연속된 메모리 공간을 가지고 있고

리스트는 연속된 메모리 공간을 할당받지 않는다

이런 차이로 인해 다음과 같은 특성이 나타난다.

• 배열 배열은 연속된 메모리 공간을 가지고 있다. 그 말인즉, 랜덤 엑세스가 용이하다는 의미이다.

  연속된 메모리 공간이 주어졌을때, i번째 요소를 찾기위해서는 시작지점에서 i번째 메모리 공간을 확인하면 그만이기 때문 시간복잡도는 O(1)

  하지만 연속된 메모리공간으로 인해 배열 중간에 새로운 요소를 추가하거나, 특정 요소를 제거하는 경우 중간에 새로운 메모리 공간을 추가 혹은 삭제하고 연속적인 메모리 공간으로 만들어야 한다.

  그렇기 때문에 최대 O(n)의 시간이 소요될수 있다.

• 연결리스트 연결리스트는 연속된 메모리 공간을 가지지 않는다.

  각각의 노드는 형태에 따라 전/후 요소가 위치한 메모리 주소를 저장하고 있다.

  만약 요소가 다음 요소에 대한 주소만 알고 있는경우라면 단방향 연결 리스트라 부른다.

  만약 그렇지 않고 이전 요소의 주소까지 알고 있다면 이중 연결리스트라 부른다.

  연결리스트는 요소들에 접근하기 위해 포인터를 이용한다.

  이런 포인터들을 이용하면 객체 하나하나에 접근이 가능하다. 하지만 특정값을 가진 요소가 몇번째 있는지는 포인터를 이동하며 하나하나 확인해 봐야 한다.

  따라서, 특정 요소를 찾는 로직은 모든 요소들을 찾아봐야 할수도 있기 때문에, O(n)의 시간이 소요된다.

  하지만 특정 노드를 추가하거나 삭제하는 로직은 매우 간단하다.

  추가 삭제의 경우 이전/이후 노드의 주소값을 변경하기만 하면 그만이기 때문.

  삭제된 노드는 그럼 어떻게 처리하는지 궁금할수도 있다. 그건 가비지 컬렉터라는것이 이런 접근이 불가능한 변수들을 청소해 주기 때문에, 걱정은 하지 않아도 된다.

해시 테이블

해시 테이블은 해시펑션을 이용하여 특정 키를 인덱싱하고 인덱싱된 값에 해당되는 버킷에 저장하는 알고리즘이다.

키-벨류 쌍을 저장하는 방식으로 자바스크립트의 객체, 파이썬의 딕셔너리와 유사하다.

이런 해시테이블은 해시펑션만 거친다면 어느 버킷에 저장해야할지 명확하게 알수 있다. 기본으로 O(1)의 시간이 추가 및 삭제에 필요하다.

해시테이블의 문제점

해시테이블은 해시펑션으로 인해 해시 충돌이라는 문제를 겪을수 밖에 없다.

해시 충돌은 무한한 수를 유한한 범위로 축약하는 과정에서 반드시 생기는 문제이다. A와 B라는 서로다른 입력을 해싱하면 C라는 같은 출력이 나오는 현상이 해시 충돌이라 한다.

이런 해시 충돌이 해시 테이블에서 생겼을때 아무런 대응이 없다면 버킷의 값이 덮어씌워지는 경우가 발생할 수도 있을것이다.

해시충돌 회피

이런 해시충돌을 해결하는 방법들은 다음과 같다. 우선 말해둘것은 이중 하나만 사용되는것이 아니라, 2개가 혼용되기도 한다는 것이다.

1. 오픈어드레싱
2. 체이닝

3. 더블 해싱

4. 오픈 어드레싱 오픈 어드레싱은 해시충돌이 발생했을때 주변에 비어있는 다른 버킷에 집어넣는 방식을 사용하는것이다.

이런 방식은

• 분포가 고르지 않음
• 해시충돌에 대해 정확한 값을 알기 어려움 와 같은 문제가 존재한다.

분포도가 고르지 않아서 생기를 문제를 해결하기 위해 알고리즘에 따라 1, 2, 4 번 옆에 있는 버킷에 값을 저장하기도 한다. 하지만 해당 방법도 해시충돌이 여러번 발생하는 경우에대해 분포도가 고르지 않다는 문제가 존재한다.

1. 체이닝 해시 충돌에 대응하기 위해 버킷은 연결리스트로 구성된다. 이때 값을 저장할때는 키와 벨류를 같이 저장한다. 벨류만 저장한다면 어떤 벨류가 어떤 키와 쌍을 이루고 있는지 알수 없기 때문이다.

체이닝 방식은 특정 키에대한 값을 알기위해 버킷에 저장된 모든 요소들을 살펴봐야 할수도 있다. 따라서 최대 O(n)의 시간이 소요된다. 새로운 요소를 추가하는것은 여전히 O(1)의 시간이 소요된다.

1. 더블 해싱 더블해싱은 해시 충돌에 대해서 다른 해시펑션을 이용해 해싱을 진행한다. 비록 첫번째 해싱에서 충돌이 발생했더라도, 전혀 다른 해시 펑션으로도 충돌이 일어날 확률이 매우 낮기 때문이다.

따라서 다른 방법에 대해 해시테이블에 분포도가 비슷해진다.

해시테이블은 해시맵, 해시셋등을 구현할때 사용한다.

트리

트리는 양방향 연결리스트를 살짝 변형한 것이다.

생긴것이 마치 나무와 유사하다 하여 트리라 부른다. 이때 트리의 구성 요소들은 노드라 부른다.

루트노드는 트리에 맨 처음 노드를 가리키며 자식노드는 어떤 노드에서 다음에 방문이 가능한 하위 노드들을 말한다. 부모노드는 어떤 노드를 자식 노드로 가진 상위 노드를 말한다. 리프노드는 자식노드를 가지지 않는 노드들을 말한다.

해당이미지에서 2를 가진 노드가 루트 노드이며, 루트노드는 각각 7과 5를 값으로 가진 노드를 자식노드로 둔다. 4란 값을 가진 노드는 리프노드이며, 9를 가진 노드를 부모노드라 한다.

자료구조에서 자주 사용되는 트리 구조는 다음과 같다.

1. 이진트리
2. 이진 탐색 트리

이진트리

이진 트리는 트리 구조에서 모든 노드의 자식노드위 숫자가 2개 이하인 경우에 해당된다.

이진트리는 아무런 특성없이 노드를 추가한 모양새 이므로, 노드의 추가 및 삭제, 탐색에 모두 최대 O(n)의 시간이 소요된다.

이렇게 되는 이유는, 특정한 규칙이 없기 때문에 노드들 하나하나 전부 살펴 보아야 하기 때문이다.

이런 이진트리는 구성 모양에 대해 다음과 같이 분류가 가능하다.

• 완전이진트리
• 포화이진트리
• 균형트리

완전이진트리의 정의는 다음과 같다. 마지막 레벨 (혹은 높이라고 부른다. 쉽게 생각하면 루트에서부터 가장 먼곳의 리프노드가 몇세대 차이나는지 보면된다.) 을 제외하고 모든 레벨에서 노드가 존재해야하며 마지막 레벨의 리프노드는 루트노드 왼쪽에 존재해야 한다.

포화 이진트리의 정의는 다음과 같다. 포화 이진트리는 마지막 레벨을 제외한 모든 레벨의 노드가 2개의 자식 노드를 가져야한다. 또한 모든 리프노드는 동일한 레벨에 존재해야 한다.

균형트리의 정의는 다음과 같다. 모든 노드의 양쪽 서브트리의 높이 격차가 1 이내인 트리.

해당 그림은 균형 트리가 아니다.

리프노드들부터 높이를 0으로 두고 부모 노드의 높이를 +1 해보자.

즉 h =0인 노드들은 12, 19, 67을 가진 노드들이다. 따라서 h = 1인 노드들은 14,23,72를 가진 노드들이다.

이때 17을 가진 노드는 왼쪽의 자식노드의 h가 3이고, 오른쪽의 노드의 h가 1이다.

차이가 2이상 벌어지게 되었으므로, 균형트리의 조건에 성립하지 않는다.

이진 탐색 트리

이진트리에서 특정한 규칙을 추가하여 노드를 추가하는 방법을 지정해둔경우이다.

만약 추가하는 값이 있다면 부모노드는 자신보다 작으면 왼쪽 노드에 새로운 노드를 추가하고, 자신보다 큰 값이면 자신의 오른쪽 노드에 새로운 노드를 추가한다.

왼쪽 서브 트리와 오른쪽 서브트리는 해당 노드를 바탕으로 다시 왼쪽 노드 혹은 오른쪽 노드에 새로운 노드를 추가한다.

재귀적 용법을 적용하기 정말 적당해 보인다. 실제로 재귀적 호출을 통해 트리를 구현해본적이 있다. 코드가 꽤나 간결했던걸로 기억한다.

특정 노드를 찾거나 추가할때 시간 복잡도는 O(logN)이다. 특정 노드를 제거할때 역시 적당한 노드를 찾는데 시간이 영향이 가장크다. O(logN)

하지만, 해당 사항은 베스트 케이스이다. 워스트케이스는 링크드 리스트처럼 왼쪽 혹은 오른쪽에만 자식노드가 추가되는 형식이다.

노드 탐색, 추가, 삭제에 O(N)의 시간복잡도를 가지게 된다.

힙과 비교

힙은 우선큐를 제작할때 주로 사용되는 자료구조이다. 우선큐에서 힙을 배열로 표현하는경우, 맨 처음의 요소를 제거하더라도 힙의 재구성의 필요가 없어진다.

정렬방식에 따라 가장 큰값이 루트에 존재하는 최대 힙과 가장 작은값이 루트에 존재하는 최소 힙 두가지로 구분이 가능하다.

힙은 다음 정렬방식을 사용한다.

1. 자식노드들은 항상 부모노드의 값보다 작은 값을 가지고 있다.
2. 형제노드 사이에는 그 어떤 우선순위도 주어지지 않는다.

그렇기 때문에 이진탐색트리와 다른점이 발견된다.

이진탐색트리는 부모노드이 오른쪽에 부모노드보다 큰 값을 가진 노드들만 존재한다.

하지만 힙은 부모노드보다 작은값들에 대해서만 자식노드로 추가된다. 그리고 최대값 혹은 최소값을 찾기집중하기 위해 동일한 부모노드를 가진 형제 노드들끼리는 우선순위가 존재하지 않는다.

그래프

그래프는 트리와 비슷해 보인다.

하지만 가장큰 차이점은 루트 노드는 존재하지 않으며, 연결된 노드는 노드 자기 자신이 될수도 있고, 연결을 따라가다보면 다시 자기 자신으로 돌아오는 Circle이 형성된 노드들도 존재할 수도 있다.

위와 같은 그림처럼 노드의 연결에 대해 제한이 없는 자료구조가 그래프이다. 사진은 화살표로 단방향처럼 표시해 두었는데, 반드시 방향성을 지정해둘 필요는 없다.

일반적으로 연결울 구성하는것을 엣지라고 부르는데, 이 엣지에도 가중치를 부여할 수 있다. 이런 그래프는 weighted 그래프라고 한다.

이런 그래프는 노드사이의 관계를 표현할때 적절하게 사용할 수 있다.

덕분에 최단 경로를 찾아야하는 네이게이션이 사용하기도 한다.

이때 정확하게 최단경로를 찾아내는 알고리즘은 다잌스트라 알고리즘이 있다. 스타 알고리즘도 존재하지만, 해당 알고리즘은 빠른 탐색시간에 초첨이 맞춰져 있다보니, 정확성이 좋지 않다.

표현방법

그래프는 두가지 방법으로 표현이 가능하다.

1. 배열
2. 연결리스트

배열은 2차원 배열을 행렬처럼 연결되었으면 1 이상의 값을 부여하고, 연결되지 않는 노드들은 0의 값을 부여하여 연결되지 않았음을 표시하는 방법이다.

하지만 그래프를 구성하는 노드의 수가 많을수록 S(n^2) -(공간 복잡도는 S를 사용한다.)의 메모리 공간이 필요해진다. 어떻게보면 공간의 낭비가 존재한다는 의미로 볼수 있다. 하지만 어떤 노드와 연결되어있는지 O(1)의 시간이 소모되며 연결여부를 확인하기 쉽다.

이에 다르게 연결리스트는 연결된 엣지의 수만큼 노드들이 구성되어 있다. 어떻게 보면 엣지의 수가 많을수록 배열의 방식에 비해 메모리 효율성이 좋고 볼수 있을듯 하다.

하지만 연결리스트의 특성상 어떤 노드에 어떤 노드들이 연결되어 있는지 확인하는데 노드들의 수만큼 O(node)의 시간복잡도를 가지게 된다.