[자료구조/알고리즘] 2. 배열과 리스트

GURI·2021년 10월 9일

엘리스AI트랙 자료구조 정리

자료구조/알고리즘

목록 보기

2/4

📑 자료구조?

Data Structure
컴퓨터 과학에서 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장을 의미
프로그램에서 특정 알고리즘을 구현하기 위해 적절한 자료구조를 사용해야 좋은 성능을 낼 수 있다.

1. 추상적 자료형

자료형 : 정수, 실수, 리스트 등이 자료형!

어떤 자료와 그 자료에 대한 연산(동작)들의 수학적인 정의를 의미한다. 그리고 그 정의를 구현하는 방법은 명시되어 있지 않다.

ex) 어떤 역을 타고 어디서 내려서 출퇴근을 한다 X

출퇴근을 한다 O - 추상적

🙄 자료형?

자료형은 어떤 자료가 식별될 수 있는 방법과 그 자료에 대한 여러 가지 연산(동작)을 제공
추상적 자료형은 구현 방법을 명시하고 있지 않다는 점이 특징

즉,

추상적 자료형 : 자료들과, 그 자료들에 대한 연산들을 개념적으로 정의만 한 것
자료구조 : 자료를 저장하는 방법과 자료에 적용할 수 있는 연산을 구체적으로 제공한 것

추상적 자료형을 구체적으로 구현한 결과가 자료구조

2. 배열과 연결리스트

여기서 리스트라는 개념은 Python에서의 리스트와 완전히 다른 개념.

그래서 기존의 파이썬에서의 리스트를 "배열"이라고 표기

🙄 리스트?

리스트라는 이름의 추상적 자료형이 있다.
순서가 존재하며, 일렬로 나열된 값들이 들어있다.

리스트가 담는 자료에 적용되는 연산

조회, 삽입, 삭제 등

🙄 배열?

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

(파이썬에서의 리스트 = 배열(Array))

배열에 저장되는 값들은 순서를 나타내는 번호, 인덱스를 가진다. 따라서 배열 내의 특정 순서의 값을 조회하고자 할 때 단번에 찾아낼 수 있다.
반면에 자료를 추가할 땐 조금 번거롭다 새로운 자료가 추가되면서, 자료들의 순서를 변경해주어야 하기 때문이다. 중간에 넣으려면 뒤에 자료들을 한칸씩 다 미룬 후 삽입
삭제는 삽입의 반대로 진행하면 된다.

🙄 연결 리스트(Linked List)

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

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

조회
연결 리스트에서 특정 위치의 자료를 찾는 것이 번거롭다.
→ 상대적인 순서가 명시되어 있기 때문에...!

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

삽입
- 추가할 위치의 이전 노드의 포인터를 새로운 노드로, 새로운 노드의 포인터를 이전 노드가 가리키던 노드로 설정한다.
제거
- 제거할 노드의 이전 노드의 포인터가 제거할 노드가 가리키던 노드를 가리키도록 설정한다.

인덱스를 이용하여 절대적인 순서를 표현하는 배열과는 달리,
연결 리스트는 자신의 다음 노드를 가리키는 상대적인 순서를 표현한다. ⇒ 장점

배열 - 조회에 유리 / 연결 리스트 - 삽입, 삭제에 유리

3. 자료구조의 구현 방법

객체지향 프로그래밍에서 추상적 자료형은 인터페이스, 자료구조는 클래스로 생각할 수 있다.

인터페이스란?
- 객체지향 구조에서 추상 메서드만으로 이루어진 설계용 클래스
- 구현 부분이 비어있는 메서드를 추상 메서드라고 하며, 상속받는 클래스에서 이를 구현하여 사용한다.

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

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

자료구조를 만드는 데에는 클래스가 좋다.

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

__init__ : 초기화 함수

'''
maxMachine 클래스를 완성하세요.
'''
class maxMachine :
    def __init__(self) :
        self.myData = []

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

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

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