지각에세이_이현진

지각에세이_이현진.pdf

0.25MB

 

 우리는 자료 구조를 왜 알아야 할까? 이 물음은 파이썬을 배우면서 시작되었다. 파이썬과 관련된 다양한 문제를 풀면서 가장 적절한 문제 해결 방안을 위해 그 문제에 걸맞는 자료 구조를 사용해야 더 간결하고 효율적으로 문제를 풀 수 있다는 것을 깨달았기 때문이다.

 

이처럼 자료 구조는 개발자가 데이터를 효율적으로 사용할 수 있도록 정리하는 방법을 말한다. 각각의 자료 구조에는 장단점이 있어 어떤 자료 구조가 최선일지는 해결하고자 하는 문제의 종류와 어떤 부분을 우선적으로 최적화할지에 따라 달라질 수 있다. 프로그래밍이란 결국 알고리즘을 작성하고, 그에 맞는 자료 구조를 선택하는 것이므로 자료 구조를 충분히 이해하지 못한다면 결코 좋은 개발자가 될 수 없다. 파스칼을 개발한 스위스의 컴퓨터 과학자 니클라우스 비르트는 ‘알고리즘 + 자료구조 = 프로그램’이라는 유명한 말을 남기기도 했는데, 이처럼 자료 구조는 개발자에게 있어 중요한 요소이다. 따라서 자료 구조에 대해 알아보고자 한다.

 

알고리즘

자료 구조를 알기 이전에 자료 구조를 선택하는 데에 있어 가장 중요한 알고리즘에 대해 먼저 알아볼 것이다.

 

알고리즘이란 어떤 문제를 해결하기 위해 밟아야 하는 연속적인 단계를 말한다. 알고리즘에서 중요한 세 가지 요소는 다음과 같다.

 

각 단계가 간결하며 모호하지 않아야 하는 명확함.

각 동작이 문제 해결에 기여하는 효율성.

알고리즘이 유한한 단계를 거친 후 종료된다는 뜻인 유한함. 이 있다.

 

최선의 알고리즘을 찾기 위해 가장 중요한 요소는 실행 시간이다. 즉, n(데이터의 양)이 커질 때 알고리즘의 단계가 얼마나 증가하는지를 보는 것이다. 이를 잘 나타내는 표기법은 빅 O 표기법이다. 빅 O 표기법이란, n이 커짐에 따라 알고리즘의 시간 또는 공간의 요건이 얼마나 커지는지를 나타내는 수학적 표기법을 말한다.

다음은 빅 O 표기법에서 가장 널리 사용되는 규모의 함수들을 최선(가장 효율적)에서 최악(가장 비효율적)의 순서로 나열한 것이다.

왼쪽부터 차례대로 O(1), O(log n), O(n), O(n log n), O(n**2), O(n**3), O(c**n) 으로 표기한다.

 

2. 자료 구조

앞에서 말했듯 자료 구조란 개발자가 데이터를 효율적으로 사용할 수 있도록 정리하는 방법을 말한다. 컴퓨터에 자료 구조를 어떻게 저장할지 지시한다는 것이다.

자료 구조는 추상 데이터 타입으로 크게 선형 자료 구조와 비선형 자료 구조로 나눌 수 있다.

 

가. 선형 자료 구조

선형 자료 구조란 하나의 자료 뒤에 하나의 자료만 오는 자료 구조로 데이터를 순서대로 정렬한다. 예를 들어 파이썬의 리스트는 각 요소의 앞과 뒤에 다른 요소가 있어 선형 자료 구조이다. 선형 자료 구조에도 다양한 방식이 존재한다.

 

(1). 배열

배열은 연속적인 메모리 블록에 인덱스와 함께 요소를 저장하는 자료 구조이다. 하지만 동질적 자료 구조로 정수나 문자열과 같이 한 가지의 데이터 타입만 담을 수 있으며, 배열의 크기는 한번 정하면 크기를 변경할 수 없다.

 

