📝 Computer Science/✏ Data Structure

자료구조 정리

자료구조 정리 1. 선형 구조와 비선형 구조 2020.04.24 - [📝 Computer Science/✏ Data Structure] - 선형 구조(Linear Structure)와 비선형 구조(Non-Linear Structure) 선형 구조(Linear Structure)와 비선형 구조(Non-Linear Structure) 1. 선형 구조 데이터를 연속적으로 연결되어 있는 모양으로 구성한다. 1) 배열(Array) 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합이다. 빠른 접근(O(1))과 random access가 tech-interview.tistory.com 2. 이진 트리 2020.04.24 - [📝 Computer Science/✏ Data Structure] - ..

알고리즘 성능 분석

알고리즘을 평가하는 데 있어 수행 시간과 메모리 사용량을 평가기준으로 두는데, 수행 시간에 해당되는 것이 시간 복잡도, 메모리 사용량에 해당되는 것이 공간 복잡도이다. 보통 알고리즘의 성능 분석은 복잡도를 계산하여 점근적 표기법으로 나타낸다. 점근적 분석 입력 값의 개수에 따라 알고리즘의 수행 시간을 바탕으로 알고리즘의 효율성을 평가한다. 1) 빅오 표기법 O 점근적 상한선으로 점근적 증가율이 f(N)을 넘지 않는 모든 함수들의 집합이다. 즉, 최고 차항의 차수가 f(N)과 같거나 더 작은 함수들의 집합이다. f(N)

해시(Hash)

해시(Hash) 적은 자원으로 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것이다. 해시 함수를 사용하여 저장할 데이터와 연관된 고유한 숫자를 만든 뒤 이를 인덱스로 사용한다. 내부적으로 배열을 이용하여 데이터를 저장하기 때문에 빠른 검색 속도(O(1))를 갖는다. 1. 해시 함수(Hash Function) 저장할 데이터와 연관된 고유한 숫자(Hash Code)를 만든다. 저장되는 값들의 key 값을 해시 함수를 통해 작은 범위의 값들로 바꾼다. 2. 해시 테이블 해시 테이블은 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조로 임의의 원소를 해시 테이블에 저장하려면 해시 함수를 통해 해시 값을 계산하고 해시 값에 따라 저장한다. 3. 충돌(Collisi..

그래프(Graph)

그래프(Graph) 정점(Vertex)과 간선(Edge)의 집합이다. 방향성(Directed) 그래프: 간선에 방향성이 포함된 그래프이다. 무방향성(Undirected) 그래프: 방향성이 없는 그래프이다. 가중치(Weight) 그래프: 간선에 가중치 정보가 포함된 그래프이다. 부분(Sub) 그래프: 그래프의 일부 정점 및 간선으로 이루어진 그래프이다. 1. 구현 방법 1) 인접 행렬 정점(V)의 수만큼 2차원 배열을 만들고 인접하면 1, 인접하지 않으면 0을 넣는 방법으로 메모리 낭비(V^2)가 있으나 밀도가 높은 그래프 표현에 적합하다. 2) 인접 리스트 각 정점마다 리스트를 만들고 인접해 있는 정점들을 연결한 방법으로 검색 시간이 오래 걸리지만 메모리 낭비가 없다. 2. 그래프 탐색 1) 깊이 우선 ..

이진 트리(Binary Tree)

이진 트리(Binary Tree) 어떤 노드의 자식 노드의 수가 최대 2개를 넘지 않는 트리이다. 포화(Perfect) 이진트리: 모든 레벨이 꽉 찬 이진트리이다. 완전(Complete) 이진트리: 위에서 아래로, 왼쪽에서 오른쪽으로 차례대로 채워진 트리이다. 사향 이진트리: 한쪽으로 기울어진 트리로 탐색 시간은 O(N)이다. 1. 이진 탐색 트리(Binary Search Tree) 탐색 시간이 평균 O(logN)으로 효율적인 탐색이 가능하다. 각 노드의 자식이 2개 이하이다. 각 노드의 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 크다. 중복된 값의 노드가 없어야 한다. 2020.04.29 - [📝 Computer Science/✏ Algorithm] - [C] 이진 탐색 트리(BST) [C] 이..

선형 구조(Linear Structure)와 비선형 구조(Non-Linear Structure)

1. 선형 구조 데이터를 연속적으로 연결되어 있는 모양으로 구성한다. 1) 배열(Array) 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합이다. 빠른 접근(O(1))과 random access가 가능하다. 논리적 저장 순서와 물리적 저장 순서가 일치하기 때문에 인덱스로 해당 원소에 접근할 수 있다. 인덱스란 배열의 요소를 간단히 구별하기 위해 사용하는 번호이다. (0 ~ n-1) 정적인 자료 구조로 기억 장소의 추가가 어렵고 데이터 삭제 시 데이터가 저장되어 있던 기억 장소는 빈 공간으로 남아있어 메모리 낭비가 발생한다. 2) 배열 리스트(Array List) 배열과 같이 연속되는 기억 장소에 차례대로 데이터가 저장되지만 빈 공간이 없다. 기억 장소를 연속적으로 배정받기 때문에 ..