TIL - 파이썬

파이썬의 타입 힌트

타입스크립트를 공부하다보니 파이썬에서도 타입 힌드라는 것을 지원한다는 것을 알게되었다. (PEP 484 문서에 추가됨) 이 기능은 파이썬 버전 3.5부터 사용할 수 있으며, '타입에 대한 힌트'를 주는 것이라 볼 수 있다.

def fn(a: int) -> bool:
...

위와 같이 타입 힌트를 사용하게 되면 함수의 파라미터 a가 정수임을 분명하게 알 수 있으며 리턴 값으로 True 또는 False를 리턴할 것이라는 점도 확실히 알 수 있다.

다만 이는 타입 힌트일 뿐, 다음과 같이 사용할 수도 있다.

a: str = 1

이에 대해서 타입 힌트에 대한 오류가 있는지 없는지 자동으로 확인해주는 mypy를 사용하면 타입 힌트가 잘못 지정된 경우 Incompatible return value type 오류가 발생한다.

다음과 같은 방식으로 설치한다.

pip install mypy

리스트 컴프리헨션

파이썬은 map, filter와 같은 함수형 기능을 지원하며 다음과 같은 람다 표현식도 지원한다.

list(map(lambda x: x+10, [1,2,3]))

// [11, 12, 13]

자바는 2014년에 출시된 8 버전에 이르러서야 람다 표현식을 지원하기 시작한 데 반해, 파이썬은 이미 1.0버전, 즉 1994년부터 람다를 지원했을 만큼 역사가 오래 됐다. 그러나 사실 파이썬의 훨씬 더 유용한 기능은 리스트 컴프리헨션(List Comprehension)이다.

리스트 컴프리헨션이란, 기존 리스트를 기반으로 새로운 리스트를 만들어내는 구문으로 파이썬 2.0부터 지원되었으며, 하스켈(Haskell) 같은 함수형 언어에서 기능을 차용해온 파이썬의 대표적인 특징이기도 하다. 무엇보다 람다 표현식에 map이나 filter를 섞어서 사용하는 것에 비해 가독성이 훨씬 높다.

빗물 트래핑(리트코드 42번 문제)

입력

[0,1,0,2,1,0,1,3,2,1,2,1]

출력

6

 

풀이1. 

 

 이 문제는 모든 공간을 차례대로 살펴보면 O(n^2)에 풀이가 가능하다. 그러나 시간 복잡도가 너무 높기 때문에 좀 더 효율적인 풀이를 찾아야 한다. 첫 번째로 투 포인터로 풀어보자. 다음 칸의 빈칸을 채워보자.

 

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        volume = 0
        left, right = 0, ?????
        left_max, right_max = height[left], height[right]

        while ????:
            left_max, right_max = max(????,????), max(????, ????)
            
            if ????:
                volume += left_max - height[left]
                left += 1
            else:
                volume += right_max - height[right]
                right -= 1
        return ????

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        volume = 0
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]

        while left < right:
            left_max, right_max = max(height[left], left_max), max(height[right], right_max)
            # 더 높은 쪽을 향해 투 포인터 이동
            if left_max <= right_max:
                volume += left_max - height[left]
                left += 1
            else:
                volume += right_max - height[right]
                right -= 1
        return volume

 

풀이2. 스택 쌓기

스택을 쌓아 나가면서 현재 높이가 이전 높이보다 높을 때, 변곡점을 기준으로 격차만큼 물 높이를 채울 수 있다. 변곡점을 만날 때마다 스택에서 하나씩 꺼내면서 물 높이를 채워나간다.

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        volume = 0

        for i in range(len(height)):
            # 변곡점을 만나는 경우
            while stack and height[i] > height[stack[-1]]:
                # 스택에서 꺼낸다
                top = stack.pop()

                if not len(stack):
                    break

                # 이전과의 차이만큼 물 높이 처리
                distance = i - stack[-1] - 1
                waters = min(height[i], height[stack[-1]]) - height[top]

                volume += distance * waters

            stack.append(i)
        return volume

 

