muntari Log muntari Log

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

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

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

자료구조 데이터를 저장하고 관리하기 위해 사용하는 구조 자체를 의미하기도 하며, 데이터의 효율적인 접근 및 조작을 가능하게 해주는 저장 및 관리 방식이다. 프로그래밍시 다양한 성격의 데이터를 접하게된다. 결국 프로그래머는 어떤 데이터를 다루고, 저장하고, 저장한 데이터를 가져올 수 있어야한다. 이때, 여러 상황에 적합한 자료구조를 선택하여 적용 할 수 있어야한다. 어떤 자료구조를 이용하는지에 따라 1초가 걸리기도 하고 100초가 걸리기도 한다. 이는 어떠한 서비스로 예를 들어도 매력적인 서비스는 결코 아닐 것이다. 자료구조는 데이터를 효율적으로 사용하기 위함인데, 그렇다면 컴퓨터에 데이터가 어떻게 저장되는지 알아보자. 크게 아래 두 곳에 데이터를 저장한다. 1. 스토리지 데이터가 영구적으로 저장되는 곳으..