24.01.19 CSAPP 3.4, 그래프, 위상정렬, 비트리, DFS, BFS

CSAPP 3.4

3.4 정보 접근하기

• x86-64 주처리 장치 CPU는 64비트를 저장할 수 있는 범용 레지스터 16개를 보유한다
• 레지스터는 정수 데이터와 포인터를 저장하는데 사용한다.
• 인스트럭션들은 16개의 레지스터 하위 바이트들에 저장된 다양한 크기의 데이터에 대해 연산 할 수 있다.
  • 바이트 수준 연산은 가장 덜 중요한 바이트에 대해 연산, 16비트 연산은 덜 중요한 2바이트, 32비트는 4바이트 , 64비트 연산은 레지스터 전체에 접근한다.
• 일반적인 프로그램에서 서로 다른 레지스터들은 서로 다른 목적으로 이용한다. 스택 포인터 %rsp는 런타임 스택 끝 부분을 가리키기 위해 사용된다. 일부 인스트럭션들은 특별히 이 레지스터를 읽고 쓴다. 다른 15개의 레지스터는 사용이 저금 더 자유롭다.

3.4.1 오퍼랜드 식별자(Specifier)

• 대부분 인스트럭션은 하나 이상의 오퍼랜드를 가진다.
  • 오퍼랜드 - 연산에 사용될 데이터 혹은 데이터가 저장된 위치
