자료구조 2주차_어레이와 링크드리스트

자료구조 2주차_어레이와 링크드리스트

---

ARRAY

□□□□□□□

캡슐 호텔과 유사.

크기가 정해진 데이터 공간

 

📌 장점

• 메모리 접근이 쉬워 값을 빠르게 가져올 수 있음(지역적인 특성, Locality)
• 특정 원소 조회가 쉬움(index로 접근, O(1)의 시간 복잡도를 가짐)
• 두번째 원소의 메모리 주소 = 최초 원소의 메모리 주소 +( 원소의 데이터 타입에 따른 바이트 크기 )
  예 ) 100, 104, 108, ...(메모리 mapping)

 

📌 단점

• 새로운 칸을 지으려면 너무 많은 자원이 필요.
• 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 함.
• 최악의 경우 배열의 길이만큼 옮겨야 하므로 O(N) 시간 복잡도를 가짐.
• 특정 원소를 삭제하거나 null로 만들어도 그 흔적이 그대로 남아 있음(공간 낭비가 심함)

---

LINKEDLIST

□→□→□→□→□→□→□→□

기차 화물칸(노드) 연결고리로 이해!

리스트는 크기가 정해지지 않은 데이터 공간.

 

📌 장점

• 원소의 삽입/삭제 를 위해서는 앞 뒤 포인터만 변경하면 됨(O(1)의 사간 복잡도를 가짐

 

📌 단점

• 조회에는 약함.
• 특정 원소에 접근하려면 연결 고리를 따라 탐색해야 함.
• 최악의 경우 모든 연결고리(포인터)를 탐색해야 하므로 O(N) 시간 복잡도를 가짐.

---

클래스(Class)

같은 속성과 기능을 가진 객체들을 묶어서 정의할 수 있음.

 

📄코드

class Person:
	# constructor
    def __init__(self, param_name):
        print('i am created!', self)
        # 속성
        self.name = param_name
        
    # talk 메소드
    def talk(self):
        print("안녕하세요, 제 이름은", self.name, "입니다.")

# 생성자 Person()
person_1 = Person("유재석")
print(person_1.name)
print(person_1)
person_1.talk()

person_2 = Person("방명수")
print(person_2.name)
print(person_2)
person_2.talk()

 

📄출력

i am created! <__main__.Person object at 0x000001990CA87BE0>
유재석
<__main__.Person object at 0x000001990CA87BE0>
안녕하세요, 제 이름은 유재석 입니다.
i am created! <__main__.Person object at 0x000001990CC35970>
방명수
<__main__.Person object at 0x000001990CC35970>
안녕하세요, 제 이름은 방명수 입니다.

Process finished with exit code 0

 

클래스를 활용해 링크드 리스트 구현해 볼 예정

---

노드 클래스로 구현

 

📌 노드에 필요한 정보

• 칸에 있는 데이터
• 다음 칸이 뭔지(포인터)

 

📄코드

# [3] -> [4]
class Node:
    def __init__(self, data):
        self.data = data
        # 처음 생성했을 때는 이어져 있는게 없으므로 포잍터 None
        self.next = None

node = Node(3)
print(node.data) # 3
print(node.next) # None

first_node = Node(4)
node.next = first_node
print(node.data) # 3
print(node.next.data) # 4
print(first_node.data) # 4

---

링크드 리스트 구현

 

📄코드

# [3] -> [4]
class Node:
    def __init__(self, data):
        self.data = data
        # 처음 생성했을 때는 이어져 있는게 없으므로 포잍터 None
        self.next = None

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

linked_list = LinkedList(3)
print(linked_list) # LinkedList 객체 at 주소값
print(linked_list.head) # Node 객체 at 주소값
print(linked_list.head.data) # 3
print(linked_list.head.next) # None

---

링크드 리스트 append 구현

 

📄코드

# [3] -> [4] -> [5] -> [new]
# 현재 헤드 노드는 [3]
class Node:
    def __init__(self, data):
        self.data = data
        # 처음 생성했을 때는 이어져 있는게 없으므로 포잍터 None
        self.next = None

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

    # append 메소드, 맨 뒤에 있는 노드로 이동해야함!!
    def append(self, data):
        # haed가 비어 있을 때 []
        if self.head is None:
            self.head = Node(data)
            return # 함수 중단

        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(data)
        print("cur is ", cur.data)

linked_list = LinkedList(3)
linked_list.append(12)
linked_list.append(8)
linked_list.append(9)

 

📄출력

cur is  3
cur is  12
cur is  8

---

링크드 리스트 출력 구현

 

📄코드

class Node:
    def __init__(self, data):
        self.data = data
        # 처음 생성했을 때는 이어져 있는게 없으므로 포잍터 None
        self.next = None

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

    # append 메소드, 맨 뒤에 있는 노드로 이동해야함!!
    def append(self, data):
        # haed가 비어 있을 때 []
        if self.head is None:
            self.head = Node(data)
            return # 함수 중단

        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(12)
linked_list.append(8)
linked_list.append(9)

linked_list.print_all()

 

📄출력

3
12
8
9

---

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

 

📄코드

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):
        # 0이 들어오면 index-1 = -1이 되므로 예외처리
        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 # 다음 노드값을 next_node에 저장
        node.next = new_node # 다음노드에 새로운 노드 추가
        new_node.next = next_node #새로운 노드 다음꺼에 next_node 넣어주기

    def delete_node(self, index):
        # 0이 들어오면 index-1 = -1이 되므로 예외처리
        if index == 0:
            self.head = self.head.next #head에 헤드 다음이 오게끔!
            return

        node = self.get_node(index - 1)  # 현재노드
        node.next = node.next.next




linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)
linked_list.add_node(0, 6)
linked_list.print_all()
print()
linked_list.delete_node(0)
linked_list.print_all()

 

📄 출력

6
5
12
8

5
12
8

---

두 링크드 리스트의 합 계산

[6] → [7] → [8]

[3] → [5] → [4]

 

678 + 354 = 1032

1032를 반환해야 한다.

 

📄코드

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):
    sum_one = 0
    node_one = linked_list_1.head
    while node_one is not None:
        sum_one = sum_one * 10 + node_one.data
        node_one = node_one.next
        # print(sum_one)

    sum_two = 0
    node_two = linked_list_2.head
    while node_two is not None:
        sum_two = sum_two * 10 + node_two.data
        node_two = node_two.next
        # print(sum_two)


    return sum_one + sum_two


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

6

67

678

 

구현하기 힘들어서 강의를 봤다!

다음에 강의 안보고 다시 풀어보는 연습을 해야 할 것 같다.

---

요세푸스 문제

1. 1부터 입력된 n까지의 요소를 리스트에 넣어주기

a = []
for i in range(7):
    a.append(i+1)
    
print(a) # [1, 2, 3, 4, 5, 6, 7]

 

2. 리스트가 비어있을 때 까지 반복

while len(a) != 0:
    a.pop(index)

 

3. pop 순서

cnt = 0

while len(a) != 0:
    if (cnt + 1) % k == 0:
        a.pop(cnt)
    cnt += 1

하지만 이렇게 구현 하면 3과 6은 잘 pop()되지만, 그 이상 리스트 a의 길이를 벗어나는 순간 index범위 최과 오류가 발생한다.

 

범위가 벗어나면 다시 리스트 a의 첫번째값에 접근하도록 해야 할듯 하다...

조금도 더 생각할 시간이 필요한 문제라, 일단 진도부터 나가야 할 듯 하다.

 

📄나의 코드

def josephus_problem(n, k):
    a = []
    for i in range(n):
        a.append(i + 1)

    result = '<'

    cnt = 0
    while len(a) != 0:
        if cnt == k-1:
            cnt = -1
            if len(a) == 1:
                result += str(a[0]) + '>'
            else:
                result += str(a[0]) + ', '
            a.pop(0)
        else:
            temp = a.pop(0)
            a.append(temp)
        cnt += 1

    return print(result)

n, k = map(int, input().split())
josephus_problem(n, k)

k번째마다 result에 append한 뒤, 삭제.

k번째가 아닐 때는 제일 앞에값 빼서 제일 뒤로 넘어가도록!

 

백준 제출해 봤는데, 시간초과 난다..ㅠㅠㅠㅠ

 

📌 시간초과 이유

(백준 질문방에서 발취)

리스트에서 pop(0)을 수행하면, 데이터 맨 앞의 값을 제거한 후 그 뒤에 오는 값들을 일일히 전부 한  칸 씩 앞땡긴다.

즉, 맨 앞 데이터를 제거하기만 하면 되는게 아니라, 나머지 값을 다 한칸씩 당겨오기까지 해야 해서 시간이 많이 소요됩니다.

메모리를 옮기는 것도 연산이기에, 리스트가 길어질수록 pop(0)에서 소요되는 시간이 길어지게 되어 시간초과가 납니다.

 

리스트의 맨 앞에 값을 추가해 주는 것도 비슷한 이유로 매우 느립니다.

반면, 리스트의 마지막 값만 제거하는 pop()은 그저 리스트 길이만 줄이면 되기 때문에 빠르게 실행됩니다.

 

그래서 이 문제는 deque로 구현해야 효육적이라고 합니다.

deque로 한번 풀어보고! 강의 자료도 보고! 다시 풀어봐야 할듯 합니다.