알고리즘 2주차 - 링크드리스트

수업 목표

• 어레이와 링크드리스트에 대해 배우고 차이점을 익히기

• 이진 탐색의 효율성과 전제 조건에 대해 배우기

• 재귀함수의 방법과 전제 조건에 대해 배우기

자료구조, 알고리즘을 배우는 이유?

특정 자료구조는 삽입/삭제가 빠르고 특정 자료구조는 조회가 빠르다.

이처럼 어떤 경우에 따라 다양한 자료구조와 알고리즘을 사용해야 한다.

능력 있는 목수가 되려면 다양한 공구들을 하나하나 배워가야 하는 것!

어레이와 링크드리스트

• 어레이는 순차적으로 저장

• 링크드리스트는 다음 node라고 불리는 공간에 데이터를 저장하고 다음 공간을 지목하는 포인터로 구성됨

어레이

rooms = ["윤아", "수영", "티파니", "효연", "유리", "태연", "써니", "서현"]

이와 같이 각 방에 해당 멤버들이 숙박한다고 가정할때 "서현"이 "수영" 오른쪽 방으로 옮기려면 얼마나 옮겨야 할까?

5번이나 옮겨야 한다. 코딩에서 변수를 옮길때는 한번에 하나씩만 가능하다.

여기서 "방"이 바로 배열, Array(어레이)이다.

특징

• 배열은 크기가 정해진 데이터의 공간이다. 한번 정해지면 바꿀 수 없다

• 배열은 각 원소에 즉시 접근할 수 있다. room[0]과 같이.

• 여기서 원소의 순서는 0부터 시작하고 이를 인덱스 라고 함

• 즉시 접근 가능하다는 말은 상수 시간 내에 접근 할 수 있다 즉 O(1)이다.

• 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 한다.

• 즉 최악의 경우 배열의 길이 N만큼을 옮겨야 하므로 O(N)의 시간 복잡도를 가진다.

• 원소를 새로 추가하려면 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조

링크드 리스트

train_compartments = ["기관실"] -> ["시멘트"] -> ["자갈"] -> ["밀가루"] -> ["우편"]

이번에는 화물열차를 만들었다는 가정으로 각 화물칸은 다음 칸을 연결짓는 연결고리로 이어져 있다고 가정.

우편 칸에 잠시 일이 생겨 갈 일이 생겼을 때는 처음부터 연결고리를 따라 이동해야 한다.

마지막 칸에 "우편" 칸이 있다.

자갈 칸과 밀가루 칸의 사이에 "흑연" 칸을 넣기로 한다 어떻게 해야할까?

"자갈"칸의 연결고리에 "흑연"을 연결하고 "흑연" 칸으로 연결고리를 만들어 "밀가루"와 연결한다.

(연결고리를 떼고 붙일 수 있음)

"밀가루" 칸이 상해 해당 칸을 버리기로 하자. 어떻게 해야할까?

"흑연"칸의 연결고리를 빼서 "우편" 칸으로 바로 연결하면 된다.

특징

• 리스트는 크기가 정해지지 않은 데이터의 공간이다. 연결고리로 이어주기만 하면 자유자재로 늘릴 수 있음

• 리스트는 특정 원소에 접근하려면 연결 고리를 따라서 탐색해야 한다. 최악의 경우 O(N)의 시간복잡도.

• 리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 된다. 삽입/삭제에는 O(1)의 시간복잡도 안에 할 수 있음

정리 및 비교

하지만 파이썬의 list는 array로 구현되어 있음에도 불구하고 내부적으로 동적 배열이라는 것을 사용해서 append를 통해 배열의 길이가 늘어나도 O(1)의 시간복잡도가 걸린다.

즉 파이썬의 list는 어레이로도, 링크드리스트로도 쓸 수 있는 매우 효율적인 구조이다.

참고:

https://stackoverflow.com/a/5932364 https://en.wikipedia.org/wiki/Dynamic_array

클래스

• 클래스는 분류, 집합의 속성과 기능을 가진 객체를 총칭하는 개념

• 객체란? 객체는 세상에 존재하는 유일무이한 사물

• 예. 사람 - 클래스, 유재석 - 객체 / 동물 - 클래스, 강아지 - 객체

class Person:
    def __init__(self):
        print("i am created!", self)


person_1 = Person()
print(person_1) 
person_2 = Person()
print(person_2)  

• Person은 클래스, person_1, person_2는 객체

