AIBLOG

제 게시물이 네이버/구글 검색에 뜨지 않는 것을 확인했습니다.. 이런 기운 빠지는 일이.. 손을 좀 봤는데 안 되면 고객 센터에 문의하기로 했습니다.

오늘은 연결 리스트를 활용한 알고리즘 문제를 풀어보겠습니다.

문제는 리트코드 #23. Merge k Sorted Lists 입니다.

https://leetcode.com/problems/merge-k-sorted-lists/

자 시작하겠습니다.

문제

문제: k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하라.

입력: [

1->4->5,

1->3->4,

2->6

]

출력: 1->1->2->3->4->4->5->6

이 문제에는 연결 리스트, 우선순위 큐 대한 개념이 필요합니다.

연결 리스트에 대한 개념은 https://byumm315.tistory.com/entry/%EB%A6%AC%ED%8A%B8%EC%BD%94%EB%93%9C-23-Merge-k-Sorted-Lists여기 있습니다!

우선순위 큐에 대한 개념은 각자 알아봅시다..! 간단해요!

풀이

문제를 풀 때 연결 리스트와 우선순위 큐를 이용합니다. 우선순위 큐를 이용하면 내림차순/오름차순으로 데이터를 추출할 수 있기 때문입니다. 

답안 코드

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def mergeKLists(self,lists: List[ListNode]) -> ListNode:
        root=result=ListNode(None)
        heap=[]
        import heapq
    
        for i in range(len(lists)):
            if lists[i]: 
                heapq.heappush(heap, (lists[i].val,i,lists[i]))
        
        while heap: 
            node=heapq.heappop(heap) 
            idx=node[1] 
            result.next=node[2] 
            result=result.next 
            if result.next: 
                heapq.heappush(heap,(result.next.val,idx,result.next)) 
        return root.next

답안 코드 설명

# 연결 리스트 정의하기

class ListNode:

    def __init__(self, data=0, next=None):

        self.data = data
        self.next = next

class Solution:

    def mergeKLists(self,lists: List[ListNode]) -> ListNode:

    #lists에는 입력값이 들어갑니다.

    #전체적으로 리스트 형태이지만 각 원소는 연결 리스트 형태입니다.

    # 예) [1->3->4,  2->5,  6->1]

        root=head=ListNode(None)

         #ListNode(None)은 data와 next를 None으로 둔 연결 리스트입니다.

         #중요한 개념이 나옵니다. root와 head의 위치를 그림으로 표현하겠습니다.

         #[그림 1]과 같이 root 와 head는 같은 위치에 있는 None 인 연결 리스트입니다.

        heap=[]

        import heapq

         #우선순위 큐를 사용하기 위해 모듈을 import 합니다.

        for i in range(len(lists)):

         #lists의 각 원소는 연결 리스트입니다.

            if lists[i]:   
                heapq.heappush(heap, (lists[i].data,i,lists[i]))

                  #heappush를 이용해서 (연결리스트의 가장 앞에 있는 데이터값, i, 연결리스트)를 heap에 저장합니다. 

                  #예) lists의 0번째 원소, 1->4->5의 경우 (1, 0, 1->4->5)가 heap에 저장됩니다.

       while heap:

       #heap이 비어있을 때까지 계속 while문을 돌립니다.

           #Step 1. while문의 첫번째 단계 (풀어서 설명하겠습니다.)

             node=heapq.heappop(heap)

               #heapq.heappop을 이용하면 가장 작은 원소부터 오름차순으로 heap의 원소가 추출됩니다.

               #추출된 원소는 heap에서 제거됩니다.

               #예) heap=[(1,0,1->4->5), (1,1,1->3->4), (2,2,2->6)]일 때 heappop을 이용하면 (1,0,1->4->5)가 추출됩니다.

               #붉은색 위치의 숫자끼리 비교하면 첫번째, 두번째 원소가 가장 작고 그 중에서 파란색 위치의 숫자끼리 비교하면 첫번째 원소가 가장 작기 때문입니다.

             idx=node[1] 
             head.next=node[2] 

              #head의 뒤쪽 포인터가 node[2] (1->4->5)를 참조하기 때문에 [그림 2]와 같이 변경됩니다.

            head=head.next

             #head의 뒤쪽 포인터가 1->4->5를 참조하기 때문에 head는 1->4->5의 맨 앞 노드 nodeA로 옮겨집니다.

            print(root.next) 

            print(head.next)
            #root.next 는 1->4->5 이고 head.next는 4->5 입니다.    

            if head.next: 
                heapq.heappush(heap,(head.next.data,idx,head.next))

            print(heap)

            #heap은 [(4,0,4->5),(1,1,1->3->4),(2,2,2->6)] 입니다.

        return root.next

           #Step 2. while문의 두번째 단계를 설명하겠습니다. 

            node=heapq.heappop(heap)

              #heappop을 이용하면 가장 작은 원소부터 오름차순으로 heap의 원소가 추출됩니다.

              #추출된 원소는 heap에서 제거됩니다.

              #예) heap=[(4,0,4->5), (1,1,1->3->4), (2,2,2->6)] 일 때 heappop을 이용하면 (1,1,1->3->4)가 추출됩니다.

              #붉은색 위치의 숫자끼리 비교하면 두번째 원소가 가장 작기 때문입니다.

            idx=node[1] 
            head.next=node[2] 

             #head의 뒤쪽 포인터가 node[2] (1->3->4)를 참조하기 때문에 [그림 4]와 같이 변경됩니다.

         head=head.next

          #head의 뒤쪽 포인터가 1->3->4를 참조하기 때문에 head는 1->3->4의 맨 앞 노드 nodeB로 옮겨집니다.

        print(root.next) 

        print(head.next)
        #root.next 는 1->1->3->4 이고 head.next는 3->4 입니다.

           
        if head.next: 
             heapq.heappush(heap,(head.next.data,idx,head.next))

        print(heap)

        #heap은 [(4,0,4->5),(3,1,3->4),(2,2,2->6)] 입니다.
       

   return root.next

