내일은 개발을 잘 할 거야

그래프에 대하여

Graphs are widely-used structure in computer science and different computer applications. We don't say data structure here and see the difference. Graphs mean to store and analyze metadata, the connections, which present in data. For instance, consider cities in your country. Road network, which connects them, can be represented as a graph and then analyzed. We can examine, if one city can be reached from another one or find the shortest route between two cities

/*

1. 그래프란?

그래프란, 정점(Vertex)과 간선(Edge)의 집합으로 구성되어있는 비선형 자료구조이다.

오일러 경로 라는 이론에서 출발한다. 

2. 그래프의 구성요소 및 용어

정점(vertex/node) : 노드, 정점... 꼭지점... 무슨 말이 필요하리...

간선(Edge/Link/line) : 각 꼭지점을 연결하는 선. 

차수(degree): 꼭지점에 연결된 간선의 수

인접(adjant): 각기 다른 2개의 꼭지점이 변으로 이어져 있을 때 인접하다고 함. 

경로(path): 첫 정점부터 임의의 정점까지 연결된 순서. 첫 정점은 시작 정점이라고 불리고, 경로의 마지막 정점이 종료 정점이라고 한다.경로 중 한 정점을 최대 한 번만 지나는 경로를 단순경로라고 한다. 

사이클(cycle): 시작정점과 종료정점이 같으면 사이클이라고한다. 한 정점을 한번만 지나는 사이클을 단순 사이클이라고 불린다. 

path (simple)	cycle (simple)

3. 그래프의 종류

1. 간선들간에 방향성이 있는가 없는가에 따라서

없다: 무방향 그래프(무향 그래프, undirected graph)

정점들간에 순서가 없는 그래프. 

(A,B)는 (B,A)와 같다.

무방향 그래프는 트리가 될 수 있다. 

무방향 그래프의 경우에는 최대 변을 가질 수 있다.

n개의 정점을 가진 그래프는 최대 n(n-1)/2개의 변을 가질 수 있다.

이런 그래프를 완전 그래프라고 한다. 

아래 그래프는 무방향 그래프이면서, 완전 그래프이다. 

있다: 방향 그래프(유향 그래프, directed graph)

정점들간에 순서가 있는 그래프

(3,4)는 (4,3)와 다르다. 

방향그래프인 경우 n개의 정점을 가진 그래프가 최대 n(n-1)개의 변을 가질 수 있고

그런 그래프를 완전 그래프라고 한다.

아래는 방향 그래프의 예이다. 

한꼭지점으로 들어오는 변의 갯수를 입력차수, 나가는 변의 갯수를 출력 찻수라고 한다.

아래의 4정점을 예로 들면 입력차수는 1이고 출력 차수는 1이다. 

2정점의 경우 입력차수는 2이고 출력차수는 0 이다. 

(출처: https://upload.wikimedia.org/wikipedia/commons/5/51/Directed_graph.svg)

2. 간선에 가중치가 있는가 없는가에 따라서

가중치 그래프: 간선에 가중치가 할당되어 있는 경우. 여러 도시를 연결하는 도로망을 예로 들면 각 도로의 가중치는 도로의 길이 또는 최소시간이 될 수 있다. 

3. 간선의 수는 어떤가

간선의 수가 최대인가? 

완전 그래프

- 무방향인 경우. 정점이 n개일때, n*(n-1)/2개의 간선을 가진 경우

- 유방향인 경우. 정점이 n개일때, n*(n-1)개의 간선을 가진 경우

간선의 수가 v^2보다 적을 때

희소 그래프(Sparse Graph): 

간선의 수가 v^2에 비례할 때

밀집 그래프(Dense Graph)

4. 기타

부분그래프: 말 그대로 부분그래프! 그래프의 일부를 따로 떼어놓은 그래프

4. 그래프의 표현법

그래프는 크게 인접행렬과 인접그래프로 표현할 수 있다!

인접행렬은 2차원 배열을 사용하고, 인접 그래프는 연결리스트를 사용한다. 

인접행렬은 많은 메모리 공간을 요구하지만, 인접 그래프보다 빠른 접근이 가능하다. 간선이 많은 밀집 그래프에 적합하다.

(희소 그래프의 경우 메모리의 낭비가 발생한다.)

인접 그래프는 적은 메모리 공간을 요구하지만 인접행렬보다 느리다. 

적은 메모리 공간을 요구하는 이유는 인접한 정점들만을 표현하기 때문이다. 

간선의 수가 많지 않은 희소 그래프에 적합하다. 

(출처:http://www.ida.liu.se/opendsa/OpenDSA/Books/TDDD86_2014/html/_images/GraphUD.png)

1. 인접행렬

위의 그림에서 (a)라는 그래프를 인접행렬로 표현한 것이 (b)이다. 

무방향 그래프의 경우 대각선을 기점으로 대칭이다. 

인접하지 않은 경우도 공간을 차지하므로 희소 그래프의 경우 메모리의 낭비가 발생한다. 

2. 인접그래프

위의 그림에서 (a)라는 그래프를 인접 그래프로 표현한 것이 (c) 이다.

5. 그래프의 순회

http://blog.naver.com/PostView.nhn?blogId=kiho0530&logNo=150139178186

DFS순회

:http://enjoypg.com/17

BFS순회

:http://enjoypg.com/18 

트리에 대하여

/*

서론. 

그래프를 먼저 공부하고 트리를 정리했어야했는데 조금 아쉽다.

트리는 그래프의 한 종류이기 때문이다. 

트리로 검색했을 때 중복되어 나오는 결과들은 다음과 같다. 

• 자료들 간에 계층관계를 가진 계층형 자료구조
• 순환을 갖지 않는 연결그래프 
• 비선형 자료구조
• 나무를 뒤집어 놓은 모양새여서 트리라고 부른다
• 이진 트리
• 이진 탐색 트리
• DFS순회/BFS순회
• in-order, pre-order, post-order (전위, 중위, 후위) 순회
• 레드-블랙 트리, AVL
• 기타 그 밖의 용어들(레벨, 차수, 단말 노드, 부모, 형제, 자손 등...)

• 차수(degree)
• 차수란 노드에서 뻗은 가지의 수 중, 가장 많이 뻗은 가지의 수를 트리의 차수라고 말한다.  
• 높이(height)
• 루트 노드부터 시작해서 맨 끝에 있는 리프 노드까지의 깊이
• 깊이
• 루트 노드부터 해당 노드까지의 경로의 길이
• 레벨
• 각 노드의 층의 번호. 

• 루트노드
• 부모노드 
• 자식노드
• 단말노드(리프노드)
• 형제노드 

/*

서론. 

자료구조를 공부하면서 Array를 배웠고, LinkedList를 구현하는 법도 배웠다. 

JAVA 수업을 들으면서 ArrayList를 사용했다.  

얼핏 기억하고 있던 각 자료구조의 특징은 다음과 같다.

• Array는 index로 빠르게 값을 찾을 수 있다.
• LinkedList는 데이터를 삭제하고 삽입하는데 빠르다
• ArrayList는 데이터를 찾는데 빠르지만 데이터의 삽입과 삭제가 느리다.

창피하지만 그 차이가 뭔지 와닿지가 않았고, 이해가지 않았다. 

DP로 자료구조 공부를하면서 이제야 조금 이해했다. 물론, 아직 다 이해하지 못했을 것이다.

이걸 그동안 몰랐다니 넘나 부끄럽지만 나중에라도 다시 이 바보스러움을 느끼기 위해 조금이나마 이해한 바를 정리해본다.

*/

