[데이터구조] 배열, 연결리스트, 클래스

배열, 연결리스트, 클래스

데이터 구조 (자료구조)이란?

• 데이터 구조 : 데이터를 저장하는 구조
• 프로그래밍에서의 자료는 숫자를 의미

컴퓨터 공학의 기본적인 커리큘럼은 아래의 3가지로 구성됨

• 프로그래밍 언어 : Python, C / C ++ / Matlab
• 자료구조 : Stack, Queue, Tree (저장하는 방법)
• 알고리즘 : Brute-Force, Divide & Computer, Dynamic Programming (연산하는 방법)
• 예를들어, 아래와 같이 샴푸를 보관하는 통(자료구조)을 만들때 아래와 같이 4개를 생각할 수 있고 각자마다의 장단점이 있음. 즉, 나의 목적에 맞게 데이터를 담는 그릇을 디자인 해야한다.

변수, 리스트, 링크드 리스트

1. 변수 : 가장 기본적인 자료구조

2. 리스트 (List) : 변수의 나열

• 장점 : i 번째 원소를 바로 알 수 있다 (myList[i])
• 단점 : 원소의 추가/ 삭제가 까다롭다
  • 4번째에 숫자를 추가하려면 4부터의 모든 값을 뒤로 밀어야함
  • 4번째에 숫자를 제거하려면 4부터의 모든 값을 앞으로 땡겨야함

3. 링크드 리스트 (Linked List) : 여러 개의 변수를 원소에 저장하는 다른 방법
   • 원소 : 값과 포인터를 저장하는 구조
   • 값 : 원소내의 값을 의미
   • 포인터 : 다음에 오는 원소를 가르킴

• 장점 : 원소의 추가/ 삭제가 편하다
• 단점 : i번째 원소를 알기가 쉽지 않다.

링크드 리스트에서 원소의 추가/삭제가 되는 과정

1. 위의 myLinkedList에서 3번째에 숫자 10을 추가하는 경우

2. 포인트 부분을 삽입하는 원소를 가르킴 (값이 아닌 원소를 가르키는게 중요)

3. 마찬가지로 제거하는 경우에도 하나를 제거하고 포인터가 가르키는 원소 부분만 변경하면됨

링크드 리스트에서 원소를 찾는 과정

1. 3번째 원소를 찾기 위해서 처음부터 출발해야함
2. 3에서부터 시작해서 11으로 이동
3. 11에서 5으로 이동하고, 3번째 원소임을 발견

캡슐화 (Encapsulation)

• 캡슐화 : 자료구조 구현의 핵심, 자료구조를 사용하는 사람은 자료구조가 어떻게 동작하는지 알 필요가 없다.
• 캡슐의 특징 : 우리가 속을 볼 수가 없음 (즉, 자료구조도 우리가 내부의 구조는 알 필요가 없이 필요한 정보만 알려주면 된다.)
  • 예) 알약을 먹는 사람한테 이 약이 감기약인거만 알려주면 됨
  • 예) 샴푸통을 눌렀을때 어떻게 샴푸가 나오는지는 모르지만 사용하는 방법은 알고있음
• 캡슐화를 구현하는 문법 : Class !! (클래스가 불필요한 개념을 숨기는게 아닌 캡슐화를 구현하는 문법이고 불필요한 개념을 숨기는 것은 캡슐화의 개념임)
• 참고로 사용하는 사람은 사용하는 법만 알면 되지만, 우리와 같이 만드는 사람은 캡슐의 내부가 어떻게 동작하는지 알아야함

클래스와 인스턴스

• 클래스 : 캡슐화를 구현하는 문법 (자료구조가 어떻게 구성되어 있는지에 대한 설명서)
  • 예) 샴푸통을 조립하는 방법 (설명서)
• 인스턴스 : 하나의 자료구조 그 자체
  • 예) 클래스에 의해서 만들어진 샴푸통

• 사용자가 알아야 하는 것 (또는 사용자가 원하는 것)

  • 자료구조에 숫자를 추가하기 위한 명령
  • 자료구조에 있는 숫자를 제거하기 위한 명령
  • 자료구조 내에 있는 숫자들 중 최댓값을 구하기 위한 명령

• 제작하는 사람이 알아야 하는 것 (또는 구현해야 하는 것)

  • 자료구조에 숫자를 추가하기 위한 구현
  • 자료구조에 있는 숫자를 제거하기 위한 구현
  • 자료구조 내에 있는 숫자들 중 최댓값을 구하기 위한 구현

• 클래스 예제 : 선언

class maxMachine :
    def __init__(self) :
        self.machine = []

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

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

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

• 클래스 예제 : 클래스 사용 (인스턴스 호출 및 메소드 사용)

def main():

    # myMachine이라는 instance를 생성 
    myMachine = maxMachine()

    myMachine.addNumber(1)
    myMachine.addNumber(2)
    myMachine.addNumber(3)
    myMachine.addNumber(2)

    myMachine.removeNumber(3)
    myMachine.removeNumber(2)

그렇다면, 리스트와 링크드 리스트 중에서 어떠한 방법을 사용해야 하는가?

• 나의 목적에 맞게 데이터를 담는 그릇을 디자인 해야함
• 목적이 먼저, 자료구조는 그 다음!!!
  • 무슨 자료를 담을지 파악한다.
  • 이 자료를 이용해서 무엇을 할 것인지 파악한다.
  • 목적을 빠르게 달성할 수 있는 자료구조를 디자인한다.

