자료구조란 무엇일까?
자료구조란 컴퓨터 과학에서 데이터를 다룰 때 접근과 수정을 조금 더 효과적으로 할 수 있는 함수 혹은 명령을 뜻한다.
또는 특정 모양 자체를 자료구조라고도 부른다.
신입 면접을 보다보면, 자료구조를 물어보는 경우가 많은데 이것을 실제로 활용할까?
이것에 대한 답은 상황마다 다르다. 라고 답을 할 수 있을 것 같다.
개인적인 생각으로 자료구조가 필요하려면 다루는 데이터의 양이 중요하다.
크지 않다면 정말 막굴려도 모자름을 느끼지 못할 수 있는데 데이터가 점점 많아지면 아, 정말 필요하구나 라고 생각이 든다.
그래서 결론만 말을 하면 무조건 알고 있어야한다.
어떤 문제던 풀이방법 자체만 알고있더라도 접근을 빠르게 할 수 있다.
그렇기 때문에 다양한 풀이에 속하는 자료구조(세부로는 알고리즘)을 알고 있어야하고
대표적인 것들로 어떤 것들이 있는지, 어떻게 구현하는지 예시를 들면 어떤 곳에서 사용하는지만 알고 있다면 충분하다고 한다.
어제 자료구조로 고민하고 있더니 대답해준 친형 아니 근데 어떻게 구현하는지 다알면 마스터아닌가
또한 자료구조라는 것이 특정 프로그래밍 언어에 국한되어있는 것이 아니라 어디서든 적용을 할 수 있기 때문에
컴퓨터공학에서도 전공필수에 들어가있는 과목이기도 하다.
그럼 한개씩 알아가보자...
시간복잡도?
그 전에 시간복잡도라는 말을 한번 확인하고 가야한다.
시간복잡도는 말그대로 얼마나 시간이 걸리느냐? 를 표현하는 방식이며 어떤 자료구조를 사용하는가?를 선택할 때 정말 중요하다.
여기서 시간복잡도는 실질적인 시간을 알려주는 것이라고 보긴 힘들고, 몇번의 과정이 필요하냐? 라는 식으로 계산을 한다.
보통 사용하는 표기법은 빅-오 표기법이라고 O(n) O(N^2) 이런식으로 많이 사용한다.
조금 더 상세한 내용은 개발공부를 할 때 정말 도움을 많이 받는 노마드 코더 니코쌤의 유투브로 확인하자.
https://www.youtube.com/watch?v=BEVnxbxBqi8&list=PL7jH19IHhOLMdHvl3KBfFI70r9P0lkJwL&index=4
선형 자료 구조
자료구조에는 두가지의 유형이 존재한다.
- 데이터를 한줄로 나열할 수 있는 선형 자료구조
- 한줄로 나열 할 수 없는 비선형 자료구조
먼저 알아볼 것은 선형 자료구조다.
연결 리스트(Linked List)
연결리스트는 데이터의 일부를 포인터로 연결한 자료구조다.
서로 연결되어있는 것이 특징이고 블록체인에서 사용하는 자료구조로 알고 있다.
데이터를 추가하거나 삭제를 하는 것은 직접적으로 접근을 할 수 있기에 O(1)의 복잡도를 가지고 있지만,
탐색같은 경우에는 모든 것을 다 훑어봐야해서 O(n)의 시간복잡도를 가지고 있다.
연결리스트에는 3가지가 존재하는데
- 싱글 연결 리스트
- Next 포인터만 가지고 있다.
- 이중 연결 리스트
- Next 포인터와 Prev 포인터를 가지고 있다.
- 원형 이중 연결 리스트
- 이중 연결 리스트와 동일하지만, 마지막 노드의 Next 포인터가 헤더의 노드를 가리킨다.
싱글 연결 리스트
이중 연결 리스트
원형 이중 연결 리스트
배열 (Array)
배열은 프로그래밍 언어를 공부해본 사람이라면 모두가 알고 있는 자료구조다.
데이터를 순차적으로 저장한다는 구조를 가지고 있으며, 데이터의 순서는 Index라는 것으로 확인을 할 수 있다.
인덱스는 0부터 시작하는 특이한 성질을 가지고 있는데, 이러한 이유는 맨 하단 참고자료에 넣어놨다.
배열은 순서를 보장해줘야만 하는 형태의 데이터를 저장할 때 사용하면 좋은 자료구조다.
인덱스로 해당하는 값을 접근할 수 있기에, 접근 자체는 O(1)의 시간 복잡도를 가지고 있지만
해당 값에 접근하기 전까지는 값을 알 수 없다는 특징이 존재하기 때문에 추가와 삭제는 O(n)의 시간 복잡도를 가지고 있다.
스택 (Stack)
정말 많이 등장하는 스택은 나중에 들어간 원소가 제일 먼저 나오는 구조를 가지고 있다.
흔히 LIFO라고 부르길래 도대체 뭔가 찾아봤더니 Last In First Out.... 약자였다..^^
보통 배열로 구현을 많이 하는 편인데 웹 브라우저 방문기록에서 많이 사용한다.
그것은 바로 뒤로가기에서 사용한다.
어디를 눌러서 계속 이동을 하더라도, 뒤로가기를 누르면 제일 최근에 방문했던 페이지로 넘어가는데
이것이 바로 스택을 사용한 대표적인 예라고 볼 수 있다.
큐 (Queue)
스택과 비슷하여 많이 헷갈리는 자료구조로 먼저 넣은 원소가 먼저 나오는 구조를 가지고 있다.
FIFO, First In First Out 이라고도 많이 부른다.
보통 네트워크 접속 대기열같은 것을 구현하는 경우에 사용하는 자료구조다.
큐 또한 배열로 구현을 하며 스택과 동일하게 추가 및 삭제는 O(1)의 시간 복잡도와 탐색에는 O(n)시간 복잡도를 가지고 있다.
해시 테이블 (Hash Table)
나는 지금까지 해시테이블이 특별한 자료구조라고 생각했는데 그게 아니였다.
자바스크립트에서의 오브젝트, 파이썬에서의 사전이 자료구조였다...(하하하...)
Key와 Value로 데이터를 저장하는 자료구조로, 제일 빠르게 데이터를 검색할 수 있는 자료구조다.
결국은 키라는 것이 해시함수를 사용하여 고유한 배열의 인덱스를 생성해 데이터를 저장하는 것이다.
하지만 배열과는 또 다른 개념으로 데이터가 저장되기 때문에
접근도, 추가도, 생성도 O(1)의 시간복잡도를 가지고 있다.
일.반.적.으.로
해시함수라는 것은 일단 언어상에서 알아서 지원을 해주는데, 이러는 와중에도 인덱스가 중복되는 경우가 발생할 수 있다.
여기서 해시함수는 들어오는 값을 고유한 값으로 만들어주는 함수를 이야기한다.
인덱스가 중복이 될 경우, 일반적으로는 버켓에 데이터가 추가로 입력이 되기 때문에
O(n)의 시간복잡도를 가질 수 있지만, 일반적으로는 O(1)이라고 이야기를 한다.
비선형 자료구조
비선형 자료구조는 데이터를 한 줄로 나열할 수 없는 경우에 사용하는 자료구조다.
개인적으로 비선형 자료구조가 정말 중요하다고 생각한다.
왜냐하면 얘가 정말 수많은 알고리즘 문제에 나온다(....)
비선형 자료구조가 정렬이나 검색 인덱스(DB) 최단거리 경우의수 같은 알고리즘을 풀 때 사용되는 자료구조로
자료구조 수업 조교를 하던 친형의 피셜로는 트리만 해도 수없이 많다고(....) 이야기를 해줬다.
보통 코딩테스트에 BFS DP라고 불리는 특정 알고리즘을 요구하는 문제들이 바로 비선형 자료구조에 대한 지식이 있어야 풀 수 있다.
그리고 저러한 알고리즘을 요구하는 것은 보통 3레벨인데, 저런 문제들이 대부분의 신입 코딩테스트의 문제로 출제된다.
결국 자료구조를 모르고 있다면 코딩테스트를 통과할 수 없다는 의미다.
그래프 (Graph)
그래프는 정점과 간선으로 이루어진 자료구조로 순환이 되는 것이 핵심인 자료구조다.
비선형 자료구조에 대해서는 공부를 해본 것이 많이 없어서 링크로 대체를 해야할 것 같다;
[Algorithm] 자료구조 그래프(Graph)란 무엇인가?
트리 (Tree)
트리는 그래프를 기반으로 방향성이 존재하는 비순환 자료구조 중 하나이다.
트리는 백엔드개발자라면 모르면 안되는 자료구조 중 하나인데(...) 수도없이 많이 쓰이고
일단 RDBMS에서 인덱스의 알고리즘이 B+Tree라는 것으로 되어있다는 것은 알고 있다.
하지만? 자세하게 다뤄본 적은 없어서 이것도 공부를 해봐야한다. . . . ..
아래 그림처럼 방향이 존재하고 순환하지 못하는 구조를 가지고 있다.
그 자료구조를 조금 더 딮하게 공부하면서 알고리즘에 대해서도 좀 찾아봐야겠다.
B Tree라던가 블랙레드트리 이런게 엄청 중요하다고 형이 알려주는데....
알..고ㄹ..ㅈ...ㅁ....
참고 & 보면 좋은 자료
그래프 2) 방향 그래프, 무방향 그래프, 가중치 방향그래프 정리
0부터 시작하는 이유와 마지막 수를 인덱스로 포함하지 않는 이유
노마드코더 - 알고리즘. 데이터구조 with Nico
코드 진행되는 것 시각화
알고리즘 - 자료구조(1) 스택, 큐
그림 : 모두 draw.io로 직접 다 그렸음(....)
