파이썬알고리즘인터뷰 8장 연결리스트

오늘 TIL 3줄 요약

• 재귀, 연결리스트 활용 500배

TIL (Today I Learned) 날짜

• 2022.10.10~2022.10.14

  
  

오늘 읽은 범위

• 파이썬 알고리즘 인터뷰 8장 연결리스트

책에서 기억하고 싶은 내용을 써보세요.

• 런너 기법- 2칸씩 이동하는 포인터 fast와 느린 런너(1칸씩 이동) slow를 둔다. 빠른 런너가 먼저 리스트 끝에 도달하면, 느린 런너는 리스트의 중간 지점을 가리킨다. 이런 방식으로 중간 위치를 찾아내면, 값을 비교하거나 뒤집기를 시도하는 등 활용도가 많다.

• 아래 파이썬의 변수다중할당 부분

• def isPalindrome(head):
    # 중략
    rev, rev.next, slow = slow, rev, slow.next
    # 위 다중할당은 아래와 같이 바꿔주면 가독성이 좋다.
    rev, rev.next = slow, rev
    slow = slow.next
    # 두줄로 나눈 위 할당으론 풀수 없다.
    #  rev, rev.next = slow, rev 구문에서 slow와 rev는 동일한 참조가 되어버린다.
    ```
    파이썬에는 원시타입이 존재하지 않고 모든 것이 객체이기에
    "=" 연산자를 사용해 할당하면 값을 할당하지 않고 불변 객체에 대한 참조를 할당하게 된다.
    이를 참고해 위 코드에 대입해 이해해보자
    ```
    # rev = 1, slow = 2->3 (연결리스트)일때
    rev, rev.next, slow = slow, rev, slow.next
    # 이 경우 rev = 2->3 , rev.next = 1, slow = 3 이 되고, rev.next = 1 이므로
    # 최종적으로 rev = 2->1, slow = 3이 된다.
    # 다중 할당으로 위 작업이 동시에 일어나기 때문에 한번의 트랜잭션으로 끝나게 된다.
  
    # 그러나
    rev, rev.next = slow, rev
    slow = slow.next
    # 위와 같이 두 줄 분기 코드로 나눠서 처리하는 경우
    # 첫줄 실행 결과 rev = 2->1 이 되고, 
    # 동일한 참조인 rev = slow 가 됐기 때문에 slow 또한 2->1이 되어버린다.
  
    
  

   

오늘 읽은 소감은? 떠오르는 생각을 가볍게 적어보세요

• 변수다중할당을 쓴 코드 1줄을 이해하기 위해서 파이썬의 = 연산자의 할당 방식, 다른 언어의 원시 타입 등을 찾아봐야했다.
• 다르게 말하면, 코드의 가독성을 높이고 효율적인 코드를 짜려면 언어들의 작동 방식, 특성을 잘 이해해야한다는 뜻이 아닐까
• 재귀는 어렵다. 함수 호출이 중첩되면서 내려가면 뒤죽박죽이 된다..
• 백준을 통해서는 연결리스트와 관련한 문제들을 접하지 못했는데, 책의 리트코드 예제를 통해 연결리스트, 노드를 활용하는 방법을 배울 수 있었다. 실제 연결리스트 구조의 데이터를 처리하려면 단순 노드들의 value만 스왑해주는 식으론 해결할 수 없기에 더 익숙해져야할듯하다.