그 외 공부/자료구조

해시테이블이란? 해시테이블은 매우 빠른 평균 삽입, 삭제, 탐색연산을 제공하는 유용한 자료구조이다. 해시테이블은 데이터를 key - value 쌍으로 묶어 관리하는데, 국어사전이 낱말들을 적어놓은 방식과 유사하다. 국어사전에서 낱말을 찾아보면, 하나의 낱말에 하나 혹은 이상의 설명들이 적혀있다. 이 때, 낱말을 key, 그에 대한 설명을 value라고 비유할 수 있다. 실제로 파이썬에서 제공하는 dictionary 자료가 대표적인 해시테이블 기반의 자료라고 할 수 있다. 해시테이블의 데이터 저장 방법 해시테이블은 일반적인 배열과는 다르게 자료들을 순차적으로 저장하는 것이 아닌 key값을 인덱스로 저장한다. 예컨대, key가 201503196에 value가 "홍길동"인 데이터를 저장하고자 한다면 0 ~ 2..

더블리 링크드 리스트는 링크드 리스트와 다르게 노드 안에 data와 다음 노드에 대한 정보, 그리고 이전 노드에 대한 정보를 가진다. 따라서 특정 노드를 탐색하거나 리스트 크기를 구할 때는 일반적인 링크드 리스트와 동일한 메서드를 사용할 수 있지만, 노드를 정의할 때와 삽입 및 제거 연산을 해줄 때는 약간은 다른 방식이 필요하다. 먼저, 더블리 링크드 리스트의 노드는 다음과 같다. # 더블리 링크드 리스트의 노드 클래스 class Node: def __init__(self, data): self.data = data self.next = None self.prev = None # 이전 노드에 대한 정보도 저장해준다. 더블리 링크드 리스트의 연산 (삽입, 삭제) 링크드 리스트와는 다르게, 특정 데이터가 삽..

링크드 리스트의 구현 (Node, __init__, __str__) 링크드 리스트를 구현하기 위해선, 각각의 데이터와 다음 데이터에 대한 주소(레퍼런스)를 저장할 '노드' 객체가 필요하다. class Node: def __init__(self, data): self.data = data # 파라미터로 받은 데이터를 저장 self.next = None # 기본값은 None으로 지정 후 추후 다른 노드들과 연결 node_1 = Node(2) node_2 = Node(3) node_3 = Node(5) node_4 = Node(7) 노드 클래스를 생성 후, 데이터가 각각 2, 3, 5, 7인 네 개의 링크드 리스트 노드를 생성해주었다. node_1.next = node_2 node_2.next = node_3..

링크드 리스트는 일련의 데이터들을 연결시켜 각 데이터에 대한 접근과 추가, 삭제 및 여러 연산을 가능케하는 리스트를 말한다. 그것의 기능적 측면이 배열과 매우 유사하기 때문에 두 자료구조의 차이를 묻는 기술면접 질문들이 종종 나온다고 한다. 링크드 리스트와 배열의 차이? -> 메모리상에 데이터를 저장하는 방식이 다르다! 링크드 리스트와 배열의 가장 큰 차이점은 그 둘이 리스트 안에 담길 데이터를 메모리 상에서 어떻게 저장하는지에 있다. 배열은 데이터들을 메모리 상에 연속적으로 저장한다. 즉, 예를들면 메모리상에서 1 ~ 10까지의 영역을 맡아놓고 그 영역 내에서 데이터를 저장한다. 반면에, 링크드 리스트는 데이터를 공간적으로 붙여놓는 것이 아닌 각 데이터에 다음 데이터의 주소에 대한 정보를 갖게 함으로써..

배열은 가장 기본적인 자료구조 중 하나로, 복수의 데이터들을 목적을 위해 하나로 묶어 사용하기 위해 사용된다. 배열에는 저장된 데이터를 추가하거나 삭제하는데 자유로운 동적배열과 그렇지 않은 정적배열이 있다. 정적배열 (Static array) 일반적으로 배열이라고 하면 정적배열을 의미하는 거라고 생각하면 된다. 배열은 실제 데이터(원소)를 저장하기 전에 현재 사용중이지 않은 연속적인 메모리들을 미리 예약해두고 시작한다. 즉, 데이터 저장 전에 "어떤 데이터를 몇 개 저장할 배열을 사용할거야" 라고 배열을 먼저 선언한 후 사용한다. int numArray[4]; 위 코드는 정수형 데이터를 4개 저장할 배열을 만들겠다는 말이다. 이렇게 배열을 선언하면 정수 하나당 4바이트씩 총 16바이트만큼의 연속적인 메모..

자료구조의 이해가 데이터 관리의 효율성을 높인다는 사실을 체감하기 위해선, 컴퓨터가 여러 형태의 데이터들을 어떻게 저장하는지를 알아야한다. 컴퓨터의 데이터 저장소는 크게 두 가지가 있다. 첫 번째는 스토리지라는 곳으로, 우리가 흔히 이야기하는 HDD, SDD가 스토리지이다. 두 번째는 메모리라는 곳으로, 노트북이나 컴퓨터를 구매할 때 이야기하는 RAM이 바로 이 메모리이다. 두 가지 저장소의 가장 큰 차이는 영구성과 휘발성, 그리고 데이터를 처리하는 속도이다. 스토리지는 데이터를 영구적으로 보관할 수 있다. 우리가 컴퓨터에 저장해놓은 영화, 음악, 과제파일 등.. 모두 우리가 직접 지우지 않는다면 계속 스토리지에 남아있다. 반면에 메모리는 데이터를 일시적으로만 보관한다. 따라서, 메모리에 데이터가 저장되..