Linked List 문제

안녕하세요. 집DS입니다. 바쁘다 바빠 현대사회. 제가 하려고 하는 일 중 알고리즘은 매우 중요합니다. 특히 그래프로 대표되는 네트워크 알고리즘까지 해내야 하는 의무가 있습니다.

오늘은 codebastardarch이 주도해준 알고리즘 문제를 풀어본 코드를 올려보겠습니다.

문제 : 4포인터 링크드 리스트 만들기

문제는 다음과 같습니다. 4개의 포인터를 가지는 링크드 리스트 노드를 가지고 위 그림을 완성시킵니다. 그 후 위 링크드 리스트를 ㄹ자로 돌며 각 값을 프린트 합니다. 전자를 build라 하고 후자를 iter라고 합시다

문제 풀이 : build

저는 반드시 재귀함수로 풀겠다 마음먹었습니다. 문제해결 측면에서는 문제를 명확히 이해했다는 것이고 개인적인 측면에서는 간지입니다.
재귀함수에는 세가지를 기억하라고 했습니다. 시작 케이스, 베이스 케이스, 메인 케이스. 이 세가지만 알면 다 푼다고 했지만 그렇습니다. 그럼 가보겠습니다

1. Node정의

노드는 크게 문제 될 것이 없습니다. 그림에서 보듯 위,아래,좌,우 포인터만 있으면 됩니다. 제 눈엔 동서남북으호 보여서 E W S N로 했습니다.

from typing import Optional


class Node:
    def __init__(self,val) -> None:
        self.val = val
        self.E:Optional[Node] = None
        self.W:Optional[Node] = None
        self.S:Optional[Node] = None
        self.N:Optional[Node] = None

프로그래밍 협업시 type hinting은 상당히 중요하다고 합니다. 파이썬은 워낙 유연해서 안해도 되지만, 그래도 본인이 어떤 타입의 데이터를 다루는지 알고있는게 중급으로 가는 길이라고 배웠습니다.

2단계 : 링크드 리스트 만들기

링크드 리스트는 마치 체인처럼 연결되어 있습니다. 디자인 하기 나름이지만 저는 head와 tail을 도입했습니다. 이를 통해 처음과 끝 노드에 접근이 쉽도록 했습니다.
또한 문제가 얼마나 일반화 될 수 있을지 궁금해서 총 길이를 정의 하고 위 그림에서 보이는 링크드 리스트의 폭을 통해 원하는 크기의 링크드 리스트가 만들어 지도록 했습니다

class LinkedList:
    def __init__(self, length:int, width:int) -> None:
        self.head = None
        self.tail = None
        self.length = length
        self.count = 0
        self.width = width
        self.cur_row = 0

위 코드의 cur_row는 이후 build에 쓰입니다

메인 알고리즘 : 3 핑거 알고리즘

제가 본 수업에서는 두 손가락으로 뭔가 구할때 투 핑거 알고리즘이라 했습니다. 저는 build를 위해 3 핑거 알고리즘을 하기로 했습니다. 여기서 사짜의 알고리즘을 설명하자면 다음과 같습니다.
해결해야 하는 서브 프라블럼은 다음과 같습니다.
1. 위아래 노드를 연결하지 않지만 옆으로만 연결하는 경우
2. 옆으로 가다가 끝에 다다라서 밑으로 내려가는 경우
3. 위아래를 연결하며 옆으로 이동하는 경우
4. 종료되는 경우
5. 첫번쨰 노드인 경우

제가 이번에 코드를 써보니 발생하는 빈도가 적은 것을 먼저 쓰고 좀더 일반적인 것을 코드 윗부분에 쓰는게 정신건강에 좋았습니다.그럼 알고리즘 쟁이 처럼 위 내용을 Topologycal sort를 해보면 다음과 같습니다

4 -> 5 -> 1 -> 2 -> 3

위 오더를 명확하게 반영하지는 않았지만 제 코드를 공개하면 다음과 같습니다.

