without haste but without rest

https://stackoverflow.com/questions/69192/how-to-implement-a-queue-using-two-stacks How to implement a queue using two stacks? Suppose we have two stacks and no other temporary variable. Is to possible to "construct" a queue data structure using only the two stacks? stackoverflow.com class Queue: def __init__(self): self.inbox = [] self.outbox = [] def enqueue(self, value): self.inbox.append(val..

Reference - https://plas.tistory.com/129 진짜 이차원배열처럼 malloc하는 방법 이차원배열을 어떻게 malloc하느냐는 질문을 받았는데, 쉽지 않은 주제네요. 이차원 배열을 함수 매개변수로 넘기는 방법을 먼저 살펴보겠습니다. C 언어에서 2차원 배열은 포인터의 배열이고 각 포인터는 COLS칸.. plas.tistory.com #include #include int main(void) { /* 진짜 2차원 배열처럼 구현하기 1. 배열 선언 (5 x 3 배열) 2. 헤드 포인터 선언 3. 헤드 포인터 연결 4. 데이터 입력 5. 데이터 출력 */ int count = 0, i, j; int r = 5, c = 3; int len = sizeof(int*) * r + size..

C 로 그래프를 구현하는 중에 이해를 못하는 상황이 발생했다. 파이썬은 딕셔너리 구조를 이용해서 정말 쉽게 구현했고, 메모리 관리를 따로 안 해줘도 되니까 구조 자체에만 집중할 수 있었다. 온라인 강의를 보면서 굉장히 비효율적인 공부를 하다가, 혼자 그래프를 그려보고 직접 생각하면서 이를 코드로 구현하는 게 역시나 정석인 것 같다고 판단했다. 결론: 노트에 구조를 그려보고, 여기에 맞춰서 코드를 짜는 게 오래 남는다. 코드로 그래프를 구현한다는 것은 사람이 눈으로 인식하는 것과는 차이가 있다. 그래프 구조의 특징은 노드가 가지는 숫자가 노드의 개수보다 크지 않고, 중간에 비는 숫자가 없다. (만약 노드가 갖는 숫자가 1부터 순차적인 숫자가 아니라 중간에 훅 건너 뛰는 경우는 배열의 크기를 늘리는 방법을 ..

힙(Heap) 힙은 최대값과 최소값을 빠르게 찾기 위한 이진 트리다. 이진 탐색 트리(Binary Serach Tree)처럼 동일한 이진 트리라는 공통점이 있다. 하지만 트리와 힙은 다르다. 가장 큰 차이점은 힙의 경우 최대값이나 최소값이 루트 노드에 자리잡고 있다는 것이다. 또한 이진 탐색 트리의 경우 링크드 리스트 구조로 각 노드를 연결하는 반면 힙은 배열을 이용한다. 위 이미지의 구조가 트리였다면 level 2에 위치하는 3과 1은 왼쪽 노드에 존재해야한다. 하지만 힙은 삽입 데이터의 크기에 따라서 좌우 정렬을 하지 않는다. 목적 자체가 최소, 최대값을 빠르게 찾기 위함이기 때문에 최대값, 최소값을 루트 노드에 위치 시키는 것이 가장 중요하다. (위 이미지의 경우 최대 힙이므로 자식 노드는 부모 노..

트리(Tree) 트리는 노드(Node)와 브랜치(Branch)로 구성되어있다. 위 이미지에서 원이 노드, 화살표가 브랜치다. 각 노드들은 링크드 리스트 구조로 연결되어 있으며, 싸이클이 없다. 마지막 데이터에서 처음 데이터로 돌아오지 않는다. 아래 애니메이션을 보면 이진 탐색 트리 구조에서 데이터가 어떻게 삽입되는지 쉽게 이해할 수 있다. 21보다 작으면 왼쪽으로, 크면 오른쪽으로 이동한다. 그리고 다음 노드를 만나서 이 단계를 반복한다. 만약 더 이상 비교할 데이터가 없으면 해당 위치에 데이터가 삽입된다. 위 애니메이션에서 21은 루트 노드(Root Node)에 해당한다. 이 값을 기준으로 마치 나무의 가지가 뻗어 나가듯이 데이터가 추가된다. 이진 트리에서는 브랜치가 최대 2개이기 때문에 각 노드는 최..

클로즈 해싱(Close Hashing) 클로즈 해싱은 해시 테이블의 충돌 문제를 해결하는 방법 중 하나로 Linear Probing, Open Addressing 이라고 부르기도 한다. 구조는 간단하다. 위 이미지에서 John Smith와 Sandra Dee의 해시는 똑같이 873이다. 이때 먼저 들어온 John이 873이라는 해시를 먼저 키 값으로 취했고, 다음으로 들어온 Sandra는 바로 다음 값인 874를 키 값으로 가진다. 해시 중복이 발생하면 해당 해시 값부터 순차적으로 빈 공간을 찾기 시작한다. 가장 처음 찾는 빈 공간에 키와 밸류를 저장한다. 저장 효율을 높이는 방법이다. #close hashing class CloseHash: def __init__(self, table_size): se..

오픈 해싱(Open Hashing) 오픈 해싱은 해시 테이블의 충돌 문제를 해결하는 대표적인 방법중 하나로 체이닝(Separate Chaining) 기법이라고도 한다. 만약 해시 값이 중복되는 경우, 먼저 저장된 데이터에 링크드 리스트를 이용하여 중복 해시 데이터를 연결한다. 파이썬에는 굳이 링크드 리스트를 안 쓰고 슬롯을 이중 리스트 구조로 활용해서 간단하게 구현할 수 있다. # open hashing class OpenHash: def __init__(self, table_size): self.size = table_size self.hash_table = [0 for a in range(self.size)] def getKey(self, data): self.key = ord(data[0]) ret..

해시 테이블(Hash Table) 해쉬 테이블은 키와 밸류를 기반으로 데이터를 저장한다. 파이썬에서는 딕셔너리가 있어서 굳이 만들 필요는 없는데, 아무래도 파이썬으로 코드를 짜면 간단해서 파악하기가 쉽다는 장점이 있다. 위 이미지에서 문자열(John smith...) 데이터는 해쉬 함수를 거쳐 숫자로 변경된다. 변경된 이 값(해시)를 배열(buckets)의 키로 삼아 밸류를 저장한다. 따라서 데이터를 서칭하는 과정에서 배열을 순차적으로 탐색할 필요없이 해시 함수를 거쳐 생성된 해시 값으로 데이터를 빠르게 찾을 수 있다. 딕셔너리의 key-value 구조와 유사하다. 키(Key): 인풋 데이터 *ex) John Smith, Lisa Smith 값(value): 저장할 데이터 *ex) 521-8976, 52..