1. array는 뭘까?

array는 뭘까? array는 배열이지. 

일반적으로 array는 array의 크기와 데이터 타입을 함께 선언해야 한다. 

이를테면, 이런식으로

int arr[6]; 

String arr[12];

array는 왜 선언하기 전에 자료형과 사이즈를 함께 적어줘야할까? 뭐 배열이 커질수도 있구 어떻게 될지 알지도 못하는 일인데 말이다.

int arr[6]을 예로 들면, 괄호 안 6은 배열의 길이를 뜻한다. int형 데이터가 들어갈 공간 6개가 메모리 공간에 할당된 것이다.

즉, 특정 자료형의 변수가 들어갈 공간을 몇개나 할당할지를 정한다. 

array는 데이터를 줄줄이 저장한다. 그래서 각 데이터가 줄줄이 저장될 것이기 때문에 자료형을 미리 적어주어야 한다. 

array는 데이터를 찾는게 빠르다. 

왜? index가 있으니까. 이 array는 데이터를 줄줄줄 저장하다 보니까. 위치를 바로 알 수가 있다. 

내가 arr[4]를 찾는다고 하면 arr라는 것의 주소값에서 바로 +4만해서 찾으면 되니까. 검색이 빠르다. 

array[4]에다가 t새로운 값을 넣으면 어떻게 될까? 덮어씌워진다. 

array[4]를 삭제하면 어떻게 될까? 그냥 텅 비어있을 뿐이다. 

그래서 arrayList가 나오게 된다. 

2. List는 뭘까?

나는 넘나 헷갈렸었다. 무엇이? array나 list나 그게 뭔 차이가 있는 건지.

array와 list의 가장 큰 차이점은. 

array는 크기를 정해주어야 한다는 것. index가 중요하다는 것. 

list는 크기가 정해지지 않아도 된다는 것. 순서가 중요하다는 것이다. 

이 차이를 알기 위해 arrayList를 보자.

array에서는 arr[4]에 새로운 값을 대입하면 덮어씌워진다.

array에서는 arr[4]를 삭제하면 텅비어있다. 

arrayList에서 만약 arrList.add()하면 어떻게 될까? 4번째 에다가 더한다면? 그러면 얘는 4번쨰에 들어간다. 

arrayList.remove()하면 어떻게 될까? 다 줄줄이 당겨진다. 

그래서 arrayList에서 값을 맨앞에 넣거나 맨뒤에 넣으면 상관이 없는데 중간에 값을 더하거나, 빼면 오래걸리는 거다. 

대신 array의 성질, 즉 index를 그대로 가지고 있기 때문에 자료를 검색하는데는 빠르다. 

List는 크기를 미리 정해줄 필요가 없다. 쭉쭉 이어진다. 

LinkedList는 그럼 어떨까?

단일 연결리스트, 다중 연결리스트 등. 여러 Linked list가 존재한다. 

단일이든, 다중이든 링크드 리스트는 한 노드에 연결될 노드의 포인터 위치를 가르킨다. 

다중은 앞뒤 모두 다 가르키는 거고, 단일은 뒤에것만 가르키는 거구 

이렇게 되니까, 데이터를 중간에 넣고 뺀다고 해도 이전에 가르치는 값, 다음 값이 가르켰던 값만 연결시켜주면 되니 빠르다.

그렇지만 11번 째 값을 찾는다고 생각해보자. 

그러면 얘는 맨처음부터 굽이굽이 건너가야 한다. 그래서 값을 찾는데는 arrayList나 array보다는 좀 걸린다.