방통대 2019-2학기 수강내용 정리 <자료구조>
한 학기를 마친 지금, 시험에 목 메지 않고 나의 실력 향상을 위해 학교를 다니자고 다짐한 내 결심을 이행하기 위해 한 학기동안 배운 내용을 정리하고자 한다.
1. 배열
- 여기서 말하는 배열이란 순수한 동적크기의 배열이다. 배열의 모든 원소들은 메모리에 다닥다닥 붙어서 올라간다. 어렵게 이야기 하자면, 메모리에 적재되는 물리적인 위치가 연속적이다 라고 하는 것이다. 이는 공간적 지역성의 원리라고도 한다.
공간적 지역성이란 방금 접근한 메모리 주소에 또 접근할 가능성이 높고 그에 인접한 원소들도 접근할 가능성도 높음을 의미한다.
배열의 공간적 지역성은 탐색을 할 때 그 빛을 발한다.
배열 a=[1,2,3,4,5]를 저장한다고 하면 a의 각 원소들은 모두 메모리 주소에 차곡차곡 순서대로 저장된다. 따라서 배열에 있는 값들은 순회하며 꺼내려 한다면 처음 1을 찾은 메모리 주소에서부터 더 멀리 찾을 필요도 없이 순서대로 꺼내기만 하면 되므로 탐색이 쉽다.
하지만 단점은 데이터의 삽입과 삭제가 일어날 때이다. 만약 배열에 원소를 5개 넣고 싶고 각 원소는 메모리 주소를 1칸씩 차지하면, 우리는 최소한 메모리가 5칸이 되는 곳을 찾아서 그곳에 저장해야한다. 메모리 중간중간에 3칸, 4칸이 비어있어도 이를 활용할 수가 없다는 단점이 있다.
또한 이미 원소가 4개인 배열이 있을때 이 배열의 중간에 값을 추가하고 싶다면 이를 위해 배열 전체를 다른 메모리주소로 옮겨야한다. 그렇지 않으면 배열의 특징인 공간적 지역성이 유효하지 않기 때문이다. 이 때문에 배열에 값이 많아질수록 삽입과 삭제는 부담스러운 연산이 되며 성능 또한 좋지 않게 된다.
2. 연결리스트
- 배열과 가장 잘 비교 되는 자료구조일 것이다. (사실 배열과 연결리스트는 어느 자료구조 커리큘럼이나 가장 초반부에 설명하고 있기 때문에 꽤 많이 봐와서 방통대 강의보다는 그 내용을 바탕으로 이 글을 쓰게 되는게 아닌가 싶다.)
연결리스트는 배열과 달리, 원소들이 메모리에 적재되는 물리적인 위치가 논리적인 위치와 다르다. 메모리의 주소에 산재되어 있는 것이다. 그렇다면 배열은 어떻게 원소의 논리적인 순서를 유지하고 있을까?(=배열의 원소들의 순서를 어떻게 알고있을까?)
리스트에 저장 된 원소는 자신이 가지고 있어야 하는 데이터 외에 다음에 가리킬 데이터의 주소도 가지고 있다. 리스트에는 값이 들어가는 것이 아니다. 노드라는 것이 들어가며 노드는<값, 다음노드 주소>의 쌍으로 이루어져 있다.
덕분에 리스트를 순회하며 값을 가져올 때 첫번째 노드의 값을 꺼내어 쓰고, 두번째노드는 첫번째 노드의 다음노드주소를 이용하여 다음 노드로 이동하게 된다.
2-1. 원형연결리스트
- 원형연결리스트는 연결리스트의 속성을 상속받는데 마지막 노드가 Head를 가리키도록 하여 순환하는 방식으로 만든 리스트이다. 원래의 연결리스트는 선형이다.
마지막 노드는 다음 노드가 없으므로 노드의 다음노드 주소 포인터가 null을 가리키지만, 원형 연결리스트는 마지막 노드가 다음노드 주소 포인터로 Head(가장 처음에 있는 노드)를 가리키게 되는것이다.
마지막 노드의 포인터를 좀 더 의미있게 사용하자는 취지에서 나온 자료구조이다.
3. 스택
- 스택은 흔히 큐와 같이 비교가 잘 되는 자료구조이며 비유는 늘 쌓아놓은 접시로 되는 것 같다. 스택은 별 다른 것이 없이 그냥 후입선출을 시켜줄 수 있는 자료구조라고 생각하면 된다. (기본적인 자료구조이기 때문에 배열이나 연결리스트처럼 설명을 덧대는 것은 의미없을거라 생각한다.)
개인적인 소득이 있다면, 이번 학기 컴퓨터구조와 프로그래밍 언어론 수업을 들으면서 실제 스택이 활용되는 모양새를 좀 알 수 있었던 것 같다. 컴퓨터 구조에서는 프로그램이 누산기를 사용할 때 스택 자료구조를 사용한다는 것을 알 수 있었고 프로그래밍 언어론에서는 함수들의 호출관계가 스택프레임으로 이루어져 있다는 것을 알 수 있었다.
자세한 설명은 각 과목의 후기에서 남기도록 하고, 스택은 별로 큰 특징이나 기존에 알던 내용에서 크게 더해진 것이 없어 여기서 pass해도 될 것 같다.
4. 트리
- 어떻게 보면 본 강의를 통해 배운 가장 큰 것이 있다면 트리라고 할 수 있겠다. 트리는 이미 뉴비일 때부터 많이 들어 온 자료구조이지만 명확한 의미와 개념을 모르고 있었다. 하지만 이번 강의를 통해 트리가 무엇이고 트리를 활용한 다양한 자료구조는 무엇이 있는지 알 수 있었던 것 같다. (사실 트리를 수업한 뒤로 나오는 거의 모든 자료구조는 이 트리를 Base로 하는 자료구조들이며 교수님 또한 트리를 구현하기 쉽고 성능 또한 좋은 자료구조라고 말씀하셨다.)
트리는 논리적 계층이 있는 자료형태이다. 트리의 장점은 검색이 빠르고 구현이 쉽다는 것에 있다. 구체적인 사항은 트리를 구현하여 새로운 속성을 가진 트리들을 보자.
4-1. 이진트리
- 아마 트리들 중 가장 유명한 트리이지 않을까 싶다. 이진트리란 노드의 진출차수가 최대 2인 트리를 의미한다. 쉽게 이야기 하면 한 노드가 가질 수 있는 최대 자식 노드의 갯수가 2개라는 것이다.
노드의 갯수가 2개인 덕분에 한 노드가 많은 자식노드를 담고 이를 탐색하는데 오래 걸리는 불상사가 없다. 다만, 메모리 공간을 비효율적으로 관리하게 될 수 있는데 다음과 같은 경우가 그 예이다.
루트노드가 0이고 자식노드 1, 2가 있다. 그리고 그 자식노드들은 또 자식노드들을 가져서 데이터는 총 0~6까지의 노드가 있다고 하자. 잎노드들은 3, 4, 5, 6이 되는데 이 때 4와 5가 삭제가 되었다면 트리의 최말단 왼쪽 노드는 3, 외말단 우측 노드는 6이 된다. 하지만 중간은 뻥 비어버리는 경우가 생긴다.
이진트리에서도 위와 같은 상황은 발생할 수 있고 이진트리가 아닌 일반 트리는 이와같은 현상이 더 심하게 일어날 수 있다 (노드의 진출차수가 2보다 클 수 있으므로)
따라서 이를 해결하고자 트리에서는 '밸런싱'이라는 것이 중요하게 작용하는듯 하다.
(사실 이건 강의에서 알려주는건 아니라서 몰랐는데 찾아보니 stackoverflow에서 꽤 활발히 이야기가 얘기되었던 주제로 보였다)
밸런싱이란 트리 구조에서 어떤 데이터의 삽입이나 삭제가 일어났을 경우 다음 데이터를 인출하거나 트리를 순회할 때 좀 더 효율적으로 할 수 있고, 메모리 관리도 유용하게 하도록 관리하는 일을 의미한다. 이런 밸런싱도 방법이 각양각색이라 밸런싱 방법을 여러방면으로 구현한 다양한 트리 구조가 있다.
4-2. 이진탐색트리
- 이진 탐색트리는 이진트리인데 자료의 order가 정해진 트리이다. 이진탐색트리는 중앙 노드의 값을 기준으로 그 값보다 작은 값은 왼쪽, 더 큰 값은 오른쪽에 저장한다. 그래서 가장 왼쪽 잎노드는 가장 작은 값이 저장되고 오른쪽 잎노드는 가장 큰 값이 저장되어 있다.
이미 정렬이 된 상태이므로 보통의 이진트리보다도 빠른 자료 탐색이 가능하다.
5. 힙
- 힙 역시 이진트리를 구현한 자료구조이다. 이진탐색트리가 전체 트리를 놓고 봤을 때 레벨에 상관 없이 좌->우 방향으로 값이 오름차순 정렬되는 자료구조라면 힙은 위->아래로 order가 정해지는 자료구조이다. 이 때 order는 오름차순일수도, 내림차순일수도 있다.
형제노드끼리는 딱히 비교하지 않는다. 그냥 부모노드와 자식노드만이 서로 비교된다.
힙으로 인해 얻을 수 있는 장점은 값의 비교가 굉장히 빠르다는 것이다. 큐의 Front 포인터처럼, 힙에서 다음 인출할 값을 가리키는 포인터는 루트노드이다. 루트노드에서 값을 인출하고나면 원래 루트노드가 차지하던 자리를 메꿀 다른 노드가 올라와야 하는데 힙은 다음에 올릴 노드를 선정하는데 소요되는 비교 횟수가 굉장히 적다.
새로운 값을 추가할 때도 기존의 값들과의 비교횟수가 적을수록 빠르게 삽입이 가능한데 힙은 노드의 전체 갯수가 늘어날 때 처음에는 트리의 레벨이 빠르게 높아지지만, 한 레벨에 2**n개의 노드가 존재하기 때문에 노드가 많이 늘어날수록 레벨은 급격하게 늘어나지 않게 된다. 힙은 삽입을 할 때 트리가 가진 레벨만큼 비교 연산이 일어나서 노드가 많아지더라도 값이 급격하게 증가하진 않게 된다.
1. 배열
- 여기서 말하는 배열이란 순수한 동적크기의 배열이다. 배열의 모든 원소들은 메모리에 다닥다닥 붙어서 올라간다. 어렵게 이야기 하자면, 메모리에 적재되는 물리적인 위치가 연속적이다 라고 하는 것이다. 이는 공간적 지역성의 원리라고도 한다.
공간적 지역성이란 방금 접근한 메모리 주소에 또 접근할 가능성이 높고 그에 인접한 원소들도 접근할 가능성도 높음을 의미한다.
배열의 공간적 지역성은 탐색을 할 때 그 빛을 발한다.
배열 a=[1,2,3,4,5]를 저장한다고 하면 a의 각 원소들은 모두 메모리 주소에 차곡차곡 순서대로 저장된다. 따라서 배열에 있는 값들은 순회하며 꺼내려 한다면 처음 1을 찾은 메모리 주소에서부터 더 멀리 찾을 필요도 없이 순서대로 꺼내기만 하면 되므로 탐색이 쉽다.
하지만 단점은 데이터의 삽입과 삭제가 일어날 때이다. 만약 배열에 원소를 5개 넣고 싶고 각 원소는 메모리 주소를 1칸씩 차지하면, 우리는 최소한 메모리가 5칸이 되는 곳을 찾아서 그곳에 저장해야한다. 메모리 중간중간에 3칸, 4칸이 비어있어도 이를 활용할 수가 없다는 단점이 있다.
또한 이미 원소가 4개인 배열이 있을때 이 배열의 중간에 값을 추가하고 싶다면 이를 위해 배열 전체를 다른 메모리주소로 옮겨야한다. 그렇지 않으면 배열의 특징인 공간적 지역성이 유효하지 않기 때문이다. 이 때문에 배열에 값이 많아질수록 삽입과 삭제는 부담스러운 연산이 되며 성능 또한 좋지 않게 된다.
2. 연결리스트
- 배열과 가장 잘 비교 되는 자료구조일 것이다. (사실 배열과 연결리스트는 어느 자료구조 커리큘럼이나 가장 초반부에 설명하고 있기 때문에 꽤 많이 봐와서 방통대 강의보다는 그 내용을 바탕으로 이 글을 쓰게 되는게 아닌가 싶다.)
연결리스트는 배열과 달리, 원소들이 메모리에 적재되는 물리적인 위치가 논리적인 위치와 다르다. 메모리의 주소에 산재되어 있는 것이다. 그렇다면 배열은 어떻게 원소의 논리적인 순서를 유지하고 있을까?(=배열의 원소들의 순서를 어떻게 알고있을까?)
리스트에 저장 된 원소는 자신이 가지고 있어야 하는 데이터 외에 다음에 가리킬 데이터의 주소도 가지고 있다. 리스트에는 값이 들어가는 것이 아니다. 노드라는 것이 들어가며 노드는<값, 다음노드 주소>의 쌍으로 이루어져 있다.
덕분에 리스트를 순회하며 값을 가져올 때 첫번째 노드의 값을 꺼내어 쓰고, 두번째노드는 첫번째 노드의 다음노드주소를 이용하여 다음 노드로 이동하게 된다.
2-1. 원형연결리스트
- 원형연결리스트는 연결리스트의 속성을 상속받는데 마지막 노드가 Head를 가리키도록 하여 순환하는 방식으로 만든 리스트이다. 원래의 연결리스트는 선형이다.
마지막 노드는 다음 노드가 없으므로 노드의 다음노드 주소 포인터가 null을 가리키지만, 원형 연결리스트는 마지막 노드가 다음노드 주소 포인터로 Head(가장 처음에 있는 노드)를 가리키게 되는것이다.
마지막 노드의 포인터를 좀 더 의미있게 사용하자는 취지에서 나온 자료구조이다.
3. 스택
- 스택은 흔히 큐와 같이 비교가 잘 되는 자료구조이며 비유는 늘 쌓아놓은 접시로 되는 것 같다. 스택은 별 다른 것이 없이 그냥 후입선출을 시켜줄 수 있는 자료구조라고 생각하면 된다. (기본적인 자료구조이기 때문에 배열이나 연결리스트처럼 설명을 덧대는 것은 의미없을거라 생각한다.)
개인적인 소득이 있다면, 이번 학기 컴퓨터구조와 프로그래밍 언어론 수업을 들으면서 실제 스택이 활용되는 모양새를 좀 알 수 있었던 것 같다. 컴퓨터 구조에서는 프로그램이 누산기를 사용할 때 스택 자료구조를 사용한다는 것을 알 수 있었고 프로그래밍 언어론에서는 함수들의 호출관계가 스택프레임으로 이루어져 있다는 것을 알 수 있었다.
자세한 설명은 각 과목의 후기에서 남기도록 하고, 스택은 별로 큰 특징이나 기존에 알던 내용에서 크게 더해진 것이 없어 여기서 pass해도 될 것 같다.
4. 트리
- 어떻게 보면 본 강의를 통해 배운 가장 큰 것이 있다면 트리라고 할 수 있겠다. 트리는 이미 뉴비일 때부터 많이 들어 온 자료구조이지만 명확한 의미와 개념을 모르고 있었다. 하지만 이번 강의를 통해 트리가 무엇이고 트리를 활용한 다양한 자료구조는 무엇이 있는지 알 수 있었던 것 같다. (사실 트리를 수업한 뒤로 나오는 거의 모든 자료구조는 이 트리를 Base로 하는 자료구조들이며 교수님 또한 트리를 구현하기 쉽고 성능 또한 좋은 자료구조라고 말씀하셨다.)
트리는 논리적 계층이 있는 자료형태이다. 트리의 장점은 검색이 빠르고 구현이 쉽다는 것에 있다. 구체적인 사항은 트리를 구현하여 새로운 속성을 가진 트리들을 보자.
4-1. 이진트리
- 아마 트리들 중 가장 유명한 트리이지 않을까 싶다. 이진트리란 노드의 진출차수가 최대 2인 트리를 의미한다. 쉽게 이야기 하면 한 노드가 가질 수 있는 최대 자식 노드의 갯수가 2개라는 것이다.
노드의 갯수가 2개인 덕분에 한 노드가 많은 자식노드를 담고 이를 탐색하는데 오래 걸리는 불상사가 없다. 다만, 메모리 공간을 비효율적으로 관리하게 될 수 있는데 다음과 같은 경우가 그 예이다.
루트노드가 0이고 자식노드 1, 2가 있다. 그리고 그 자식노드들은 또 자식노드들을 가져서 데이터는 총 0~6까지의 노드가 있다고 하자. 잎노드들은 3, 4, 5, 6이 되는데 이 때 4와 5가 삭제가 되었다면 트리의 최말단 왼쪽 노드는 3, 외말단 우측 노드는 6이 된다. 하지만 중간은 뻥 비어버리는 경우가 생긴다.
이진트리에서도 위와 같은 상황은 발생할 수 있고 이진트리가 아닌 일반 트리는 이와같은 현상이 더 심하게 일어날 수 있다 (노드의 진출차수가 2보다 클 수 있으므로)
따라서 이를 해결하고자 트리에서는 '밸런싱'이라는 것이 중요하게 작용하는듯 하다.
(사실 이건 강의에서 알려주는건 아니라서 몰랐는데 찾아보니 stackoverflow에서 꽤 활발히 이야기가 얘기되었던 주제로 보였다)
밸런싱이란 트리 구조에서 어떤 데이터의 삽입이나 삭제가 일어났을 경우 다음 데이터를 인출하거나 트리를 순회할 때 좀 더 효율적으로 할 수 있고, 메모리 관리도 유용하게 하도록 관리하는 일을 의미한다. 이런 밸런싱도 방법이 각양각색이라 밸런싱 방법을 여러방면으로 구현한 다양한 트리 구조가 있다.
4-2. 이진탐색트리
- 이진 탐색트리는 이진트리인데 자료의 order가 정해진 트리이다. 이진탐색트리는 중앙 노드의 값을 기준으로 그 값보다 작은 값은 왼쪽, 더 큰 값은 오른쪽에 저장한다. 그래서 가장 왼쪽 잎노드는 가장 작은 값이 저장되고 오른쪽 잎노드는 가장 큰 값이 저장되어 있다.
이미 정렬이 된 상태이므로 보통의 이진트리보다도 빠른 자료 탐색이 가능하다.
5. 힙
- 힙 역시 이진트리를 구현한 자료구조이다. 이진탐색트리가 전체 트리를 놓고 봤을 때 레벨에 상관 없이 좌->우 방향으로 값이 오름차순 정렬되는 자료구조라면 힙은 위->아래로 order가 정해지는 자료구조이다. 이 때 order는 오름차순일수도, 내림차순일수도 있다.
형제노드끼리는 딱히 비교하지 않는다. 그냥 부모노드와 자식노드만이 서로 비교된다.
힙으로 인해 얻을 수 있는 장점은 값의 비교가 굉장히 빠르다는 것이다. 큐의 Front 포인터처럼, 힙에서 다음 인출할 값을 가리키는 포인터는 루트노드이다. 루트노드에서 값을 인출하고나면 원래 루트노드가 차지하던 자리를 메꿀 다른 노드가 올라와야 하는데 힙은 다음에 올릴 노드를 선정하는데 소요되는 비교 횟수가 굉장히 적다.
새로운 값을 추가할 때도 기존의 값들과의 비교횟수가 적을수록 빠르게 삽입이 가능한데 힙은 노드의 전체 갯수가 늘어날 때 처음에는 트리의 레벨이 빠르게 높아지지만, 한 레벨에 2**n개의 노드가 존재하기 때문에 노드가 많이 늘어날수록 레벨은 급격하게 늘어나지 않게 된다. 힙은 삽입을 할 때 트리가 가진 레벨만큼 비교 연산이 일어나서 노드가 많아지더라도 값이 급격하게 증가하진 않게 된다.
댓글
댓글 쓰기