배열 구조의 특징으로는 가장 간단한 자료 구조로 접근 속도가 빠르다.

하지만 표와 같이 탐색, 삽입, 삭제에 대한 시간 복잡도가 선형 시간을 따르는 것을 볼 수 있는데 이는 삽입, 삭제 등의 작업을 할 때 자료의 이동이 필요하기 때문에 작업이 번거로워져 시간 복잡도가 증가한다는 특징을 갖는다.

 

(2). 링크드(연결) 리스트

링크드 리스트의 요소는 연속적인 메모리 블록에 저장하지 않고, 임의의 기억 공간에 기억시키되, 자료항목의 순서에 따라 노드(데이터를 포함하여 다른 데이터와 연결될 수 있는 자료 구조의 일부분)의 포인터(노드에서 다음 노드의 위치를 가리키는 데이터) 부분을 이용하여 서로 연결시킨 자료 구조이다.

 

링크드 리스트에는 여러 타입이 존재하는데, 노드에 다음 여소를 가리키는 포인터만 있는 단일 링크드 리스트, 각 노드에 다음 요소를 가리키는 포인터와 이전 요소를 가리키는 포인터가 모두 있는 이중 링크드 리스트, 마지막으로 마지막 노드에 첫 번째 노드를 가리키는 포인터가 있어 마지막 요소에서 처음으로 돌아올 수 있는 환형 링크드 리스트가 있다.

배열에서는 하나의 위치 정보, 인덱스만 알고 있으면 어떤 요소에 접근하든 상수 시간을 따랐지만 링크드 리스트에서는 포인터를 찾아가는 시간이 필요하기 때문에 원하는 요소에 접근 속도가 느려 선형 시간을 따른다. 하지만 삽입, 삭제 작업이 용이하고, 기억 공간이 연속적으로 놓여 있지 않아도 저장이 가능하다는 장점을 있다.

 

(3). 스택

스택은 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출 구조로 저장되는 자료 구조를 말한다. 반드시 순서를 따라야 하기에 접근이 제한된 자료 구조이다.

 

스택은 푸시와 팝이라는 두 가지 동작이 존재하는데, 푸시는 스택에 요소를 추가하는 것이고, 팝은 스택에 마지막으로 추가한 요소를 꺼내는 것을 의미한다.

 

스택은 추가할 수 있는 요소의 수에 제한이 있는 스택인 제한된 스택과, 추가할 수 있는 요소의 수에 제한이 없는 무제한 스택으로 나눌 수 있다.

스택의 요의 푸시와 팝은 상수 시간을 따르기에 데이터를 추가하거나 제거할 때 효율적이지만, 스택의 전체에 접근해야 하는 동작에는 효율적이지 않다.

 

(4). 큐

컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어넣은 데이터가 먼저 나오는 선입선출 구조로 저장하는 형식을 말한다.

 

큐에는 인큐와 디큐라는 두 가지 기본 동작이 있다. 인큐는 요소를 큐에 추가하는 것을 의미하고, 디큐는 요소를 큐에서 제거하는 것을 의미한다. 즉, 인큐는 큐의 뒷부분에서 요소를 추가하고, 디큐는 큐의 앞부분에서 요소를 제거한다.

 

스택과 마찬가지로 큐는 두 가지 타입이 존재한다. 추가할 수 있는 요소의 수에 제한이 있는 제한적 큐와, 추가할 수 있는 요소의 수에 제한이 없는 무제한 큐가 있다. 제한적 큐는 배열을 사용하여 만들고, 무제한 큐는 링크드 리스트를 사용하여 만든다. 큐에 저장하는 요소의 개수를 추가하면 링크드 리스트로도 제한적 큐를 만들 수 있다.

큐도 스택과 마찬가지로 삽입과 삭제를 할 때 상수 시간 복잡도를 따르기 때문에 데이터를 효율적으로 추가하거나 제거할 수 있다. 인큐와 디큐는 모두 크기에 관계 없이 상수 시간을 따른다. 또한 특정 요소를 찾기 위해 요소 전체를 순회해야 하므로 선형 시간이 걸려 탐색이 비효율적이다.

 