• 오퍼랜드 연산을 수행할 소스(Source)값과 그 결과를 저장할 목적지(Destination)의 위치를 명시한다. x86-64는 여러가지 오퍼랜드 형식을 지원한다. 소스값을 상수로 주어지거나 레저스터나 메모리로부터 읽을 수 있다. 결과 값은 메모리나 레지스터에 저장된다.
• 오퍼랜드의 종류는 세가지 타입으로 구분할 수 있다.
  1. 상수 값 즉시 값(Immediate)
     • ATT 형식의 어셈블리 코드에서, 상수는 $ 기호 다음에 C 표준 서식을 사용하는 정수로 $577, $0xAF 같이 나타낸다. 서로 다른 인스트럭션들은 다양한 범위의 상수값을 사용할 수 있다.
  2. Register 레지스터에 내용을 나타낸다.
     • 각각 16개 64비트, 32비트, 16비트 레지스터들의 하위 일부분인 8,4,2,1바이트 중 하나의 레지스터를 가리킨다. Ra는 임의의 레지스터를 나타내며 해당 값을 R[ra]을 참조하여 지정되며, 레지스터 집합을 배열R과 레지스터 식별자를 인덱스로 사용하는 형태로 나타낸다.
  3. Memory 메모리 참조
     • 유효주소(Effective address) 라고 부르는 계산된 주소에 의해 메모리에 접근한다.
       • 유효주소 : 주소지정 방식에 의해 결정되는 오퍼랜드 주소
     • 메모리는 거대한 바이트 배열로 생각할 수 있으므로 Mb[Addr] 와 같이 표시하며 메모리주소 Addr부터 저장된 b바이트를 참조하는것을 나타낸다. 단순화를 위해 b는 생략할 수 있다.
     • 여러 주소지정 방식이 존재하는데, 가장 일반적인 형태는 lmm(rb,ri,s)다. 상수 오프셋 lmm, 베이스 레지스터 rb, 인덱스 레지스터 ri, 배율 s. s는 1, 2, 4, 8의 값. 베이스 레지스터와 인덱스레지스터는 64비트 레지스터다
     • 유효주소는 lmm+ R[rb] + R[ri] * s로 계산한다.
  3.4.2 데이터 이동 인스트럭션
  • 가장 많이 사용되는 인스트럭션은 데이터를 한 위치에서 다른 위치로 복사하는 명령이다.
  • MOV클래스 이 인스트럭션들은 소스 위치에서 데이터를 목적지 위치로 어떤 변환도 하지 않고 복사한다. movb, movw, movl, movq 1, 2, 4, 8byte 대해 계산
  • 소스 오퍼랜드는 상수, 레지스터 저장 값, 메모리 저장 값을 표시한다.
  • 목적 오퍼랜드는 레지스터 또는 메모리 주소 위치를 저장 한다.
  • x86-64는 데이터 이동 인스트럭션에서 두 개의 오퍼랜드 모두가 메모리 위치에 올 수 없도록 제한하고 있다. 하나의 메모리 위치에서 다른 위치로 어떤 값을 복사하기 위해서는 두개의 인스트럭션이 필요하다.
    • 첫 번째는 소스 값을 레지스터에 적재하는 인스트럭션.
    • 두 번째는 이 레지스터 값을 목적지에 쓰기 위한 인스트럭션이 필요하다.
  • 인스트럭션들의 레지스터의 크기는 인스트럭션의 마지막 문자(’b’, ‘w’, ‘l’, ‘q’)가 나타내는 크기와 일치 해야한다. 대부분의 경우 MOV 인스트럭션들은 특정 레지스터 바이트들이나 대상 오퍼랜드에 의해 지정된 메모리 위치만을 업데이트 할 것이다. 유일한 예외는 movl이 레지스터를 목적지로 가지는 것으로 이 경우 레지스터의 상위 4바이트를 0으로 설정한다.
  • 명령어 소스오퍼랜드 목적오퍼랜드
  • movabsq는 64비트 상수를 다루기 위한 것이다. movq는 32비트 2의 보수 숫자로 나타낼 수 있는 상수 소스 오퍼랜드 만을 갖는다. 이 값은 그 후 부호 확장되어 목적지를 위해 64비트 값을 생성한다. movabsq는 임의의 64비트 상수값을 소스 오퍼랜드로 가질 수 있으며, 목적지로는 레지스터만을 가질 수 있다.
  • MOVZ 클래스의 인스트럭션은 목적지의 남은 바이트를 모두 0으로 채워주며 MOVS클래스는 소스오퍼랜드의 가장 중요한 비트를 반복해서 복사하는 부호 확장으로 채운다. 이 명령들의 이름에는 마지막 두개의 문자가 크기를 나타내는 지시자를 갖는다. 첫 번째는 소스의 크기, 두 번째는 목적지의 크기
  • cltq 인스트럭션 : 오퍼랜드가 없다. 언제나 레지스터 %eax를 소스로 ,%rax를 목적지로 사용해서 부호 확장 결과를 만든다. movslq %eax %rax와 정확히 동일한 효과지만 조금 더 압축적인 인코딩을 갖는다.
  데이터 이동 예제
  • 데이터 이동(mov), 함수가 호출 된 위치로 리턴(ret)
  어셈블리 코드에서 두 가지 특징
  1. C언어에서 ‘포인터’라고 부르는 것이 어셈블리 어에서는 단순히 주소다. 포인터를 역참조하는 것은 포인터를 레지스터에 복사하고, 이 레지스터를 메모리 참조에 사용하는 과정으로 이루어진다.
     • 역참조(Dereferencing) : 프로그래밍에서 데이터가 저장된 주소로 가서, 그 주소가 해당하는 데이터 값에 접근하는 것을 말한다.
  2. 지역변수들은 메모리에 저장되기 보다는 종종 레지스터에 저장된다. 레지스터 접근은 메모리 보다 속도가 훨씬 더 빠르다.
  3.4.4 스택 데이터의 저장과 추출
  • 스택은 프로시저 호출을 처리하는데 중요한 역할을 한다.
  • Top에서 제거하거나 추가한다.
  • x86-64에서 프로그램 스택은 메모리의 특정 영역에 위치한다. 스택의 top원소는 모든 스택 원소중에서 가장 낮은 주소를 갖는 형태로 스택은 아래 방향으로 성장한다. 스택 포인터 %rsp는 스택 맨 위 원소의 주소를 저장한다.
  • popq, pushq는 한개의 오퍼랜드를 사용한다. 추가할 소스 데이터와, 추출을 위한 데이터 목적지. 쿼드워드 값을 스택에 추가하려면 먼저 스택포인터를 8감소시키고, 그 값을 스택 주소의 새로운 탑top에 기록 하는 것으로 구현한다.
  • 스택이 프로그램 코드와 다른 형태의 프로그램 데이터와 동일한 메모리에 접근 되기 때문에 프로그램들은 표준 메모리 주소지정방법을 사용해서 스택 내 임의의 데이터에 접근할 수 있다.

자료구조

그래프(Graph)

그래프의 정의와 특징

• 정의
  • 그래프는 정점(vertex)와 그 정점을 연결하는 간선(Edge)으로 구성된다. 이러한 정점과 간선의 집합으로 이루어진 자료구조를 그래프라고 한다.

그래프 용어

• 정점(Vertex) : 노드(Node) 라고도 하며 데이터가 저장되는 그래프의 기본 원소이다.
• 간선(Edge) : 링크(Link) 라고도 하며 정점간의 관계를 나타낸다.
• 인접정점(Adjacent Vertex) : 하나의 정점에서 간선에 의해 직접 연결된 정점을 뜻한다.
• 차수(Degree) : 정점에 연결된 간선의 수, 무방향 그래프에서 하나의 간선은 두개의 정점에 인접하기에 간선 수에 2배를 해주면 된다. 방향 그래프의 경우 외부에서 오는 간선의 수를 진입차수(in-degree)라고 하며, 외부로 향하는 간선의 수를 진출차수(out-degree)라고 한다.
• 경로(Path) : 간선을 따라 갈 수 있는 길, 정점을 나열하여 표시한다.
• 경로의 길이(Length) : 경로를 구성하는데 사용된 간선의 수
• 단순 경로(Simple Path) - 경로 중에서 반복되는 간선이 없는 경로
• 사이클(Cycle) : 시작 정점과 종료 정점이 같은 단순경로

