책 리뷰/101가지 문제로 배우는 딥러닝 허깅페이스 트랜스포머

8장 연결리스트 (1) - 연결리스트란? (예제 - 회문 판별)

조조링 2024. 11. 22. 00:24
728x90
반응형

 

 

연결 리스트(Linked List)

연결 리스트(Linked List)는 배열과 함께 대표적인 선형 자료구조로, 다양한 추상 자료형(ADT) 구현의 기반이 됩니다. 이 구조는 동적으로 새로운 노드를 삽입하거나 삭제하기가 용이하며, 물리 메모리를 연속적으로 사용하지 않아도 되므로 메모리 관리에도 유리합니다.

 

연결 리스트의 특징

  1. 동적 메모리 관리: 물리적으로 연속적이지 않아도 되므로 메모리 활용도가 높습니다.
  2. 삽입/삭제의 효율성: 시작 또는 끝에 데이터를 삽입하거나 삭제하는 작업은 O(1)에 가능합니다.
  3. 탐색의 비효율성: 특정 인덱스에 접근하려면 순차적으로 읽어야 하므로 탐색 시간은 O(n)입니다.

 

 

문제. 연결 리스트로 Palindrome(회문) 검사하기
- 입력: 1->2 / 출력: False
- 입력: 1->2->2->1 / 출력: True

 

 

풀이1. 리스트 변환

연결 리스트의 값을 리스트로 변환한 뒤, 리스트에서 앞뒤를 비교하며 Palindrome을 확인합니다.

def isPalindrome(self, head: ListNode) -> bool:
    q: List = []
    
    if not head:
        return True
    
    node = head
    
    while node is not None:
        q.append(node.val)
        node = node.next
        
    while len(q) > 1:
        if q.pop(0) != q.pop():
            return False
        
    return True
  • 리스트 변환: 연결 리스트의 각 노드를 순차적으로 탐색하며 리스트 q에 값을 추가합니다.
  • Palindrome 확인: pop(0)으로 리스트의 첫 번째 값을 제거하고, pop()으로 마지막 값을 제거하여 비교합니다.
  • 시간 복잡도: 리스트의 pop(0)은 전체 요소를 한 칸씩 이동시키므로 이 소요됩니다.

 

단점

리스트의 pop(0) 연산은 비효율적입니다. 리스트는 동적 배열로 구현되어 있어 첫 번째 값을 꺼낼 때마다 나머지 요소를 모두 이동시키는 시프팅(shifting)이 발생합니다. 

 

 

 

풀이2. 데크를 이용한 최적화

Python의 collections.deque를 사용하여 앞뒤 데이터를 추출하는 작업을 에 수행하도록 최적화합니다.

import collections

def isPalindrome(self, haed: ListNode) -> bool:
    q: Deque = collections.deque()
    
    if not head:
        return True
    
    node = head
    
    while node is not None:
        q.append(node.val)
        node = node.next
        
    while len(q) > 1:
        if q.poplist() != q.pop():
            return False
        
    return True
  • 데크 사용 이유: 데크는 양방향 연결 리스트로 구현되어 있으며, popleft()와 pop() 모두 로 실행됩니다.
  • 시간 복잡도 개선: 리스트 기반 풀이에서 O(n^2)가 걸리던 탐색이 로 최적화됩니다.

성능 비교

  • 리스트 풀이: 약 164ms
  • 데크 풀이: 약 72ms
    데크를 사용하면 두 배 이상의 성능 향상을 기대할 수 있습니다.

 

 

풀이3. 런너를 이용한 풀이

런너 기법을 사용하면 추가 공간 없이 Palindrome 여부를 검사할 수 있습니다. 연결 리스트를 절반으로 나누어 앞부분을 뒤집고, 뒤집은 리스트와 나머지 리스트를 비교합니다.

def isPalindrome(self, head: ListNode) -> bool:
    rev = None
    slow = fast = head
    
    # 연결 리스트를 절반으로 나누며 앞부분을 뒤집기
    while fast and fast.next:
        fast = fast.next.next
        rev, rev.next, slow = slow, rev, slow.next
    
    # 리스트의 길이가 홀수일 경우 중앙값을 건너뜀
    if fast:
        slow = slow.next
    
    # 뒤집은 앞부분과 뒷부분을 비교
    while rev and rev.val == slow.val:
        slow, rev = slow.next, rev.next
    
    return not rev

 

  • 런너 기법: 두 포인터 slow와 fast를 사용합니다. fast는 두 칸씩, slow는 한 칸씩 이동하여 연결 리스트를 절반으로 나눕니다.
  • 리버스(rev) 사용: slow가 이동할 때마다 앞부분을 rev로 역순 저장합니다.
  • 중앙값 처리: 연결 리스트의 길이가 홀수일 경우, 중앙값을 건너뛰고 비교를 시작합니다.
  • 공간 복잡도: 추가 공간 사용 없이 연결 리스트를 직접 수정하여 작업하므로 입니다.
728x90
반응형