자료구조(Data Structure)는 컴퓨터가 데이터를 효율적으로 다룰 수 있게 도와주는 데이터 보관 방법과 데이터에 관한 연산의 총체를 뜻합니다. 『이것이 자료구조 + 알고리즘이다 with C언어』
자료구조의 정의를 『이것이 자료구조 + 알고리즘이다 with C언어』 라는 책에서 따온 내용이다.
또는 위키피디아에서 따온 '자료구조(資料構造, 영어: data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.' 라는 설명이 오히려 더 와닿을지도 모르겠다.
더 간단하게 말하면 컴퓨터가 자료를 저장하는 방식이라고 생각하면 편할것 같다.(비전공자 개인적인 견해입니다 😗)
( 이미지 출처 : https://m.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS8073601837)
파이썬이나 c++ 등 주로 대부분이 사용하는 프로그래밍 언어에서는 기본적으로 다양한 데이터타입을 기본적으로 제공하고 있으며, 필요에따라 쉽게 사용할 수 있는 구조로 되어있다. 파이썬의 경우 str, list, dict, tuple(순서쌍), set 등이 있으며 이를 활용하면 웬만한 문제들에 대해서 쉽게 해결이 가능하다.
그러면 도데체 왜 우리는 '자료구조' 에 대해 굳이 더 알아보고 배워봐야 될까? 이유는 크게 두가지이다.
- 기본제공 데이터 타입으로는 해결 불가능한 경우 역시 존재함
- 필요에 따라 적절한 자료구조를 선택할 줄 알아야 함 (그러기 위해선 자료구조에 대한 이해가 필요하다)
본 포스팅에서는, '프로그래머스 AI 데브코스' 를 통해 배운 여러 자료구조에 대한 설명을 바탕으로 복잡한 내용을 간추려 간단하게 정리해 보고자 한다.
1. 배열 ( Array )
> 선형 배열 (linear array)
기본적으로 파이썬에서 제공하는 리스트로 생각하면 되는데, 이는 다른 언어와는 조금 다른 파이썬의 특이한 배열구조로 볼 수 있다. (참고)
리스트의 연산에는 O(1)의 일정한 복잡도를 갖는 연산과, 원소의 길이에 비례해 처리속도가 느려지는 연산을 생각해 볼 수 있는데, 일정한 복잡도를 갖는 연산의 예로 리스트 끝에 원소 덭붙이기(list_.append()), 원소 끝에서부터 꺼내기(list_.pop()) 가 있고, 원소의 길이에 비례해 처리속도가 느려지는 연산으로는 리스트 중간에 원소 끼워넣기(list_.insert(index, num)), 리스트 중간 원소 삭제(del(list_[index])), 원소정렬(list_.sort()) 등이 있다.
원소정렬에는 내장함수 sorted(list, 옵션~~) 를 통한 정렬이 있을 수 있고, 메서드 list_.sort() 두가지 방식이 있는데, 내장함수의 경우 단순히 정렬결과를 출력해 줄 뿐 원본데이터의 순서가 바뀌지 않는 반면 메서드의 경우 원본이 실제로 정렬순서대로 위치가 바뀌는 걸 볼 수 있다.
+) TMI
정렬의 방식과 시간복잡도에 대해 자세히 알고싶다면 이곳(링크) 를 살펴보길 바란다. 파이썬 기본 정렬의 경우에 병합정렬과 삽입정렬을 섞은 알고리즘으로 시간복잡도는 O(NlogN)이라고 한다. 참고로, 원소끼리의 대소비교를 통한 정렬방식을 사용할 경우 시간복잡도는 O(NlogN) 보다 빠른 방식의 알고리즘은 존재할 수 없다. 그러나, 직접비교를 하지 않는 더 빠른 정렬속도를 내는 몇몇 알고리즘들도 존재하긴 한다.
다음으로 원소탐색에 있어서도 크게 두가지의 방식이 존재하는데 리스트 원소를 순서대로 하나하나 꺼내 보면서 일치하는 원소를 찾으면 그 인덱스를 반환하는 선형탐색과, 크기순으로 정렬된 리스트에 매 중심의 값을 기준으로 찾는값과 대소관계를 비교해보면서 반씩 버려가며 탐색(업앤다운 게임과 같이)하는 이진탐색 방법이 존재한다.
2. 연결리스트 ( Linked-List )
연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. (위키)
연결리스트의 경우에는 자료를 저장하는 매개체인 노드에 자료의 값(number) 과 다음 자료의 위치를 가르키는 포인터 두가지를 저장해 둔다. 그럼 1번 자료(가장 처음 노드를 head 라고 하자) 는 자기 값과 2번자료의 위치를, 1번자료를 통해 찾아간 2번 자료에는 2번 자료의 값과 3번자료의 위치를 가지고 있는 셈이다.
쉽게 생각해보면 이런 기차놀이를 떠올릴 수 있다. 기차놀이의 각 개인은 기차놀이에 어떤 사람들이 참여하고 있는지 모르지만 자신 앞에 누구를 잡고 있는지는 분명히 알고 있다. 그러면 맨 뒷사람부터 차근차근 앞사람을 따라가다 보면 기차놀이에 참여한 모든 사람을 확인할 수 있는 것이다.
연결리스트 자체는 사실 구현하기도 어렵고, 그렇다고 자료 탐색이나 삽입이 일반 리스트보다 빠르지도 않다. 그럼에도 불구하고 이런 자료구조를 사용하는 이유도 몇가지 존재하는데 이는 다음과 같다.
- 삽입과 삭제가 유연하다
- 삽입 : 삽입하려는 위치의 전 노드가 기존 노드 대신 삽입하려는 노드를 가리키도록 수정하고, 새로 삽입하는 노드를 원래 그 위치에 있던 노드를 가리키도록 하면 된다. 즉 한번의 포인터 수정으로 삽입가능. 즉 기차놀이에서 한명만 팔을 끊어주면 그 사이로 한명이 들어갈 수 있다.
- 삭제 : 삭제하려는 위치의 전 노드의 포인터를 삭제하려는 위치의 다음 노드를 가르키도록 하면 된다. 즉 한번의 포인터 수정으로 삭제가능, 즉 기차놀이에서 한명을 밀어내버리고 뒷사람이 그대로 앞사람을 잡도록 하면 된다.
- 두 리스트이 연결이 매우 쉽다.
- 그냥 앞의 맨 마지막 노드의 포인터가 원래는 없으므로 None 이나, 이를 뒤에 이을 연결리스트로 연결하려면 그냥 그 포인터를 뒤이을 연결리스트의 헤드에 연결해 주기만 하면 된다.
기본적인 코드 구성은 아래와 같고, 여기서 class 내에 각 연산기능(삽입, 삭제, 순회, 정렬) 등을 구현해주면 자료구조가 완성된다.
class Node :
def __init__(self, item):
self.data = item
self.next = None
class LinkedList :
def __init__(self) :
self.nodecount = 0 # 노드 갯수, 초기 노드 0개
self.head = None # 헤더, 초기헤더 없음
self.tail = None # 가장 끝 노드도 기억해둠, 초기테일 없음
++ )
한편 head와 tail의 경우 가리킬 다음 노드가 없어 특정 예외조건을 둬야 한다는 점을 개선하기 위한 더미노드를 추가한 연결리스트 방식이 있고, 다음 원소를 찾아갈 순 있으나 이전 원소를 찾는건 불가능한 기존의 문제를 개선하기 위해 이전 노드를 가리키는 포인터를 추가로 가지고 있는 양방향 연결 리스트 역시 존재하는데 이는 나중에 기회가 되면 따로 다뤄보려고 한다.