[Python] 자료구조

자료구조란?

 

자료를 저장하는 구조

여러 가지 종류가 있으며 저장된 자료에 대해 접근하는 방법 등의 차이가 존재한다.

 

자료구조를 배우는 이유

똑같은 음식을 같은 양만큼 담고 있는 두 그릇이 있다.

여우는 넓은 그릇이 편리하고 두루미는 길쭉한 그릇이 편리하다.

 

자료구조 또한 형태에 따라 장단점이 존재하며 구현하고자 하는

프로그램의 성능을 고려하여 알맞은 자료구조를 선택해야 한다

 

밥상에는 음식이 필요한 것처럼, 프로그램에도 자료가 빠져서는 안 된다.

프로그램에 필요한 자료를 효율적으로 담기 위해 자료구조를 배운다.

 

여우는 접시를, 두루미는 호리병을 써야 행복하게 음식을 먹을 수 있다.

음식을 담는 그릇도 먹는 사람, 먹을 음식을 고려하여 적절한 것을 선택해야 한다.

 

프로그램에서 특정 알고리즘을 구현하기 위해 적절한 자료구조를 사용해야 좋은 성능을 낼 수 있다

 

추상적 자료형이란

어떤 자료와 그 자료에 대한 연산(동작)들의 수학적인 정의를 의미한다.

그리고 그 정의를 구현하는 방법은 명시되어 있지 않다.

 

"추상적"이라는 단어의 의미도 뭔가 추상적이다.

"추상적 자료형"이란 용어를 파악하기 위해서, 자료형이 무엇인지부터 알아보자

 

 

자료형

자료형은 어떤 자료가 식별될 수 있는 방법과, 그 자료에 대한 여러 가지 연산(동작)을 제공한다.

 

자료형의 중요성 - 값의 해석 방법 명시

예를 들어, 65라는 자료가 있다. 컴퓨터는 이 자료가 수를 나타내는 65인지,

아니면 알파벳 'A' 를 나타내는 값인지 자료형을 모르는 경우에는 해석할 수 없다

(컴퓨터는 내부적으로 unicode라고 불리는 숫자를 문자에 대입하는 방식으로 각 문자를 식별하고, 65는 'A'에 해당한다.)

 

자료형의 중요성 - 연산 방법 제공

또, 수를 나타내는 자료형은 덧셈, 뺄셈 등을 비롯한 연산이 가능하다.

 

이처럼, 자료형은 어떤 자료가 식별되는 방법을 정의하고 자료에 적용할 수 있는 연산을 결정한다.

자료를 특정 분류에 따라 올바르게 표현하기 위한 정의와, 그 구현이 바로 자료형이라고 할 수 있다.

 

추상적 자료형은 구현 방법을 명시하고 있지 않다는 점이 특징이다

 

그릇을 추상적 자료형이라고 한다면, 그릇이 보관하는 자료와,

그 자료에 해당하는 연산의 정의를 포함해야 한다

 

그릇은 음식(자료)을 보관하고, 그릇에 담긴 음식(연산)을 먹을 수 있다.

이때 음식을 어떻게 먹을 수 있는지, 즉 어떻게 자료에 접근할 수 있는지는 주어지지 않는다

 

'그릇' 이라는 추상적 자료형이 있고, 그릇에 음식을 어떻게 담을 것인지,

그릇을 이용하여 어떻게 음식을 먹을 수 있는지 명확히 구현된 것을 자료구조라고 할 수 있다.

 

추상적 자료형과 자료구조

추상적 자료형 : 자료들과, 그 자료들에 대한 연산들을 개념적으로 정의만 한 것

자료구조 : 자료를 저장하는 방법과 자료에 적용할 수 있는 연산을 구체적으로 제공한 것 추상적 자료형을 구체적으로 구현한 결과가 자료구조

 

배열과 연결 리스트

리스트(List)

순서가 존재하며, 일렬로 나열된 값들이 들어있다

 

조회 : 임의의 위치의 자료가 무엇인지 알아본다.

삽입 : 임의의 위치에 자료를 추가한다.

삭제 : 임의의 위치의 자료를 제거한다. 이외에도 다양한 연산이 있다.

 

배열(Array)

리스트라는 추상적 자료형을 구현한 대표적인 예시가 바로 '배열'이다.

(Python에서는 배열을 리스트라는 이름으로 제공한다.)

