문과생이 이해한 파이썬 연결리스트1(다항식 덧셈 프로그램)

class ListNode:
    class Node:
        def __init__(self, coef, expon, link):
            self.coef = coef
            self.expon = expon
            self.link = link

    def __init__(self):
        self.Ahead = None;  self.Asize = 0
        self.Bhead = None;  self.Bsize = 0
        self.Chead = None;  self.Csize = 0

    def Ais_empty(self):
        return self.Asize == 0

    def Bis_empty(self):
        return self.Bsize == 0

    def Cis_empty(self):
        return self.Csize == 0

    def A_insert(self, coef, expon):
        if self.Ais_empty():
            self.Ahead = self.Node(coef, expon, None)
        else:
            self.Ahead = self.Node(coef, expon, self.Ahead)
        self.Asize += 1

    def B_insert(self, coef, expon):
        if self.Bis_empty():
            self.Bhead = self.Node(coef, expon, None)
        else:
            self.Bhead = self.Node(coef, expon, self.Bhead)
        self.Bsize += 1

    def C_insert(self, coef, expon):
        if self.Cis_empty():
            self.Chead = self.Node(coef, expon, None)
        else:
            self.Chead = self.Node(coef, expon, self.Chead)
        self.Csize += 1

    def poly_add(self):
        print("다항식 계산중...")
        a = self.Ahead;
        b = self.Bhead;
        self.sum = 0
        while a != None and b != None:     
            if a.expon == b.expon:
                self.sum = a.coef + b.coef
                self.C_insert(self.sum, a.expon)
                a = a.link;
                b = b.link
            elif a.expon > b.expon:
                self.C_insert(a.coef, a.expon)
                a = a.link
            elif a.expon < b.expon:
                self.C_insert(b.coef, b.expon)
                b = b.link
                
        if a is None:   
            self.poly_add2(b)
        elif b is None:
            self.poly_add2(a)
        else:       
            return  
        
    def poly_add2(self, p):
        while p is not None:    
                c_pointer = self.Chead     
                flag = True
                while c_pointer is not None:   
                    if c_pointer.expon == p.expon:  
                        c_pointer.coef += p.coef    
                        flag =False
                    c_pointer = c_pointer.link    
                if flag == True: 
                    self.C_insert(p.coef, p.expon)
                p = p.link  
        
        
    def sorted_List(self):
        follow_pointer=None
        C_pointer=self.Chead
        leading_pointer=self.Chead.link
        flag=False
        
        while True:
            while leading_pointer is not None:
                if C_pointer.expon<leading_pointer.expon:
                    if follow_pointer is not None:
                        follow_pointer.link=leading_pointer
                    C_pointer.link=leading_pointer.link
                    leading_pointer.link=C_pointer
                    flag=True
                        
                    if C_pointer==self.Chead:
                        self.Chead=leading_pointer
                    
                if flag:
                    C_pointer, leading_pointer = leading_pointer, C_pointer
                    flag=False
                    
                leading_pointer=leading_pointer.link
                
            if C_pointer.link is None:
                    break
            follow_pointer=C_pointer
            C_pointer=C_pointer.link
            leading_pointer=C_pointer.link
            
    def print_Clist(self):
        c = self.Chead
        while c:
            if c.link != None:
                print(c.coef, "^", c.expon, "+", end=" ")
            else:
                print(c.coef, "^", c.expon)
            c = c.link


s = ListNode()
s.A_insert(3, 12)
s.A_insert(5, 6)
s.A_insert(1, 2)

s.B_insert(3, 12)
s.B_insert(4, 5)
s.B_insert(2, 2)

s.poly_add()
s.sorted_List()
s.print_Clist()

 

---

