1. 배열(Array)와 링크드리스트(Linked List)의 차이
1) 배열의 특징
- 연속된 메모리를 할당받으며, 이로인해 크기가 고정되어있다.
- 데이터에 접근할 때 인덱스를 사용하여 바로 접근할 수 있기 때문에, 시간복잡도가 O(1)이다.
- 배열 중간에 새로운 요소를 삽입하거나 기존 요소를 삭제하려면, 모든 요소를 한 칸씩 이동해야하기 때문에
시간복잡도가 O(N)이다.
2) 링크드리스트의 특징
- 비연속적인 메로리를 할당받으며, 크기가 고정되어있지 않다.
- 각 요소를 '노드'라고 다음 노드 주소를 가리키는 '포인트'를 가진다.
- 데이터에 접근하려면 리스트의 맨 처음부터 시작하여 포인터를 따라 하나씩 이동해야하기 때문에 시간복잡도가 O(N)이다.
- 새로운 요소를 삽입하거나 기존 요소를 삭제할 때, 노드와 노드의 포인터만 바꿔주면 되기때문에 시간복잡도가 O(1)이다.
👉 요약
- 데이터 접근이 잦을 때는 배열이 효율적이다.
- 삽입과 삭제가 빈번할 때는 링크드리스트가 효율적이다.
2. 파이썬으로 링크드리스트 구현해보기
파이썬에는 링크드리스트 타입이 없기때문에, 클래스를 정의하여 노드를 직접 구현해야한다.
class Node:
def __init__(self, data):
self.data = data # 값을 저장하는 변수
self.next = None # 다음 노드의 주소를 가리키는 포인터 역할
class LinkedList:
def __init__(self, value):
self.head = Node(value) #맨 처음 노드(Head)를 생성
def append(self, value): # 맨 끝에 새로운 데이터를 추가하는 함수
cur = self.head
while cur.next is not None: # cur노드가 마지막 노드일때까지 반복문이 실행된다
cur = cur.next
cur.next = Node(value)💡 다음 노드 주소를 가리키는 포인터 역할이 None인 이유는?
처음 노드를 만들 때는 다음 노드가 없으므로, 기본값을 None으로 한다.
💡 파이썬의 None과 자바의 null은 무슨 차이?
| 특징 | 파이썬의 None | 자바의 null |
| 타입 | NoneType이라는 고유 타입의 객체 | 키워드(Literal)로 참조타입(객체)변수가 객체를 가리키지 않음을 나타냄 |
| 싱글턴 | 유일한 인스턴스 | null값은 유일한 객체가 아님 |
| 비교연산 | is 연산자 권장 | == 연산자 사용 |
3. 두 링크드리스트의 합 계산하기
Q. 다음과 같은 두 링크드 리스트를 입력받았을 때, 합산한 값을 반환하시오. 예를 들어 아래와 같은 링크드 리스트를 입력받았다면, 각각 678, 354 이므로 두개의 총합 678 + 354 = 1032 를 반환해야 한다. 단, 각 노드의 데이터는 한자리 수 숫자만 들어갈 수 있다.
1) 첫번째 풀이
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_node(self,index):
cur = self.head
count = 0
while count < index:
cur = cur.next
count += 1
return cur
def join_node(linked_list):
node = linked_list.head
node_data = str(node.data)
while node.next is not None:
node_data = node_data + str(node.next.data)
node = node.next
print("node_data=", node_data)
return node_data
def get_linked_list_sum(linked_list_1, linked_list_2):
num_linked_list_1 = int(linked_list_1.join_node())
num_linked_list_2 = int(linked_list_2.join_node())
return num_linked_list_1+num_linked_list_2
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+7+8 연산을 하게 될 것이다.
그래서 [6] - [7] - [8] 형태의 링크드리스트를 '678'로 붙여주었다.
join_node 함수를 새로 만들어서 문자열을 이어붙여주었고 get_linked_list_sum 함수에서 문자열을 int로 형변환을 하여 값을 더해주었다.
✅ 효율적인 풀이인가?
이 방법은 직관적이지만 비효율적이다.
node_data = node_data + str(node.next.data) 연산을 할 때마다 새로운 문자열 객체를 생성하기 때문이다.
join을 하게되면 입력값이 N개일 때, 문자열 연결로 인해 시간복잡도는 O(N ²) 이 된다.
공간복잡도 측면에서도 while문 안에서 새로운 문자열 객체를 메모리에 매번 담기때문에 N이 커질 수록 메모리사용량은 N의 제곱에 비례하여 증가한다.
두번째 풀이로 이 문제를 더 효율적으로 풀어보자.
2) 두번째 풀이
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_node(self,index):
cur = self.head
count = 0
while count < index:
cur = cur.next
count += 1
return cur
def sum_linked_list(linked_list):
sum = 0
cur = linked_list.head
while cur is not None:
sum = sum*10 + cur.data
cur = cur.next
return sum
def get_linked_list_sum(linked_list_1, linked_list_2):
sum_1 = sum_linked_list(linked_list_1)
sum_2 = sum_linked_list(linked_list_2)
return sum_1 + sum_2
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] - [7] - [8] 형태의 링크드리스트를 '678' 형태로 만들어줄 수 있을까?
678은 600 + 70 + 8이다.
노드의 갯수만큼 반복문을 돌리면서 이전 합계에 10을 곱해주면 원하는 형태로 만들어줄 수 있다.
✅ 효율적인 풀이인가?
이 풀이는 불필요한 데이터 복사를 하지 않고 핵심 연산만 수행하고 있기때문에 효율적이라고 볼 수 있다.
연결 리스트의 노드가 N개 일때, 노드를 딱 한번씩만 방문하기때문에 시간복잡도가 O(N)이다.
(노드를 한번 방문할때마다 앞에 있는 모든 데이터를 다시 복사했던 첫번째 풀이에 비해 훨씬 효율적이다.)
메모리 효율측면에서 보자면 sum_1과 sum_2 정수 변수 2개만 사용하여 최종 결과를 저장하고있다.
이 의미는 입력크기 N이 커져도 추가로 사용하는 공간이 늘지 않는 O(1)의 공간복잡도라는 것이다.
3. 마무리
문제를 풀고 원하는 출력값을 얻었다하더라도 한번 다시 고민해보는 것이 중요하다는 것을 느꼈다.
내가 생각한 방법이 최선이 맞는지, 입력값에 비례하여 복잡도가 늘어나지는 않는지 생각해봐야겠다.
'알고리즘&자료구조' 카테고리의 다른 글
| 백준 1181 - 단어 정렬 (0) | 2024.05.24 |
|---|---|
| [백준 1991] 트리 순회 (0) | 2024.02.05 |