• () 은 생성자임. 바로 객체를 생성할 때 쓰는 함수를 의미

• self는 인자로 자기 자신을 넘겨주는 것. 파이썬 클래스가 알아서 자기 자신을 넘겨주는 것.

• 항상 클래스 내부의 메소드에는 self 인자가 존재해야 함.

• ()로 생성되면 클래스에서 기술해준 init 부분이 불리게 됨.

class Person:
    def __init__(self, param_name):
        print("i am created!", self)
        self.name = param_name


person_1 = Person("유재석")
print(person_1.name)
person_2 = Person("박명수")
print(person_2.name)

• param_name이 클래스 내부의 self.name에 저장이 되어서 그 self.name을 호출했기에 해당 결과값을 볼 수 있음

class Person:
    def __init__(self, param_name):
        print("i am created!", self)
        self.name = param_name

    def talk(self):
        print("안녕하세요, 제 이름은", self.name, "입니다.")


person_1 = Person("유재석")
print(person_1.name)
person_1.talk()
person_2 = Person("박명수")
print(person_2.name)
person_2.talk()

• 이와 같이 클래스를 이용하면 되게 유사한 행동 혹은 유사한 데이터를 쌓을 수 있게 구조를 만들 수 있음

• 연관성 있는 데이터를 클래스 내에서 관리하면서 다양한 객체를 쉽게 생성하기 위해 클래스 개념을 사용

링크드리스트 구현

• 각각의 칸이 노드라고 생각한다면 두가지 정보가 필요
  • 칸에 있는 데이터
  • 다음 칸이 뭔지

• 두 가지 데이터를 가지고 있어야 하므로 "클래스"를 이용하여 묶어서 구현

• 클래스의 생성자에 data를 인자로 받아서 self.data에 저장

• 현재는 다음 이어진 노드가 없기에 self.next에는 None을 넣어줌

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# 3을 가진 Node 를 만드려면 아래와 같이 하면 됩니다!
node = Node(3) # 현재는 next 가 없이 하나의 노드만 있습니다. [3]

first_node = Node(5) # 현재는 next 가 없이 하나의 노드만 있습니다. [5]
second_node = Node(12) # [12] 를 들고 있는 노드를 만듭니다.
first_node.next = second_node # 그리고, [5]의 next 를 [12]로 지정합니다. [5] -> [12]

• 하지만 위와 같이 구현하면 매번 노드를 연결하는 반복적 코드가 요구된다.(비효율)

• 다시 맨 앞칸만 저장하고, next를 통해서 다음 노드에 접근하게 구현한다.

• 링크드리스트는 self.head에 시작하는 노드를 저장

• 다음 노드를 보기 위해서 각 노드의 next를 조회하며 찾아가기

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

node = Node(3)
first_node = Node(4)
node.next = first_node

class LinkedList:
    def __init__(self, data):
        self.head = Node(data)
    def append(self, data):
        self.head.next = Node(data)

• 하지만 위와 같이 구현하면 처음부터 붙여나가는 것이 아닌 해당 노드에서만 새로 붙여지는 것이다.

• head가 쭉 모든 리스트를 순회하며 맨 마지막에 붙일 수 있게 구현해보자

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self, data):
        self.head = Node(data)
    def append(self, data):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(data)

linked_list = LinkedList(3)
linked_list.append(4)
linked_list.append(5)

• cur은 가장 처음 head를 가리키며 None이 나올때까지 그 다음 연결고리를 타고 감

• None이 나오면 next에 새로운 노드를 붙임

링크드리스트의 모든 원소 출력

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self, data):
        self.head = Node(data)
    def append(self, data):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(data)
    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

linked_list = LinkedList(3)
linked_list.append(4)
linked_list.append(5)
linked_list.print_all()

# 결과: 3 4 5 순차적으로 한줄씩 띄며 출력됨

링크드리스트의 원소 찾기/원소 추가

• 링크드리스트에서 index번째 원소를 반환하시오

# 원소 찾기 코드 스니펫
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        return "index 번째 노드를 반환해보세요!"

linked_list = LinkedList(5)
linked_list.append(12)
linked_list.get_node(0) # -> 5를 들고 있는 노드를 반환해야 합니다!

# 답변
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

linked_list = LinkedList(5)
linked_list.append(12)
print(linked_list.get_node(0).data) # -> 5를 들고 있는 노드를 반환해야 합니다!

