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

데이터 구조론 1, 2

1주차

데이터 구조(자료구조) = 데이터를 저장하는 구조.

데이터 구조를 배우는 이유?

  • 값을 어떻게 효율적으로 저장할 수 있을까? (저장: 자료구조) 예) Stack, Queue, Tree

  • 저장된 값을 이용해서 어떻게 효율적으로 활용할 수 있을까? (연산: 알고리즘) 예) Brute-Force, Divide & Conquer, Dynamic Programming

예제: 샴푸통 제작

  1. 샴푸를 짤때 뒤짚어야 한다

  2. 1을 해결하기 위해 위아래를 바꾼 디자인은 뚜껑을 열어야 한다. 양 조절이 필요해야 한다. 라는 문제가 있음

  3. 2를 해결하기 위해 누르면 짜는 형태로 나옴.

  4. 근데 내가 샴푸를 많이쓰는 사람이면 앞의 두 디자인이 나을 수 있음.

  5. 결론 : 사람마다 샴푸를 쓰는 목적이 다름. (원하는게 다름) 우리는 사람의 목적에 맞게 샴푸통을 만드는 능력(자료구조 능력)을 길러야 함.

변수 : 자료를 저장하는 구조 (= 가장 기본적인 자료구조)

리스트 : 변수의 나열 (= 배열)

  • 장점 : i번째에 뭐가 저장된 지 알 수 있음.

  • 단점 : 원소의 추가/ 삭제가 까다롭다.

링크드 리스트 : 여러 개의 변수를 저장하는 다른 방법 / 하나의 원소는 값과 포인터(다음 원소가 누구다. 값이 아니라 원소!!!)로 이루어져 있음.

  • 장점 : 중간에 숫자를 추가하기 쉬움.

  • 단점 : i번째 원소를 찾는게 쉽지 않음.

  • 리스트와 링크드 리스트는 같은 일은 하지만 장단점은 정반대임.

캡슐화: 자료구조의 구현의 핵심

  • 특징 : 속을 우리가 볼 수 없음. 알아야 하는 정보만 알림.

  • 이유 : 알약을 먹는 사람이 입자의 크기, 색, 맛 등을 알 필요가 없고 어떤 약인지 성분만 알면 됨.

  • 결론 : 데이터 구조를 사용하는 사람이 꼭 필요한 정보외의 다른 정보는 숨겨버림. 알아봐야 복잡하니깐.

  • 예 : 샴푸를 쓰는 사람은 샴푸를 어떻게 쓰는지만 알면 되지, 내부가 어떻게 작동하는지는 알 필요가 없다. 자료구조를 사용하는 사람은 자료구조가 어떻게 동작하는지 알 필요가 없다.

  • 캡슐화라는 개념을 어떻게 구현할 수 있을까? 구현할 때 쓰는 문법이 CLASS임.

  • Q. 클래스가 뭐야? A. 캡슐화를 구현하는 문법.

  • 우리는 클래스를 어떻게 사용하는지만 알면 됨. 그 원리는 몰라도 상관없음.

  • 클래스와 인스턴스 차이 :

    • 클래스 : 캡슐화를 구현하는 언어. 자료구조가 어떻게 구성되어 있는지에 대한 설명서

    • 인스턴스 : 하나의 자료구조 그 자체.

    • 클래스는 자료구조의 틀이고 인스턴스는 틀로 만들어진 자료구조.

예제1. 최댓값 기계.

이번 문제에서는 최댓값 기계를 만들어 봅니다. 이 최댓값 기계는 숫자를 여러개 담을 수 있으며, 담겨있는 숫자들 중에서 최댓값을 반환할 수 있습니다. 조금 더 자세히 이야기하면, 다음의 기능을 지원합니다.