`

배열에 저장되는 값들은 순서를 나타내는 번호를 가진다. 이 번호를 인덱스라고 부른다

 

배열 - 조회

따라서 배열 내의 특정 순서의 값을 조회하고자 할 때 단번에 찾아낼 수 있다.

5번 인덱스의 값은? 2

 

 

배열 - 삽입

반면에 자료를 추가할 땐 조금 번거롭다.

새로운 자료가 추가되면서, 자료들의 순서를 변경해주어야 하기 때문이다.

 

3번 인덱스에 10을 추가

 

우선, 새로운 자료가 들어갈 공간을 마련해주어야 한다.

배열에 들어갈 자료가 하나 늘었으므로 공간도 하나 더 만들어준다.

3번 인덱스에 10을 추가함

 

추가될 자료가 들어갈 공간을 비워주기 위해 기존 자료들은 한 칸씩 밀려나게 된다

 

3번 인덱스에 10을 추가

 

마련된 빈 자리에 추가될 값을 넣어준다.

자료를 제거할 때는 이와 반대로 진행하면 된다.

 

 

연결 리스트(Linked List)

리스트를 구현한 자료구조 중 대표적인 다른 예시는 연결 리스트이다.

배열은 각 자료에 인덱스를 붙여 저장하는 반면, 연결 리스트는 여러 개의 '노드'를 저장하는 방식으로 구현한다

 

노드는 자료와 포인터를 가진다.

자료는 저장하는 값 자체를 의미하고, 포인터는 자신의 다음 순서의 노드를 가리킨다.

 

이러한 특성 때문에, 연결 리스트에서 특정 위치의 자료를 찾는 것이 번거롭다.

배열은 찾는 자료의 위치와 관계없이 항상 단번에 값을 찾을 수 있지만, 연결 리스트는 찾는 자료의 위치가 시작점으로부터 멀수록 연산 횟수가 많아진다.

연결 리스트는 자료의 추가, 삭제에서 그 진가를 발휘한다.

 

조회 연산과 마찬가지로 연결 리스트 상에서 n번째 위치를 찾아야 하는 과정은 동일하다.

3번째 위치에 10을 추가

 

 

추가할 위치의 이전 노드의 포인터를 새로운 노드로, 새로운 노드의 포인터를 이전 노드가 가리키던 노드로 설정한다

제거는 정 반대로 실시하면 됨

 

배열

장점 : 특정 위치의 자료 탐색

단점 : 자료의 삽입과 삭제

연결 리스트

장점 : 자료의 삽입과 삭제

단점 : 특정 위치의 자료 탐색

 

자료구조의 구현 방법

자료구조는 추상적 자료형에 명시된 표현 및 연산 방법을 구현한다.

객체지향 프로그래밍에서 추상적 자료형은 인터페이스

자료구조는 클래스

 

인터페이스란?

객체지향 구조에서 추상 메서드만으로 이루어진 설계용 클래스

구현 부분이 비어있는 메서드를 추상 메서드라고 하며

상속받는 클래스에서 이를 구현하여 사용한다.

 

즉, '리스트'라는 인터페이스에는 "삽입과 삭제를 지원해야 한다"라는

명세만 주어지고 실제 동작 부분은 리스트를 상속받은 배열 클래스, 연결 리스트 클래스에서 구현해야 한다.

 

class MyInterface(metaclass=ABCMeta) : (추상 클래스로 만들기 위한 메타클래스 정의(Abstract Class Meta))
	@abstractmethod (추상 메서드임을 나타내는 데코레이션)
	def func() :
		pass

Java 등 다른 언어와는 달리 Python에서는 인터페이스 기능을 직접 지원하지는 않으므로

위와 같은 방식으로 표현된다.

(본 강의에서는 인터페이스를 만들지 않습니다)

 

자료구조의 구현 방법

자료구조를 만드는 데에는 클래스가 탁월하다

클래스가 갖고 있는 '필드'가 자료에 해당하고, '메서드'가 자료에 적용할 수 있는 연산이다

 

자료구조의 구현 예

import queue
q = queue.Queue()

파이썬 기본 라이브러리 중, '큐'라는 자료구조를 구현한 Queue 클래스도 있다. 큐 자료구조의 자료 저장 및 연산 방법을 갖추고 있다.

클래스를 이용한 첫 자료구조를 만들어보자.

 

첫 번째 줄에 최댓값 기계가 수행할 명령의 수를 나타내는 정수 nnn을 입력한다.

( 500≤n≤55000500 \le n \le 55000500≤n≤55000)

두 번째 줄부터 n개의 줄에 걸쳐 수행할 명령을 입력합니다. 명령의 종류는 다음과 같다.

• 0 x : 정수 x를 입력
• 1 x : 정수 x를 제거
• 2 : 최댓값 반환

입력예시

9
0 1
0 2
0 4
0 5
2
1 5
2
1 2
2

출력 예시

5
4
4

 

'''
maxMachine 클래스를 완성.
'''
class maxMachine :
    def __init__(self) :
        # 객체가 생성될 때 자동으로 호출되는 함수
        self.numbers = []
        

    def addNumber(self, n) :
        self.numbers.append(n)

    def removeNumber(self, n) :
        self.numbers.remove(n)

    def getMax(self) :
        return max(self.numbers)