(5). 해시 테이블

고유한 키와 값의 쌍을 저장하는 추상 데이터 타입인 연관 배열을 구현한 자료 구조로 연관 배열을 구현하는 많은 타입 중에 키-값 쌍 타입을 사용해 저장하는 선형 자료 구조이다. 여기서 키는 값을 가져올 때 사용하며 고유해야 하기에 중복된 키를 저장하지 못한다. 값은 키를 사용해 가져온 데이터를 의미한다.

 

해시 테이블에 값을 저장할 때 각 슬롯에 값을 저장한다. 하지만 추가한 데이터가 이미 데이터가 들어있는 슬롯을 가리킬 경우 충돌이 생기며 시간 복잡도가 증가한다. 이는 추가한 데이터는 비어 있는 다음 슬롯에 값을 저장하는데 추가한 데이터를 찾을 때까지 비어 있는 다음 슬롯을 확인해야 하기 때문이다. 따라서 해시 테이블을 만들 때는 충돌을 최소화하는 해시 함수를 만드는 것을 목표로 해야 한다.

해시 테이블의 데이터 탐색은 평균적으로 상수 시간을 따른다. 하지만 충돌이 발생하면 해시 테이블의 효율성이 떨어지며, 최악의 경우 탐색과 삽입, 삭제 작업이 선형 시간을 따를 수 있다. 해시 함수에 데이터를 전달해 구한 인덱스가 배열에 존재하는 지만 확인하면 해시 테이블에 데이터가 존재하는지 알 수 있기 때문에 거대한 데이터 세트를 저장할 때 가장 효율적인 자료 구조 중 하나이다. 하지만 n번째 요소에 접근하는 방법이 없다는 단점이 있지만 데이터의 탐색 효율이 가장 좋기 때문에 대량의 데이터가 있고 개별 데이터에 빠르게 접근해야 한다면 해시 테이블을 가장 먼저 고려한다.

 

나. 비선형 자료 구조

하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 형태를 말한다.

 

(1). 트리 자료 구조

기본 동작으로 삽입, 탐색, 삭제가 있다. 일반 트리 AVL 트리, 레드 블랙 트리, 이진 트리, 이진 탐색 트리 등 다양한 타입이 존재한다. 그중 일반 트리, 이진 트리, 이진 탐색 트리 타입에 대하여 알아보겠다.

 

1. 일반 트리 구조

하나의 노드를 두고 시작하는 자료 구조이다. 계층 구조로 노드를 연결하는 비선형 추상 데이터 타입이다.

2. 이진 트리

각각의 노드가 최대 두 개의 자식 노드(노드 아래로 연결된 노드)만 가질 수 있는 트리 자료 구조를 말한다. 나머지 요소는 일반 트리와 같으며 유일한 차이는 자식 노드 제한에 있다.

 

3. 이진 탐색 트리

이진 트리에서 업그레이드된 것으로 각각의 노드가 최대 두 개의 자식만 가질 수 있다는 것은 같지만, 각 노드의 값이 왼쪽에 있는 서브 트리의 어떤 값보다 작고, 오른쪽에 있는 서브 트리의 어떤 값보다 작도록 정렬하여 저장한다. 즉 왼쪽에 있는 자식 노드는 부모 노드(하나 이상의 자식 노드를 가진 노드)보다 작고, 오른쪽에 있는 자식 노드는 부모 노드보다 크다는 것이다.

노드의 삽입, 삭제, 탐색을 사용할 수 있으며, 모두 로그 시간을 따른다.

계층적 정보가 저장 가능하기 때문에 각 데이터 간의 관게를 알기 쉽게 표현할 수 있다.

 