#사설이 조금 길다. 넘어가도 좋다. 

 

 현재 알바하는 곳이 참 신기하게도. 팀장님도 교대하는 오빠도 컴퓨터 전공이셨다. 그래서 오늘 조금 진지하게 상담을 받았다. 

 

 연구실 지도 교수님께 석사 제의를 받았다. 교수님께서 대학원 등록금 전액 지원 해주시고 당해 연구실 사정에 따라 가능하면 생활비도 지원해주신다고 하셨다.(물론 내가 한다고 하면) 이제는 전과를 하겠지만 그래봤자 나의 인문대 꼬리표는 끊기지 않을거고. 4년을 온전히 다닌 학생들과 비교하여 나의 경쟁력을 떨어질거다. 하지만 석사 학위가 있으면 다르지 않을까?  

 

 팀장님과 오빠는 서울 강남에 있는 학원을 다녀보라 하셨다. 국비 지원이라 생활비만 해결하면 되고, 6개월 동안 포트폴리오도 잘 쌓을 수 있으며, 코딩 실력이 다니지 않은 사람들보다 훨씬 나아질 것이라고. 

 

 나는 둘 다 할 수는 없다. 집에서 언제까지 나를 지원해 줄 수 있을지 항상 불안불안한 상태다. 

 

 팀장님은 진지하게. 취업이 먼저면 학원을 다니는 게 좋지만. 학원을 다녔다고 해서 무조건 취업할 수 있는 것은 아니다. 깊게 파고 들고 싶은 분야가 있다면 석사를 하는 게 좋지만. 대학원을 다니는 동안 불안할 거다. 동기들은 모두 취업했는데 너혼자 공부하고 있고, 하면서도 내가 이걸로 취업할 수 있을까-에 관한 물음표들이 꼬리에 꼬리를 물어 마음고생이 심할건데. 너가 그걸 버틸 수 있을지도 잘 생각해봐야 한다. 고 말씀하셨다. 

 

 결국 무엇을 선택할지 결정하지 못했다. 

 

 막연히 교수님께서 내주시는 과제만 해결하면 어떻게든 될 지 않았다. 교수님께서도 석사 제의하실 때 말씀하셨다. 내주는 과제를 완벽히 하는 것도 중요하지만 무엇보다 스스로의 로드맵을 잘 설계하는 것이 나의 앞날에 더 도움이 될 것이라고. 

 

 지금은 머리가 좀 복잡해서 있었던 일에 관한 고민들을 간략히 적어놓는다...!!!

 

---

#insert

 insert는 매우 간단하므로 넘어갈거다. 여기서는 노드 하나에 3개의 변수가 잇는데 coef라고 하는 첫번째 변수가 계수이고, expon이 지수이다. 그림처럼 생각하면 될 듯!

 

 

---

#poly_add()

 

 일단 a와 b를 설정한다. 이거는 각 노드를 순회하면서 다항식 덧셈을 하기 위해 사용할거다. self.sum변수는 지수 즉, expon이 같은 노드끼리 coef 변수를 더하기 위해 사용된다. 

 

 

슬슬 감이오시나요???

 

 여기같은 경우 a의 지수가 더 크니까 a만 insert 해준다!

 

 

 

 

여기서 문제점은 현재 a와 b가 가리키는 노드를 잘보면. 현재 a가 가리키는 노드의 지수와 b가 가리키는 노드의 다음 노드의 지수가 같은 걸 알 수 있다. 그런데 코드에 따르면 54줄 elif문을 시행할 수 밖에 없다...!!!!

 

 

그래서 이렇게 연산을 하고 출력하면 다음과 같이 나온다...ㅎ

 

 

 왜 이렇게 나오냐면 아마 a가 None이라서 비교연산 자체가 안 돼서 그런 거 같다. 그래서 b의 남은 노드는 추가 못하고 종료.

 

 

---

#poly_add2()- 여긴 코드 비하인드 이야기이므로 다음으로 넘어가도 좋다.

 

 여기까지가 연구실 오빠 K씨의 코드였고. 이걸 고치려고 머리 싸매고 고민하다가 다른 오빠 Y씨가 고쳐 주셨다. 더 디테일하게 가자면 Y오빠가 준 코드는,

 

 

 64번째 줄부터였는데 어차피 64번째 줄이나, 77번째 줄이나 둘 다 똑같은 코드인데 하나로 만들면 되지 않을까?!해서 내가 고친 코드가 본 코드인거다.(별거아니지만.. poly_add2()에 나의 공도 개미 뒷다리만큼 들어갔다는 말이 하고 싶었다...!) 

 

 

 

 사실 여기서 의문인건 and할 때는 코드가 돌아가는데 반해 or를 할 때는 

 

 이렇게 A와 B의 모든 지수를 맞추면 잘 나오지만 그렇지 않으면 오류가 난다. 왜 그런지는 잘 모르게쑴...

 

