알고리즘 - 2주차 Array / LinkedList

 

Array 와 LinkedList

경우	Array	Linked List
특정 원소 조회	O(1)	O(N)
중간에 삽입 삭제	O(N)	O(1)
데이터 추가	데이터 추가 시 모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당 받아야 한다.	모든 공간이 다 찼어도 맨 뒤의 노드만 동적으로 추가하면 된다.
정리	데이터에 접근하는 경우가 빈번하다면 Array 를 사용하는 것이 좋다.	삽입과 삭제가 빈번하다면 LinkedList 를 사용하는 것이 더 좋다.

 

파이썬의 list 는 array로 구현되어있다. 하지만 내부적으로 동적배열을 사용하여 배열의 길이가 늘어나도 O(1)의 시간 복잡도가 걸리도록 되어있다. 따라서 파이썬의 배열은 링크드 리스트로 쓸 수 도 있고, 배열로도 쓸 수 있다.

 

---

Class 클래스

: 분류. 집합. 같은 속성과 기능을 가진 객체를 총칭하는 개념

 

생성자(Constructor) : 객체를 생성할 때 데이터를 넣어주거나, 내부적으로 원하는 행동을 실행하게 할 수 있다. 

                                  def __init__(self): 로 사용한다.

 

self : 객체 자기 자신

 

메소드(method) : 클래스 내부의 함수

 

class Person:
    def __init__(self, param_name):
        print("hihihi", self)
        self.name = param_name

    def talk(self):
        print("안녕하세요 저는", self.name, "입니다")


person_1 = Person("유재석")  # hihihi <__main__.Person object at 0x1067e6d60> 이 출력됩니다!
print(person_1.name)  # 유재석
person_1.talk()  # 안녕하세요 저는 유재석 입니다

person_2 = Person("박명수")  # # hihihi <__main__.Person object at 0x106851550> 이 출력됩니다!
print(person_2.name)  # 박명수
person_2.talk()  # 안녕하세요 저는 박명수 입니다

person_1 = Person("유재석") 으로 class 실행하면, self 는 person_1 이되고, param_name 은 "유재석"이 된다.

따라서 self.name = person_1.name = param_name = 유재석

또한 person_1.talk() 로 메소드를 통하여 원하는 동작을 실행 할 수 있다.

 

---

 

링크드리스트 구현

 

1. Node 생성

# 노드 : 1)칸에 있는 데이터 2)다음으로 오는 칸

# 노드 생성
class Node:
    # 노드가 가질 속성
    def __init__(self, data):
        self.data = data
        self.next = None


node = Node(3)          
first_node = Node(4)    
node.next = first_node  
print(node)             # <__main__.Node object at 0x000001E2BB737BE0>
print(node.next.data)   # 4
print(node.data)        # 3
# 노드 갯수가 많아지면 호출과 .next를 계속 선언해야하는 노가다해야함
# 따라서 링크드 리스트 필요

• .data 를 통해서 값을 조회 할 수 있다.

 

2. LinkedList 생성 (후미에 원소 추가, 노드 전체 조회)

# 링크드 리스트 : self.head로 head 속성을 가진 Node 생성.
# append 함수로 self.head 뒤로 self.head.next 속성을 가진 Node 생성
# 추가로 append 선언하게되면 self.head ~ next.next.next 로 계속 Node 를 생성 할 수 있다.
class LinkedList:
    def __init__(self, data):
        self.head = Node(data)

    # 원소 추가
    def append(self, data):
        # .head 없는 경우
        if self.head is None:
            self.head = Node(data)
            return

        cur = self.head

        # cur.next 가 존재한다면 cur.next.next 에 node 생성
        while cur.next is not None:
            cur = cur.next
            print("cur is", cur.data)
        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(9)
linked_list.append(4)
linked_list.append(5)
linked_list.print_all()     # 9  # 4  # 5
print(linked_list.head.data)             # 9
print(linked_list.head.next.data)        # 4
print(linked_list.head.next.next.data)   # 5

• LinkedList 는 self.head 에 시작하는 노드만 저장한다.
• .append 로 다음 노드를 self.head.next에 저장한다.
• 노드를 조회하려면 self.head 부터 next를 하나씩 붙여가며 조회한다.

 

3. index 번째 노드 조회

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

• head에 저장되어있는 노드를 node 라는 변수에 담고
• count 라는 인덱스를 저장하기 위한 변수를 저장
• count 가 index 가 될 때까지
• while 문 내부에서 1씩 더해주니까 index보다 작을때까지로 조건
• node의 next 값을 node 에 대입하고 count 를 증가

 

4. index 번째 노드 추가

# index       next_node
# ["자갈"] -> ["밀가루"] -> ["우편"]      index.next = new_node
#       new_node                       new_node.next = next_node
#       ["흑연"]

    def add_node(self, index, value):
        new_node = Node(value)  # [6]

        if index == 0:
            new_node.next = self.head   # [6] -> [5]
            self.head = new_node    # head = [6]
            return

        node = self.get_node(index-1)   # [5]   # index가 0이 들어올 경우도 생각
        next_node = node.next   # [12]
        node.next = new_node    # [5] -> [6]
        new_node.next = next_node   # [6] -> [12]
        return


linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)

linked_list.add_node(1, 6)
print(linked_list.print_all())	# 5  # 6  # 12  # 8

• .get_node(index-1) 로 추가될 인덱스의 바로 이전 노드를 기준으로 잡아둔다.
• next_node = node.next 로 기준 노드의 기존의 next 노드를 변수에 담아둔 뒤 
• node.next = new_node 로 기준 노드의 다음을 새로 추가된 노드로 저장
• new_node.next = next_node 로 새로 추가된 노드의 next 를 기존의 next 노드로 이어 붙여준다.
• index가 0 일 경우에는 
• new_node.next = self.head 로 self.head 를 새로 추가될 노드 뒤에 붙이고
• self.head = new_node 로 새로운 노드를 head로 지정한다.

 

5. index 번째 노드 삭제

    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
        return


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

• .get_node(index-1) 로 추가될 인덱스의 바로 이전 노드를 기준으로 잡아둔다.
• node.next = node.next.next 로 기준 노드의 다음의 다음을 기준 노드의 다음으로 변경
• index 가 0일 경우
• head의 next 를 head로 변경

 

---

 

링크드 리스트 문제 풀기

 

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

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

 

A.

def get_linked_list_sum(linked_list_1, linked_list_2):
    sum_1 = 0
    head_1 = linked_list_1.head
    while head_1 is not None:
        sum_1 = sum_1 * 10 + head_1.data
        head_1 = head_1.next

    sum_2 = 0
    head_2 = linked_list_2.head
    while head_2 is not None:
        sum_2 = sum_2 * 10 + head_2.data
        head_2 = head_2.next

    return sum_1 + sum_2

• 입력받은 linkedlist 를 head 부터 반복하면서 next 노드로 넘어가는데 이때 곱하기 10을 하여 단위를 계산한다.
• 비슷한 변수와 중복되는 로직이 많다면 함수로 만들어 줄 생각을 해야한다.

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):
    sum = 0
    head = linked_list.head
    while head is not None:
        sum = sum * 10 + head.data
        head = head.next
    return sum

 

 

요세푸스 문제

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제