CS/Algorithm 이론
[Algorithm] 그래프(Graph)
[Algorithm] 그래프(Graph) 용어 그래프(Graph) : 정점(Node / Vertex)과 간선(Edge)으로 이루어진 자료구조 차수(degree) : 각 정점에 연결된 간선의 개수 루프(loop) : 한 정점에서 시작해 같은 정점으로 들어오는 간선 가중치 그래프(Weighted Graph) : 간선에 가중치가 표기된 그래프 무방향 그래프(Undirected Graph) : 그래프의 간선에 방향성이 없을 경우 방향 그래프(Directed Graph) : 그래프의 간선에 방향성이 있을 경우. 이때 자신에게서 나가는 간선을 outdegree, 들어오는 간선을 indegree라고 부름. 사이클(Cycle) : 임의의 한 점에서 출발해 자기 자신으로 돌아올 수 있는 경로를 사이클이라고 부름. Cyc..
[Algorithm] BFS(Breadth First Search), DFS(Depth First Search)
[Algorithm] BFS(Breadth First Search), DFS(Depth First Search) 블러드 필(Blood Fill) 다차원 배열에서 어떤 칸과 연결된 영역을 찾는 알고리즘 BFS(queue), DFS(stack)로 풀수 있음. BFS(Breadth First Search) - 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘. - 모든 칸이 큐에 1번 씩만 들어감이 보장되므로 시간 복잡도는 칸이 N개 일때 O(N). - 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문. - 그래프를 시작점을 루트로 하는 트리라고 생각한다면 height가 작은 노드부터 차례대로 방문하는 전체 탐색 방식이라고 할수 있음. - 현재 보는 칸으로부터 추가되는 인접한 칸은 반..
[Algorithm] 전위/중위/후위 표기법(prefix/infix/postfix)
[Algorithm] 전위/중위/후위 표기법(prefix/infix/postfix) 수식 표기법의 종류 * 연산자: +, -, *, ... 피연산자: 1, 2, 3, ... 1. 전위 표기법 (ex. +AB) 연산자를 먼저 표시하고 연산에 필요한 피연산자를 나중에 표기하는 방법. 2. 중위 표기법 (ex. A+B) 연산자를 두 피연산자 사이에 표기하는 방법으로 가장 일반적으로 사용되는 표현 방법. 이항 연산자 표현이 적합하다. 3. 후위 표기법 (ex. AB+) 피연산자를 먼저 표시하고 연산자를 나중에 표시하는 방법. 컴파일러가 사용하는 것으로 스택을 사용하는 예들 중 가장 빈번하게 등장. 수식 표기법의 변환 1. 중위 -> 전위 중위 표기법으로 표기된 3+2+4*5+3/1 를 전위 표기법으로 바꿔본다...
[Algorithm] 덱 (Deque)
[Algorithm] 덱 (Deque) 덱 (Deque) -정의 Double-ended Queue의 약자로 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조. -연산/함수 (1) push_front(item) : item을 덱의 앞에 넣는다. (2) push_back(item) : item을 덱의 뒤에 넣는다. (3) pop_front() : 덱의 가장 앞에 있는 item을 반환하며 삭제한다. (4) pop_back() : 덱의 가장 뒤에 있는 item을 반환하며 삭제한다. (5) front : 덱의 가장 앞에 있는 item을 반환한다. (6) back : 덱의 가장 뒤에 있는 item을 반환한다. -특징 (1) 스택의 특징과 큐의 특징 모두 가지고 있음 -시간복잡도 (1) 원소 추가: O(1) (2) 원..
[Algorithm] 큐 (Queue)
[Algorithm] 큐 (Queue) 큐 (Queue) -정의 컴퓨터의 기본적인 자료구조 중 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식 -연산/용어 (1) push() : 큐의 제일 앞에 값을 삽입 (=Enqueue) (2) pop() : 큐의 마지막 값을 제거 (=Dequeue, Pull) (3) front(head) : 데이터를 pop할 수 있는 위치 (4) rear(tail) : 데이터를 put할 수 있는 위치 (5) 오버플로우(overflow) : 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우 (6) 언더플로우(underflow) : 큐가 비어 있어 자료를 꺼낼 수 없는 경우 (7) 큐의 길이(size) : rear - ..
[Algorithm] 스택 (Stack)
[Algorithm] 스택 (Stack) 스택(Stack) -정의: 한쪽 끝에서만 원소를 넣거나 뺄수 있는 자료 구조(FIFO-First In Last Out). -연산 1) push(item) : 스택의 가장 위에 원소(item)를 추가 2) pop() : 스택의 가장 위에 있는 원소를 제거 3) isempty() : 스택이 비었으면 참(true)을 반환. 아니면 거짓(false). 4) top() : 스택의 가장 위에 있는 원소를 반환 -특징 1) FIFO-First In Last Out : 가장 최근에 push된 원소가 가장 먼저 pop된다. 2) 활용 : 수식의 괄호 쌍, 전위/중위/후위/표기법, DFS, Flood Fill, 문자열 뒤집기, 재귀 알고리즘, 웹 브라우저 방문기록, 실행 취소 등 ..
[Algorithm] 연결리스트(Linked List)
연결리스트(Linked List) -정의: 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당한다. -특징 (1) 원소들은 메모리 상에 불연속적으로 위치하고 있어도 무방 -종류 (1) 단일 연결리스트(Singly Linked List) -정의: 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킴 (2) 이중 연결리스트(Doubly LInked List) -정의: 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다. (3) 단순 원형 ..
[Algorithm] 배열
배열(Array) - 정의: 메모리 상에 원소를 연속하게 배치한 자료구조. - 특징 (1) 다른 자료구조와 달리 원소를 저장하는 것 이외에 추가적으로 소모되는 메모리의 양(=오버헤드)이 거의 없는 것이 장점 (2) 메모리 상에 원소가 연속해서 있어야 한다는 성질로 인해 cache hit rate(https://parksb.github.io/article/29.html)가 높다는 장점이 있으나 할당에 제약이 걸린다는 단점도 있음 (3) 배열의 길이: 따로 변수를 하나 두어 배열의 길이 저장. 따라서 배열의 길이를 알고 있다고 가정 - 시간 복잡도 (1) 임의의 위치에 있는 원소를 확인/변경: 원소는 연속하므로 O(1) (2) 원소를 끝에 추가: 배열의 길이를 알고 있으니 마지막 위치에 원소를 두기만 하면 ..