JTesseract의 Programming

차이점

-삽입과 삭제 그리고 임의의 원소에 접근하는데 드는 시간

-삽입과 삭제 경우, Linked list

-탐색 시, Dynamic Array

Linked list 

-linked list는 원소들이 메모리 여기저기 흩어져 있고, 각 원소들이 다음 원소를 가리키는 포인터를 가지는 방식으로 구현됨

-임의의 위치에 원소를 삽입, 삭제하는 것이 시간이 오래걸리는 문제를 해결하기 위해 사용

-linked list를 사용하면 특정위치에서의 삽입과 삭제를 상수시간에 할 수 있음

-linked list는 첫번째 node(Head)와 마지막 node(Tail)에 대해 포인터의 가짐

Node(노드) : 사각형으로 표현된 원소와 포인터의 집합들을 list의 Nod라고 부름

struct ListNode
{
	int element; //담고 있는 원소
    ListNode* prev, next; //이전 노드, 다음 노드의 포인터
}

Linked list의 종류

-양방향 연결 리스트(Doubly linked list) : 각 원소가 이전과 다음 원소에 대한 정보를 모두 가짐

-단방향 연결 리스트(Singly linked list) : 각 원소가 다음 원소를 가리키는 포인터만 가짐

Linked list의 장점

-삽입과 삭제가 상수 시간에 이루어짐(포인터만 변경하면 되기 때문에)

Linked list의 단점

-Linked list는 메모리 여기저기에 Node들이 흩어져 있음

-따라서, 탐색의 경우 list의 머리에서 부터 시작해 하나씩 포인터를 따라가며 다음 Node를 찾을 수 밖에 없음

-걸리는 시간은 O(N) - list 길이에 선형 비례

삭제했던 Node 돌려놓기

-Doubly linked list의 장점

-삭제된 Node의 포인터들은 원래 자기가 들어가 있던 위치를 알고 있기 때문에 가능

-다만, 항상 삭제한 순서의 반대로 복구해야함(이전노드나 이후 노드 또한 삭제된 상태에서 수행하면 list를 망가뜨리기 때문)

*C++ STL의 list는 splice()멤버 함수를 통해 잘라 붙이기 연산을 지원하는 대신, list의 크기를 구하려면 O(N)의 반복문을 수행해야함 // 잘라 붙이기 연산을 할 때는 몇 개의 원소가 추가되는지 알 방법이 없기 때문에

반대로, Java,C#은 size()연산을 O(1)에 하는대신 잘라붙이기 연산 포기

동적 배열 : 자료의 개수가 변함에 따라 크기가 변경되는 배열

-메모리 상의 연속적인 공간을 할당

-동적배열은 동적으로 할당받은 배열(new를 통한)을 사용

동적배열은 배열에 비해 다음과 같은 특성을 지님

-resize() 연산 가능 - 배열의 크기를 변경하는 //  배열의 크기 N에 비례하는 시간 걸림

-append()연산 - 주어진 원소의 배열의 맨끝에 원소 추가하는 

동적배열의 메모리 할당방법

-capacity메모리 정책 사용

-메모리를 할당받을 때 배열의 크기가 커질 때를 대비해서 여유분의 메모리(capacity)를 미리 할당받음

-size가 capacity를 넘어서는 경우, 기존메모리 size의 반만큼 늘리고 (결과값이 소수점이면 내림) 배열의 원소를 그쪽으로 옮김

int size; //배열의 크기
ElementType* array; //실제 배열을 가리키는 포인터

동적배열의 append() 연산 시간 복잡도

-size < capacity 경우 O(1) 걸리다가, 

 size  = capacity 경우 재할당 연산을 수행해야 돼서 O(N+M)이 걸림 // N : 원래 원소갯수 , M : 추가 여유 공간 크기

-이를해결하기 위해서 재할당을 할때 마다 정해진 크기(상수)를 확보하는 것이 아니라, 현재 가진 원소의 개수에 비례해서 여유크기를 확보

-이런 식이면, 평균적으로 O(1)이 걸림

*제일 좋은 방법은 배열의 최종 크기를 미리 안다면, 동적 배열의 용량을 사전에 충분히 늘려둬서 재할당에 드는 비용을 없앰 ( C++의 reserver()이용해서)

BFS(Breadth Fist Search)

-탐색 순서로 폭을 우선적으로 함

-노드로부터 같은 거리에 있는 인접 노드를 모두 탐색함

-이러한 특성 때문에 목적까지의 최단 경로(Shortest Path)를 찾을 수 있게 됨

-Queue를 사용

-안 가본 노드가 없을 때까지 모든 노드를 방문하는 소모적 탐색의 방법 중 하나

BFS 규칙

