youngmin.log

📢  방향그래프

• 방향그래프(Digraph) : 모든 간선이 방향간선인 그래프

📢  방향그래프 속성

• 모든 간선이 한 방향으로 진행하는 그래프 G = (V,E)에서
  
  👉 간선(a,b)는 a -> b 로는 가지만, b -> a 로는 가지 않는다.
• 그래프 G가 단순하다면 ( 즉, 병렬간선이나, 루프가 없으면 )
  
  👉 M <= N(N-1) 이다.  ( 무방향그래프에선 M <= (N(N-1)/2 였다. )
  ( 여기서 M = 간선 수, N = 정점 수 이다. )
  
  
• 진입간선들(in-edges)과 진출간선들(out-edges)을 각각 별도의 인접리스트로 보관한다면, 진입간선들의 집합과
  진출간선들의 집합을 각각의 크기에 비례한 시간에 조사 가능하다.

📢  방향 DFS

• 간선들을 주어진 방향만을 따라 순회하도록 하면, DFS 및 BFS 순회 알고리즘들을 방향그래프에 특화 가능하다.
• 방향 DFS 알고리즘에서 네 종류의 간선이 발생한다.
  
  👉 트리간선(tree edges) : 트리에서, DFS경로에 해당하는 간선
  👉 후향간선(back edges) : 트리에서 나의 조상방향으로 그려질 간선
  👉 전향간선(forward edges) : 트리에서 나의 자식이 아닌, 더 아래 자식 정점의 경우 그려질 간선
  👉 교차간선(cross edges) : 같은 레벨이나 하위레벨 정점끼리의 연결 간선
  
  
• 정점 s에서 출발하는 방향 DFS  👉  s로부터 도달 가능한 정점들을 결정한다.

• 도달 가능성이란 ?
  
  👉 방향그래프 G의 두 정점 v와 u에 대해, 만약 G에 v에서 u로의 방향 경로가 존재한다면, "v는 u에 도달한다" 또는 "u는 v로부터 도달 가능하다" 를 의미한다.
  👉 s를 루트로 하는 DFS 트리 : s로부터 방향경로를 통해 도달 가능한 정점들을 표시한 것

📢  강연결성

• 방향그래프 G의 어느 두 정점 u와 v에 대해서나 u는 v에 도달하며 v는 u에 도달하면
  
  👉 G를 강연결(strongly connected)이라고 말한다. 즉, 어느 정점에서든지 다른 모든 정점에 도달 가능하다.

• 강연결 검사 알고리즘
  
  👉 1. 그래프 G의 임의의 정점 v를 선택한다.
  👉 2. 그래프 G의 v로부터 DFS를 수행한다. ( 방문되지 않은 정점 w가 있다면, False를 반환한다. )
  👉 3. 그래프 G의 간선들을 모두 역행시킨 그래프 G` 를 얻는다.
  👉 4. G`의 v로부터 DFS를 수행한다. ( 방문되지 않은 정점 w가 있다면, False를 반환. 그렇지 않으면, True 반환)
  
  실행시간 = O(N + M)

• 강연결요소
  
  👉 방향그래프서 각 정점으로 다른 모든 정점으로 도달할 수 있는 최대의 부 그래프
  👉 DFS를 사용하여 O(N + M)시간에 계산 가능하다.

📢  이행적폐쇄

• 주어진 방향그래프 G에 대해, 그래프 G의 이행적폐쇄(Transitive Closure)는 다음을 만족하는 방향그래프 G*
  
  👉 G* 는 G와 동일한 정점들로 구성
  👉 G에 u로부터 v ≠ u 로의 방향경로가 존재한다면, G*에 u로부터 v로의 방향간선이 존재한다.
  👉 더 쉽게, 수학적으로,  "A -> B , B -> C 이면, A -> C"  를  의미하는 것
  
  
• 이행적폐쇄는 방향그래프에 관한 도달 가능성 정보를 제공한다.

• 이행적폐쇄 계산
  
  👉 각 정점에서 출발하여 DFS를 수행할 수 있다.
  
  실행시간 : O(N(N + M)))  👉 N개의 각 정점의 대해 * DFS
  
  
• 대안으로, 동적프로그래밍(DP, Dynamic Programming)을 사용할 수 있다.
  
  👉 Floyed-Warshall 알고리즘 : 위에서 설명한,  "A -> B , B -> C 이면, A -> C"

📢  Floyed-Warshall 이행적폐쇄

• 정점들을 1,2,....n으로 번호를 매긴다.
• 1,2,....,k로 번호 매겨진 정점들만 경유 정점으로 사용하는 경로들을 고려해본다.

Alg Floyed-Warshall(G)
	input a digraph G with n vertexs
    output transitive closure G* of G

Let V(1),V(2),...,V(n) be an arbitrary numbering of the vertexs of G