class LinkedList:
    def __init__(self, length:int, width:int) -> None:
        self.head = None
        self.tail = None
        self.length = length
        self.count = 0
        self.width = width
        self.cur_row = 0

    def build(self) -> None:
        self.build_helper()

    def build_helper(self,
                     runner: Optional[Node] = None, 
                     anchor: Optional[Node] = None, 
                     follower:Optional[Node] = None)-> None:

        if self.cur_row > 0:
            self.connect_runner_follower(runner,follower)
        # base case
        if self.count >= self.length:
            self.tail = runner
            print("end")
            return

        new_node = Node(self.count)
        # caset 1 : first node 
        if self.count == 0:
            print(f"At first node {self.count=}")
            self.head = new_node
            anchor = new_node
        # case 2 : go down
        elif self.count % self.width == 0:
            print(f"Go down at {self.count=}")
            anchor.S = new_node
            new_node.N = anchor
            follower = anchor
            anchor = new_node
            self.cur_row += 1
        # case 3 : go right
        else:
            print(f"Go right at {self.count=}")
            new_node.W = runner
            runner.E = new_node
            if follower:
                follower = follower.E



        runner = new_node

        self.count += 1
        self.build_helper(runner,anchor,follower)


        return
        

    def connect_runner_follower(self, runner:Optional[Node], follower:Optional[Node]) -> None:
        if follower and runner:
            runner.N = follower
            follower.S = runner
        return None


    def iter(self):
        cur = self.head
        count = 1
        while cur:
            print(cur.val)
            #go down
            if count == 1:
                cur = cur.E
            elif count % self.width == 0:
                print("down")
                cur = cur.S
            # go right
            elif int(count / self.width) %2 == 0:
                cur = cur.E
            elif int(count / self.width) %2 == 1:
                cur = cur.W
            count += 1



test = LinkedList(25,5)
test.build()
test.iter()
# print(test.head.val)

 

나는야 그림쟁이. 그림으로 설명해보겠습니다.

 

첫 노드가 생겼을 때는 self.head = new_node로 해줍니다. runner와 anchor도 new_node로 해줍니다. 여기서 runner는 매 row에서 가로로 이동하는 노드이며, follwer보다 한줄 앞서 움직이기 때문에 runner라고 했습니다. anchor는 다음 row로 이동할때 도움을 주는 노드 입니다.

오른쪽으로 갈때 새로운 노드를 runner로 정의합니다. anchor는 각 row에서 변함이 없도록 설정했습니다. 새로운 노드를 만들며 이전 노드와 doubly link를 시킵니다.

 

아래로 내려갈때 Anchor가 드디어 사용됩니다. 맨끝에 다다랐을 runner를 achor.S로 할당 합니다. 그리고 이제 두개 이상의 줄이 되었기 때문에 anchor가 원래 가리키고 있던 자리를 follower 로 설정합니다. 이제 하나의 row를 사이에 두고 같은 column위치에 follower와 runner가 위치하게 됩니다.

앞의 내용과 거의 비슷합니다. 이제 follower가 있다는 점만 다릅니다. Runner.N = Follower, Follower.S = Runner만 해결하면 됩니다.

어느 순간이 되면 다음과 같이 종료되게 될 것입니다. 저는 tail을 도입했기 때문에 tail을 설정해줍니다. 

끝맺으며

다시 정리하며 보니 논리적으로 몇개 케이스에서는 틀릴 것이라는 생각이 들었습니다. 그래도 꽤나 고민해서  풀어서 나름 재밌었습니다. 그리고 자문자답 time complexity를 해보자면

build() = O(n)

Iter() = O(N)

일 것이고, 메모리의 경우

build() = O(n)

일 것입니다. 메이비

 

열심히 하는 것보다 중요한 것은 잘하는 것이다
그러나 잘하기 위해서는 열심히 해야 한다
집 DS