이 과정을 반복하다보면 heap이 빈 값이 됩니다. 이때 root.next를 결과값으로 리턴하면 1->1->2->3->4->4->5->6 이 나옵니다.

감사합니다!!!

제가 요즘 코딩 테스트를 준비하면서 자료 구조도 함께 공부하고 있는데요. 연결 리스트라는 큰 난관에 부딪혀서 어려워하고 있습니다. 따라서 저처럼 연결 리스트를 어려워하시는 분들을 위해 게시물을 만들었습니다.

게시물을 읽으신 모든 분들....... 연결 리스트 타파합시다. 화이팅입니다.

'Do it 자료구조' 책의 도움을 많이 받았습니다. 감사합니다.

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=246435695 

오늘의 게시물은 아래 항목으로 나눠집니다.

1. 연결 리스트란?

2. 머리 노드와 꼬리 노드란?

3. 파이썬으로 연결 리스트를 만들어보기 

그럼 시작하겠습니다.

1. 연결 리스트란?

연결 리스트는 데이터를 사슬처럼 연결한 구조입니다. 연결 리스트에서는 각 원소들을 노드라고 부릅니다. 이 노드는 data와 next, pointer 로 구성됩니다. data는 노드의 data, next와 pointer는 뒤쪽 노드(바로 옆에 있는 노드)에 대한 참조를 의미합니다. [그림 1]은 연결 리스트의 기본적인 구조입니다. (연결 리스트 1->3->4 를 나타냈습니다) 

[그림 1]을 설명하자면 node A의 뒤쪽 포인터 next 가 node B를 참조하고 node B의 뒤쪽 포인터 next 가 node C를 참조합니다. 그럼 node C의 뒤쪽 포인터는 무엇을 참조할까요? 더이상 참조하는 대상이 없기 때문에 None을 참조합니다.

만약에 node C를 삭제하고 싶다면 어떻게 할가요? 우선 node A부터 node B까지 이동한 후 node B의 뒤쪽 포인터가 None을 참조하면 됩니다. 연결 리스트에서 특정 노드를 찾을 때 또는 특정 노드에 다가가고 싶을 때 처음 노드부터 연결된 순서로 이동해야 됩니다. 

2. 머리 노드와 꼬리 노드란?

리스트와 다르게 연결 리스트에는 머리 노드가 존재합니다. 머리 노드는 처음 시작하는 노드입니다.

[그림 1]에서는 머리 노드가 node A이겠죠? 이 머리 노드는 또다른 존재 head에 의해서 선택받은 자입니다.

head는 머리 노드를 참조하는 존재입니다.  [그림 1]에서 head는 node A를 참조했으므로 node A가 연결 리스트의 머리 노드입니다.

만약 머리 노드를 새로운 노드 node G로 변경하려면 어떻게 할까요? head가 node G를 참조하여 '얘가 머리 노드이다'라고 선언하면 됩니다. 그리고 node G의 뒤쪽 포인터는 기존의 머리 노드 node A를 참조합니다.

머리 노드가 있으면 꼬리 노드도 있겠죠? node C의 뒤쪽 포인터는 더이상 참조하는 대상이 없기 때문에 None을 참조합니다. 이렇게 뒤쪽 포인터가 더이상 참조하는 게 없는 경우, 해당 노드를 '꼬리 노드' 라고 합니다.

3. 파이썬으로 연결 리스트를 만들어보기 

이번에는 연결 리스트를 파이썬에 입력해봅시다.