트리 구조의 장점을 해시 테이블과 비교했을 때의 장점은 메모리 사용량과 데이터 이동의 용이성에 있다. 해시 테이블은 충돌로 인해 실제로 저장하는 데이터보다 열 배 이상의 공간을 사용할 경우가 존재하지만 이진 탐색 트리는 메모리를 낭비하지 않는다. 또한, 이진 탐색 트리는 데이터의 정렬된 순서나 역순으로 빠르게 이동할 수 있는 반면, 해시 테이블은 데이터를 순서대로 저장하지 않으므로 순서에 따라 이동하는 것이 불가능하다.

 

(2). 이진 힙

힙은 우선순위 큐를 표현하는 트리 자료 구조로, 각 노드에 값과 우선 순위가 함께 담긴다. 우선순위 큐는 각 데이터에 우선순위가 있는 자료 구조를 정의하는 추상 데이터 타입이다. 선입선출을 따르는 일반적인 큐와 달리 우선순위 큐는 우선순위에 따라 요소를 꺼낸다.

 

이진 힙은 이진 트리를 사용해 만든 힙으로 최대 힙과 최소 힙, 두 가지 타입이 존재한다. 최대 힙은 부모 노드의 우선순위가 항상 자식의 우선순위보다 크거나 같다는 특징이 있다. 이에 따라 우선순위가 가장 높은 노드가 루트 노드(부모 노드가 없는 노드)이다. 최소 힙은 부모 노드의 우선 순위가 항상 자식의 우선 순위보다 작거나 같다는 특징이 있다. 이에 따라 우선 순위가 가장 낮은 노드가 루트 노드이다.

 

우선순위에 따라 실행해야 하는 작업에 적합하다. 예를 들면, 운영 체제를 표현할 때 사용한다. 또한 그래프에서 두 노드의 최단 경로를 찾는 데이크스트라 알고리즘을 구현할 때 사용되며, 힙 정렬 알고리즘에 사용된다.

3. 자료 구조 실제 활용 예시

 

(상황)

100만 개의 고객 데이터를 최신으로 업데이트하기 위한 배치 작업 필요 

- 100만 개의 고객 데이터는 CSV로 제공

- CSV 데이터 중 기존 DB에 없는 고객은 추가

- CSV 데이터엔 고객 key 값이 없으므로 DB의 여러 필드를 대조해야 함

 

(구현)

100만 개 데이터를 매번 순회하여 고객을 찾은 후 업데이트, 없으면 추가

→  5일이 넘게 소요

 

(개선)

해시 테이블과 링크드 리스트를 이용하여 데이터 구조를 변경 후 이진 탐색 알고리즘 적용

→ 20분 만에 해결 

 

 

이처럼 자료 구조에는 정말 다양한 타입이 존재하고 이를 알면 실생활에서의 다양한 문제들을 간편하게 해결할 수 있다. 자료 구조와 알고리즘의 관계를 요리에 비유한 글이 있었는데, 이를 보면 더욱 쉽게 깨달을 수 있다.

 

 

개발자는 올바른 데이터와 자료 구조 그리고 알고리즘을 골라 소프트웨어를 만들 수 있다는 것이다. 나도 개발자와 비슷한 직종을 꿈꾸는 사람으로서 다양한 자료 구조를 학습하여 더 적절한 곳에 적합한 자료 구조를 사용할 수 있도록 공부할 것이다. 여기서 정리한 자료는 파이썬 스터디를 통해 알게 된 내용인 ‘알고리즘 + 자료 구조’ 책을 활용하여 작성했지만 이 책에 나오지 않은 부분을 추가로 학습할 것이다.

 

출처

책

나의 첫 알고리즘+자료구조 with 파이썬 ( 코리 알트호프 저/한선용 역 )

https://uuukpyo.tistory.com/3

[자료구조]선형 구조의 종류와 설명

 

http://esslab.hanyang.ac.kr/uploads/data_structure_2019_1/lecture_note/877d2a06709c0b1324e51afb6df31317/%5BDS-2%5D%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.pdf

 

https://prgms.tistory.com/134

자료구조와 알고리즘, 왜 중요할까?