자료구조 & 알고리즘

그래프(Graph) 그래프는 tree의 상위개념으로 그래프(Graph)란 사물을 정점(vertax)와 간선(edge)으로 이루어져있다. 그래프는 두 가지 방식으로 구현할 수 있다. 인접 행렬(adjacency matrix): 2차원 배열을 사용하는 방식 인접 리스트(adjacency list): 연결 리스트를 이용하는 방식 인접 행렬(Adjacency Matrix) 인접행렬(adjacency matrix)에서는 그래프를 2차원 배열로 표현한다. 가중치가 0인 경우와 대비하기 위해 ∞로 표시하기도 한다. 인접행렬 - 무방향 무가중치 그래프 모든 간선이 방향성을 가지지 않는 그래프를 부방향 그래프라고 한다. 모든 간선에 가중치가 없는 그래프를 무가중치 그래프라고 한다. 무방향 비가중치 그래프가 주어졌을 때 ..

트리(Tree) 트리는 가계도와 같이 계층적인 구조를 표현할 때 사용할 수 있는 자료구조이다. 나무(tree)의 형태를 뒤집은 것과 같이 생겼다. 트리에서는 부모와 자식관계, 형제관계가 성립한다. 트리(Tree) 용어 정리 루트 노드(root node): 부모가 없는 최상위 노드 단말 노드(leaf node): 자식이 없는 노드 -> (이때 5리프와 23리프끼리는 17이라는 같은 부모를 두었으므로 형제관계에 속한다고 볼 수 있다.) 깊이(depth): 루트노드에서의 길이(length) -> 길이란 출발노드에서 목적지 노드까지 거쳐야 하는 간선의 수를 의미한다. 트리의 높이(height): 루트노드에서 리프노드까지의 길이를 의미한다. 이진 트리(Binary Tree) 이진 트리(Binary Tree)는 최..

큐(Queue) 큐(Queue)는 먼저 삽입된 데이터가 먼저 추출되는 자료구조이다. 예시) 게임대기 큐는 먼저 대기한 사람이 먼저 게임에 매칭된다. 연결 리스트로 큐 구현하기 큐를 연결리스트로 구현하면, 삽입과 삭제에 있어서 O(1)을 보장할 수 있다. 연결리스트로 구현할 때는 머리(head)와 꼬리(tail) 두개의 포인터를 가진다. 머리(head): 남아있는 원소중 가장 먼저 들어온 데이터를 가리키는 포인터 꼬리(tail): 남아있는 원소중 가장 마지막에 들어온 데이터를 가리키는 포인터 삽입할 때에는 꼬리(tail)위치에 데이터를 넣는다. 삭제할 때에는 머리(head)위치에서 데이터를 꺼낸다. 큐 동작속도: 배열(Array) vs 연결리스트(Linked List) 다수의 데이터를 삽입 및 삭제할때에 ..

스택(Stack) 스택: 먼저 들어온 데이터가 나중에 나가는 자료구조 흔히 박스가 쌓인 형태를 스택(stack)이라고 한다 우리가박스를쌓은뒤에꺼낼때는,가장마지막에올렸던박스부터꺼내야한다. 새로운 원소를 삽입할 때는 마지막 위치에 삽입한다. 새로운 원소를 삭제할 때는 마지막 원소가 삭제된다. Stack 시간 복잡도 연산 시간 복잡도 설명 설명 1 삽입(Push) 𝑂(1) 스택에 원소를 삽입하는 연산 2 추출(Pop) 𝑂(1) 스택에서 원소를 추출하는 연산 3 최상위 원소(Top) 𝑂(1) 스택의 최상위 원소(가장 마지막에 들어온 원소)를 확인하는 연산 3 Empty 𝑂(1) 스택이 비어있는지 확인하는 연산 JS에서의 Stack JavaScript에서 스택을 구현할 때 배열(Array) 자료형을 사용한다. 𝑝..