machine.addNumber(x) : 숫자 x를 최댓값 기계 machine에 추가합니다.
machine.removeNumber(x) : 숫자 x를 최댓값 기계 machine으로부터 제거합니다. 만약 숫자 x가 최댓값 기계 내에 없다면 아무 일도 일어나지 않습니다.
machine.getMax() : 최댓값 기계 machine이 갖고있는 숫자들 중 최댓값을 반환합니다.
예를 들어, 최댓값 기계의 이름이 myMachine이고 숫자 2, 5, 3, 4 를 각각 추가하기 위해서는 다음의 명령어를 사용합니다.

myMachine.addNumber(2) myMachine.addNumber(5) myMachine.addNumber(3) myMachine.addNumber(4)

이후 myMachine.getMax() 를 호출하면, 이는 5를 반환하게 됩니다.

class를 이용하여 최댓값 기계를 구현하세요.

코드1.

class maxMachine : #하나의 클래스 : 인스턴스를 찍어내는 설명서 
    def __init__(self) : # 인스턴스가 호출되자마자 실행되는 함수. # self : 인스턴스에 대한 함수를 암시. (함수의 인자가 아니라 인스턴스의 함수를 암시.)
        self.myData = []
        pass

    def addNumber(self, n) :
        # 인스턴스 내에 숫자 n을 추가하라 
        self.myData.append(n)
        #pass

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

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

def main():

    myMachine = maxMachine() # myMachine : 인스턴스 / 캡슐화의 개념이 사용됨. 
    # 위를 호출하면 init에 의해 myMachine.MyData가 빈 리스트가 됨. 
    '''
    테스트를 하고싶으면, 아래 부분을 수정합니다.
    '''

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

    print(myMachine.getMax())

    myMachine.removeNumber(3)

    print(myMachine.getMax())

    myMachine.removeNumber(2)

    print(myMachine.getMax())

if __name__ == "__main__":
    main()
  • Q. 그래서 무엇을 써야하나? 리스트를 써야하나? 링크드 리스트를 써야하나?

  • A. 그때그때 다르다.

    • 왜? 장단점이 다르다. 리스트의 장점이 필요하냐? 링크드 리스트의 장점이 필요하냐에 따라 다르다.

    • 나의 목적에 맞게 사용해야 함.

예제2. 구슬 넣기 (리스트)

구슬 넣기 (리스트)
Elice의 토끼는 암기력을 높이기 위해 구슬 넣기 놀이를 고안했다. 토끼는 nn개의 구슬이 있으며, 각 구슬은 1부터 nn까지의 번호를 하나씩 갖고 있다. 또한, 토끼는 양 쪽이 뚫려있고 투명하지 않은 관을 갖고 있다. 토끼는 nn개의 구슬을 이 파이프에 무작위로 넣은 후에, 최종적으로 구슬이 파이프 속에서 어떻게 배치되어 있는지를 암기함으로써 암기력을 높인다.

토끼는 파이프의 왼쪽에, 혹은 오른쪽에 구슬을 넣을 수 있다. 예를 들어, 파이프의 왼쪽으로 숫자 1의 구슬을 넣고, 파이프의 오른쪽으로 숫자 3의 구슬을 넣고, 마지막으로 파이프의 왼쪽으로 숫자 2의 구슬을 넣게 되면, 최종적으로 구슬의 배치는 2 1 3 이 된다.