1. 인접 노드가 여러 개 있을 경우 보통 알파벳 순서로 먼저 접근함

탐색 순서 예시

1.시작노드 A의 인접노드인 B,G를 탐색 , 이때 Queue Front(Queue의 첫번째 원소)를 제거하고 B,G를 순서대로 Queue에 삽입

2. 그다음 B와 G의 인접노드인 C,E,H탐색, 마찬가지로 Queue Front를 제거하고 C,E,H를 Queue에 삽입

이러한 작업을 반복하면서 Queue에서 제거된 노드를 순차적으로 나열하면 너비우선 탐색 순서가 됨

<코드 예시>

#include <iostream>
#include <vector>
#include <queue>

//그래프의 인접리스트 표현
std::vector<std::vector<int>> adj;

std::vector<int> Bfs(int start)
{
	//정점 발견했는지 여부
	std::vector<bool> discovered(adj.size(), false);
	//방문할 예정인 정점
	std::queue<int> q;
	//방문한 순서
	std::vector<int> order;
	
	q.push(start);
	discovered[start] = true;
	
	while (!q.empty())
	{
		int here = q.front();
		q.pop();
		order.push_back(here);

		for (int i = 0; i < adj[here].size(); ++i)
		{
			int there = adj[here][i];
			if (!discovered[there])
			{
				q.push(there);
				discovered[there] = true;
			}
		}
	}

	return order;
}

DFS(Depth First Search, 깊이우선 탐색)

-깊이를 우선적으로 추구하는 탐색

-Stack사용

-갈 수만 있다면 끝까지 깊숙히 가 보고, 거기서 길이 없다면 되돌아오는 방식

-갈 수 있는 길을 다 가보고 그래도 가는 길이 없다면 그때가서 탐색을 종료하는 소모적 탐색(Exhaustive Search)의 종류 중 하나(다른 하나는 BFS(너비우선 탐색))

-그래프 순회(Graph Traversal)방법 중 하나

사용하는 경우

1. 어떤 정해진 목적지를 찾는 경우

2. 주어진 그래프 내부의 모든 노드를 찾아가서 필요한 작업을 수행하게 하는 경우

DFS의 규칙

1.막다른 노드에 도착한 경우 막다르지 않은 길을 찾을 때까지 Backtracking(노드를 되돌아가는 행위)

-stack의 pop작업으로 수행

-Backtracking예시 ( A(출발노드)에서 F(목적지노드)까지 갈경우 )

  1. A-G-H순서대로 탐색하면서 들린 노드를 Stack에 Push

  2. H가 막다른 길이여서 막다른 길이 아닐 때까지 Backtracking하면서 Stack에서 Pop

  3. 새로운 길이 나오면 다시 Stack에 Push

2.어떤 길을 따라서 계속 원을 그리며 도는 경우를 막기 위해 "한번 들린 노드는 다시 안간다는 규칙을 추가" 

- 처음 들린 노드를 Stack에 Push를 할 때 들렸다는 표시를 해줌

- 새로운 노드가 나올 때 까지 Stack에서 Pop하면서 Backtracking

-예시(A에서 E까지 가는 경우)

3. 인접한 노드가 여럿 있을 때 어떤 노드로 먼저 가느냐에 대한 규칙

-보통, 알파벳 순서로 함 (어떤 규칙이든 일관성있게 적용하면 됨)

<코드 예시>

#include <iostream>
#include <vector>

//그래프의 인접 리스트 표현
std::vector<std::vector<int>> adj_list_graph;
//각 정점 방문 여부
std::vector<bool> visited;

void dfs(int _start_vertice)
{
	std::cout << "DFS Visits " << _start_vertice << std::endl;
	visited[_start_vertice] = true;
	//모든 인접 정점을 순회
	for (int i = 0; i < adj_list_graph[_start_vertice].size(); ++i)
	{
		int there = adj_list_graph[_start_vertice][i];
		//아직 방문안했다면 방문
		if (!visited[there])
		{
			dfs(there);
		}
	}
}
void dfsAll()
{
	visited = std::vector<bool>(adj_list_graph.size(), false);
	//모든 정점 순회하면서, 아직 방문한적 없으면 방문
	for (int i = 0; i < adj_list_graph.size(); ++i)
	{
		if (!visited[i])
		{
			dfs(i);
		}
	}
}
int main(void)
{
	int num_vertices = 5;
	adj_list_graph = std::vector<std::vector<int>>(num_vertices);
	adj_list_graph[0].push_back(1);
	adj_list_graph[0].push_back(2);
	adj_list_graph[1].push_back(3);
	adj_list_graph[1].push_back(4);
	adj_list_graph[2].push_back(0);
	adj_list_graph[3].push_back(1);
	adj_list_graph[4].push_back(1);
	dfsAll();
}