G(0) <- G
for k <- 1 to n				// Stopover vertex
    G(k) <- G(k-1)
    for i <- 1 to n, i ≠ k		// start vertex
        for j <- 1 to n, j ≠ i,k	// end vertex
            if(G(k-1).areAdjacent(V(i),V(k) & G(k-1).areAdjacent(V(k),V(j))
                if(!(G(k).areAdjacent(V(i),V(j))
                     G(k).insertDirectedEdge(V(i),V(j),k)
return G(n)

• Floyed-Warshall 알고리즘은 G의 정점들을 V(1),....,V(n)으로 번호 매긴 후, 방향그래프 G(0),....,G(n)을 잇달아 계산
  
  👉 G(0) = G
  👉 G에 { V(1),....V(k) } 집합 내의 경유정점을 사용하는 V(i)에서 V(j)로의 방향경로가 존재하면 G(k)에 방향간선
  (V(i), V(j))를 삽입
  
  
• k 단계에서, 방향그래프 G(k-1)로부터 G(k)를 계산
• 마지막에 G(n) = G*를 얻음
• 실행시간 : O(n^3)
  
  👉 전제 : 인접한지 알아보는 areAdjacent( )가 O(1)시간에 수행 ( 즉, 인접행렬 버젼일 경우 )

📢  방향 비싸이클 그래프

• 방향 비싸이클 그래프(DAG, Directed Acyclic Graph) : 방향싸이클이 존재하지 않는 방향그래프
• 예시
  
  👉 클래스 간 상속 또는 인터페이스
  👉 교과 간의 선수 관계 등등
  
  
• 방향그래프의 위상순서(Topological Order)
  
  👉 모든 i < j인 간선 (V(i),V(j))에 대해 정점들을 번호로 나열한 것이다.
  👉 예시) 작업스케쥴링 방향그래프에서 위상순서는 작업들의 우선 d 만족하는 작업 순서
  
  결론 : 방향그래프가 DAG 이면 👉 위상순서를 가지며, 그 역도 참이다.

📢  위상정렬(Topological Sort)

• 위상 정렬(Topological Sort) : DAG로부터 위상순서를 얻는 절차
• 알고리즘
  
  👉 1. topologicalSort : 정점의 진입차수(in-degree)를 이용한 방법
  👉 2. topologicalSortDFS : DFS의 특화된 방법
• 1. topologicalSort : 정점의 진입차수(in-degree)를 이용한 방법

Alg topologicalSort(G)
	input a digraph G with n vertexs
    output a topological ordering V(1),...,V(n) of G,
    or an indication that G has a directed cycle

Q <- empty queue
for each u ∈ G.vertexs()
    in(u) <- inDegree(u)
    if(in(u) == 0)
        Q.enqueue(u)

i <- 1		// topological number
while(!(Q.isEmpty())
    u <- Q.dequeue()
    Label u with topological number i
    i <- i + 1
    for each e ∈ G.outIncidentEdges(u)
    	w <- G.opposite(u,e)
        in(w) <- in(w) - 1
        if(in(w) == 0)
        	Q.enqueue(w)

if(i <= n)	// i = n + 1, for DAG
     write("G has a directed cycle)	// DAG가 아님을 알리는 메시지 

return


// 각 정점에 새로운 라벨을 정의 => 현재 진입차수(inCount) : in(v) => 정점 v의 현재의 진입차수 계산

• 2. topologicalSortDFS : DFS를 활용한 위상정렬

Alg topologicalSortDFS(G)
	input DAG G
    output topological ordering of G
    
n <- G.numVertexs()
for each u ∈ G.vertexs()
    l(u) <- Fresh
for each v ∈ G.vertexs()
    if(l(v) == Fresh)
        rTopologicalSortDFS(G,v)

=========================================

Alg rTopologicalSortDFS(G,v)	// 재귀적 DFS를 활용한 위상정렬
	input graph G, and a start vertex v of G
    output labeling of the vertexs of G
    in the connected component of v

l(v) <- Visited
for each e ∈ G.outIncidentEdges(v)
    w <- opposite(v,e)
    if(l(w) == Fresh)		// 간선 e는 tree 간선
        rTopologicalSortDFS(G,w)

Label v with topological number n
n <- n - 1		// 전역 변수로 제어할 것이다.

• 위상 정렬 알고리즘 비교
  
  1. topologicalSort : 정점의 진입차수를 이용한 버젼
  
  👉 O(N + M) 시간과 O(N) 공간 소요
  👉 그래프 G가 DAG라면 위상순서를 계산
  👉 그래프 G에 방향싸이클이 존재할 경우, 일부 정점의 순위를 매기지 않은 채로 "정지"
  
  2. topologicalSortDFS : DFS 활용한 버젼
  
  👉 O(N + M) 시간과 O(N) 공간 소요
  👉 그래프 G가 DAG라면 G의 위상순서를 계산
  👉 그래프 G에 방향싸이클이 존재할 경우, 허위의 위상순서를 계산 = 방향싸이클을 발견하도록 수정 가능함 !!

📢  그래프순회

• 순회(Traversal) : 모든 정점과 간선을 검사함으로써 그래프를 탐험하는 체계적인 절차
• 주요전략
  
  👉 깊이우선탐색(DFS, Depth First Search)
  👉 너비우선탐색(BFS, Breadth First Search)
  
  

📢  깊이우선탐색(DFS)

• 깊이우선탐색(DFS, Depth First Search) : 그래프를 순회하기 위한 일반적 기법 중 하나.
• 그래프 G에 대한 DFS순회로 가능한 것들
  
  👉 G의 모든 정점과 간선을 방문
  👉 G가 연결그래프인지 결정
  👉 G의 연결요소들을 계산
  👉 G의 신장숲을 계산
  
  
• N개의 정점과 M개의 간선을 가진 그래프에 대한 DFS는 O(N + M)시간 소요
• DFS를 확장하면 해결 가능한 그래프 문제들
  
  👉 두 개의 주어진 정점 사이의 경로를 찾아 보기
  👉 그래프 내 싸이클 찾기
  
  
• 그래프에 대한 DFS는 이진트리에 대한 선위순회와 유사하다. ( 선위순회는 재귀, 즉 스택(Stack)을 활용한다. )
  ( 자료구조 스택을 모른다면, 아래 포스팅을 보고오길 바란다. )

Alg DFS(G)
	input graph G
    output labeling of the edges of G 
    as tree edges and back edges

for each u ∈ G.vertexs()
	l(u) <- Fresh
for each e ∈ G.edges()
	l(e) <- Fresh
for each v ∈ G.vertexs()
	if(l(v) == Fresh)
    	rDFS(G,v)		// 재귀적 DFS 호출

=======================================================

Alg rDFS(G,V)		// 재귀적 DFS
	input graph G and a start vertex v of G
    output labeling of the edges of G in the connected 
    component of v as tree edges and back edges
    
l(v) <- Visited		// 방문한 노드 체크

for each e ∈ G.incidentEdges(v)		// 정점 v에 부착된 간선에 대해
	if(l(e) == Fresh)			// 간선 e가 아직 안지나간 간선이면
    	w <- G.opposite(v,e)			// 정점 v와 간선 e를 통한 반대편 정점 w
        if(l(w) == Fresh)			// w가 아직 미방문 정점이면			
        	l(e) <- Tree			// 일단, 간선 e는 Fresh -> Tree 간선으로 변경
            rDFS(G,w)				// rDFS 재귀호출
        else						// 간선 e가 Fresh한 간선이 아니다 ?
        	l(e) <- Back			// 그럼, 간선 e는 Fresh -> Back 간선으로 변경

• DFS 수행 예시

• DFS 속성
  
  👉 속성 1. rDFS(G,v)는 v의 연결요소내의 모든 정점과 간선을 방문한다.
  👉 속성 2. rDFS(G,V)에 의해 라벨된 트리 간선들은 v의 연결요소의 신장트리(DFS tree)를 형성한다.
• DFS 분석
  
  👉 정점과 간선의 라벨을 쓰고 읽는데 O(1)시간 소요
  👉 각 정점은 두 번 라벨 ( 한 번은 Fresh, 또 한번은 Visited )
  👉 각 간선은 두 번 라벨 ( 한 번은 Fresh, 또 한번은 Tree 또는 Back 으로 )
  👉 incidentEdges( ) ( 한 정점에 붙어있는 부착간선 메소드 )는 각 정점에 대해 한 번 호출
  👉 그래프가 인접리스트 구조로 표현된 경우, DFS는 O(N + M)시간에 수행 ( 어떤 그래프 G의 deg(v) 합 = 2M )
  
  
• DFS 템플릿 활용
  
  👉 연결성 검사, 경로 찾기, 싸이클 찾기 등의 문제들을 DFS를 확장해서 해결할 수 있다.

📢  비재귀적 DFS

• rDFS ( 재귀 DFS )는 이름 그대로, 재귀호출을 통해서 그래프 순회를 한다.
• 비재귀적 DFS는 재귀호출이 아닌, 스택(Stack)을 사용해서 DFS를 실행한다.

Alg DFS(G,v)
	input graph G and a start vertex v of G
    output labeling of the edges of G 
    in the connected component of v
    as tree edges and back edges

S <= empty stack
S.push(v)		// 매개변수 v정점 스택에 push

while(!(S.isEmpty())	// 스택을 비울동안
	v <= S.pop()		// 스택 pop()
	l(v) <- Visited		// pop()한 정점는,이제 Visited
    for each e ∈ G.incidentEdges(v)	// pop()한 정점에 부착된 모든 간선에 대해
		if(l(e) == Fresh)			// 그 간선이 아직 방문안한 간선이면
        	w <- G.opposite(v,e)	// pop()한 정점 v와 연결된 간선 e의 반대편 정점이 w
            if(l(w) == Fresh)		// 그 정점 w가 아직 방문안한 정점이면 ?
            	l(e) <- Tree		// 건너언 간선 e는 일단 Fresh -> Tree 간선으로 변경
                S.push(w)			// 그리고, w정점을 스택에 push
            else					// 정점 w가 이미 방문한 정점이면
            	l(e) <- Back		// 건너온 간선 e는 Fresh -> Back 간선으로 변경 ( 싸이클 제어 )
return

• 실제 구현 ( By. C )

// DFS 비재귀버젼

#include <stdio.h>
#include <stdlib.h>

typedef struct incidentedge
{
	int key;
	char state[6];
	struct incidentedge* next;
	struct incidentedge* prev;
}IncidentEdge;
typedef struct vertex
{
	int key;
	char state[6];
	IncidentEdge* head;
}Vertex;
typedef struct stack						// 비재귀 DFS를 위한 stack ( 정점의 키값을 저장할것이다. )
{
	int* list;
	int top;
}Stack;

void nrDFS(Vertex* V, int S, int n);		// 비재귀 DFS
void makeVertex(Vertex* V, int n);
void linkEdge(Vertex* V, int start, int end);
void initStack(Stack* S, int n);			// 스택 초기화
void push(Stack* S, int n);					// 스택 push
int pop(Stack* S);							// 스택 pop
int isStackEmpty(Stack* S);					// 스택 비었는가 ?
void freeVertexIncidentList(Vertex* V, int n);

int main()									
{
	int N, M, S, start, end;
	Vertex* v = NULL;
	scanf("%d %d %d", &N, &M, &S);

	v = (Vertex*)malloc(sizeof(Vertex) * N);

	makeVertex(v, N);

	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &start, &end);
		linkEdge(v, start, end);
		linkEdge(v, end, start);
	}
	nrDFS(v,S,N);							// 비재귀 DFS 호출만 다른 부분
	
	freeVertexIncidentList(v, N);			// 각 정점에 달린, 인접 리스트 동적할당 해제
	for (int i = 0; i < N; i++)
		free(v[i].head);					// 각 정점에 달린, 인접헤드 동적할당 해제
	free(v);								// 정점배열 동적할당 해제
	return 0;
}
void nrDFS(Vertex* V,int s,int n)			// 비재귀적 DFS
{
	IncidentEdge* p = NULL;					// 인접리스트 조사할 p
	Stack* stack = NULL;					// 스택 포인터					
	
	stack = (Stack*)malloc(sizeof(Stack));	// 스택 동적할당
	initStack(stack,n);						// 스택 초기화
	
	push(stack, V[s - 1].key);				// 파라미터로 넘어온 s, 정점 s부터 시작, 스택에 push
	strcpy(V[s - 1].state, "visit");		// 정점 s 는 이제 visit
	printf("%d\n", V[s-1].key);				// 방문의미하는 출력
	
	while (!isStackEmpty(stack))			// 이제부터 스택이 비울 때까지 반복할 것임
	{
		// 매 차례마다
		p = V[stack->list[stack->top]-1].head->next;	// 스택에 가장 최근에 들어온, 정점위치의, 인접노드 시작을 p에 대입해서	
		while (p != NULL && strcmp(V[p->key - 1].state, "visit") == 0)	// 인접해 있는데, 아직 방문안한, 정점 찾음
			p = p->next;
		if (p != NULL && strcmp(V[p->key-1].state,"fresh") == 0)	// 아직 방문안한, 인접한 정점이 있으면
		{
			push(stack, V[p->key - 1].key);				// 그 정점, 스택에 push
			strcpy(V[p->key - 1].state, "visit");		// 그 정점은 이제, visit
			printf("%d\n", V[p->key - 1].key);			// 그 정점으로, 방문했음을 의미,출력
		}
		if (p == NULL)		// 윗 while문을 통해서, 현재 stack에 peek한 정점의, 인접 정점을 다 방문했으면
			pop(stack);		// 그 정점은, 이제 들어갈 만큼 들어간 것이니, pop
	}
	free(stack->list);	// 스택 리스트 동적할당 해제
	free(stack);	// 스택 동적할당 해제
}
void makeVertex(Vertex* V, int n)
{
	for (int i = 0; i < n; i++)
	{
		V[i].key = i + 1;
		strcpy(V[i].state, "fresh");
		V[i].head = (IncidentEdge*)malloc(sizeof(IncidentEdge));
		if (V[i].head != NULL)
		{
			V[i].head->next = NULL;
			V[i].head->key = 0;
		}
	}
}
void linkEdge(Vertex* V, int start, int end)
{
	IncidentEdge* p, * newNode;
	
	newNode = (IncidentEdge*)malloc(sizeof(IncidentEdge));
	if (newNode != NULL)
	{
		newNode->key = end;
		newNode->prev = NULL;
		newNode->next = NULL;
		strcpy(newNode->state, "fresh");
	}
	p = V[start - 1].head;
	while (p->next != NULL && end > p->next->key)
		p = p->next;
	if (p->next == NULL)
	{
		p->next = newNode;
		newNode->prev = p;
	}
	else
	{
		newNode->next = p->next;
		p->next->prev = newNode;
		newNode->prev = p;
		p->next = newNode;
	}
}
void initStack(Stack* S, int n)
{
	S->list = (int*)malloc(sizeof(int) * n);
	S->top = -1;
}
void push(Stack* S, int n)
{
	S->top += 1;
	S->list[S->top] = n;
}
int pop(Stack* S)
{
	int returnData = S->list[S->top];
	S->top -= 1;
	return returnData;
}
int isStackEmpty(Stack* S)
{
	return S->top == -1;
}
void freeVertexIncidentList(Vertex* V, int n)
{
	IncidentEdge* p = NULL;

	for (int i = 0; i < n; i++)
	{
		while (V[i].head->next != NULL)
		{
			p = V[i].head->next;
			while (p->next != NULL) p = p->next;
			p->prev->next = NULL;
			free(p);
		}
	}
}

📢  너비우선탐색(BFS)

• 너비우선탐색(BFS, Breadth First Search) : 그래프를 순회하기 위한 일반적 기법 중 하나.
• 그래프 G에 대한 BFS순회로 가능한 것들
  
  👉 G의 모든 정점과 간선을 방문
  👉 G가 연결그래프인지 결정
  👉 G의 연결요소들을 계산
  👉 G의 신장숲을 계산
  
  
• N개의 정점과 M개의 간선을 가진 그래프에 대한 BFS는 O(N + M)시간 소요
• BFS를 확장하면 해결 가능한 그래프 문제들
  
  👉 두 개의 주어진 정점 사이의 최소 간선을 사용하는 경로를 찾아보기
  👉 그래프 내 단순싸이클 찾기
  
  
• 그래프에 대한 BFS는 이진트리에 대한 레벨순회와 유사하다. ( 레벨순회는 큐(Queue)를 활용했었다. )
  ( 자료구조의 레벨순회를 모른다면, 아래 포스팅을 확인하고 오길 바란다. )

Alg BFS(G)
	input graph G
    output labeling of the edges of G
	as tree edges and cross edges

for each u ∈ G.vertexs()
	l(u) <- Fresh
for each e ∈ G.edges()
	l(e) <- Fresh
for each v ∈ G.vertexs()
	if(l(v) == Fresh)
		BFS1(G,v)

=======================================

Alg BFS1(G,v)
	input graph G and a start vertex v of G
	output labeling of the edges of G
	in the connected component of v as tree
    edges and cross edges
    
L(0) <- empty list		// 레벨순회 큐(queue)
L(0).addLast(v)			// 큐에 매개변수로 넘어온, 정점 v 를 enqueue
l(v) <- Visited			// 정점을 큐에 enqueue 했다는 것은, 방문했다는 의미. 고로 정점 v를 Fresh -> Visited
i <- 0					// 큐 인덱싱할 i

while(!(L(i).isEmpty())		// 큐를 비울때까지
	L(i+1) <- empty list
    for each v ∈ L(i).elements()	// 큐에 있는 정점 하나를 dequeue를 하고
    	for each e ∈ G.incidentEdges(v)	// 그 정점과 연결된 모든 간선에 대해
        	if(l(e) == Fresh)		// 아직 방문안해본 간선이면 가서
        		w <- G.opposite(v,e)	// 그 정점 v와 간선 e를 통한 반대편 정점을 w라 하고
            	if(l(w) == Fresh)		// 그 정점 w가 아직 방문안한 정점이면
            		l(e) <- Tree		// 간선 e는 Fresh -> Tree 간선으로
                	l(w) <- Visited)	// 정점 w는 Fresh -> Visited 정점으로 변경하고
                	L(i+1).addLast(w)	// 정점 w를 큐에 enqueue
				else					// 정점 w가 이미 방문한 정점이라면
            		l(e) <- Cross		// 간선 e는 Fresh -> Cross 간선으로
	i <- i + 1

• BFS 수행 예시

• BFS 속성
  
  👉 G(v) : v의 연결요소라 했을 때
  👉 속성 1. BFS1(G,v)는 G(v)의 모든 정점과 간선을 방문한다.
  👉 속성 2. BFS1(G,v)에 의해 라벨된 트리 간선들은 G(v)의 신장트리(BFS tree)라 불린다. ( T(v) )
  👉 속성 3. L(i)내의 각 정점 w에 대해
  
  1. T(v)의 v에서 w로 향하는 경로는 i개의 간선을 가진다.
  2. G(v)내의 v에서 w로 향하는 모든 경로는 최소 i개 간선을 가진다.
  
  
• BFS 분석
  
  👉 정점과 간선의 라벨을 쓰고 읽는데 O(1) 시간소요
  👉 각 정점은 두 번 라벨 ( 한 번은 Fresh로 , 또 한 번은 Visited 로 )
  👉 각 간선은 두 번 라벨 ( 한 번은 Fresh로 , 또 한 번은 Tree 또는 Cross 로 )
  👉 각 정점은 리스트 L(i)에 한 번 삽입 ( 여기서 리스트는 큐(queue)를 의미 )
  👉 incidentEdges( ) ( 부착간선 메소드 )는 각 정점에 대해 한 번 호출
  👉 그래프 G가 인접리스트 구조로 표현된 경우, BFS는 O(N + M)시간에 수행
  
  
• BFS 템플릿 활용
  
  👉 G의 연결요소들을 계산하기
  👉 G의 신장숲을 계산하기
  👉 G내의 단순 싸이클 찾기 또는 G가 숲임을 보고하기
  👉 G의 주어진 두 정점에 대해, 그 사이의 최소 간선로 이루어진 G 내의 경로 찾기, 또는 그런 경로 없음을 찾기
  ( 즉, 최단 경로(Directed Path) 문제 활용 가능 )

📢  그래프(Graph)

• 그래프(Graph) : (V,E)쌍, 여기서 V,E는 각각
  
  👉 V : 정점(Vertex)이라 불리는 노드의 집합
  👉 E : 간선(Edge)이라 불리는 정점쌍들의 집합
  
  
• 정점(V)과 간선(E)은 원소, 즉 정보를 저장한다.

📢  간선에 따른 그래프 유형

• 방향간선(Directed edgd)
  
  👉 정점들의 순서쌍 (u,v)
  👉 u : 시점(Origin)
  👉 v : 종점(Destination)
  
  
• 방향그래프(Directed Graph)
  
  👉 모든 간선이 방향간선인 그래프
  
  

• 무방향간선(Undirected edge)
  
  👉 정점들의 무순쌍 (u,v)
  
  
• 무방향그래프(Undirected Graph)
  
  👉 무방향간선으로 이루어진 그래프

• 그래프 응용분야
  
  👉 교통망 : 고속도로망, 항공노선망
  👉 컴퓨터 네트워크 : LAN(Local Area Network), 인터넷, 웹
  👉 데이터베이스 : ER-Dirgram
  👉 그 외에도, 아주 많은 분야에서 그래프 응용분야가 많다.

📢  그래프 용어정리

• 간선의 끝점(end Vertex, endpoint)
  
  👉 정점 U와 V는 a의 양끝점
  
  
• 정점의 부착(Incident)간선
  
  👉 a,d,b는 V에 부착한다.
  
  
• 정점의 인접(Adjacent)정점
  
  👉 U와 V는 인접하다.
  
  
• 정점의 차수(Degree)
  
  👉 X의 차수는 5다.
  
  
• 병렬 간선(Parallel edges)
  
  👉 h와 i는 병렬 간선
  
  
• 루프(Loop 또는 self-loop)
  
  👉 j는 루프다.

• 경로(Path)
  
  👉 정점과 간선의 교대열
  👉 정점으로 시작하여 정점으로 끝난다.
  👉 각 간선은 그 양끝점으로 시작하고 끝난다.
• 단순경로(Simple path)
  
  👉 모든 정점과 간선이 유일한 경로
  
  
• 예시
  
  👉 P1 = (V,b,X,h,Z)는 단순경로 ( 위 그래프에서      경로 )
  👉 P2 = (U,c,W,e,X,g,Y,f,W,d,V)는 비단순경로 ( 위 그래프에서      경로 )

• 싸이클(Cycle)
  
  👉 정점과 간선이 교대 원형
  👉 각 간선은 그 양끝점으로 시작하고 끝난다.
  
  
• 단순싸이클(Simple Cycle)
  
  👉 모든 정점과 간선이 유일한 싸이클
  
  
• 예시
  
  👉 C1 = (V,b,X,g,Y,f,W,c,U,a)는 단순싸이클 ( 위 그래프에서      경로 )
  👉 C2 = (U,c,W,e,X,g,Y,f,W,d,V,a)는 비단순싸이클 ( 위 그래프에서      경로 )

📢  그래프 속성

•  n = 정점 수, m = 간선 수, deg(v) = 정점 v의 차수 일때,
• 속성 1
  
  👉 어떤 그래프의 차수(Degree) 합 = 2m ( m = 간선(edge)의 수 )
  
• 속성 2
  
  👉 루프와 병렬 간선이 없는 무방향그래프에서,  m <= (n(n-1) )/2)

• 위와 같은 그래프가 있을 경우 ( n = 4, m = 6, deg(v) = 3 )
  
  👉 최대 6 <= (4(4-1)/2) 가 성립한다. 

📢  부그래프(Sub Graph)

•  그래프 G = (V,E)의, 부그래프(Sub Graph)는 다음 정점과 간선으로 구성된 그래프다.
  
  👉 정점 : V의 부분집합
  👉 간선 : E의 부분집합
• 그래프 G = (V,E)의, 신장부그래프(Spanning Subgraph)는 다음 정점과 간선으로 구성된 그래프다.
  
  👉 정점 : V
  👉 간선 : E의 부분집합

📢  연결성

• 모든 정점쌍에 대해 경로가 존재하면, "그래프가 연결(Connected)되었다."라고 말한다.
• 그래프 G의 연결요소(Connected Component) : G의 최대 연결 부그래프

📢  밀집도

• 그래프 알고리즘의 선택은 종종 간선의 밀집도에 따라 좌우된다.
• 예로들어, 주어진 그래프 G에 대해, 알고리즘 A,B가 동일한 문제를 각각 O(NM)시간과 O(N^2)시간에 해결할 경우
  
  👉 G가 희소하다면, 알고리즘 A가 B보다 빠르다.
  👉 G가 밀집하다면, 알고리즘 B가 A보다 빠르다.
  
  

📢  싸이클

• 자유트리(Free Tree), 또는 트리 : 다음 조건을 만족하는 무방향그래프 T
  
  👉 T는 연결되어있다.
  👉 T에 싸이클이 존재하지 않는다.
  ❗❗ 자료구조의 "트리(Tree)"랑은 다른 개념이다.
  
  
• 숲(Forest) : 싸이클이 없는 무방향그래프
• 숲의 연결요소는 트리"들"이다.

📢  신장

• 연결그래프의 신장트리(Spanning Tree) : 신장 부그래프 가운데 트리인 것
• 신장트리는 그래프가 트리가 아닌 한(즉, 싸이클이 존재하지 않는 한), 유일하지 않다.
• 신장트리는 통신망 설계에 응용한다.
• 그래프의 신장숲(Spanning Forest) : 신장 부그래프 가운데 숲인 것

📢  그래프 구현

• 그래프 구현에는 크게 3가지 구조로 가능하다.
  
  👉 간선리스트(edge list)구조
  👉 인접리스트(adjacency list)구조
  👉 인접행렬(adjacency matrix)구조
• 인접리스트 구조는
  
  👉 연결리스트를 이용한 구현
  👉 배열을 이용한 구현
  
  

• 인접행렬 구조는
  
  👉 연결리스트를 이용한 구현
  👉 배열을 이용한 구현

📢  인접행렬(Adjacency Matrix)

• N X N 행렬로 표현
• 무향 그래프의 경우
  
  👉 원소(i,j) = 1 : 정점 i와 정점 j 사이에 간선이 있다.
  👉 원소(i,j) = 0 : 정점 i와 정점 j 사이에 간선이 없다.
  
  

• 유향 그래프의 경우
  
  👉 원소(i,j)는 정점 i 로부터 정점 j 로 연결되는 간선이 있는지를 나타낸다.
  
  

• 가중치 있는 그래프의 경우
  
  👉 원소(i,j)는 1 대신에 가중치를 가진다.

📢  인접리스트(Adjacency List)

• N 개의 연결 리스트로 표현
  
  👉 i 번째 리스트는 정점 i  에 인접한 정점들을 리스트로 연결해 놓은 것
• 가중치 있는 그래프의 경우
  
  👉 리스트는 가중치도 보관한다.

📢  그래프 성능 & 특징

• 점근적 성능 비교

• 그래프 상세 구현 비교

📢  그래프 구현 ADT

• 단순한화한 무방향그래프 ADT 구현
  
  👉 Integer deg(v) : 정점 v의 차수를 반환
  👉 Integer opposite(v,e) : 정점 v와 간선 e에 대한 반대쪽 끝점을 반환
  👉 Boolean areAdjcent(v,u) : 정점 v와 u가 인접한지 여부를 반환
  👉 Iterator adjacentVertex(v) : 정점 v의 인접정점을 모두 반환
  👉 Iterator incidentEdge(v) : 정점 v의 부착간선을 모두 반환
• A. 그래프가 인접리스트 구조로 표현된다.
• B. 그래프가 인접행렬 구조로 표현된다.
• 전제
  
  👉 인접행렬 구조에서 인접행렬은 배열 A에 저장됬다.
  👉 index(v) 함수 사용 가능 : 인접행렬에서 정점 v에 대응하는 배열첨자를 반환

차수 메소드( deg(v) )

Alg deg(v)			// 인접리스트 버전
	input vertex v
    output integer

c <- 0
e <- (v.incidentEdge).next

while(e != ∅)
	c <- c + 1
	e <- e.next
return c

// Total = O(deg(v))

======================================

Alg dev(v)			// 인접행렬 버전
	input adjacency matrix A, vertex v
	output integer

c <- 0
vi <- index(v)
for j <- 0 to n-1
	if(A[vi,j] != ∅)
		c <- c + 1
return c

// Total = O(n)

나의 상대방 정점 반환 메소드( opposite(v,e) )

Alg opposite(v,e)			// 인접리스트 버전
	input vertex v, edge e
	output vertex

u,w <- e.endpoints
if(v == u)
	return w
else
	return u
    
// Total = O(1)

==========================

Alg opposite(v,e)			// 인접행렬 버전
	input adjacency matrix A, vertex v, edge e
	output vertex

u,w <- e.endpoints
if(v == u)
	return w
else
	return u

// Total = O(1)

정점 v,w가 인접한지 확인 메소드( areAdjacent(v,w) )

Alg areAdjacent(v,w)		// 인접리스트 버전
	input vertex v,w
	output boolean

if(deg(v) < deg(w))
	m <- v
else
	m <- w

e <- (m.incidentEdges).next
while(e != ∅)
	a,b <- e.endpoints
	if((v == a) && (w == b) || (v == b) && (w == a))
		return True
	e <- e.next
return False

// Total = O(min(deg(v),deg(w)))

=====================================================

Alg areAdjacent(v,w)		// 인접행렬 버전
	input adjacency matrix A, vertex v,w
	output integer

return A[index(v),index(w)] != ∅

// Total = O(1)

나의 인접한 정점 반환 메소드( adjacentVertex(v) )

Alg adjacentVertex(v)		// 인접리스트 버전
	input vertex v
	output set of vertex objects

L <- empty list
e <- (v.incidentEdges).next

while(e != ∅)
	L.addLast(opposite(v,e))
	e <- e.next
return L.element()

// Total = O(deg(v)) // 자기랑 연결된 간선만 조사하면 되니깐

===================================

Alg adjacentVertex(v)		// 인접행렬 버젼
	input adjacency matrix A, vertex v
	output set of vertex objects

L <- empty list
vi <- index(v)

for j <- 0 to n - 1
	if(A[vi,j] != ∅)
		L.addLast(opposite(v,A[vi,j]))
return L.element()

// Total = O(n)		// 나를 제외한 모든 정점에 대해, 연결되어 있는지 하나씩 조사해야되니깐

나의 부착간선 반환 메소드( incidentEdges(v) )

Alg incidentEdges(v)		// 인접리스트 버젼
	input vertex v
	output set of edge objects

L <- empty list
e <- (v.incidentEdges).next

while(e != ∅)
	L.addLast(e)
	e <- e.next
return L.element()

// Total = O(deg(v))		// 나한테 부착된 연결리스트만 확인하면 되니깐

=================================

Alg incidentEdges(v)		// 인접행렬 버젼
	input adjacency matrix A, vertex v
	output set of edge objects

L <- empty list
vi <- index(v)

for j <- 0 to n - 1
	if(A[vi,j] != ∅)
		L.addLast(A[vi,j])
return L.elements()

// Total = O(n)			// 나를 제외한 모든 정점에 대해 부착됬는지 확인해야되니깐

📢  번외

•  그래프 구현 방식 선택 : 다음 각 경우에 인접리스트 구조와 인접행렬 구조 둘 중 어느 것을 사용하겠는가 ?
  
  👉 a. 그래프가 10,000개의 정점과 20,000개의 간선을 가지며, 가능한 최소한의 공간 사용이 중요
  👉 b. 그래프가 10,000개의 정점과 20,000,000개의 간선을 가지며 가능한 최소한의 공간 사용이 중요
  👉 c. 얼마의 공간을 사용하든, areAdjacent 질의에 가능한 빨리 답해야 할 경우
  
  
• 해결책
  
  👉 a. 인접리스트 구조가 유리 = 실상 인접행렬 구조를 쓴다면 많은 공간을 낭비한다. 왜냐면 20,000개의 간선만이 존재하는데도 100,000,000개의 간선에 대한 공간을 할당하기때문 ( M <= (N(N-1)/2 )
  👉 b. 일반적으로, 이 경우에는 양쪽 구조 모두가 적합 = areAdjacent 작업은 인접행렬 구조가 유리, insertVertex와 removeVertex 작업에서는 인접리스트 구조가 유리
  👉 c. 인접행렬 구조가 유리 = 이유는, 이 구조가 areAdjacent작업을 정점이나 간선의 개수에 관계없이 O(1)시간에 지원하기 때문이다.
  
  
• O(log M) == O(log N)인 이유 ( M = 간선 수, N = 정점 수 )
  
  👉 G를 N 개의 정점과 M 개의 간선으로 이뤄진 단순 연결그래프라 가정하자.
  👉 M <= N(N-1)/2 이며, 이는 O(N^2)이다.
  👉 따라서, O(log M) == O(log N^2) == O(2log N) == O(log N) 이다.

📢  해시테이블(Hash Table)

• (키-주소) 매핑에 의해 구현된 사전 ADT
  👉 예 : 컴파일러의 심볼 테이블, 환경변수들의 레지스토리

• 해시테이블 = 버켓 배열 + 해시함수
  👉 항목들의 키를 주소(즉, 배열첨자)로 매핑함으로서 1차원 배열에 사전 항목들을 저장한다.
• 성능
  👉 탐색,삽입,삭제 : 최악의 경우 O(N), 그러나 기대시간 O(1)

📢  버켓배열(Bucket Array)

• 키가 유일한 정수며 [0...M-1] 범위에 잘 분포되어 있다면, 해시테이블에서의 탐색, 삽입, 삭제에 O(1) 소요

• 두 가지 중요한 결함
  
  👉 O(N) 공간을 사용하므로, M이 N에 비해 매우 크면, 공간 낭비
  👉 키들이 [0...M-1] 범위 내의 유일한 정수여야 하지만, 이는 종종 비현실적
• 설계 목표
  
  👉 그러므로 해시테이블 데이터구조를 정의할 때는, 키를 [0...M-1] 범위 내의 정수로 매핑하는 좋은 방식과
  버켓배열을 구성해야 한다.

📢  해시함수 및 해시테이블

• 해시함수(Hash Function), h :  주어진 형의 키를 고정범위 [0...M-1]로 매핑
  
  👉 예 : h(x) = x % M ( h는 정수 키 x에 대한 해시함수 )
• 정수 h(x) : 키 x의 해시값(Hash value)
• 주어진 키 형의 해시테이블은 다음 두 가지로 구성
  
  👉 해시함수 h
  👉 크기 M의 배열(테이블이라 부른다.)
• 사전을 해시테이블로 구현할 때, 목표는 항목(k,e)를 첨자 i = h(k)에 저장하는 것
• 해시함수(Hash Function)는 보통 두 함수의 복합체로 명세한다.
  
  👉 해시코드맵(Hash code map) h1 : keys -> integers
  👉 압축맵(Compression map) h2 : integers -> [0...M-1]
• 먼저 해시코드맵을 적용하고, 그 결과에 압축맵을 적용한다. 즉,
  
  👉 h(k) = h2(h1(k))
• 좋은 해시함수가 되기 위한 조건
  
  👉 키들을 외견상 무작위하게(Random) 분산시켜야 한다.
  👉 계산이 빠르고 쉬워야 한다 ( 가능하면 상수시간 )

📢  압축맵

• 나누기(Division) (보통사용 방식)
  
  👉 h2(k) = |k| % M
  👉 해시테이블의 크기 M은 일반적으로 소수(Prime)로 선택
• 승합제(MAD, Multiply Add and Divide)
  
  👉 h2(k) = |ak + b| % M
  👉 a와 b는 음이 아닌 정수로서, a % M != 0, 그렇지 않으면, 모든 정수가 동일한 값 b로 매핑됨

📢  해시코드맵

• 메모리 주소(Memory address)
  
  👉 키 개체의 메모리 주소를 정수로 재해석( 모든 Java객체들의 기본 해시코드다. )
  👉 일반적으로 만족스러우나 수치 또는 문자열 키에는 적용 곤란
• 정수 캐스트(Integer case)
  
  👉 키의 비트값을 정수로 재해석
  👉 정수형에 할당된 비트 수를 초과하지 않는 길이의 키에는 적당 ( Java의 byte, short, int, float )
• 요소합(Component sum)
  
  👉 키의 비트들을 고정길이(16 or 32bit)의 요소들로 분할한 후 각 ㅊ 합한다(overflow는 무시한다.)
  👉 정수형에 할당된 비트 수 이상의 고정길이의 수치 키에 적당 ( 예 : Java의 long, double )
  👉 문자의 순서에 의미가 있는 문자열 키에는 부적당 ( 예: temp01-temp10, stop-tops-spot-pots )
• 다항 누적(Ploynomial accumulation)
  
  👉 요소합과 마찬가지로, 키의 비트들을 고정길이(8,16,32bit)의 요소들로 분할 ( a(0),a(1),...,a(N-1) )
  👉 고정값 z를 사용하여 각 요소의 위치에 따른 별도 계산을 부과한 다항식 p(z)를 계산 (overflow 무시)
  👉 p(z) = a(0) + a(1) * z + a(2) * z^2 + .... + a(N-1) * z ^ (N-1)
  👉 문자열에 특히 적당 ( 예 : 고정값 z = 33을 선택할 경우, 50,000개의 영단어에 대해 단지 6회 충돌만 발생

📢  충돌해제 (중요 !!)

• 충돌(Collision) : 두 개 이상의 원소들이 동일한 셀로 매핑되는 것
• 즉, 상이한 키, k1과 k2에 대해 h(k1) = h(k2)면 "충돌이 일어났다."고 말한다.
• 충돌 해결(Collision resolution)을 위한 일관된 전략이 필요하다.
  
  👉 분리연쇄법(Separate Chaining)
  👉 선형조사법(Linear Probing)
  👉 2차 조사법(Quadratic Probing)
  👉 이중해싱(Double Hashing)
  
  

📢  분리연쇄법

• 분리연쇄법(Separate Chaining), 연쇄법 : 각 버켓 A[i]는 리스트 L(i)에 대한 참조를 저장 ( L(i)는 리스트 )
  
  👉 해시함수가 버켓 A[i]로 매핑한 모든 항목들을 저장
  👉 무순리스트가 또는 기록파일 방식을 사용하여 구현된 미니 사전이라 볼 수 있다.
• 장단점 : 단순하고 빠르다는 장점이 있으나 테이블 외부에 추가적인 저장공간을 요구

• 예시
  
  👉 h(k) = k % M
  👉 키 : 25,13,16,15,7,28,31,20,1  (    = 충돌 일어난 키값 )
  👉 리스에 추가되는 항목들의 위치는, 리스트의 맨 앞에 삽입하는 것이 유리하다. (리스트의 tail 포인터 없는경우)

📢  개방주소법 ( 선형조사법 )

• 개방주소법(Open Addresssing) : 충돌 항목을 테이블의 다른 셀에 저장
• 장단점 : 분리연쇄법에 비해 공간 사용을 절약하지만, 삭제가 어렵다는 것과 사전 항목들이 연이어 군집화

• 선형조사법(Linear Probing) : 충돌 항목을 (원형으로)바로 다음의 비어있는 테이블 셀에 저장함으로써 충돌을 처리
• 즉, 다음 순서에 의해 버켓을 조사한다.
  
  👉 A[ (h(k) + f(i)) % M ], f(i) = i, i = 0,1,2,...
• 검사되는 각 테이블 셀은 조사(Probe)라 불린다.
• 충돌 항목들은 군집화하며, 이후의 충돌에 의해 더욱 긴 조사열(Probe sequence)로 군집됨 = "1차 군집화"
• 예시
  
  👉 h(k) = k % M
  👉 키 : 25,13,16,15,7,28,31,20,1,38 (      = 충돌 키 )

📢  개방 주소법( 2차 조사법 )

• 2차 조사법(Quadratic Probing) : 다음 순서에 의해 버켓을 조사
  
  👉 A[ (h(k) + f(i) % M ], f(i) = i^2, i = 0,1,2,...
• 해시 값이 동일한 키들은 동일한 조사를 수반한다.
• 1차 군집화를 피하지만, 나름대로의 군집을 형성 할 수 있다. = "2차 군집화"
• M이 소수가 아니거나 버켓 배열이 반 이상 차면, 비어 있는 버켓이 남아 있더라도 찾지 못할 수 있다. ( 단점 )
• 예시
  
  👉 h(k) = k % M, f(i) = i^2
  👉 키 : 25,13,16,15,7,28,31,20,1,38

📢  이중해싱

• 이중해싱(Double Hashing) : 두 번째의 해시함수 h`를 사용하여 다음 순서에 의해 버켓을 조사
  
  👉 A[ (h(k) + f(i)) % M ], f(i) = i * h`(k), i = 0,1,2,....
• 동일한 해시값을 가지는 키들도 상이한 조사를 수반할 수 있기 때문에 군집화를 최소화한다.
• h`는 계산 결과가 0이 되면 안된다. 👉 ( 0이 되면, f(i)는 결과적으로 0만 되겠죠 ? 그럼 한자만 계속 해싱충돌 )
• 최선의 결과를 위해, h`(k)와 M은 서로소(Relative Prime)여야 한다.
  
  👉 d(1)*M = d(2)*h`(k)이면, d(2) 개의 조사만 시도한다. 즉, 버켓들 중 d(2)/M만 검사
  👉 h`(k) = q - (k % q) 또는 1 + (k % q)를 사용 ( 단, q < M은 소수며 M 역시 소수일 경우 )
  👉 한 마디로 위에 두 조건을 만족시키는, 해시함수를 적용하면, 군집화를 최소화하면서, 최소화로 실행가능
• 예시
  
  👉 h(k) = k % M, h`(k) = 11 - (k % 11),  ( 이때 q = 11이고, 11은 서로소이다. )
  👉 키 : 25,13,16,15,7,28,31,20,1,38 (      = 충돌 키 )

• 개방주소법( 선형조사법, 2차조사법 ), 이중해싱 알고리즘

Alg findElement(k)
	input bucket array A[0...M-1], hash function h, key k
    output element with key k

v <- h(k)			// h(k) = 해시함수는 보통 주어진다.
i <- 0
while(i < M)
	b <- getNextBucket(v,i)
    if(isEmpty(A[b])
		return NoSuchKey
	elseif(k == key(A[b])
		return element(A[b])
	else
    	i <- i + 1
return NoSuchKey

=========================================================
Alg insertItem(k,e)

v <- h(k)
i <- 0
while(i < M)
	b <- getNextBucket(v,i)
    if(isEmpty(A[b]))
    	Set bucket A[b] to (k,e)
        return
	else
    	i <- i + 1
overflowException()
return

Alg getNextBucket(v,i)		// 선형조사법

return (v + i) % M

==========================================
Alg getNextBucket(v,i)		// 2차조사법

return (v + i^2) % M
==========================================
Alg getNextBucket(v,i)		// 이중해싱

return (v + i * h`(k)) % M




===========================================
Alg initBucketArray()		// 버킷초기화(예시)
	input bucket array A[0...M-1]
    output bucket array A[0...M-1] initialized with null buckets

for i <- 0 to M-1
	A[i].empty <- 1			// Set empty
return
===========================================
Alg isEmpty(b)
	input bucket b
    output boolean

return b.empty

📢  적재율

• 해시테이블의 적재율(Load factor), a = N/M ( N은 키 수, M은 버켓배열 크기 )
  
  👉 즉, 좋은 해시함수를 사용할 경우의 각 버켓의 기대크기
• 적재율은 낮게 유지되어야 한다 ( 가능하면 1 아래로, 즉 a = N/M < 1 되도록)
• 좋은 해시함수가 주어졌다면, 탐색,삽입,삭제 각 작업의 기대 실행시간 = O(a)
• 분리연쇄법
  
  👉 a > 1 이면, 작동은 하지만 비효울적
  👉 a < 1 이면, O(a) = O(1)의 기대실행시간 성취 가능
• 개방주소법 ( 선형조사법, 2차조사법 )
  
  👉 항상 a < 1
  👉 a > 0.5 이면, 선형 및 2차 조사인 경우 군집화 가능성 농후하다.
  👉 a <= 0.5 이면, O(a) = O(1) 기대실행시간

📢  해싱의 성능

• 해시테이블에 대한 탐색,삽입,삭제
  
  👉 (최악의 경우) O(N) 시간 소요
• 최악의 경우란 : 사전에 삽입된 모든 키가 충돌할 경우
• 적재율(Load factor) : a = N/M은 해시테이블의 성능을 좌우한다.
• 해시값들은 흔히, 난수(Random numbers)와 같다고 가정하면, 개방주소법(선형조사법 or 2차조사법)에 의한
  삽입을 위한 기대 조사횟수는 1/(1 - a)라고 알려져 있다.
• 해시테이블에서 모든 사전 ADT 작업들의 기대실행시간 : O(1)
• 실전에서, 적재율이 1(즉, 100%)에 가깝지만 않다면, 해싱은 매우 빠른 것이다.
• 응용분야
  
  👉 소규모 데이테베이스 ( 인덱스 )
  👉 컴파일러
  👉 브라우저 캐시

📢   이진탐색트리(Binary Search Tree)

• 내부노드에 (키,원소)쌍을 저장하며 다음의 성질을 만족하는 이진트리

  성질
  트리노드 u,v,w가 있을때, u와 w가 각각 v의 왼쪽과 오른쪽 부트리에 존재할 때  Key(u) < Key(v) < Key(w) 성립

• 전제 : 적정이진트리로 구현

• 이진탐색트리를 중위순회(Inorder Traversal)하면 키가 증가하는 순서로 방문한다. 

• 이진탐색 트리 예

📢   이진탐색트리 탐색

• Key를 찾기 위해, 루트에서 출발하는 하향 경로를 추적한다.

• 다음 방문할 노드는 Key와 현재 노드의 Key의 크기를 비교한 결과에 따라 결정한다.

• 외부노드(External Node, 리프노드(Leaf Node))에 다다르면, 찾는 Key가 발견되지 않은 것이다.

📢   이진탐색트리 삽입

• 우선 Key를 탐색한다.

• Key가 현재 이진탐색트리에 존재하지 않을 경우 👉 탐색은 외부노드(w로 가정)에 도착

• 도착한 외부노드 w에 Key를 삽입한 후 👉 이 외부노드를 내부노드로 확장해줘야 한다.

• 여기서 외부노드 👉 Key값을 가지지 않은 트리의 말단에 위치한 노드
  내부노드 👉 Key값을 가지고 있는 노드

Alg insertItem(K, E)		// 이진탐색트리 삽입
	input binary search tree T, Key K, element E
    output none

w <- treeSearch(root(),K)	// 일단, 이진탐색으로, K를 Key값으로하는 노드가 현재 있나 탐색
if(isInternal(w))			// 반환된 w노드가 내부노드 -> 이미 이진탐색트리 내에 존재한다는 것
	return			// 삽입 할 필요 X -> 종료
else					// 외부노드인 경우
	Set node w to (K, E)	// w노드의 Key값을 K, 원소를 E로 적용하고
    expandExternal(w)		// ★ 이 w노드를 내부노드로 확장한다.
    return

Alg expandExternal(z)
	input external node z
    output none

l <- getnode()
r <- getnode()
l.left <- Ø
l.right <- Ø
l.parent <- z
r.left <- Ø
r.right <- Ø
r.parent <- z
z.left <- l
z.right <- r
return

📢   이진탐색트리 삭제

• 크게 Case 1, Case 2로 나뉜다. 

• Case 1  👉  삭제할 Key를 가진 노드의 양쪽 자식 노드 중 하나가 외부노드일 경우
  Case 2  👉  삭제할 Key를 가진 노드의 양쪽 자식 노드 둘 다 내부노드일 경우 ★

📌 이진탐색트리 삭제 ( Case 1. 삭제할 노드 양쪽 자식노드 중 하나가 외부노드인 경우 )

• 삭제할 노드의 양쪽 자식 노드 중 하나가 외부노드일 경우이다.

• 우선 삭제할 Key를 탐색

• Key가 트리에 존재할 경우, 탐색은 Key를 저장하고 있는 노드(w라 가정)에 도착

• 노드 w의 자식 중 하나가 외부노드(z라 가정)라면, 노드 w의 축소과정을 통해, w, z를 트리로부터 삭제한다.

📌 이진탐색트리 삭제 ( Case.2 삭제할 노드의 양쪽 자식노드가 둘 다 내부노드 일 경우 ) ★

• 삭제할 노드의 양쪽 자식노드 둘 다 내부노드일 경우이다. ( 이 때 삭제할 노드는 w라 가정 )

• 1. 트리 T에 대해 w의 중위순회 계승자 y와 그 자식노드 z를 찾아낸다.

  • 노드 y는 우선 w의 오른쪽 자식으로 이동한 후, 거기서부터 왼쪽 자식들만을 끝까지 따라 내려가면 도달하게 되는 마지막 내부노드이며, 노드 z는 y의 왼쪽 자식인 외부노드

  • y는 T를 중위순회할 경우, 노드 w바로 다음에 방문하게 되는 내부노드이므로, w의 중위순회 계승자(Inorder successor)라 불린다.

  • 따라서, y는 w의 오른쪽 부트리 내 노드 중 가장 왼쪽으로 돌출된 내부노드이다.

• 2. y의 내용을 w에 복사

• 3. reduceExternal(z) 작업을 사용해서 노드 y와 z를 삭제

Alg removeElement(K)
	input binary search tree T, Key K
    output element with Key K

W <- treeSearch(root(),K)

// Key K를 가지는 T내에 찾은 w노드가 외부노드인 경우
if(isExternal(W))
	return NoSuchKey

// Key K를 가지는 T내에 찾은 W노드가 외부노드인 경우
e <- element(W)
z <- leftChild(W)

if(!(isExternal(z))
	z <- rightChild(W)

if(isExternal(z))						// Case 1. 삭제할 W노드의, 양쪽 자식노드 중 하나가 외부노드인 경우
	reduceExternal(z)
else								// Case 2. 삭제할 W노드의, 양쪽 자식노드 둘 다 내부노드인 경우 ★
	y <- inOrderSucc(W)				// W의 중위순회계승자( 즉, W노드의 Key값 바로 다음으로 큰, Key값을 가진 노드 ), y
    z <- leftChild(y)					// 중위순회계승자 y노드의 왼쪽 자식노드가 z
    Set node W to (Key(y),element(y))		// 삭제한다는 개념으로, 삭제할 W노드의 key값과 element값을 y의 Key,element로 변경
	reduceExternal(z)				// y에 대해, 내부노드 축소과정

return e

📢   이진탐색트리의 성능

• 높이 h의 이진탐색트리를 사용하여 구현된 N 항목의 사전을 가정해보자.

• O(N) 공간을 사용한다.

• 탐색,삽입,삭제 작업 모두 O(h)시간에 수행

• 높이 h는

  1. 최악의 경우  👉  O(N) 

  2. 최선의 경우  👉  O(log(N))

📢   참고 

• 동일한 키 집단으로 생성된 이진탐색트리에서, 삽입 순서와는 상관없이 항상 동일한 이진탐색트리가 생성된다 ?👉  NO !!

• 간단한 예로 확인가능 👉 [ 9,5,12,7,13 ] 순서와 [ 9,7,12,5,13 ] 순서로 생성되는 이진탐색트리의 모양은 다르다.

📢   정의

• 사전은 탐색 가능한 형태의 (키,원소)쌍 항목들의 모음을 모델링 한 것이다.

• 사전에 관한 주요 작업
  1. 탐색(Searching)
  2. 삽입(Inserting)
  3. 삭제(Deleting)

• 사전에는 두 종류의 사전 존재한다.
  1. 무순사전 ADT  (Ex. "가계부")  👉  "순서가 없다"
  2. 순서사전 ADT  (Ex. "출석부", "백과사전")  👉  "학번 or 자음순,모음순" 등의 정렬된 순서가 있다.

• 사전 응용에는 두 가지
  1. 직접 응용  👉  "연락처 목록", "신용카드 사용승인", "인터넷주소 매핑"
  2. 간접 응용  👉  "알고리즘 수행을 위한 보조 데이터구조", "다른 데이터구조를 구성하는 요소"

📢   탐색

• 비공식적 : 탐색(Search)은 데이터 집단으로부터 특정한 정보를 추출함을 말한다.

• 공식적 : 탐색(Search)은 사전으로 구현된 데이터 집단으로부터 지정된 키(key)와 연관된 데이터 원소를 반환함을 말한다.

• 사전 구현에 따른 탐색 기법
  

📢   무순사전 ADT

• 무순리스트를 사용하여 구현된 사전  👉  사전 항목들을 임의의 순서로 리스트에 저장
  ( 이중연결리스트 또는 원형 배열을 사용 )

• 성능
  삽입 : O(1) 소요 👉 새로운 항목을 기존 리스트의 맨 앞 또는 맨 뒤에 삽입하면 되기 때문
  삭제 : O(N) 소요 👉 (최악의 경우)항목이 존재하지 않을경우, 리스트 전체를 순회해야 하기 때문
  탐색 : O(N) 소요 👉  (최악의 경우)항목이 존재하지 않을경우, 리스트 전체를 순회해야 하기 때문

• 효과적인 경우 : 소규모 사전, or 삽입은 빈번하나, 탐색이나 삭제는 드문 사전 ( Ex. 서버의 로그인 기록 )

📢   무순사전 선형탐색 알고리즘

Alg findElement(K)		// 배열 Ver.
	input Array[0..N-1], Key K
    output element with key K

i <- 0				// 첫번째 배열 인덱스 초기화
while(i < N)			// 배열 끝까지 갈때까지 반복 
	if(A[i].key == K)	// A[i].key != 목표 Key값
    	return A[i].key
    else				// A[i].key != 목표 Key값
    	i <- i + 1		
return NoSuchKey

================================================================

Alg findElement(K)		// 연결리스 Ver.
	input doubly linked list with header H and trailer T, Key K
    output element with Key K

i <- H.next			// 연결리스트 Header에 다음 노드로 초기화
while(i != T)			// 연결리스트의 끝 Tailer전까지 
	if(i.key == K)		// i.key == 목표 Key값
    	return i.elem
	else				// i.key == 목표 Key값
    	i <- i.next
return NoSuchKey

📢   순서사전 ADT

• 순서리스트를 사용하여 구현된 사전  👉  사전 항목들을 배열에 기초한 리스트에 키로 정렬된 순서로 저장

• 성능
  삽입 : O(N)  👉  새 항목을 삽입하기 위한 공간 확보를 위해, (최악의 경우) N개의 기존 항목을 이동해야 한다.
  삭제 : O(N)  👉  항목이 삭제된 공간을 기존 항목들로 메꾸기 위해 (최악의 경우) N개의 기존 항목 이동해야 한다.탐색 : O(log(N))  👉  이진탐색을 사용하면 가능하다.

• 효과적인 경우 : 소규모 사전, or 탐색이 빈번하나, 삽입 삭제는 드문 사전 ( Ex. 전화번호부 )

📢   이진탐색(Binary Search)

• 키값으로 된 "배열(Array)"에 기초한 리스트로 구현된 사전에 대해 탐색 작업을 수행한다.

• 배열의 키값들은 반드시 "정렬(Sorted)"되어 있어야 한다.

• 재귀적인 방식 비재귀적 방식이 두 가지 모두 구현 가능하다.

• 입력크기(N)의 로그 수(log(N))에 해당하는 수의 재귀(or 비재귀)를 수행한 후 정지한다. ( Ex. 스무고개 )

📢   재귀적 이진탐색

Alg findElement(K)
    input sorted Array A[0..N-1], K
    output element with key K
    
return rFE(K, 0, N-1)

=====================================
Alg rFE(K,l,r)			// l,r은 배열조사 범위의 왼쪽,오른쪽 인덱스

if(l > r)
	return NoSuchKey
mid <- (l + r)/2			// 재귀호출마다, 중앙 인덱스 mid값 구하고
if(K = Key(A[mid]))		// A[mid]값 = 찾아야될 key값, A[mid]값 반환 
	return element(A[mid])
elseif(K < Key(A[mid]))	// A[mid]값 > 찾아야될 key값, (범위를 l~(mid-1)로 재귀 이진탐색 재귀호출)
	return rFE(K, l, mid-1)
else					// A[mid]값 < 찾아야될 key값, (범위를 (mid+1)~r)로 재귀 이진탐색 재귀호출)
	return rFE(K, mid+1, r)

📢   비재귀적 이진탐색

Alg findElement(K)
	input sorted Array A[0..N-1], Key K
    output element with key K

l <- 0
r <- N-1
while(l <= r)			// 재귀호출 대신,반복문 사용
	mid <- (l + r) / 2	// 매 과정, 배열의 중앙 인덱스 mid 구하고
    if(K == Key(A[mid]))	// A[mid] == 목표 Key
    	return element(A[mid])
    elseif(K < key(A[mid]))	// A[mid] > 목표 Key
		r <- (mid - 1)
	else				// A[mid] < 목표 Key
    	l <- (mid + 1)
return NoSuchKey

📢   이진탐색 수행 예

📢   [ 참고 ] 재귀 알고리즘 👉 비재귀 알고리즘 전환하기 위한 일반적인 요령

1. 재귀호출을 반복문으로 대체한다.

2. 재귀의 매개변수를 반복문의 제어변수로 전환한다.

3. 최초의 재귀호출에 사용하는 매개변수 값을 반복문 진입 전 초기화로 전환한다.

4. 재귀의 BaseCase를 반복문의 종료 조건으로 전환한다.

📢 배경

• 4학년, 졸업하기 마지막 학기를 앞두고, 처음에는 "컴공" 이라면, 있으면 "음~있구나" 하고, 없다면 "왜 없어 ?"
  라는 반응이 나오기도 한다길래 "정보처리기사" "자격증 시험을 따긴 해야겠다" 고 처음에는 생각했다.
  
• 그렇게 당장, 압박감을 느끼고, 시작을 하진 않았던 거 같다.

📢 필기

• 난 정기 3회를 지원했었다. 첫 지원한거다.
• 준비는 "독학"으로 했고, 소스는 "(이기적)2020정보처리기사 필기" 책을 하나 사서, 조금씩 분할해서
  스윽~보면서 준비한거 같다.

• 개인적으로, 나도 나름 전공자인데, 본인이 학부생 때부터, "소프트웨어공학"에 지식을, 체계적으로 정리해놓고
  있던 것이 아니라면, 크게 5가지 모듈 중에서
  
  

  모듈1. 소프트웨어 설계

  모듈2. 소프트웨어 개발

  모듈3. 데이터베이스 구축

  모듈4. 프로그래밍 언어 활용

  모듈5. 정보 시스템 구축 관리

• 저 모듈 1,2가 책 순서상은, 초반부에 나오는데, 매우!! 몸에서 거부감이 들었다.
  ( 느낌적으로, "책에 글자가 있구나..나는 이걸 읽고 있을 뿐... )
• 나머지, 뒤에 3개의 모듈은, 솔직히, 본인이 전공자라면
  1. 데이터베이스
  2. 기본 프로그래밍언어(들)
  3. 네트워크
  4. 운영체제
  정도의 수업들만, 배울 때, 열심히만 했었더라면, 어느정도 다 기억이나서, 익숙한 내용이었다 생각한다.
  ( 물론 비전공자일 경우는,,, 아닐 수 있겠다.. 😢 )
• 나는 결론적으론, 필기는 2주 정도 잡고, 하루에 조금씩 꾸준히, 책 내용 읽어보고, 뒤에 있는 연습문제
  한번씩, 풀어보는 느낌으로 공부했다.
  ( 하면서 느낀건데,,, 절대 !! 시험 전에, 한번 더 훑어봐야지 !! 이런거 절대 없다 !! 못할 것이다. )
• 하루 전에는, 개편 되고나서, 기출이라곤 "1,2회 통합" 필기 시험 1회본 밖에 없었기 떄문에
  일부러, 과거의 (17~19년도, 대략 3년치) 필기 기출을 다 출력해서, 이번 개편 부분과, 겹치는 부분만
  골라서 ( 예를 들어, DB 나 프로그래밍 언어, 네트워크 ) 쭉 풀어보면서, 내 점수가 몇 점 나오는지 확인
  하면서, 또 중복되어 나오는 문제들은, 머리 속에 기억해 놓는 식으로 준비했다. ( 중요 📌 )

📢 필기 결과

• 필기는, 📌 평균 60점 이점 합격이다. ( 단, 한 과목이라도 과락(40점) 있을 시, 탈락이다. )
• 결과적으론, 필기는 한번에 합격했다.
  점수는 저런식으로 받았다.
• 내가 어쩌고 저쩌고, 하기보단, 만약 아직 필기를 준비 중이라면, 내 생각에, 전략을 제시하자면
• 본인이, "전공자"라면,
  "데이터베이스 구축, 프로그래밍 언어 활용, 정보 시스템 구축 관리"  👉 점수 최대한 확보 ❗❗
  "소프트웨어 설계, 소프트웨어 개발"  👉 과락만 피하자 ❗❗
• 본인이 "비전공자"라면
  "데이터베이스 구축, 프로그래밍 언어 활용"  👉 점수 최대한 확보 ❗❗
  "소프트웨어 설계, 소프트웨어 개발, 정보 시스템 구축 관리"  👉 최대한 아는 건 맞추자  ❗❗
• 물론, 그 무엇보다, 기출만 3년치 보고가면, (현재 기준)기출도 좀 생겼을 것이고,,기출만 잘 보고가도
  왠만해선, 필기는 한번에 통과하는 사람들이 많은 것 같다. ( 실제로, 합격률도 그러하고..😁 )

📢 실기

• (문제의) 실기다.
• 이번, 개편 후, 정보처리기사가 합격하기 힘든 이유는, 필기가 아닌 "실기" 때문이다.
• 일단, 기본적으로, 기출이란게 존재하지 않고, "현재진행형"으로 문제 또한, 사방팔방에서 출제 된다.
  어디서부터 어디까지..( 물론, 출제범위가 있다만..의미 없는거 같다. )출제 될지를 일단 모르니..😂
• 현 상황만 말하자면, 3회 필기를 합격하고 본, 3회 실기는 난 떨어졌다.
   

• 그것도,, 가장 화가나는 "1문제" 가 모자라 불합격 이었다. ( 이 또한,,벌써 한달전 )
• 사실, 이때 시험 치르고, 가책점 할때부터, 이래저래 찝찝한 부분이 한 두가지가 아니긴 했다.
  ( 예로들면, SQL 작성시 Alias할 때 ' ' 써도 되는 걸로 아는데 여러 블로그에서 가답안 나오는 것은 쓰지 않는다하고,, 또, 오답 지울 때는 2줄,,딱 2줄 ❗❗ 을 그어야 한다는 규정이 ( 있긴 있다.. 꼭 2줄 긋자..))
  
  
• 결과적으로 3회 정기 실기고사는 떨어졌다. 개인적으로 너무 화가나고,,찝찝했지만 나름 가책점했을 때
  55점 정도는 확실히 확보했다는 건 알았었고, 나머지 중에서 1개라도 적은 것이 정답 처리 해줬다면
  그래도 합격은 될꺼라 생각했던 것과 달리, 결과는 나락이었고, 진심,,무엇을 틀렸다고 한건지 너무 궁금했는데
  Q-Net에 문의까지 했지만, 기계적인 답변만 돌아올 뿐, 딱히 수는 없었고,,그렇게 3회 정기 실기는 불합격이었다. 

📢 실기( 수시고사, 재시험 )

• 바로 저번 주에 치르고 왔다.
• 개인적으로, 학기 중이기도 해서, 시험 보기 한 2주전에 생각했던, 계획대로 준비하진 못하고, 3회 정기 실기
  준비했을 때, 보았던 것을 "상기" 한다는 느낌으로 준비할 수 밖에 없었다.
• 원래, 이런 시험 있을 때, 밤을 새는 타입은 아닌데, 그래도 정리는 한번 다시 해야겠다는 생각으로 진행하다가
  어쩌다 보니, 자기 애매한 시간이 됬고, 더구나 아침 ( 09:00 ) 시험이고, 더구나 서울에서 시험이 있어서 ( 난 인천 )
  그냥,,, 밤 샜다. 🤣🤣🤣
• 결과는 12월 중순이나 말에 나온다고 예정 되어 있다.
• 2020-12-31 연말 선물이 왔다 🙏

📢 꿀팁 👏

• 이 글을 보고, 이후에 있을, 실기를 준비하는 사람이 있을테니, 나름 준비하면서 조언이 될만한 것을 좀 남기려 한다.
• 일단, 저번 정기 3회차 실기와 이번 수시 실기를 보고, 출제되는 편향을 보니 먼저
  📌 (간단한) 프로그래밍언어 관련 코드 문제 ( C,C++,Java,Python ) (SQL 포함이다 ❗❗ )  👉 6 ~ 7 문제
  
  📌 응용 SW 기초 기술 활용 ( 운영체제, DB, 네트워크 )  👉 3 ~ 4 문제
  
  📌 소프트웨어 개발 보안 구축 ( 보안, 공격기법, 네트워크 여러 프로토콜 정도 )  👉  4 ~ 5 문제
  
  📌 요구사항, 통합구현, 화면설계, 서버프로그램 구현, 소프트웨어 패키징  👉  3 ~ 4 문제
  
  📌 나머지, 진심 틀리라고 내는 문제 ( 난생 처음보는 구석탱이 내용 )  👉  1~3 문제 ( 이건 틀려도 됨, 맞으면 👍 )

• 결론 : [ 프로그래밍언어 활용, 운영체제, DB, 네트워크 ] 내용만 일단 90 % 만 맞는다 치면  👉 대략 45~55 점 확보
  그리고, 나머지 파트에서 적어도 2~3문제는 건진다는 생각으로 해서  👉 60점 돌파 ❗❗
  한다는 생각으로, 이 시험을 통과하겠단 생각으로 임해야, 어느정도 합격 확률이 높아 질 것이라 생각한다.
  ( 사실상, 이 시험을 100점 맞을 목표로 준비하는 시험은 절대 아니라도 하고 싶다. )

📢 마무리

• 이 글 시작에도 말했지만, 처음 "정보처리기사"를 준비하는 나의 자세는, "필요하긴 할꺼 같으니깐.." 이었다 했다.
• 그러나, 필기를 합격하고, 실기를 준비하면서, 생각이 달라졌다. 이 시험을 준비하면서, 나름 지금 껏 공부했던
  CS 개념을 다시 한번, 정리해보면서, 상기할 수 있는 시간이 되고 있단 생각을 했고, 이 시험이 끝날 수 있다해도
  내가 "취업"을 하는 그 날까진 "CS지식"은 주기적으로 정리하면서, 머릿속에 기억하고 있어야 할 부분이다.
• 올해, 말에 결과가 나오는데, 뭐,,,결과가 나와봐야 알겠지만, 가책점 결과, 기다려볼만한 상황인 거 같긴 하나
  끝까지 기다려 보자. 그 후는 ? 결과가 나온 후에 생각하자. 🙏🙏🙏   👉  합격 !! 😂

📢 ❗❗ 중요 ❗❗

• 이글을, 끝까지 읽어줬다는 전제하에,,(근데, 나름 진심 읽어볼만한 내용이기 때문에, 꼭 읽어봤음 좋겠고 )
  다른 사람의 자료는 함부로 공유하긴 그렇고,, 재시험 준비하면서, 나름 알고 가면 좋을 것 같은 것을
  정리한 내용을 공유하려고 한다.
• 참고해볼 생각이 있는 사람이 있다면, 댓글을 달아준다면, 공유해 보겠습니다. 🙏

소프트웨어 패키징

모듈별로 생성한 실행 파일들으 묶어 배포용 설치 파일을 만드는 것을 말한다.

- 개발자가 아닌, 사용자 중심으로 진행
- 소스 코드는 향후 관리를 고려하여 모듈화하여 패키징한다.

• 소프트웨어 패키징 작업 순서
  : 기능 식별 -> 모듈화 -> 빌드진행 -> 사용자 환경 분석 -> 패키징 및 적용 시험 -> 패키징 변경 개선 -> 배포

릴리즈 노트( Release Note )

개발 과정에서 정리된 릴리즈 정보를 소프트웨어 최종 사용자인 고객과 공유하기 위한 문서
[ Header(머릿말) ]  실기기출
: 릴리즈 노트 이름, 소프트웨어 이름, 릴리즈 버전, 날짜, 노트 날짜, 노트 버전 등을 표시함

• 릴리즈 노트 작성 순서
  • 1. 모듈 식별
  • 2. 릴리즈 정보 확인
  • 3. 릴리즈 노트 개요 작성
  • 4. 영향도 체크
  • 5. 정식 릴리즈 노트 작성
  • 6. 추가 개선 항목 식별

디지털 저작권 관리( DRM )

저작권자가 배포한 디지털 콘텐츠가 저작권자가 의도한 용도로만 사용되도록 디지털 콘텐츠의 생성, 유통, 이용까지의 전 과정에 걸쳐 사용되는 디지털 콘텐츠 관리 및 보호 기술

소프트웨어 패키징의 형상 관리( SCM : Software Configuration Management ) 실기기출

소프트웨어의 개발 과정에서 소프트웨어의 변경 사항을 관리하기 위해 개발된 일련의 활동

소프트웨어 버전 관리 도구

• 공유 폴더 방식 : 버전 관리 자료가 로컬 컴퓨터의 공유폴터에 저장되어 관리되는 방식
• 클라이언트/서버 방식 : 버전 관리 자료가 중앙 시스템(서버)에 저장되어 관리되는 방식
• 분산 저장소 방식 : 버전 관리 자료가 하나의 원격 저장소와 분산된 개발자 PC의 로컬 저장소에 함께 저장되어 관리
• SVN : Subversion :  CVS(Concurrent Version System)를 개선한 것. 클라이언드/서버 구조이며, 아파치 SW재단
• Git : 리누스 토발즈가 2005년 리눅스 커널 개발에 사용할 관리 도구로 개발

빌드 자동화 도구

빌드는 소스 코드 파일들을 컴파일한 후 여러 개의 모듈을 묶어 실행 파일로 만드는 과정

• Jenkins
  • Java 기반의 오픈 소스 형태, 가장 많이 사용되는 빌드 자동화 도구
  • 서블릿 컨테이너에서 실행되는 서버 기반 도구
  • SVN, Git 등 대부분의 형상 관리 도구와 연동이 가능
  • 여러 대의 컴퓨터를 이용한 분산 빌드나 테스트가 가능
• Gradle
  • Groovy를 기반으로 한 오픈 소스 형태의 자동화 도구, 안드로이드 앱 개발 환경에서 사용
  • 뿐만 아니라, 플러그인을 설정하면, Java,C/C++,Python등의 언어도 빌드 가능
  • Groovy를 사용해서 만들 DSL( Domain Specific Language )을 스크립트 언어로 사용
  • Gradle은 실행할 처리 명령들을 모아 태스크(Task)로 만든 후 태스크 단위로  실행함

네트워크( Network )

두 대 이상의 컴퓨터를 전화선이나 케이블 등으로 연결하여 자원을 공유하는 것

• 근거리 통신망( LAN : Local Area Network )
  
  • 학교,회사,연구소 등에서 비교적 가까운 거리에 있는 컴퓨터,프린터,저장장치 등과 같은 자원을 연결해서 구성
  • 사이트 간이 거리가 짧아 데이터의 전송 속도가 빠르고, 에러 발생율이 적다.
  • 주로 버스형 이나 링형 구조를 사용
• 광대역 통신망( WAN : Wide Area Network )
  
  • 국가와 국가 혹은 대륙과 대륙 등과 같이 멀리 떨어진 사이트들을 연결하여 구성
  • 사이트 간의 거리가 멀기 때문에 통신 속도가 느리고, 에러 발생률이 높다.

IP 주소( Internet Protocol Address )

인터넷에 연결된 모든 컴퓨터 자원을 구분하기 위한 고유한 주소

- 숫자로 8비트씩 4부분, 총 32비트로 구성
* 서브넷 마스크 : 4바이트의 IP 주소 중 네트워크 주소와 호스트 주소를 구분하기 위한 비트

IPv6( Internet Protocol version 6 )

현재 사용하고 있는 IP 주소 체계인 IPv4의 주소 부족 문제를 해결하기위해 개발

- 16비트씩 8부분, 총 128비트로 구성
- 각 부분을 16진수로 표현. 콜론(:)으로 구분
- IPv4에 비해 자료 전송 속도가 빠르고, IPv4와 호환성이 뛰어나다.
- 인증성, 기밀성, 데이터 무결성의 지원으로 보안 문제를 해결할 수 있다.

• IPv6 주소 체계
  • 유니캐스트( Unicast ) : 단일 송신자와 단일 수신자 간의 통신 ( 1:1 통신에 사용 )
  • 멀티캐스트( Multicast ) : 단일 송신자와 다중 수신자 간의 통신 ( 1:N 통신에 사용 )
  • 애니캐스트( Anycast ) : 단일 송신자와 가장 가까이 있는 단일 수신자 간의 통신 ( 1:1 통신에 사용 )

도메인 네임( Domain Name )

숫자로 된 IP 주소를 사람이 이해하기 쉬운 문자 형태로 표현한 것

* DNS( Domain Name System) : 다시, 문자로 된 도메인 네임을 컴퓨터가 이해할 수 있는 IP주소로 변환하는 역할
* 이런 역할을 하는 서버 : DNS 서버

OSI 참조 모델 ( Open System Interconnection )

다른 시스템 간의 원활한 통신을 위해 ISO(국제표준화기구)에서 제안한 통신규약(Protocol)

• OSI 7계층( 하위계층 ~ 상위계층, 하위계층으로 갈수록 개념이 세부적 )
  • 1. 물리 계층( Physical Layer )
    : 전송에 필요한 두 장치 간의 실제 접속과 절단 등 기계적, 전기적, 기능적, 절차적 특성에 대한 규칙 정의
  • 2. 데이터링크 계층( Data Link Layer )
    : 두 개의 인접한 개방 시스템들 간에 신뢰성 있고 효율적인 정보 전송을 할 수 있도록 함
    흐름제어, 프레임 동기화, 오류 제어, 순서 제어
  • 3. 네트워크 계층( Network Layer, 망 계층 )
    : 개방 시스템들 간의 네트워크 연결을 관리하는 기능과 데이터의 교환 및 중계 기능을 함
    경로 설정(Routing), 트래픽 제어, 패킷 정보 전송
  • 4. 전송 계층( Transport Layer )
    : 종단 시스템( End-to-End )간의 전송 연결 설정, 데이터 전송, 연결 해제 기능을 함
    주소 설정, 데이터의 분할과 재조립, 오류 제어, 흐름 제어
  • 5. 세션 계층( Session Layer )
    : 송수신 측 간의 관련성을 유지하고 대화 제어를 담당함
    대화 구성 및 동기 제어, 데이터 교환 관리 기능
  • 6. 표현 계층( Presentation Layer )
    : 응용 계층으로부터 받은 데이터를 세션 계층에 맞게, 세션 계층에서 받은 데이터는 응용 계층에 맞게 변환
    코드 변환, 데이터 암호화, 데이터 압축, 구문 검색, 포맷 변환, 문맥 관리 기능
  • 7. 응용 계층( Application Layer )
    : 사용자(응용 프로그램)가 OSI 환경에 접근할 수 있도록 응용 프로게스 간의 정보 교환, 전자 사서함, 파일 전송
    가상 터미널 등의 서비스를 제공함

네트워크 관련 장비

• 허브( Hub ) : 한 사무실이나 가까운 거리의 컴퓨터들을 연결하는 장치, 각 회선을 통합적으로 관리
• 리피터( Repeater ) : 물리 계층의 장비로, 전송되는 신호가 왜곡되거나 약해질 경우 원래의 신호 형태로 재생함
• 브리지( Bridge ) : 데이터 링크 계층의 장비, LAN과 LAN을 연결하거나 LAN 안에서의 컴퓨터 그룹을 연결
• 라우터( Router ) : 네트워크 계층 장비로, LAN과 LAN의 연결 및 경로 선택, 서로 다른 LAN이나 LAN과 WAN 연결
• 게이트웨이( Gateway ) : 전 계층(1~7계층)의 프로토콜 구조가 전혀 다른 네트워크의 연결을 수행함
• 스위치( Switch ) : 브리지와 같이 LAN과 LAN을 연결하여 훨씬 더 큰 LAN을 만드는 장치
  • L2 스위치 : OSI의 2계층. MAC주소를 기반으로 프레임 전송
  • L3 스위치 : OSI의 3계층. L2 스위치에 라우터 기능이 추가됨. IP 주소를 기반으로 패킷 전송
  • L4 스위치 : OSI의 4계층. IP 주소 및 TCP/UDP를 기반으로 사용자들의 요구를 서버의 부하가 적은 곳으로 배분
  • L7 스위치 : OSI의 7계층. IP 주소, TCP/UDP 포트정보에 패킷 내용까지 참조하여 세밀하게 부하 적은곳에 배분

TCP / IP( Transmission Control Protocol / Internet Protocol )

인터넷에 연결된 서로 다른 기종의 컴퓨터들이 데이터를 주고받을 수 있도록 하는 표준 프로토콜

• TCP( Transmission Control Protocol )
  • 신뢰성 있는 연결형 서비스를 제공
  • 패킷의 다중화, 순서 제어, 오류 제어, 흐름 제어 기능을 제공
  • 스트림( Stream ) 전송 기능을 제공
• IP ( Internet Protocol )
  • 데이터그램을 기반으로 하는 비연결형 서비스를 제공
  • 패킷의 분해/조립, 주소 지정, 경로 선택 기능을 제공
  • 헤더의 길이는 최소 20Byte에서 최대 60Byte

프로토콜( Protocol )

서로 다른 기기들 간의 데이터 교환을 원활하게 수행할 수 있도로 표준화시켜 놓은 통신 규약

• 프로토콜의 기본 요소 실기기출

TCP / IP의 구조 

TCP / IP의 응용 계층(Application Layer) 프로토콜

• FTP( File Transfer Protocol )
  : 컴퓨터와 컴퓨터 또는 컴퓨터와 인터넷 사이에서 파일을 주고받을 수 있도록 하는 원격 파일 전송 프로토콜
• SMTP( Simple Mail Transfer Protocol )
  : 전자 우편을 교환하는 서비스
• TELNET
  : 멀리 떨어져 있는 컴퓨터에 접속하여 자신의 컴퓨터처럼 사용할 수 있도록 해주는 서비스
• SNMP( Simple Network Management Protocol )
  : TCP / IP의 네트워크 관리 프로토콜
• DNS( Domain Name System )
  : 도메인 네임을 IP 주소로 매핑( Mapping )하는 시스템
• HTTP( HpyerText Transfer Protocol ) 실기기출
  : 월드 와이드 웹(WWW)에서 HTML 문서를 송수신 하기 위한 표준 프로토콜

TCP / IP의 전송 계층(Transport Layer) 프로토콜

• TCP( Transmission Control Protocol ) 실기기출
  
  • 양방향 연결( Full Duplex Connection )형 서비스를 제공
  • 가상 회선 연결( Virtual Circuit Connection ) 형태 서비스를 제공
  • 스트림 위주의 전달(패킷 단위)을 한다.
  • 신뢰성 있는 경로를 확립하고 메시지 전송을 감독
• UDP( User Datagram Protocol ) 실기기출
  • 데이터 전송 전에 연결을 설정하지 않는 비연결형 서비스 제공
  • TCP에 비해 상대적으로 단순한 헤더 구조를 가짐. 오버헤드가 적다
  • 고속의 안정성 있는 전송 매체를 사용하여 빠른 속도를 필요로 하는 경우
    동시에 여러 사용자에게 데이터를 전달할 경우
    정기적으로 반복해서 전송할 경우에 사용
  • 실시간 전송에 유리하며, 신뢰성보다는 속도가 중요시되는 네트워크에서 사용된다.
• RTCP( Real-Time Control Protocol )
  • RTP( Real-Time Transprot Protocol ) 패킷의 전송품질을 제어하기 위한 제어 프로토콜
  • 세션(Session)에 참여한 각 참여자들에게 주기적으로 제어 정보를 전송
  • 하위 프로토콜은 데이터 패킷과 제어 패킷의 다중화를 제공

TCP / IP의 인터넷 계층( Internet Layer ) 프로토콜

• IP( Internet Protocol )
  : 전송할 데이터에 주소 지정 및 경로 설정 등의 기능. 비연결형인 UDP 방식을 사용하므로 신뢰성 보장되지 않음
• ICMP( Internet Control Message Protocol )
  : IP와 조합하여 통신중에 발생하는 오류의 처리와 전송 경로 변경 등을 위한 제어 메시지를 관리하는 역할
  헤더는 8 Byte로 구성
• IGMP( Internet Group Management Protocol )
  : 멀티캐스트를 지원하는 호스트나 라우터 사이에서 멀티캐스트 그룹 유지를 위해 사용됨
• ARP( Address Resolution Protocol ) 실기기출
  : 호스트의,  IP 주소 -> MAC 주소로 변경
• RARP( Reverse Address Resolution Protocol )
  : ARP와 반대, MAC 주소 -> IP 주소로 변경

TCP / IP의 네트워크 액세스 계층( Access Layer ) 프로토콜

• Ethernet(IEEE 802.3) : CSMA/CD 방식의 LAN
• IEEE 802 : LAN을 위한 표준 프로토콜
• HDLC : 비트 위주의 데이터 링크 제어 프로토콜
• X.25 : 패킷 교환망을 통한 DTE와 DCE간의 인터페이스를 제공하는 프로토콜
• RS-232C : 공중 전화 교환망(PSTN)을 통한 DTE와 DTC간의 인터페이스를 제공하는 프로토콜

회선 교환 방식( Circuit Switching )

통신을 원하는 두 지점을 교환기를 이용하여 물리적으로 접속시키는 방식, 기존의 음성 전화망이 대표적

- 접속에는 긴 시간이 소요, 일단 접속되면 전송 지연이 거의 없어 실시간 전송이 가능
- 일정한 데이터 전송률을 제공하므로 동일한 전송 속도가 유지된다.

• 회선 교환 방식의 종류
  • 1. 공간 분할 교환 방식( SDS : Space Division Switching )
    : 기계식 접점과 전자 교환기의 전자식 접점 등을 이용하여 교환을 수행하는 방식. 음성 전화용 교환기가 속함
  • 2. 시분할 교환 방식( TDS : Time Division Switching )
    : 전자 부품이 갖는 고속성과 디지털 교환 기술을 이용하여 다수의 디지털 신호를 시분할적으로 동작시킴

패킷 교환 방식( Packet Switching )

메시지를 일정한 길이의 패킷으로 잘라서 전송하는 방식

- 패킷은 장애 발생 시의 재전송을 위해 패킷 교환기에 일시 저장되었다가 곧 전송되며 전송이 끝난 후 폐기된다.
- 전송 시 교환기, 회선 등에 장애가 발생하더라도 다른 정상적인 경로를 선택해서 우회할 수 있다
- 음성 전송보다 데이터 전송에 더 적합
- 패킷 교환망은 OSI 7계층의 네트워크 계층에 해당

• 패킷 교환 방식의 종류
  • 1. 가상 회선 방식 ( TCP 느낌 )
    : 단말장치 상호간에 논리적인 가상 통신 회선을 미리 설정하여 송신자와 수신자 사이의 연결을 확립한 후에
    설정된 경로를 따라 패킷들으 순서적으로 운반하는 방식
  • 2. 데이터그램 방식 ( UDP 느낌 )
    : 연결 경로를 설정하지 않고 인접한 노드들의 트래픽 상황을 감안하여 각각의 패킷들을 순서에 상관없이
    독립적으로 운반하는 방식

라우팅( Routing, 경로 제어 )

송수신 측 간의 전송 경로 중에서 최적 패킷 교환 경로를 결정하는 기능
경로 제어표( Routing Table )를 참조해서 이루어지며, 라우터에 의해 수행된다.

• 라우팅 프로토콜
  • RIP( Routing Information Protocol )
    : 현재 가장 널리 사용되는 라우팅 프로토콜, 소규모 동종의 네트워크 내에서 효율적 방법, 최대 홉수 15
  • IGRP( Interior Gateway Routing Protocol )
    : RIP의 단점을 보완하기 위해 개발된 것. 네트워크 상태를 고려하여 라우팅. 중규모 네트워크에 적합함
  • OSPF( Open Shortest Path First Protocol )
    : 대규모 네트워크에서 많이 사용되는 라우팅 프로토콜. 라우팅 정보에 변화가 생길 경우
    변화된 정보만 네트워크 내의 모든 라우터에 알림. RIP에 비해 홉수에 제한이 없음
  • BGP( Border Gateway Protocol )
    : 자율 시스템 간의 라우팅 프로토콜. EGP의 단점을 보완하기 위해 개발
• 라우팅 알고리즘
  • 1. 거리 벡터 알고리즘( Distance Vector Algorithm )
    : 인접해 있는 라우터 간의 거리(Distance)와 방향(Vector)에 대한 정보를 이용하여 최적의 경로를 찾고
    그 최적 경로를 이용할 수 없을 경우, 다른 경로를 찾는 알고리즘, RIP와 IGRP가 있다.
  • 2. 링크 상태 알고리즘( Link State Algorithm )
    : 라우터와 라우터 간의 모든 경로를 파악하여 미리 대체 경로를 마련해 두는 알고리즘
    거리 벡터 알고리즘의 단점을 보완하기 위해 개발. OSPF가 있다.

데이터베이스( Database )

특정 조직의 업무를 수행하는 데 필요한 상호 관련된 데이터들의 모임

DBMS( DataBase Management System, 데이터베이스 관리 시스템 )

사용자와 DB 사이에서 사용자의 요구의 따라 정보를 생성해주고, DB를 관리해주는 소프트웨어

• DBMS의 필수 기능
  • 정의 기능( Definition )
    : 모든 응용 프로그램들이 요구하는 데이터 구조를 지원하기 위해
    DB에 저장될 데이터의 형(Type)과 구조에 대한 정의, 이용방식, 제약 조건 등을 명시하는 기능
  • 조작 기능( Manipulation )
    : 데이터 검색, 갱신, 삽입, 삭제 등을 체계적으로 처리하기 위해 사용자와 DB 사이의 인터페이스 수단 제공
  • 제어 기능( Control )
    : DB를 접근하는 갱신, 삽입, 삭제 작업이 정확하게 수행되어 데이터의 무결성이 유지되도록 제어 기능
• DBMS의 종류
  • 계층형 DBMS
    : 트리(Tree) 구조를 이용해서 데이터의 상호관계를 계층적으로 정의한 DBMS
    개체 타입 간에는 상위(Owner)와 하위(Member) 관계가 존재하며, 일 대 다(1:N) 대응 관계만 존재
  • 망형 DBMS
    : 그래프를 이용해서 데이터 논리 구조를 표현한 DBMS로, 상위(Owner)와 하위(Member) 레코드 사이에서
    1:1, 1:N, N:M 대응 관계를 모두 지원
  • 관계형 DBMS
    : 계층형과 망형 DBMS의 복잡한 구조를 단순화시킨 가장 널리 사용되는 DBMS
    파일 구조처럼 구성한 2차원적인 표(Table)를 하나의 DB로 묶어서 테이블 내에 있는 속성들 간의
    관계(Relationship)를 설정하거나 테이블 간의 관계를 설정하여 이용

분산 데이터베이스( Distributed Database )

논리적으로는 같은 시스템에 속하지만 물리적으로는 컴퓨터 네트워크를 통해 분산되어있는 DB

• 분산 데이터베이스 목표
  • 1. 위치 투명성( Location Transparency )
    : 접근하려는 데이터베이스의 실제 위치를 알 필요 없이 단지 DB의 논리적인 명칭만으로 접근할 수 있음
  • 2. 중복 투명성( Replication Transparency )
    : 동일한 데이터가 여러 곳에 중복되어 있더라도 사용자는 마치 하나의 DB만 존재하는 것처럼 사용할 수 있음
  • 3. 병행 투명성( Concurrency Transparency )
    : 분산 데이터베이스와 관련된 다수의 트랜잭션들이 동시에 실행되더라도 그 트랜잭션들의
    수행 결과를 서로 영향을 받지 않는다
  • 4. 장애 투명성( Failure Transparency )
    : 트랜잭션은 DBMS, 네트워크, 컴퓨터 장애에도 불구하고 트랜잭션은 정확하게 수행됨

고급 데이터베이스

• 데이터 웨어하우스( Data Warehouse )
  : 급증하는 다량의 데이터를 효과적으로 분석하여 정보화하고, 이를 여러 계층의 사용자들이
  효율적으로 사용할 수 있도록 한 DB
  
• 데이터 마트( Data Mart )
  : 데이터 웨어하우스로부터 특정 주제나 부서 중심으로 구축된 소규모 단일 주제의 데이터 웨어하우스
• 데이터 마이닝( Data Mining ) 실기기출
  : 데이터 웨어하우스에 저장된 데이터 집합에서 사용자의 요구에 따라 유용하고 가능성 있는 정보를 발견하는 기법
• OLAP( Online Analytical Processing )
  : 다차원으로 이뤄진 데이터로부터 통계적인 요약 정보를 분석하여 의사결정에 활용하는 방식
• OLTP( Online Transaction Processing )
  : 온라인 업무 처리형태의 하나. 네트워크상의 여러 이용자가 실시간으로 DB의 데이터를
  갱신하거나 검색하는 등의 단위 작업을 처리하는 방식

ER( Entity Relationship )모델

개념적 데이터 모델의 가장 대표적인 모델

• 관계 및 관계 타입

- 차수( Degree ) : 관계에 참여하는 개체 타입( 속성,Attribute )의 개수
- 카디널리티( Cardinality ) : 관계에 참여하는 개체(튜플, Tuple)의  개수

• 차수에 따른 관계 종류
  • 단항 관계 : 관계에 참여하고 있는 개체 타입이 1개인 관계
  • 이항 관계 : 관계에 참여하고 있는 개체 타입이 2개인 관계
  • 삼항 관계 : 관계에 참여하고 있는 개체 타입이 3개인 관계
  • n항 관계 : 관계에 참여하고 있는 개체 타입이 n개인 관계
• 카디널리티에 따른 관계 종류
  • 1:1 관계 : 두 개체 타입이 모두 하나씩의 개체 카디널리티를 갖는 관계
  • 1:N 관계 : 개체 타입 중 한 개체타입은 여러 개의 개체 카디널리티를 갖고, 다른하나는 1개의 개체 카디널리티
  • N:M 관계 : 두 개체 타입 모두 여러 개의 개체 카디널리티를 가질 수 있는 관계

관계 데이터베이스의 Relation 구조 실기기출

릴레이션은 데이터들의 표(Table)의 형태로 표현한 것
- 릴레이션 스키마 : 구조를 나타냄
- 릴레이션 인스턴스 : 실제 값들

• 튜플( Tuple )
  • 릴레이션을 구성하는 각각의 행
  • 속성의 모임으로 구성
  • 파일 구조에서 레코드(Record)와 같은 의미
  • 튜플의 수 = 카디널리티(Cardinality)
• 속성( Attribute )
  
  • 릴레이션을 구성하는 각각의 열
  • DB를 구성하는 가장 작은 논리적 단위
  • 파일 구조 상의 데이터 항목 또는 데이터 필드에 해당
  • 개체의 특성을 기술
  • 속성의 수 = 차수(Degree)
• 도메인( Domain )
  • 하나의 속성(Attribute)이 취할 수 있는 같은 타입의 원자값(Atomic)들의 집합
  • 실제 속성(Attribute)값이 나타낼 때 그 값의 합법 여부를 시스템이 검사하는데 사용
• 인스턴스( Instance )
  
  • 속성들에 데이터 타입이 정의되어 구체적인 데이터 값을 갖고 있는 것

ER모델을 관계형 데이터 모델로 변환

ER 모델을 -> ( 논리적 데이터 모델인 ) 릴레이션 스키마로 변환. 매핑(Mapping)한다고도 한다.

키( Key )의 개념 및 종류 

키( Key )는 DB에서 조건에 만족하는 튜플을 찾거나 순서대로 정렬할 때 기준이 되는 속성

• 슈퍼키( Super Key )
  : 한 릴레이션 내에 있는 속성들의 집합으로 구성된 키. 릴레이션을 구성하는 모든 튜플에 대해
  유일성( Unique )은 만족하지만, 최소성( Minimality )은 만족하지 못함
• 후보키( Candidate Key ) 
  : 릴레이션을 구성하는 속성들 중에서 튜플을 유일하게 식별하기 위해 사용되는 속성들의 부분집합
  유일성과 최소성을 모두 만족함
• 기본키( Primary Key )
  : 후보키 중에서 특별히 선정된 키. 중복된 값과 NULL값을 가질 수 없음
• 대체키( Alternate Key )
  : 기본키를 제외한 나머지 후보키
• 외래키( Foreign Key )
  : 다른 릴레이션의 기본키를 참조하는 속성 또는 속성들의 집합. 릴레이션 간의 관계를 표현할 때 사용

무결성( Integrity )

DB에 저장된 데이터 값과 그것이 표현하는 현실세계의 실제값이 일치하는 정확성을 의미

• 1. 개체 무결성( Entity Integrity ) : 기본 테이블의 기본키를 구성하는 어떤속성도 Null 값이나 중복값 가질수 없다.
• 2. 도메인 무결성( Domain Integrity ) : 주어진 속성 값이 정의된 도메인에 속한 값이어야 한다.
• 3. 참조 무결성( Referential Integrity ) : 외래키 값은 Null이거나 참조 릴레이션의 기본키 값과 동일해야 함
• 4. 사용자 정의 무결성( User-Defined Integrity ) : 속성 값들이 사용자가 정의한 제약조건에 만족해야 함