datastructure
-
[Data Structure] 시간 복잡도, 공간 복잡도카테고리 없음 2020. 2. 11. 15:18
* 시간 복잡도 알고리즘의 수행시간을 분석한 결과를 말한다. 일반적으로 빅오 표기법(Big-O Notation)을 사용해 나타낸다. 1. Big-O 알고리즘의 성능을 수학적으로 표현해주는 표기법. 이를 통해 알고리즘의 시간 복잡도, 공간 복잡도를 표현할 수 있다. Big-O는 알고리즘의 실제 러닝타임을 표기하기보다는 알고리즘의 성능을 예측하는 데 사용된다. 2. 상수(Constants) 위에서 언급했듯, Big-O의 용도는 실제 알고리즘 러닝타임이 아니라, 성능 예측이기 때문에 빅오 표기시 상수는 중요하게 고려하지 않아 제거한다. 3. 표기 - O(1) : Constant Time 입력 데이터의 크기와 상관없이 언제나 일정 시간이 걸리는 경우다. 예를 들어, 연결 리스트의 맨 앞에 노드를 추가하는 작업의..
-
[Data Structure] Stack, Queue카테고리 없음 2020. 2. 9. 20:42
자료를 일정한 규칙에 따라 데이터를 정리하는 것을 자료구조(Data Structure)라고 한다. 자료를 효율적으로 저장하고 관리하기 위해서 자료구조를 알맞게 활용하는 것이 중요하다. 1. 스택 (Stack) 스택은 한 방향에서만 자료를 넣고 뺄 수 있는 구조를 의미한다. Stack의 사전적 의미는 '쌓다' 이다. 스택을 이해하기 위해서는 책상 위에 쌓아 올려진 책을 생각하면 편하다. 스택의 특징은 마지막으로 들어간 요소가, 제일 먼저 나간다는 데 있다. 이를 LIFO(Last In First Out)라고 줄여 말하기도 한다. 그림으로 보면 더욱 간편하다. 2. 큐 (Que)큐는 스택과 달리 양방향으로 열려 있어, 먼저 들어간 데이터가 먼저 나오는 구조를(FIFO, First In First Out)가지..
-
[Data Structure] Hash Table카테고리 없음 2020. 2. 7. 14:53
* Hash Table 해시테이블은 배열과 연결리스트의 장점을 취한 자료구조이다. 키-밸류 쌍의 자료를 저장한다. 배열과 유사한 구조로 각 칸별로 인덱스가 있다. 그 칸에 자료를 저장할 수 있다. 연결 리스트를 이용해 한 칸에 여러 개의 자료를 저장할 수 있다. * Hash Function 해시함수는 특정 키를 받으면 이를 일정한 규칙(함수)을 통해 해시코드를 만들어낸다. 2. 주어진 key 에 항상 같은 값을 반환 3. 무엇도 저장하지 않고, 그때그때 값을 줌 해시함수의 역할은 자료를 알맞게 구분해 해시테이블에 배분시키는 것이다. 따라서 해시함수가 얼마나 고르게 자료를 해시테이블에 배분하는지가 해시함수 알고리즘을 짤 때 가장 중요한 사항이다. * 예시 candy : sweet 이라는 자료가 있다고 가정..