특징

1. 방향성 : 그래프는 방향성이 있을 수도 있고, 없을 수도 있습니다. 방향성이 있는 그래프를 유향 그래프(Directed Graph), 없는 그래프를 무향 그래프(Undirected Graph)라고 한다.
2. 가중치 : 간선에 가중치가 할당 되어 있을 수 있다. 이를 가중그래프(Weighted Graph)라고 한다. 네트워크(Network)라고 불리기도 한다.
3. 루프와 다중간선 : 그래프에는 자기자신으로 돌아오는 루프나 두 정점 사이에 여러 간선이 있을 수 있다.
4. 연결성 : 모든 정점이 어떤 경로로든 연결되어 있으면 연결그래프(Connected Graph)라고 한다.
5. 모든 정점간에 간선이 존재하는 그래프를 완전그래프(Complete Graph)라고한다. 정점이 N이면 간선의 수는 N*(N-1)/2

• ‘arc’는 그래프 이론에서 주로 ‘간선(edge)’와 같은 의미로 사용되며, 보통 유향그래프(Directed Graph)에서 간선을 지칭할 때 사용된다. 즉, 유향 그래프에서는 시작 정점에서 끝 정점까지 방향성이 있는 연결선을 ‘arc’라고 부른다.
  • 간선 : 방향성이 없다.
  • Arc : 방향성이 있다. ‘A-B’ Arc와 ‘B-A’ Arc는 다르게 취급한다.

그래프 구현 - 인접행렬(Adjacency Matrix)

• 컴퓨터에서 그래프를 구현하는 방법에는 배열(Array)을 사용하는 방법과 연결리스트(LinkedList)를 사용하는 방법이 있다.

인접행렬을 이용한 그래프 구현

• 그래프의 정점을 2차원 배열로 만든 것.
  • 정점의 개수가 n이라면 n*n 형태의 2차원 배열이 인접행렬로 사용된다.
  • 인접행렬에서 행과 열은 정점을 의미하며, 각각의 원소들은 정점간의 간선을 나타낸다.
• 무 방향 그래프는 대칭적 구조를 가진다.(두 개의 정점에서 간선이 동시에 연결되어 있기 때문이다.)
• 가중치 그래프 는 행렬에서 0과 1이 아니라 각 간선의 가중치 값이 저장된다. (이 경우 가중치가 0인 것과 간선이 없는것이 구별 되어야 한다.)
• 장점
  • 2차원 배열에 모든 정점들이 간선 정보가 있기 때문에, 두 정점을 연결하는 간선을 조회시키는 O(1) 시간복잡도로 가능하다.
  • 정점(i)의 차수를 구할때는 다음과 같이 인접행렬의 i번째 행을 모두 더하면 되므로 O(n)시간 복잡도를 가진다.
  • 구현이 비교적 간단하다.
• 단점
  • 간선의 수와 무관하게 n² 크기의 2차원 배열이 필요하므로 메모리 공간이 낭비된다.
  • 그래프의 모든 간선의 수를 알기 위해서는 인접행렬 전체를 확인 해야하므로 O(n²) 시간이 소요된다.

그래프 구현 -인접리스트(Adjacency List)

• 각 정점에 인접한 정점들은 연결리스트(Linked List)로 표현하는 방법
• 정점의 개수만큼 인접리스트가 존재하고, 각각의 인접리스트에는 인접한 정점 정보가 저장 되는것이다. 그래프는 각 인접리스트에 대한 헤드 포인터를 배열로 갖는다.
• 무방향 그래프의 경우 간선이 추가되면 각각의 정점의 인접리스트에 반대편 정점의 노드를 추가해야한다.
• 장점
  • 존재하는 간선만 관리하면 되므로 메모리 사용 측면에서 보다 효율적이다. 그래프의 모든 간선의 수를 알아내려면 각 정점의 헤더노드부터 모든 인접리스트를 탐색해야 하므로 O(n+e)의 시간이 소요된다.
• 단점
  • 두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해서는 정점의 인접리스트를 탐색해야하므로 정점 차수만큼의 시간이 필요하다. O(degee(v))
  • 구현이 비교적 어렵다.

Algorithm

