CS/자료구조

[CS - 자료구조] 이진 탐색 트리 (BST, Binary Search Tree), Red-Black Tree

이진 탐색 트리 (Binary Search Tree) 배경 이진 트리에서 데이터를 효과적으로 찾는 방법을 고민함 데이터를 효과적으로 찾기 위해 데이터를 효과적으로 저장하는 것이 더욱 효율적이다는 아이디어를 고안해냄 개념 이진 트리 기반의 데이터 탐색을 위한 자료구조 (이진 트리 + 데이터 저장 규칙) 데이터 저장과 동시에 정렬을 하는 자료구조 이진 트리의 효율적인 탐색 능력을 가지며, 삽입과 삭제 가능 조건 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 모든 노드에서 위의 조건을 충족 모든 노드는 유일한 키를 가짐 (노드 중복값 없음) operation 시간복잡도 (검색, 저장, 삭제 등) O(logn) worst case : 편향 트리 (skewed tree) → 한쪽으로만 노드가 추가되는 것 이..

[CS - 자료구조] 트리 (Tree), 이진 트리 (Binary Tree)

트리 (Tree) 개념 선형 구조인 큐, 스택과 달리, 비선형 구조로 계층적 관계(Hierarchiral Relationship)를 표현하며 데이터를 저장하는 자료구조 그래프의 한 종류이며, 사이클이 허용되지 않는 그래프 (자기 자신으로 돌아오지 않는) 용어 노드 (Node) : 트리를 구성하는 각각의 요소 간선 (Edge) : 노드를 연결하는 선 루트 노드 (Root Node) : 트리 구조에서 최상위에 있는 노드 단말 노드 (Leaf Node 또는 Terminal Node) : 하위에 다른 노드가 없는 노드 (맨 끝에 있는 노드) 내부 노드 or 비단말 노드 (Internal Node) : 단말 노드를 제외한 모든 노드 (루트 노드도 포함) 레벨 (Level) : 노드가 몇 층인지 나타냄 (루트 노드..

[CS - 자료구조] 그래프 (Graph)

그래프 (Graph) 개념 요소들이 서로 복잡하게 얽혀있는 연결 관계를 정점(vertex)과 간선(edge)으로 표현한 자료구조 스택, 큐처럼 CS의 대표적인 자료구조 중 하나 현실 세계의 많은 것들을 그래프로 나타낼 수 있어서 알고리즘 문제에 그래프 유형이 많음 cf) 트리 또한 그래프의 한 종류이며, 사이클이 허용되지 않는 그래프를 의미함 용어 정점 (Vertex, Node) 데이터가 저장되는 기본 원소 간선 (Edge, Link) 정점간의 관계를 나타내는 선 인접 정점 (Adjacent Vertex) 하나의 정점에서 간선으로 직접적으로 연결된 정점 차수 (degree) 각 정점에 연결되어 있는 간선의 수 진입 차수 (in-degree) : 방향 그래프에서 해당 정점으로 외부에서 오는 간선의 수 진출..

[CS - 자료구조] 해시 테이블 (Hash Table)

해시 테이블 (Hash Table) 배경 직접 주소화 테이블 (Directed Address Table) 의 단점을 보완하기 위해 직접 주소화 테이블 (Directed Address Table) key, value를 저장할 때 key값으로 k를 갖는 원소는 index k에 저장하는 방식 (key를 그대로 인덱스로 쓰는 테이블) key가 적절(배열의 인덱스로 쓰기 적절)하면 상관이 없음 ex) (2,”노정호”), (1,”배준석”), (4,”정재헌”) 만약 (학번, 이름)이나 (아이디, 닉네임) 등의 key, value를 저장하는 상황에 문제가 발생 (201622528, 박강욱) → 배열의 201622528 번째 공간에 value 저장 → 메모리 공간 낭비 발생 (syunxttm, 박강욱) → 배열의 syu..

[CS - 자료구조] 큐 vs 스택 (Queue vs Stack)

Queue 개념 시간 순서상 먼저 들어온 데이터가 먼저 추출되는 선입선출(FIFO, First In First Out) 방식으로 데이터를 저장하는 자료구조 선형 (Linear) 자료구조 Queue Overflow : Queue의 용량보다 데이터를 더 추가하려는 경우 발생 Queue Underflow : Queue가 비었음에도 데이터를 삭제하려는 경우 발생 단순 투 포인터로만 구현하게 되면, push/pop 연산 시 포인터가 증가만 하기 때문에 메모리 공간 낭비 발생 (계속 뒤쪽으로만 추가된다는 의미) 코드 struct Queue { // Property private var array: [Int] private var f: Int private var r: Int private var capacity: ..

[CS - 자료구조] 배열 & 연결 리스트 (Array & Linked List)

Array 개념 연관된 data를 메모리상에 연속적, 순차적으로 미리 할당된 크기만큼 저장하는 자료구조 operation의 time plexity 조회(lookup), 마지막 인덱스에 추가(append), 삭제 : O(1) 이유 random access (즉시 접근) 설명 Array는 데이터가 연속적으로 저장되기 때문에, 한 번의 계산으로 접근 가능 삽입(insert), 삭제(delete) : O(n) 이유 Array의 연속적, 순차적인 특징 설명 데이터가 연속적, 순차적으로 붙어있어야 하기 때문에, 변경이 생긴 곳 뒤에 있는 데이터들은 일일이 자리를 밀거나 땡겨야 함 탐색(search) : O(n) 이유 주소값 하나씩 돌면서 찾는 데이터가 어떤 주소값에 있는지 일일이 확인해야 함 장점 조회(lookup..