글 원본 : https://blog.naver.com/tigerkey10/222401563122
이 글은 내가 지킬 블로그를 만들기 전,
네이버 블로그에 공부 내용을 기록할 때 학습하고 복습하면서 기록했던 글을 옮겨온 것이다.
네이버 블로그에서 글을 옮겨와 지킬 블로그에도 기록해둔다.
모든 공부 과정을 기록으로 남겨 치열했던 시간들을 기록으로 남기고,
미래에 전달해 스스로 동기부여할 것이다. 또한 반복해서 학습. 복습하는 과정에서
어떤 개념에 대한 내 이해가 어떻게 변화.발전 했는지 관찰함으로써 스스로의 학습 정도를 돌아보는 거울로 삼고자 한다.
자료구조란?
- 데이터를 저장. 조직하는 틀. 구조.
자료형
- 개별 데이터의 속성. 컴파일러에게 각 데이터 사용법, 속성 등을 알려준다.
자료 간 순서 여부로 구분한 자료구조
선형자료구조 :
각 자료가 순서 가지고 선형[직선 형태로] 나열된 자료구조를 말한다
- 하나의 데이터 뒤에는 하나의 데이터만 올 수 있다.
- 데이터-데이터 간 1:1 선형관계 갖는다.
- 예 : 시퀀스 자료구조, 스택 자료구조, 큐 자료구조 등
비선형 자료구조 :
자료들이 일렬로 나열되어 있지 않는 자료구조
- 순서 부여 불가능
- 하나의 데이터 뒤에는 여러 데이터가 올 수 있다.
- 데이터-데이터 간 1:N, N:N 관계 갖는다.
- 예 : 트리. 그래프. 맵. 집합 자료구조 등
추상자료형
핵심 : ‘속성’과 ‘연산’으로 구성되어 있다.
- 마치 객체지향프로그래밍에서의 클래스와 개념 상 비슷하다.
- 연산은 “어떠한 연산이 가능하다~”만 정의할 뿐, 구체적인 연산 구현방법은 정의하지 않는다. (구체적인 구현 방법이 나와있지 않은 메소드와 비슷하다) 각 자료구조를 추상자료형으로 먼저 정의한 뒤, 세부적인 구현 방식을 선택한다. 예컨대 ‘리스트’ 자료구조가 있다고 하면, 리스트의 추상자료형을 먼저 정의한다. 순서. 인덱스를 가지고 있는 자료구조다. (속성) 리스트 마지막에 항목을 하나씩 추가할 수 있다(append 연산) 리스트에서 구체적인 항목을 특정해서 제거한다(remove 연산) 등등 … 그 후 위 추상자료형을 바탕으로 각 연산을 실제로 구현한다. 리스트 자료구조의 경우, 구현 방법으로 ‘배열’을 사용하거나 ‘연결리스트’ 를 사용해서 각 연산 구현이 가능할 것이다.
# 추상자료형
class stack :
def isEmpty(self) # 스택은 스택이 비어있는지 확인할 수 있다.
def push(self, item) # 스택은 스택에 새 자료를 넣을 수 있다.
def pop(self) # 스택은 가장 최근 항목을 빼서 보여주고, 제거할 수 있다.
.....
- 예컨대 ‘스택’의 추상 자료형은 위 처럼 정의할 수 있다. 이제 위 추상 자료형의 각 연산을 구체적으로 구현하고, 이 클래스로 스택 객체를 생성하면 결과물은 ‘스택’ 자료구조이다.
# 배열 리스트 사용해서 스택 구현
class stack :
def isEmpty(self) :
return self.items == []
def push(self, item) :
self.items.append(item)
def pop(self) :
if not isEmpty() :
return self.items.pop()
......
스택 자료구조 객체 생성완료.
stack = stack()
-
결과물은 클래스로 만든 객체와 같을 것이다.
-
내부 구현 방법이 바뀌어도 추상자료형이 그대로면 사용자는 구현 방법이 바뀌었다는 사실을 모를 것이다. 이렇게 사용자에게 변경 내용을 숨기는 것을 ‘정보은닉’ 이라고 한다.
추상자료구조
-
추상자료형에 더해 각 연산의 시간 복잡도까지 정의하면 추상자료구조라고 한다.
-
추상자료형과 마찬가지로, 각 연산의 실제 구현 방법은 정의하지 않는다.
자료구조
- 추상자료형에서 각 연산을 실제로 어떻게 구현할 것인지 명시하면 그때부터 자료구조의 영역이 된다.
시퀀스 자료구조
‘순서가 있는 나열’
아래 특징이 있는 자료구조를 ‘시퀀스 자료구조’라고 한다.
-
데이터를 하나씩 나열하고, 순서를 부여한 자료구조
-
특정 위치의 데이터를 인덱스로 접근 가능
-
시퀀스 자료구조 예 : 리스트, 튜플, 레인지, 문자열 등
시퀀스 자료구조_1 리스트
-
순서가 있는 나열
-
각종 속성 및 연산 포함
-
구현 방법 : 1차원 배열 / 연결리스트
시퀀스 자료구조_2 튜플
-
순서가 있는 나열
-
각종 속성 및 연산 포함
-
수정이 불가능한 ‘리스트’와도 같다
시퀀스 자료구조_3 레인지
-
순서가 있는 나열
-
각종 속성 및 연산 포함
시퀀스 자료구조_4 문자열
-
순서가 있는 나열
-
각종 속성 및 연산 포함
맵 자료구조
-
‘키. 값 쌍으로 이루어진 자료구조’
-
대표적으로 딕셔너리 자료구조가 있다.
-
딕셔너리 자료구조의 경우 해시테이블 이용해 구현된다.
-
부여된 인덱스 없다.
-
데이터 접근을 위해서 ‘key’를 사용한다.
-
비선형자료구조다.
집합 자료구조
-
딕셔너리와 마찬가지로 부여된 인덱스 없다.
-
인덱싱/슬라이싱이 무의미하다. (못한다)
-
비선형자료구조다.