항해 알고리즘 1주차 - 2회차

2회차에 들어왔다 하기 전에 매니저님께서 어제 오늘은 더 어려울거라는 말을 들어서 긴장을 했다
연결리스트 라는 것을 배웠다

연결 리스트란?

추상적 자료형인 리스트를 구현한 자료구조로, Linked List라는 말 그대로 어떤 데이터 덩어리(이하 노드Node)를 저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장한다. 예를 들어 한 반에 있는 학생들의 자료를 저장한다면, 학생 하나하나의 신상명세 자료를 노드로 만들고, 1번 학생의 신상명세 자료에 2번 학생 신상명세가 어디있는지 표시를 해 놓는 방식이다. 쉽게 생각하면 자료를 비엔나 소시지마냥 줄줄이 엮어놓은 것이다.

라고 하는데 솔직히 무슨 말인지 잘 모르겠다고 생각했다 강의를 듣고 나서도 계속 같은 생각이 들었다

아니 뭐 저런거 그냥필요없이 배열쓰면 되지않나? 라는 생각이 들었다

그런생각 을 가지고 문제를 풀기 시작했다.

1.첫번쨰 문제

한마디로 역순 연결리스트 이다.
인자값으로 전해준 연결리스트를 거꾸로 뒤집는 방식이다.
그래서 나는 이전과 생각이 바뀌지 않았기 때문에
아래와 같은 풀이방식으로 해결했다.

1)풀이

  def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        result = []
        if not head:
            return head
        node = head
        while node:
            result.append(node.val)
            node = node.next
        result = result[::-1]
        nodes = head
        while len(result) > 0:
            nodes.val = result.pop(0)
            nodes = nodes.next
        return head

결과는 어떻게든 문제는 넘어갔는데...
시간복잡도와 공간복잡도가 거의 최하위 그룹에 머물렀다
그래서 나는 연결리스트의 구조에대해서 공부 하기 시작했고

결국 이해하는데 시간이 꾀나 걸렸지만 조별 과제톡을 준비 하고 이전 미니 프로젝트 때 팀원이
C++ 언어로 풀이를 진행한 것을 보고
아 어쩌면 연결리스트로 선언한 변수가 우리가 생각한 배열 변수와 완전 다른 방식일수도 있겠다 라는 생각을 하고 그 생각을 기반으로 문제들의 풀이 들을 보았다.

생각의 전환이 되니 신기하게도 차이점이 보이기 시작했다

흔히 생각하는 배열을 변수로 사용하면

a = ["가","나","다","라"]

이런식으로 해서 값을 불러올때 a의 값을 불러서 해결하는 방식이다

근데 연결리스트는 포인터 라는개념이 존재하는 것 같다.

연결리스트의 구조를 비슷하게 생각한다면

a("가","나","다","라")
b=a
a,b("가","나","다","라")

이런식으로 된다 이때 b.next 라는걸 사용하면
포인터인 b가 아래와 같이 이동된다.

a("가",b("나","다","라"))

이때 b값을 None 을 줘서 없애버리면 이점이 신기한게
a에도 값에 영향을 준다는 것이다.

b=None
a("가")

이런식으로 값이 변경된다.
우리가 생각하는 변수는

a = 123
b = a
b = 456

이렇게 한다고 해서
a의 값이 456이 되진않는데 연결리스트와 배열의
사용하는 방법의 제일 큰 차이 점이 저부분 인것같다
그래서 해당 방법을 인지 하면서 조금씩 생각해보니 나머지 문제들이 이해가 되기 시작했고 오늘은 문제를 모두 풀 수 있었다.