예제 : 구슬 넣기

• 리스트와 링크드 리스트를 사용하는 경우

• 둘중에서 어떤 방법이 좋은 방법인가??
  • 우리 알고리즘이 무슨 일을 하는지에 대해서 계산 (시간 복잡도에 대해서 계산 - 최악의 경우에 대해서 계산)
  • 리스트의 경우 숫자 n개를 모두 왼쪽으로만 삽입하는 경우 계속 오른쪽으로 밀어야하니 최악의 상황임
    • 숫자 하나를 왼쪽으로 삽입 : 숫자 개수만큼 밀어야함
    • 숫자 하나를 오른쪽으로 삽입 : 1번의 명령

• 위의 방법을 링크드 리스트에 대해서 생각해보면 링크드 리스트는 왼쪽이든 오른쪽이든 삽입시에 한번의 명령만 필요

# 리스트의 경우 코드 
class ListPipe:
    '''
    List를 이용하여 다음의 method들을 작성하세요.
    '''
    def __init__(self) :
        '''
        리스트 myPipe를 만듭니다. 이는 구슬의 배치를 저장합니다.
        '''
        self.myPipe = []


    def addLeft(self, n) :
        '''
        파이프의 왼쪽으로 구슬 n을 삽입합니다.
        '''
        self.myPipe = [n] + self.myPipe

    def addRight(self, n) :
        '''
        파이프의 오른쪽으로 구슬 n을 삽입합니다.
        '''
        self.myPipe = self.myPipe + [n]

    def getBeads(self) :
        '''
        파이프의 배치를 list로 반환합니다.
        '''
        return self.myPipe

def processBeads(myInput) :
    '''
    구슬을 파이프에 넣는 행위가 myInput으로 주어질 때, 구슬의 최종 배치를 리스트로 반환하는 함수를 작성하세요.

    myInput[i][0] : i번째에 넣는 구슬의 번호
    myInput[i][1] : i번째에 넣는 방향

    예를 들어, 예제의 경우 

    myInput[0][0] = 1, myInput[0][1] = 0,
    myInput[1][0] = 2, myInput[1][1] = 1,
    myInput[2][0] = 3, myInput[2][1] = 0

    입니다.

    '''

    myPipe = ListPipe()
    for i, j in myInput: 
        if j == 0: 
            myPipe.addLeft(i)
        else: 
            myPipe.addRight(i)
    return myPipe.getBeads()

def main():
    '''
    이 곳은 수정하지 마세요.
    '''

    n = int(input())

    myList = []

    for i in range(n) :
        myList.append([int(v) for v in input().split()])

    print(*processBeads(myList))

if __name__ == "__main__":
    main()

# 링크드 리스트의 경우 코드 
class LinkedListElement :
    def __init__(self) :
        self.value = None
        self.myNext = None

class LinkedListPipe:
    '''
    Linked List를 이용하여 다음의 method들을 작성하세요.
    '''
    def __init__(self) :
        '''
        리스트 myPipe를 만듭니다. 이는 구슬의 배치를 저장합니다.
        '''
        self.start = None
        self.end = None

    def addLeft(self, n) :
        '''
        파이프의 왼쪽으로 구슬 n을 삽입합니다.
        '''
        if self.start == None: 
            self.start = LinkedListElement()
            self.start.value = n 
            self.start.myNext = None
            self.end = self.start 
        else:
            self.element = LinkedListElement()
            self.element.value = n 
            self.element.myNext = self.start 
            self.start = self.element 

    def addRight(self, n) :
        '''
        파이프의 오른쪽으로 구슬 n을 삽입합니다.
        '''
        if self.end == None: 
            self.end = LinkedListElement()
            self.end.value = n 
            self.end.myNext = None    
            self.start = self.end 
        else:
            self.element = LinkedListElement()
            self.element.value = n 
            self.element.myNext = None 
            self.end.myNext = self.element 
            self.end = self.element 

    def getBeads(self) :
        '''
        파이프의 배치를 list로 반환합니다.
        '''
        self.myList = []
        self.nextElement = self.start
        self.myList.append(self.nextElement.value)
        while self.nextElement.myNext != None:
            self.myList.append(self.nextElement.myNext.value)
            self.nextElement = self.nextElement.myNext
        return self.myList


def processBeads(myInput) :
    '''
    구슬을 파이프에 넣는 행위가 myInput으로 주어질 때, 구슬의 최종 배치를 리스트로 반환하는 함수를 작성하세요.

    myInput[i][0] : i번째에 넣는 구슬의 번호
    myInput[i][1] : i번째에 넣는 방향

    예를 들어, 예제의 경우 

    myInput[0][0] = 1, myInput[0][1] = 0,
    myInput[1][0] = 2, myInput[1][1] = 1,
    myInput[2][0] = 3, myInput[2][1] = 0

    입니다.

    '''

    myPipe = LinkedListPipe()
    for i, j in myInput: 
        if j == 0: 
            myPipe.addLeft(i)
        else: 
            myPipe.addRight(i)

    return myPipe.getBeads()

def main():
    '''
    이 곳은 수정하지 마세요.
    '''

    n = int(input())

    myList = []

    for i in range(n) :
        myList.append([int(v) for v in input().split()])

    print(*processBeads(myList))

if __name__ == "__main__":
    main()

출처

• Elice Academy | 데이터구조 - 배열, 연결리스트, 클래스