---

 #poly_add2()

 

 

  a가 가리키는 연결리스트가 먼저 None이 되어서 강제 while문 종료. 그래서 b노드에 남은 노드가 있쥬? 그래서 poly_add2()의 인자로 b를 넘겨준다. 

 

 

 

 현재 Chead에 있는 노드들의 지수 중에 p가 가리키는 노드의 지수와 똑같은 건 없으므로 77줄의 if문을 실행한다. 

그리고 다음 루프로 이동이동

 

 다음 루프에서는 지수가 똑같은 노드가 있다...!! 그러므로 73줄의 if문 실행하면...!!1

 

 

insert... 종료....

 

 

---

#sorted_List()

 

 여기서 끝내면 참 좋겠지만.. 그러면 출력이 이상하게 된다

 

 계산이 맞긴 맞는데 순서가 엉망진창.(지수가 가장 큰 게 앞에 와야한다)그래서 insert문을 어떻게든 수정하고 싶었는데. 포기하고 그냥 연결리스트를 정렬하는 메소드를 하나 만들었따... 참고로 이 메소드는 내가 3시간 동안 머리 싸매면서 만든 거다. 꺅

 

 

 

 정렬을 할 때 두 가지 경우를 생각 했다. chead앞으로 이동할 때랑 그 외. 코드와 저 도식도를 잘 보고 따라오길 바란당!!!

 

 

 일단 3개의 포인터가 필요하고 각각의 역할은 다음과 같다.(잘 이해가 안 되면 도식도와 같이 보길 바란다)

 

follow : C_pointer의 뒤에서 따라오며, 바꾼 노드를 앞의 노드와 연결해준다

C : leading이 가리키는 노드와 비교하는 기준이 되는 노드

leading : C가 가리키는 노드의 앞을 가리키며 만약 leading이 가리키는 노드의 지수가 더 크면 C노드와 위치를 변경한다(정렬)

 

 flag는 Y오빠가 쓴 코드에 있는데 좀 있어보이길래 한 번 써봤다... 의미는 leading_pointer와 C_pointer의 위치가 바꼈다는 의미. 도식도를 보면 두 노드의 위치가 바꼈을 때(정렬햇을 때) leading과 C포인터가 바뀐 것을 알 수 있다. 각 포인터의 역할 상 위치가 바뀌면 안 되므로 100줄처럼 다시 leading과 C의 위치를 바꿔주었다. 

 

 나머지는 코드를 보면 쉽게 알 수 있으므로 원리만 간단히 설명해봐ㅑ징

 

 

 우선 첫번째 while문에서는 위의 상태를 만들어주고 두번째 while문에서 leading을 저 빨간색 영역에 한해서 계속 이동시킨다. 이동 시키면서 만약 C가 가리키는 지수(expon)보다 큰 지수를 가진 노드가 잇으면 위치를 바꿔준다. leading이 None이 되면 두번째 while문이 끝이 난다.

 

 첫번째 while문에서 C의 위치를 바꿔주고 또 똑같이 두번째 while문으로 들어가 leading을 빨간색 영역 안에서 이동시키며 연결리스트를 정렬한다. 그러면 요로코롬 예쁘게 정렬된.. 연결리스트... 완성...!!!!

 

 

 

 

---

 하하항 이 코드 만들고 수정하고 메소드 추가하고 설명하려고 디버깅만 몇 번 돌리고 핸드 시뮬만 몇 번 한지 모르겠다... 아무튼 성취감 넘쳤떤 다항식 덧셈 프로그램 코드 끗~~