[TIL] sys.maxsize / (단일) 연결 리스트 / 파이썬 다중할당

[주절주절]

-

 

[Today I Learned]

# sys.maxsize

import sys

test = sys.maxsize
print(test)

 

+ 최대 이익 산출

# 책 풀이
import sys

def best_profit(prices):
    profit = 0
    min_price = sys.maxsize

    for price in prices:
        min_price = min(min_price, price)
        profit = max(profit, price-min_price)

    return profit

prices = [7,1,5,3,6,4]
best_profit(prices)

- if-else문으로 비교 (X) → min, max 이용하기 (O)

 

# 연결 리스트

- 배열과 함께 가장 기본이 되는 대표적인 선형 자료구조
- 동적으로 새로운 노드를 삽입하거나 삭제하기 간편함
- 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리가 쉽다 (메모리 관리 용이)

- 특정 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야 해서 탐색에 O(n) 시간이 소요된다
- 시작, 끝 지점에 아이템을 추가, 삭제, 추출하는 작업은 O(1)에 가능

+ 구현

Single Linked List

print_all - 모든 노드 값 출력
get_node - 노드 인덱스 알아내기
append - 맨 뒤에 노드 추가
insert - 원하는 위치에 노드 추가
delete - 원하는 위치의 노드 삭제

class Node(object):
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

class SList(object):
    def __init__(self):
        self.head = Node(None)
        self.size = 0

    def print_all(self):
        cur = self. head

        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, idx):
        cnt = 0
        node = self.head

        while cnt < idx:
            cnt += 1
            node = node.next

        return node

    def append(self, data):
        cur = self.head

        while cur.next is not None:
            cur = cur.next
        
        cur.next = Node(data)

    def insert(self, data, idx):
        new_node = Node(data)

        if idx == 0:
            new_node.next = self.head
            self.head = new_node
            return
        
        node = self.get_node(idx-1) # insert될 자리의 앞 노드 호출
        next_node = node.next 
        node.next = new_node
        new_node.next = next_node

    def delete(self, idx):
        
        if idx == 0:
            self.head = self.head.next
            return

        node = self.get_node(idx-1)
        node.next = node.next.next

ㄴ return (빈칸)은 None을 return하라는 의미와 같다.

 

+ 회문 검사

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 혜린
def is_palindrome(head: ListNode) -> bool:

    if not head:
        return True

    vals = []
    node = head

    while node is not None:
        vals.append(node.val)
        node = node.next 

    return vals == vals[::-1]

- 무슨 런너 기법을 사용하면 연결 리스트 그 자체로 우아하게 풀 수 있다는데... 일단 패스 👶

 

# 파이썬 다중 할당

- 2개 이상의 값을 2개 이상의 변수에 동시에 할당하는 것

a, b = 1, 2

 

ex. p는 1을, head는 2→3을 참조하고 있는 상황.

# 다중할당
p, p.next, head = head, p, head.next

① p는 head가 가르키던 2→3을 참조하게 된다.

② p.next는 ① 과정 전의 p가 가르키던 1을 참조하게 된다.

③ head는 원래의 head가 가르키던 3을 참조하게 된다.

 

하지만 다중할당이 아닐 경우...

p, p.next = head, p
head = head.next

① p는 head가 가르키던 2→3을 참조하게 된다.

② p.next는 ① 과정 전의 p가 가르키던 1을 참조하게 된다.

// 여기까진 동일하다.

③ 위의 과정이 모두 반영되어, 2가 담긴 노드의 next가 가르키는 1을 head가 가르키게 된다.

 

파이썬의 강력한 기능인 다중할당을 잘 이용하면 변수 swap등을 할 때 temp 변수를 따로 두지 않아도 된다.

a, b = b, a

ㄴ 참고) https://stacked-stacks.tistory.com/12

 

[질문 노트]

-