Computer Science/Data Structure
비순차적(비선형) 자료구조 - 트리
순차적 자료구조는 어떠한 '순서'를 가지고 데이터가 저장 공간에 저장되었습니다. 비순차적 자료구조는 트리구조와 같이 계층적 구조를 가지는 자료구조입니다. 한 노드의 다음의 노드가 여러 개일수 있기 때문에 탐색을 구현하기 복잡하지만, 메모리를 좀 더 효율적으로 활용할 수 있다는 장점이 있습니다. 트리 가계도나 회사 조직도와 같이 위아래의 개념을 컴퓨터로 표현한 자료구조이며, 루트 노드와 부모-자식 관계의 서브 트리로 구성됩니다. - 간선(엣지, 링크) : 노드 사이의 연결을 의미 - 크기 : 자신을 포함한 자식 노드의 개수 - 루트 : 최상위 노드 - 리프 : 가장 하위에 있는 노드들 - 높이 : 루트 노드부터 가장 멀리 떨어진 리프까지 간선의 수. 가장 높은 레벨과 동일함 - 깊이 : 현재 노드에서 목적..
순차적(선형) 자료구조 - 해시 테이블
어떠한 'key'값을 입력하면 'value' 값을 출력하고 싶을 땐 어떤 자료구조를 사용해야 할까요? 예를 들면, '학번'을 입력하면 '이름'을 출력하는 프로그램을 만든다고 가정해봅시다. 앞서 배운 배열에서 인덱스를 이용하여 값에 접근을 했습니다. 이 점을 이용하여 'key'를 인덱스로 하여 값에 접근할 수 없을까요? 해시 테이블을 이용하면 'key'를 이용하여 값에 접근을 할 수 있습니다. 해시 함수 해시 함수는 임의의 크기의 데이터를 고정된 크기의 값으로 매핑시켜주는 함수를 말합니다. 그래서 패스워드와 같은 민감한 데이터를 저장할 때 해시 함수를 사용하기도 합니다. 해시 함수를 사용하는 것을 '해싱(hashing)'이라고 부르기도 합니다. 자료구조의 관점에서 해시 함수는 'key'를 인덱스로 매핑하는..
순차적(선형) 자료구조 - 연결 리스트
연결 리스트는 앞서 살펴본 배열과는 다르게 데이터가 물리적인 메모리에 연속적으로 저장되지 않습니다. 즉, 메모리 어딘가에 데이터가 흩뿌려진 듯하게 저장되어 있습니다. 그래서 인덱스로 접근이 가능했던 배열과는 다르게 앞에서부터 차례대로 찾아야 합니다. 연결 리스트(Linked List) 연결 리스트를 알기 위해서는 노드를 알아야 합니다. 노드는 data와 next라는 두 개의 값이 저장되어 있습니다. data에는 말 그대로 요소 값이 저장됩니다. next는 다음 노드의 주소를 가리킵니다. 즉, 노드는 자신의 데이터와 자신과 연결된 이웃 노드가 누구인지만 알고 있습니다. 연결 리스트는 이러한 노드의 집합입니다. 여러 개의 노드가 존재하며 그중 첫 번째 노드는 'head'라고 부르며, 연결 리스트의 시작점을 ..
순차적(선형) 자료구조 - 스택, 큐, 데크
스택은 대표적인 LIFO(후입 선출), 큐는 대표적인 FIFO(선입선출)로 처리되는 자료구조입니다. 파이썬에서는 두 자료구조 모두 리스트로 구현할 수 있습니다. 다만, 큐의 경우 리스트로 구현하면 삭제 연산을 수행 시(pop 연산) 시간 복잡도가 O(n)이 됩니다. 이 문제를 해결하기 위해 양방향 삽입, 삭제가 가능한 데크에 대해서 알아봅시다. 스택(stack) 스택은 아래와 같은 2가지 연산을 지원하는 추상 자료형(ADT)입니다. - push() : 가장 최근에 삽입된 요소 끝에 새로운 요소 추가 - pop() : 가장 최근에 삽입된 요소 제거 파이썬은 스택을 위한 자료구조는 따로 존재하지 않습니다. 다만, 스택이 수행하는 연산 2가지를 리스트의 append와 pop으로 구현할 수 있습니다. 리스트는 ..
순차적(선형) 자료구조 - 배열 또는 리스트
순차적 자료구조는 활용도가 굉장히 높으므로 완벽히 이해하고 있어야 하는 자료구조입니다. 요소가 순차적으로 배열되어 있어 선형(Linear) 자료구조라고 부르기도 합니다. 배열(array) 또는 리스트(list)는 가장 기본적이고 순차적인(sequential) 자료구조입니다. 메모리에 요소 값이 순서대로 들어가기 때문에 인덱스만 알면 해당 값을 한 번에 탐색이 가능합니다. 순차적 자료구조의 종류 - 배열(Array) 또는 리스트(List) - 스택(Stack) - 큐(Queue) - 데크(Dequeue) - 연결 리스트(Linked List) 배열(정적 배열) 파이썬은 정적 배열을 지원하지 않기 때문에 C언어로 정적 배열에 대해 알아보려고 합니다. C 언어에서 배열을 생성하려면 배열의 요소 타입과 배열의 ..