DFS(Depth-First Search)

• 깊이 우선 탐색 알고리즘
• 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문 한 후 다시 돌아가 다른 경로로 탐색하는 알고리즘
• DFS는 스택 자료구조를 이용한다(보통 재귀함수를 이용해 DFS를 구현한다.)
• 동작과정
  1. 탐색 시작노드를 스택에 삽입 후 방문 처리를 한다.
  2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접노드가 없으면 최상단 노드를 꺼낸다.
  3. 2를 수행할 수 없을때까지 반복한다.

def DFS(graph,v,visit):
	visited[v] = True
	print(v)
	for i in graph[v]:
		if not visited[i]:
			DFS(graph,i,visited)

BFS(Breadth-First Search)

• 너비 우선 탐색 알고리즘
• 가까운 노드부터 탐색하는 알고리즘
• 큐를 이용해서 구현하는 것이 정석이다.
• 동작과정
  1. 탐색 시작노드를 큐에 삽입 후 방문처리를 한다.
  2. 큐에서 노드를 꺼내 해당 노드의 인접노드중 방문하지않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
  3. 2의 과정을 수행할 수 없을때까지 반복한다.

from collections import deque

def BFS(graph,start,visited):
	queue = deque([start])
	visited[start] = True
	while queue:
		v = queue.popleft()
		print(v)
		for i in graph[v]
			if not visited[i]:
				queue.append(i)
				visited[i] = True

위상정렬(Topological Sorting)

• 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘.
• 사이클이 없는 방향, 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것.

진입차수와 진출차수

• 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수
• 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수
• 동작과정
  • 큐를 이용해 구현한다.
  1. 진입차수가 0 인 노드를 큐에 넣는다.
  2. 큐가 빌 때까지 다음의 과정을 반복한다
     1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다
     2. 새롭게 진입차수가 0이 된 노드를 큐에 삽입한다.
  • 위상정렬을 수행할 수 있는 그래프는 사이클이 없는 방향 그래프(DAG)이여야 한다.

위상정렬의 특징

• 위상정렬은 사이클이 없는 방향그래프(DAG)에 대해서만 수행할 수 있다.
  • DAG(Direct Acyclic Graph) : 순환하지 않는(사이클이 없는) 방향 그래프
• 위상정렬에서는 여러가지 답이 존재할 수 있다. 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러가지 답이 존재할 수 있다는 의미다.
• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다.
• 보통 큐로 구현하나 스택을 이용한 DFS를 이용해 위상정렬을 구현할 수 있다.
• 시간복잡도 O(V+E)

B-Tree

• B트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 밸런스를 맞추는 트리다. 정렬된 순서를 보장하고, 멀티 레벨 인덱싱을 통한 빠른 검색이 가능하다.
• B트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다. 최대 M개의 지식을 가질 수 있는 B트리를 M차 B트리라고하며 다음과 같은 특징을 가진다.
  • 노드는 최대 M개부터 최소 M/2개 까지의 자식을 가질 수 있다.
  • 노드에는 최대 M-1개 부터 최소 [M/2]-1개의 키가 포함 될 수 있다.
  • 노드의 키가 x라면 자식의 수는 x+1개 이다.
  • 최소차수는 자식수의 하한값을 의미, 최소차수가 t라면 M=2t-1를 만족한다.

Key 검색과정

• 루트노드에서 시작하여 하향식으로 검색을 수행한다(검색하고자 하는 key가 k)
  1. 루트노드에서 시작하여 key들을 순회하면서 검사
     1. 만일 k와 key가 같다면 검색 종료
     2. 검색하는 값과 key들의 대소 관계를 비교. 어떠한 key들 사이에 k가 들어간다면 해당 key들 사이의 자식노드로 내려간다.
  2. 해당 과정을 리프노드에 도달할 때까지 반복, 리프노드에도 k와 같은 key가 없다면 검색을 실패한다.

삽입

1. 추가는 항상 Leaf노드에서 한다.
2. 노드가 넘치면 가운데 기준으로 분할, 가운데 키를 승진시킨다.

삭제

1. 삭제도 항상 Leaf에서 한다.
2. 삭제 후 최소 key보다 작은가?
   1. 형제 노드의 지원을 받는다.
   2. 1이 안된다면 부모의 지원을 받고 형제와 합한다.
   3. 문제가 있다면 다시 1번부터 반복한다.
3. 문제가 있다면 다시 1번부터 한다.

• 인터널에서 삭제시

1. Leaf노드에서 삭제하고 필요시 재조정한다.
2. Leaf 노드 중 적절한 위치(가장 가까운) 키 값과 swap후 제거한다.
3. 삭제 과정을 반복한다.