muntari Log muntari Log

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

리스트 데이터 간 순서 관계를 유지할 수 있다. 파이썬 리스트는 동적 배열 자료구조로 구현되어있다. 접근/ 탐색/ 삽입/ 삭제의 기능을 가지고 있다. 큐 데이터간 순서 관계를 유지할 수 있다. 맨 뒤 데이터 추가 맨 앞 데이터 삭제 맨 앞 데이터 접근의 기능 등을 가지고 있다. FIFO First-in-first-out 가장 먼저 들어온 데이터가 가장 먼저 삭제됨을 말한다. (선입선출) 큐는 동적배열과 더블리 링크드 리스트로 구현이 가능하며 파이썬에서는 (deque) 자료형은 더블리 링크드 리스트로 구현되어 있다. 일반적으로 queue는 한쪽으로 들어가고 한쪽으로만 나가는데, deque는 양쪽으로 들어가고 양쪽으로 나갈 수 있다. (스택을 deque로 사용하기도 한다) 파이썬에서는 deque 자료형을 사..

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

Direct Access Table 배열의 인덱스 접근의 시간복잡도는 O(1)이었다. 인덱스는 데이터의 순서에 해당하는 색인, 데이터이다. 이 인덱스를 순서가 아닌 Key라 생각하고 데이터를 저장할 수 있는데 이러한 방식으로 데이터를 저장하고 관리하는 테이블을 Direct Access Table 이라 한다. Key (= 인덱스)라고 생각하고 value에 접근하는 방식이다. 특징 효율적으로 Key - value 쌍을 저장하고 가져올 수 있다. (O(1)) 하지만, 아래와 같이 Key에 해당하는 값이 커질 수 록 낭비하는 공간이 많다. (메모리 낭비가 심하다) 이 문제를 보완하기 위해 해시 테이블이 등장하게 된다. 해시 함수 하나의 Key와 그 Key에 해당하는 value를 합쳐서 Key-value 쌍이라 ..

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

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

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

빅오란 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법이다. 빅오는 점근적 실행 시간을 표기할때 가장 널리 쓰이는 수학적 표기 방법이다. 여기서 점근적 실행 시간이란 간단하게 n이라는 입력값이 무한대로 커질떄의 실행 시간의 추이를 의미한다. 따라서 충분히 큰 입력값에서의 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다. 점근적 실행 시간을 달리 말하면 "시간 복잡도"라 할 수 있다. 시간 복잡도의 사전적 정의 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도를 의미하며, 계산 복잡도를 표기하는 대표적인 방법이 빅오 표기법인 것이다. 빅오로 시간 복잡도를 표현할때는 최고차항만 표기힌다. 4n^2 + 3n +4 ==> O(n^2) 최고 차항만 표기 한다 -> O..