토끼가 nn개의 구슬을 파이프에 넣는 행위가 입력으로 주어질 때, 최종적으로 구슬이 파이프 속에서 어떻게 배치되어 있는지를 출력하는 프로그램을 작성하시오. (단, 파이프의 길이는 nn개의 구슬을 모두 담기에 충분히 길다고 가정하자)
# List의 경우 시간이 너무 느림. 
# 이유 : 오른쪽으로 넣을때는 괜찮은데, 왼쪽에서 넣을때는 계속해서 한칸씩 밀기때문에(리스트는 원소의 추가삭제가 굉장히 느림.)
class ListPipe:
    '''
    List를 이용하여 다음의 method들을 작성하세요.
    '''
    def __init__(self) :
        '''
        리스트 myPipe를 만듭니다. 이는 구슬의 배치를 저장합니다.
        '''
        self.myPipe = []
        pass

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

    def addRight(self, n) :
        '''
        파이프의 오른쪽으로 구슬 n을 삽입합니다.
        '''
        self.myPipe.append(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 x in myInput:
        # x[0] <- 구슬 이름, x[1] <- 방향
        if x[1] == 0:
            myPipe.addLeft(x[0])
        else :
            myPipe.addRight(x[0])

    result = myPipe.getBeads()

    return result

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
        pass

    def addLeft(self, n) :
        '''
        파이프의 왼쪽으로 구슬 n을 삽입합니다.
        '''
        elem = LinkedListElement()
        elem.value = n

        #만약 초기 리스트가 비어져있으면
        if self.start == None:
            self.start = elem
            self.end = elem
        else:
            elem.myNext = self.start

            #이제 start가 바뀌니 self.start도 바꿔줘야함. 
            self.start = elem

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

        elem = LinkedListElement()
        elem.value = n

        #만약 초기 리스트가 비어져있으면
        if self.start == None:
            self.start = elem
            self.end = elem
        else:
            self.end.myNext = elem
            #이제 end 바뀌니 self.end 바꿔줘야함. 
            self.end = elem

    def getBeads(self) :
        '''
        파이프의 배치를 list로 반환합니다.
        '''
        #              c가 계속해서 가면서 출력하도록 함 
        # 1 -> 2 -> 3 -> 4 -> 5 (None)
        # [1, 2, 3, 4 ,5 ]

        c = self.start

        result = []

        while c != None : 
            result.append(c.value)
            # 한칸 앞으로 감. c.myNext가 None이 되는 순간 끝이 남. 
            c = c.myNext 
        return result

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 x in myInput:
        # x[0] <- 구슬 이름, x[1] <- 방향
        if x[1] == 0:
            myPipe.addLeft(x[0])
        else :
            myPipe.addRight(x[0])

    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()

문제1. 내림차순 정렬하기

#문제 
내림차순 정렬하기
숫자들이 주어질 때, 이를 내림차순 정렬하여 출력하는 프로그램을 작성하세요.

단, '최댓값 기계’문제에서 작성하였던 자료구조를 이용하여 문제를 풀도록 합니다.
class maxMachine : #하나의 클래스 : 인스턴스를 찍어내는 설명서 
    def __init__(self) : # 인스턴스가 호출되자마자 실행되는 함수. # self : 인스턴스에 대한 함수를 암시. (함수의 인자가 아니라 인스턴스의 함수를 암시.)
        self.myData = []
        pass

    def addNumber(self, n) :
        # 인스턴스 내에 숫자 n을 추가하라 
        self.myData.append(n)
        #pass

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

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

def sorting(myList) :
    '''
    myList를 내림차순으로 정렬하여 반환하는 함수를 작성하세요.

    예를 들어, myList = [5, 2, 3, 1] 이라면 [5, 3, 2, 1] 을 반환해야 합니다.

    단, maxMachine class를 이용하도록 합니다. 
    '''

    myMachine = maxMachine()
    result = []

    for i in myList:
        myMachine.addNumber(i)

    while len(myMachine.myData) != 0 :
        n = myMachine.getMax()
        myMachine.removeNumber(n)
        result.append(n)

    return result

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

    myList = [int(v) for v in input().split()]

    print(sorting(myList))

if __name__ == "__main__":
    main()

문제2. 주문관리시스템 (리스트)

#문제 
주문 관리 시스템 (리스트)
이번 실습 문제에서는 주문 관리 시스템을 구현합니다. 이 주문관리 시스템은 총 3가지 기능을 지원해야 합니다. 이는 주문생성, 주문취소, 주문조회입니다. 각각의 자세한 설명은 다음과 같습니다.

주문생성: 고객이 쇼핑몰에서 주문을 하게 되면 이 주문은 고유의 주문번호를 갖게 되고, 이 주문번호가 주문관리시스템에 등록됩니다. 물론 고객은 여러명이기 때문에 주문관리시스템 내에 등록된 주문 번호가 여러개 있을 수 있으며, 먼저 주문을 한 주문번호가 먼저 처리되는 구조입니다.
주문취소: 고객의 요청에 따라 주문은 취소가 될 수도 있습니다. 주문이 취소될 경우에는 그 주문은 주문관리시스템으로부터 삭제됩니다.
주문조회: 주문이 몇 번째로 처리가 될지를 알려줍니다.
이번 실습문제에서는 orderManager class내의 함수 addOrder, removerOrder, getOrder를 통해 위 기능을 구현합니다.

addOrder(x) : 주문번호 x를 주문관리시스템에 추가합니다. return 값은 없습니다.
removeOrder(x) : 주문번호 x를 주문관리시스템에서 제거합니다. 만약 해당하는 주문번호가 관리시스템에 존재하지 않는 경우 아무런 동작도 하지 않으면 됩니다. return 값은 없습니다.
getOrder(x) : 입력한 주문번호 x가 주문관리시스템에서 몇번째로 처리되는지를 return 합니다. 만약 입력한 주문번호 x가 주문관리시스템 내에 존재하지 않는 경우 -1을 return 합니다.
예를 들어, addOrder(1), addOrder(2), addOrder(4)를 차례로 실행하면 주문관리시스템에 1 - 2 - 4 로 입력된 순서대로 저장됩니다. 이 상태에서 removeOrder(2)를 실행하면 주문관리시스템에서 주문번호 2를 찾아낸 다음 제거하여 1 - 4 로 주문관리시스템이 업데이트됩니다.

이 상황에서 getOrder(1)를 실행한 결과는 주문번호 1이 처리될 순서인 1이 반환되며, getOrder(4)를 실행한 결과는 주문번호 4가 처리될 순서인 2가 반환될 것입니다.
class orderManager :
    '''
    주문을 처리하는 class를 작성합니다.
    '''

    def __init__(self) :
        '''
        이 부분은 고치지 마세요.
        '''
        self.data = []

    def addOrder(self, orderId) :
        '''
        주문번호 orderId를 추가합니다.
        '''
        self.data.append(orderId)

    def removeOrder(self, orderId) :
        '''
        주문번호 orderId를 제거합니다.
        '''
        self.data.remove(orderId)

    def getOrder(self, orderId) :
        '''
        주문번호 orderId가 몇 번째로 처리될지를 반환합니다.

        만약 주문번호 orderId가 존재하지 않으면 -1을 반환합니다. 
        '''
        if (orderId in self.data) == False:
            return -1
        else:
            return (self.data.index(orderId) + 1)

def main():
    manager = orderManager()

    '''
    테스트를 하고싶으면, 아래 부분을 수정합니다.
    '''

    manager.addOrder(4)
    manager.addOrder(8)

    print(manager.getOrder(8))

    manager.addOrder(2)
    manager.addOrder(1)
    manager.removeOrder(4)

    print(manager.getOrder(8))

    manager.addOrder(59)
    manager.addOrder(5959)

    print(manager.getOrder(59))


if __name__ == "__main__":
    main()

문제3. 주문관리시스템 (링크드 리스트)

#문제 
주문 관리 시스템 (링크드 리스트)
(요구사항은 [문제 5] 주문관리시스템과 동일합니다. 다만, 이번엔 링크드 리스트로 구현해주세요.)

이번 실습 문제에서는 주문 관리 시스템을 구현합니다. 이 주문관리 시스템은 총 3가지 기능을 지원해야 합니다. 이는 주문생성, 주문취소, 주문조회입니다. 각각의 자세한 설명은 다음과 같습니다.

주문생성: 고객이 쇼핑몰에서 주문을 하게 되면 이 주문은 고유의 주문번호를 갖게 되고, 이 주문번호가 주문관리시스템에 등록됩니다. 물론 고객은 여러명이기 때문에 주문관리시스템 내에 등록된 주문 번호가 여러개 있을 수 있으며, 먼저 주문을 한 주문번호가 먼저 처리되는 구조입니다.
주문취소: 고객의 요청에 따라 주문은 취소가 될 수도 있습니다. 주문이 취소될 경우에는 그 주문은 주문관리시스템으로부터 삭제됩니다.
주문조회: 주문이 몇 번째로 처리가 될지를 알려줍니다.
이번 실습문제에서는 orderManager class내의 함수 addOrder, removerOrder, getOrder를 통해 위 기능을 구현합니다.

addOrder(x) : 주문번호 x를 주문관리시스템에 추가합니다. return 값은 없습니다.
removeOrder(x) : 주문번호 x를 주문관리시스템에서 제거합니다. 만약 해당하는 주문번호가 관리시스템에 존재하지 않는 경우 아무런 동작도 하지 않으면 됩니다. return 값은 없습니다.
getOrder(x) : 입력한 주문번호 x가 주문관리시스템에서 몇번째로 처리되는지를 return 합니다. 만약 입력한 주문번호 x가 주문관리시스템 내에 존재하지 않는 경우 -1을 return 합니다.
예를 들어, addOrder(1), addOrder(2), addOrder(4)를 차례로 실행하면 주문관리시스템에 1 - 2 - 4 로 입력된 순서대로 저장됩니다. 이 상태에서 removeOrder(2)를 실행하면 주문관리시스템에서 주문번호 2를 찾아낸 다음 제거하여 1 - 4 로 주문관리시스템이 업데이트됩니다.

이 상황에서 getOrder(1)를 실행한 결과는 주문번호 1이 처리될 순서인 1이 반환되며, getOrder(4)를 실행한 결과는 주문번호 4가 처리될 순서인 2가 반환될 것입니다.

요구사항
링크드 리스트를 이용하여 구현해주시기 바랍니다.
class LinkedListElement :
    # 링크드리스트는 파이프(링크드 리스트전체 - 스타트와 앤드 원소), 각 원소 클래스 두가지를 가지고 있음. 
    # 각 원소는 값과 포인터 두가지를 가지고 있음. 

    def __init__(self, data, myPrev, myNext) :
        self.data = data
        self.myNext = myNext
        self.myPrev = myPrev 

class orderManager :
    '''
    주문을 처리하는 class를 작성합니다.
    '''
    def __init__(self) :
        '''
        이 부분은 고치지 마세요.
        '''
        dummy = LinkedListElement(-1, None, None)
        self.begin = dummy
        self.end = dummy 
        self.orderToElem = {}

    def removeItemId(self, orderId):
        del self.orderToItem[orderId]

    def addOrder(self, orderId) :
        '''
        주문번호 orderId를 추가합니다.
        '''
        singleOrder = LinkedListElement(orderId, None, None)
        self.end.myNext = singleOrder
        singleOrder.myPrev = self.end
        self.end = singleOrder
        self.orderToElem[orderId] = singleOrder 


    def removeOrder(self, orderId) :
        '''
        주문번호 orderId를 제거합니다.
        '''
        elem = self.orderToElem[orderId]
        prevElem = elem.myPrev 
        nextElem = elem.myNext 

        if prevElem != None:
            prevElem.myNext = nextElem 

        if nextElem != None:
            nextElem.myPrev = prevElem 

        if elem is self.end : 
            self.end = prevElem 

        del self.orderToElem[orderId]

    def getOrder(self, orderId) :
        '''
        주문번호 orderId가 몇 번째로 처리될지를 반환합니다.

        만약 주문번호 orderId가 존재하지 않으면 -1을 반환합니다. 
        '''
        cnt = 0
        cur = self.begin

        while cur != None : 
            if cur.data == orderId:
                return cnt 
            cur = cur.myNext 
            cnt = cnt + 1 
        return -1 

def main():
    manager = orderManager()

    '''
    테스트를 하고싶으면, 아래 부분을 수정합니다.
    '''

    manager.addOrder(1)
    manager.addOrder(2)
    manager.addOrder(3)
    manager.removeOrder(2)

    print(manager.getOrder(1))
    print(manager.getOrder(2))
    print(manager.getOrder(3))

if __name__ == "__main__":
    main()

댓글(0)

Designed by JB FACTORY