우선 코드에 대한 설명을 한 후, 1->3->4->5를 입력해보겠습니다.

이후 연결 리스트를 구현하는 다른 방법을 알려드리고 마치겠습니다.

코드 설명

from __future__ import annotations
from typing import Any, Type

#연결 리스트용 노드 클래스
class Node:

#첫 번째로 head, data, next, current 초기값을 정의합니다.     
    def __init__(self, data:Any=None, next: Node=None):
        #초기화
        self.data=data #데이터에 대한 참조
        self.next=next  #뒤쪽 노드에 대한 참조
        self.head=None #머리 노드에 대한 참조
        self.current=None

        #현재 주목하고 있는 노드에 대한 참조(리스트에서 노드를 검색하여, 그 노드를 주목한 직후에 노드를 삭제하는 등의 용도로 사용됩니다.)
        

#두 번째로 머리 노드를 생성합니다. [그림 2]
    def add_first(self, data:Any)->None:
        ptr=self.head

        #삽입하기 전의 머리 노드, 저희는 머리 노드를 생성하는 단계이니 None이겠죠?
        self.head=self.current=Node(data,ptr)

         #삽입할 노드 node A를 Node(data,ptr)로 생성합니다.

         #해당 노드의 데이터가 data가 되고, 해당 노드의 뒤쪽 포인터가 참조하는 곳은 ptr이 됩니다.  

        return self.head

        
#세 번째로 만들어진 연결 리스트의 끝 노드에 새로운 노드를 삽입합니다. [그림 3]

    def add_last(self, data=Any):
        if self.head is None:

            self.add_first(data)

            #만약에 head가 없는 경우, 앞에서 정의한 add_first함수로 head를 생성합니다.

        else:
            ptr=self.head

            #While문을 이용해서 꼬리 노드를 찾습니다.
            while ptr.next is not None:
                ptr=ptr.next

               #연결 리스트에서 특정 노드를 찾을 때 무조건 머리 노드부터 하나씩 지나면서 이동합니다.

            ptr.next=self.current=Node(data,None)
            #꼬리 노드를 찾았으면 꼬리 노드 옆에 새로운 node D Node(data,None)를 추가합니다. 

            #Node(data,None)에서 새로운 node D의 뒤쪽 포인터가 참조하는 것이 None인 이유는

            #node D가 곧 꼬리 노드가 되기 때문입니다.

            return ptr

구현하기

A=Node() #클래스 할당
A.add_first(1) #머리 노드 지정 (node A)
A.add_last(3) #꼬리 노드에 새로운 노드 추가 (node B)
A.add_last(4) #꼬리 노드에 새로운 노드 추가 (node C)
A.add_last(5) #꼬리 노드에 새로운 노드 추가 (node D)

결과 확인하기 (긴가민가 합니다. 틀리면 바로 댓글 주세요!)

[그림 4]는 앞의 코드 구현한 후 object 항목에서 가져왔습니다. 1->3->4->5가 잘 들어갔는지 확인해보겠습니다.

- 우선 path의 A.head를 봅시다. A.head는 머리 노드 node A를 참조합니다. 따라서 A.head의 data (A.head.data)는 node A의 데이터 1 입니다.  

- path의 A.head.next 를 봅시다. A.head.next는 머리 노드 node A의 뒤쪽 포인터가 참조하는 노드입니다. [그림 3]에 따르면 node B겠죠? 마찬가지로 A.head.next의 data (A.head.next.data)는 node B의 데이터 3 입니다.

- path의 A.head.next.next 를 봅시다. A.head.next.next는 node B의 뒤쪽 포인터가 참조하는 노드입니다. [그림 3]에 따르면 node C겠죠? A.head.next.next의 data (A.head.next.next.data)는 node C의 데이터 4 입니다.

- path의 A.head.next.next.next 를 봅시다. A.head.next.next.next는 node C의 뒤쪽 포인터가 참조하는 노드입니다. [그림 3]에 따르면 node D겠죠? A.head.next.next.next의 data (A.head.next.next.next.data)는 node D의 데이터 5 입니다.

**연결 리스트를 구현하는 방법이 하나 더 있습니다.

https://lsjsj92.tistory.com/461 블로그에서 더 간단한 방법을 찾았습니다. 

근데 코드를 갖고오는게 저작권 침해 같고 걱정돼서 링크만 올렸습니다. 여기서 더 쉽게 구현할 수 있습니다!!

여러분, 사실 이 게시물은 빅픽처입니다. 다음 게시물에서는 리트코드 문제 풀이를 할건데요. 이 문제를 풀기 위해서 연결 리스트 개념이 꼭 필요하답니다. https://leetcode.com/problems/merge-k-sorted-lists/

그럼 곧 봐요!!