muntari Log muntari Log

딕셔너리 자바에서의 맵 자료형과 비슷하다고 한다.(맵을 딕셔너리로 이해해도 좋다. 뜯어보면 다른 녀석이지만 말이다.) 이전 추상 자료형들과 달리 데이터의 순서 관계를 약속하지 않는다. Key-value 쌍 데이터를 탐색 / 삽입/ 삭제할 수 있도록 도와주는 자료형이다. 리스트와 마찬가지로 자료형 이름인 딕셔너리(Dictonary)를 그대로 가져와 사용한다. 딕셔너리에서는 탐색/ 삽입 / 삭제 연산은 O(1)의 시간 복잡도를 갖는다. 왜냐하면? 딕셔너리는 해시 테이블 자료구조로 구현되어 있기 때문이다. 해시 테이블에서와 마찬가지로 하나의 key는 하나의 value만 가지고 있어야 한다. 앞서 말했던 바와같이 딕셔너리는 해시 테이블로 구현되어 있기에 충돌이 일어나는 상황에서는 Open Addressing 방..

추상 자료형 (Abstract Data Type) 자료 구조를 "추상화" 한 개념으로 데이터를 어떻게 저장하고 어떻게 사용할 것인지 보다는 오로지 기능만을 생각하여 사용할 수 있게 해주는 자료형? 이라고 보면 될 것 같다. 즉, 어떻게에 대한 생각은 하지 않고 어떤 기능을 하는지만 알고 있으면 해당 기능이 필요한 상황에서 이를 활용할 수 있다. 대표적으로 파이썬의 리스트, 딕셔너리와 같은 자료형을 추상 자료형이라 부른다. 우리가 흔히 알고있는 자료구조는 추상 자료형의 기능 + 구현을 함께 다루는 더 큰 개념으로 이해하자. 사실상 자료구조와 추상 자료형은 다른 의미이다. (자바스크립트에서의 배열은 자료구조의 배열이 아니라는 의미와 같다.) 기능은 연산이 "무엇"을 하는지가 핵심이며 구현은 연산의 기능을 "..

링크드 리스트란? 노드 라는 단위의 데이터를 저장하고 이처럼 데이터가 저장된 각 노드들을 순서대로 연결시켜 만든 자료구조이다. 노드라는 객체가 순서대로 저장된 것 처럼 보이나, 실제 메모리에서는 여기저기 흩어져 있다는 것을 기억하자. 각 노드에서 레퍼런스의 갯수를 기준으로 싱글리 링크드 리스트와 더블리 링크드 리스트로 나뉜다. 이처럼 링크드 리스트는 데이터를 순서대로 저장해주는 자료구조이며 동적 배열과 같이 요소를 계속 추가할 수 있다 (구현 방식이 동적 배열보다 더 복잡하다) 주어진 상황에 따라 링크드 리스트 / 동적 배열 중 어느 자료구조를 적용하여 효율적으로 문제를 해결 할 수 있는지에 대한 감을 찾는것이 중요하다. 노드 (Node) 싱글리 링크드 리스트 각 노드는 하나의 객체로 표현되며 2가지 속..

배열 (Array) 번호와 번호에 대응하는 데이터들로 이루어진 가장 기본적인 자료구조 중 하나이다. (Python 은 C 언어를 기반으로 만들어졌으며, Python의 List 자료형은 C언어의 배열을 기반으로 만들어졌다. 같지는 않다.) 1. 정적 배열 크기가 고정돼 있다. 같은 타입의 데이터만 담을 수 있다. 메모리에 필요한 공간만큼을 미리 할당(예약)한다. 보통 C의 배열에서는 정수하나가 4 Byte를 차지하기 때문에 아래와 같이 크기가 4인 배열은 총 16Byte의 메모리를 차지하게 된다. 이처럼 데이터가 메모리에 순서대로, 연속적으로 저장된다. 배열 접근 순서대로 연속적으로 저장하기 때문에 시작되는 주소를 참고하여 배열의 인덱스에 빠르게 접근할 수 있다. 어떠한 인덱스든 O(1)으로 접근할 수 있..