B Tree & B+ Tree

---

 

이진 트리는 하나의 부모가 두 개의 자식밖에 가지질 못하고, 균형이 맞지 않으면 검색 효율이 선형검색 급으로 떨어진다. 하지만 이진 트리 구조의 간결함과 균형만 맞다면 검색, 삽입, 삭제 모두 O(logN)의 성능을 보이는 장점이 있기 때문에 계속 개선시키기 위한 노력이 이루어지고 있다.

 

#B Tree

---

데이터베이스, 파일 시스템에서 널리 사용되는 트리 자료구조의 일종이다.

이진 트리를 확장해서, 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것이 B-Tree

 

직접 그려볼 수 있는 사이트

https://www.cs.usfca.edu/~galles/visualization/BTree.html

 

자료구조에 대해

https://potatoggg.tistory.com/174

 

자식 수에 대한 일반화를 진행하면서, 하나의 레벨에 더 저장되는 것 뿐만 아니라 트리의 균형을 자동으로 맞춰주는 로직까지 갖추었다. 단순하고 효율적이며, 레벨로만 따지면 완전히 균형을 맞춘 트리다.

대량의 데이터를 처리해야 할 때, 검색 구조의 경우 하나의 노드에 많은 데이터를 가질 수 있다는 점은 상당히 큰 장점이다. 대량의 데이터는 메모리보다 블럭 단위로 입출력하는 하드디스크 or SSD에 저장해야하기 때문! ex) 한 블럭이 1024 바이트면, 2바이트를 읽으나 1024바이트를 읽으나 똑같은 입출력 비용 발생. 따라서 하나의 노드를 모두 1024바이트로 꽉 채워서 조절할 수 있으면 입출력에 있어서 효율적인 구성을 갖출 수 있다. → B-Tree는 이러한 장점을 토대로 많은 데이터베이스 시스템의 인덱스 저장 방법으로 애용하고 있음

 

#규칙

• 노드의 자료수가 N이면, 자식 수는 N+1이어야 함
• 각 노드의 자료는 정렬된 상태여야함
• 루트 노드는 적어도 2개 이상의 자식을 가져야함
• 루트 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야함
• 외부 노드로 가는 경로의 길이는 모두 같음.
• 입력 자료는 중복 될 수 없음

#B+ Tree

---

데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드(not Leaf)가 추가로 있음

(기존의 B-Tree와 데이터의 연결리스트로 구현된 색인구조)

 

B-Tree의 변형 구조로, index 부분과 leaf 노드로 구성된 순차 데이터 부분으로 이루어진다. 인덱스 부분의 key 값은 leaf에 있는 key 값을 직접 찾아가는데 사용함.

 

실습

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

 

#장점

블럭 사이즈를 더 많이 이용할 수 있음 (key 값에 대한 하드디스크 액세스 주소가 없기 때문)

leaf 노드끼리 연결 리스트로 연결되어 있어서 범위 탐색에 매우 유리함

#단점

B-tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+tree는 무조건 leaf 노드까지 내려가봐야 함

#B-Tree & B+ Tree

B-tree는 각 노드에 데이터가 저장됨

B+tree는 index 노드와 leaf 노드로 분리되어 저장됨

(또한, leaf 노드는 서로 연결되어 있어서 임의접근이나 순차접근 모두 성능이 우수함)

 

B-tree는 각 노드에서 key와 data 모두 들어갈 수 있고, data는 disk block으로 포인터가 될 수 있음

B+tree는 각 노드에서 key만 들어감. 따라서 data는 모두 leaf 노드에만 존재

B+tree는 add와 delete가 모두 leaf 노드에서만 이루어짐

 

 

출처

 

파이썬 알고리즘 인터뷰, 박상길 지음, 책만

https://gyoogle.dev/blog/computer-science/data-structure/B%20Tree%20&%20B+%20Tree.html