-

해시 테이블에 대해서 알아보겠습니다. 핸드폰 전화번호부를 만든다고 생각해볼게요. 이렇게 쭉 데이터를 쌓아보겠습니다. 자료구조는 데이터를 효율적으로 정렬하고 찾기 위해서 사용하겠죠? 그래서, 한큐에 찾기 위해 Hash Table이라는 애를 만들었습니다. Insert와 Delete의 시간복잡도는 O(1)입니다. 최악의 경우 O(n)일 수도 있습니다. (충돌이 났을 때) 아래와 같은 그림처럼 충돌이 일어나면 어떻게 해야 하는가? 이럴 때는, 데이터를 옆에 붙여버리거나, 빈 공간에 할당해줄 수 있습니다. 이 것은 Chaining, Open Addressing 이라고 합니다. 자, 그러면 hash table을 구현해보겠습니다. # Hash table만들기 hash_table = [[] for _ in range(..

잠깐 파이참에 디버거 사용버을 알아보고 갑니다. 버그를 잡는다는 뜻인데, 영상 참조해주세요~

자, 그리고 이번엔는 remove를 만들어보겠습니다. remove는 여러가지 케이스를 고려해줘야 합니다. 1) 자식이 없을 때 2) 자식이 한개일 때 3) 자식이 두개일 때 의 3개의 케이스를 고려해줘야 합니다. 1) 케이스를 봐 볼까요? 여기 보이시는 맨 밑의 노드가 없어진다고 해도 딱히 특별한 변화가 있지 않습니다. 때문에, 그냥 지워주면 됩니다. 그러면 2)의 경우 자식 노드가 하나일 때를 생각해볼게요 30이 지워지면 20이 들어오면 끝납니다. 그런데 자식이 2개면 어떻게 될까요?? 3)의 케이스를 한번 보겠습니다. 이렇게 자식 노드가 2개인 50이 remove되면, 얘의 오른쪽에서 가장 왼쪽에 있는 노드를 찾아와서 맨 위로 넣어줍니다. 여기에서는 60이죠? 그러면 얘를 코드로 한번 표현해보겠습니다..

이진 탐색 트리에 대해 알아보겠습니다. 굉장히 많이 들어본 것 중에 하나입니다. 얘는 root 보다 작은애는 왼쪽, 큰 애는 오른쪽으로 보내줍니다. [50,30,20,40,70,60,80] 만약에 이런 애가 있다고 하면 50을 root로 지정하고, root보다 작은 애는 왼쪽, 큰 애는 오른쪽으로 처리해줍니다. 자, 그렇다면 얘를 왜 쓰는가? 에 대한 의문입니다. 만약 80을 찾는다고 가정했을 때 초기 배열은 [50,30,20,40,70,60,80] 50 -> 80까지 전체를 훑어야 하는데, BST같은 경우는 50 -> 70 -> 80 이렇게 가면 끝입니다. 훨씬 더 간단합니다. 때문에, BST를 씁니다. 탐색에 걸리는 시간 복잡도는 logN ~ N 입니다. 아래와 같은 경우가 최악의 경우입니다. 얘를 ..

그럼 큐는 뭘까요 얘는 앞뒤가 뚫려있는 원통같은 형태입니다. 처음 넣은 것이 가장 처음으로 나옵니다. 상담 전화를 할 때 앞의 대기자가 00명입니다. 라고 나올 때, 처음에 전화연결 한 사람부터 꺼내서 연결시켜주는 것을 생각하면 됩니다. 얘를 코드로 구현해보겠습니다. 여기서 아래와 같이 실행을 시켜주면 p = Queue() p.enqueue(1) p.enqueue(2) p.enqueue(3) print(p.dequeue()) print(p.dequeue()) print(p.isEmpty()) print(p.dequeue()) print(p.isEmpty()) print(p.dequeue()) print(p.isEmpty()) 아래와 같이 나옵니다. 1 2 False 3 True None True

흔히들 듣는 스택에 상식 수준의 간단한 설명입니다. stack은 원통 같은 곳에 데이터를 하나씩 쌓는다고 생각하시면 됩니다. 원통에 1,2,3,4 순서로 들어갔으니, 꺼낼 때는 4,3,2,1 이런 형태로 나옵니다. 얘는 실제로 어디에 쓰여 있을까요? 저희가 지금 쓰고 있는 브라우저가 대표적인 예입니다. stack을 간단하게 파이썬으로 구현해보면 아래와 같습니다. 얘를 node를 이용해서 처리해봅니다. 이런 식으로 Stack을 구현해볼 수 있습니다.

가장 처음으로 설명하고 가는 애가 Linked List입니다. Stack이나 Queue 그리고 다른 것을을 Linked List를 이용해서 구현해볼텐데, Linked List라는 애가 뭘까요? 각 노드가 데이터를 가지고, 포인터로 다음 노드나 이전 노드를 가르키는 형태의 자료구조 형태입니다. 아래와 같이 생긴 형태인데요 근데 이걸 왜 쓰냐하면 자료구조를 배우는 이유와 같습니다. 메모리의 효율적인 사용을 위해서입니다. 앞으로 stack이나 queue에서도 계속 사용하고 있으니, 유의깊게 봐 주셨으면 좋겠습니다. 일단 linked list를 파이썬으로 구현해보겠습니다. 위와 같은 코드로 노드를 연결해서 아래와 같이 나오게 할 수 있습니다. Linked List를 이용해서 다양한 것들을 구현해보겠습니다.