# 원소 추가 코드 스니펫
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

    def add_node(self, index, value):
        return "index 번째 Node 뒤에 value 를 추가하세요!"


linked_list = LinkedList(5)
linked_list.append(12)
linked_list.add_node(0, 3)
linked_list.print_all()

# 내 코드
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

    def add_node(self, index, value):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        try:
            prev_node = self.get_node(index - 1)
        except:
            pass
        now_node = node
        add = Node(value)
        if count == 0:
            add.next = now_node
            self.head = add
        else:
            add.next = now_node
            prev_node.next = add
        return


linked_list = LinkedList(5)
linked_list.append(12)
linked_list.add_node(0, 3)
linked_list.print_all()

• 뭔가 개떡같이 짠 느낌이 강하다.

• 예전 링크드리스트를 배울때 삽입시에는 삽입하는 것을 그 다음것에 먼저 연결해주고 이전거에 삽입하는 것을 연결하는 순서로 배웠었는데 그대로 짜려니까 먼가 이상해진 것 같다.

# 튜터 코드
def add_node(self, index, value):
        new_node = Node(value)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return

        node = self.get_node(index - 1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node

링크드리스트의 원소 삭제

# 튜터 코드
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

    def add_node(self, index, value):
        new_node = Node(value)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            return

        node = self.get_node(index - 1)
        next_node = node.next
        node.next = new_node
        new_node.next = next_node

    def delete_node(self, index):
        return "index 번째 Node를 제거해주세요!"


linked_list = LinkedList(5)
linked_list.append(12)
linked_list.add_node(0, 3)
linked_list.print_all()

# 내 코드
def delete_node(self, index):
        if index == 0:
            next_node = self.head.next
            self.head = next_node
            return
        node = self.get_node(index - 1)
        next_node = self.get_node(index + 1)
        node.next = next_node

 # 튜터 코드
def delete_node(self, index):
        if index == 0:
            self.head = self.head.next
            return
        node = self.get_node(index - 1)
        node.next = node.next.next

두 링크드리스트의 합 계산

Q. 다음과 같은 두 링크드 리스트를 입력받았을 때, 합산한 값을 반환하시오. 예를 들어 아래와 같은 링크드 리스트를 입력받았다면, 각각 678, 354 이므로 두개의 총합 678 + 354 = 1032 를 반환해야 한다. 단, 각 노드의 데이터는 한자리 수 숫자만 들어갈 수 있다.

[6] -> [7] -> [8]
[3] -> [5] -> [4]

# 코드 스니펫
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self, value):
        self.head = Node(value)

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)


def get_linked_list_sum(linked_list_1, linked_list_2):
    # 구현해보세요!
    return 1032


linked_list_1 = LinkedList(6)
linked_list_1.append(7)
linked_list_1.append(8)

linked_list_2 = LinkedList(3)
linked_list_2.append(5)
linked_list_2.append(4)

print(get_linked_list_sum(linked_list_1, linked_list_2))

# 내 코드
def get_linked_list_sum(linked_list_1, linked_list_2):
    list_1 = []
    list_2 = []
    sum = []
    cur_1 = linked_list_1.head
    cur_2 = linked_list_2.head
    while cur_1 is not None:
        list_1.append(cur_1.data)
        cur_1 = cur_1.next
    while cur_2 is not None:
        list_2.append(cur_2.data)
        cur_2 = cur_2.next
    for num1, num2 in zip(list_1, list_2):
        sum.append(num1+num2)
    return sum

# 튜터 코드
def get_linked_list_sum(linked_list_1, linked_list_2):
    sum_1 = _get_linked_list_sum(linked_list_1)
    sum_2 = _get_linked_list_sum(linked_list_2)
    return sum_1 + sum_2

def _get_linked_list_sum(linked_list):
    linked_list_sum = 0
    head = linked_list.head
    while head is not None:
        linked_list_sum = linked_list_sum * 10 + head.data
        head = head.next
    return linked_list_sum

# 원래 linked_list_sum 변수명은 sum으로 했었다가 
# 파이썬 내장함수 sum과 이름이 겹쳐서 좋은 코드가 아니기에 수정

• 내가 문제를 또 잘못 이해한 모양이다. 결과값으로 678 + 354 = 1031를 반환해야 하는데 문제도 제대로 안 읽고 혼자 이상한 코드를 짜버렸다.....

• 느낀점: 문제를 끝까지 읽자 제발....., 이미 사용되는 함수의 이름으로는 함수나 변수 이름 정하지 말자!!