24.01.23 CSAPP 3.8, 복습,2Week, Python

CSAPP

3.8 배열의 할당과 접근

• C에서 배열을 스칼라 데이터를 보다 큰 자료형으로 연계 시키는 수단이다. 한가지 특이한 점은 배열 원소들에 대한 포인터를 만들고 이들 포인터간에 연산을 할 수 있다는 점이다. 이것은 기계어에서 주소 계산으로 번역된다.

3.8.1 기본원리

• 자료형 T와 정수형 상수 N

T A[N];

• 시작하는 위치를 xA라고 표시했을 때, 이 선언은 두 가지 효과를 갖는다.
  1. 이것은 L*N 바이트의 연속적인 공간을 메모리에 할당하며, 여기서 L(바이트의 단위)은 자료형 T의 크기를 나타낸다.
  2. 새로운 식별자 A를 통해서 배열이 시작하는 위치의 포인터로 사용한다. 이 포인터의 값은 xA다.
• 배열의 각 원소는 0에서 N-1 사이의 정수형 인덱스를 사용해서 접근 가능하다.
• 배열의 원소 i는 xA + L*i에 저장된다.

3.8.2 포인터 연산

• C는 포인터간에 연산을 허용하며, 계산된 값은 포인터가 참조하게 되는 자료형의 크기에 따라 그 값이 확대된다.
• 단항 연산자(unary) ‘&’ ‘*’ 는 포인터 생성과 역참조를 수행한다 즉 어떤 객체를 나타내는 식 Expr에 대해 &Expr은 그 객체의 주소를 주는 포인터이다. 주소를 나타내는 식 AExpr에 대해 *AExpr은 그 주소에 위치한 값을 준다.
• 배열참조 A[i]는 *(A+i)와 동일하다. 이것은 i번째 배열 원소의 주소를 계산해서 이 메모리 위치에 접근한다.
• 동일한 자료구조내에서 두 포인터의 차를 계산 할 수 있다.

3.8.3 다중배열

• 배열의 원소들은 메모리에 ‘행 우선(row major)’ 순서로 저장되는데, 이것은 A[0]으로 표시하는 모든 행 0의 원소들 다음에 행1(A[1])의 원소가 따라오는 방식으로 저장되는 것을 의미한다. 이러한 저장 순서는 우리가 사용한 다중선언의 결과이다.
• 다차원 배열의 원소에 접근하기 위해서 컴파일러는 원하는 원소의 오프셋을 계산하는 코드를 생성하고, 배열의 시작을 기본 주소로, 오프셋을 인덱스(배율이 적용될 수도 있음)로 하는 MOV인스트럭션을 사용한다.

3.8.4 고정 크기의 배열

• 최적화 수준이 -0일때 GCC가 수행하는 몇 가지 최적화

#define N 16

typedef int fix_matrix[N][N];

• 프로그램이 배열의 차원이나 버퍼의 크기로 상수를 사용할 때, 매번 숫자를 사용하는것보다 #define 선언을 통해 변수명과 숫자를 연관지어 일괄적으로 변수명을 사용하는 것이 가장 좋다.

1. A의 행 i의 연속된 원소들을 가리키는 Aptr로 이름 붙인 포인터를 생성한다.
2. B의 열 k의 연속된 원소들을 가리키는 Bptr로 이름 붙인 포인터를 생성한다.
3. 루프를 종료할 때 Bptr이 갖게 될 값과 동일한 Bend라고 이름 붙인 포인터를 생성한다.

3.8.5 가변 크기 배열

int A[expr1][expr2]

• 가변 크기 배열의 C버전에서는 배열을 다음과 같이 지역변수나 함수의 인자로 선언할 수 있으며, 그러고 나서 배열의 차원은 선언 부분을 만날 때 수식 expr1과 expr2를 계산해서 결정된다.

int var_ele(long n, int A[n][n], long i, long j){
	return A[i][j];
}

• 매개변수 n은 반드시 매개변수 A[n][n] 보다 먼저 나와야 한다. 그래서 함수가 매개변수를 만날 때 배열의 차원을 계산 할 수 있다.
• 가변 크기 배열은 참조하기 위해서는 고정 크기 배열의 결과를 약간만 일반화 하면 된다. 동적 버전에서는 일련의 쉬프트와 더하기 대신에 i를 n으로 확대하기 위해서 곱셈을 사용해야 한다. 일부 프로세서에서는 곱셈이 상당한 성능저하를 가져오지만, 이 경우에는 어쩔 수 없다.
• 루프내에서 가변 크기 배열을 참조할 때, 컴파일러는 접근하는 유형의 규칙성을 활용해서 종종 인덱스 계산을 최소화 할 수있다.

PYTHON

• 2차원 배열 for 만드는 법

arr = [[0 for i in range(num)] for i in range(num)]

2_Week 퀴즈

캐시메모리 지역성(locality)

• 시간적지역성(Temporal Locality) : 한번 접근 된 데이터는 가까운 미래에 다시 접근 될 가능성이 높다.
• 공간적지역성(Spatial Locality) : 메모리의 특정 주소에 접근한 후, 그 주변 주소에 접근 될 가능성이 높다.

복습

비트리(B-Tree)

• 이진 탐색 트리의 경우 시간복잡도가 이진탐색의 시간복잡도인 O(logN)이 되지만, 균형이 잡히지 않은 경우 O(n)에 수렴하게 된다. 이러한 단점을 보완하고자 나왔다.
• 비트리는 이진트리와는 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다. 최대 M개의 자식을 가질 수 있는 비트리를 M차 비트리라고 하며 다음과 같은 특징을 가진다.
  • 노드는 최대 M개부터 최소 ⌈M/2⌉개 까지의 자식을 가질 수 있다.
  • 노드에는 최대 M-1 부터 최소⌈M/2⌉ - 1 개의 키가 포함될 수 있다.
  • 노드의 키가 x개라면 자식의 수는 x+1 이다
• O(logN)의 검색성능
• 모든 leaf node는 같은 레벨에 있다.
• 자료는 중복되지 않는다.
• 자식 수의 하한값을 t 라고 하면 M = 2t-1을 만족한다.

트라이(trie)

• 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조이다.
• 자동완성, 사전 검색등 문자열 탐색에 특화되어있는 자료구조이다.
• 장점
  • 문자열 검색이 빠르다
  • 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간 복잡도 측면에서 훨씬 더 효율적이다
• 단점
  • 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가 크다는 단점도 있다(메모리 측면에서 비효율적)
• 트라이의 생성 시간 복잡도는 O(M*L), 탐색 시간 복잡도는 O(L)
  • 제일 긴 문자열의 길이 : L , 총 문자열들의 수 M
  • 이진 검색 트리에서는 O(LlogM)

다익스트라(dijkstra)

• 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.

동작단계

1. 출발 노드와 도착 노드를 설정한다.
2. ‘최단 거리 테이블’을 초기화 한다
3. 현재 위차한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다.
4. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 ‘최단 거리 테이블’을 업데이트 한다.
5. 3,4 과정을 반복한다.

• ‘최단 거리 테이블’은 1차원 배열로, N개 노드까지 오는 데 필요한 최단 거리를 기록한다. N개( 1부터 시작하는 노드 번호와 일치시키려면 N+1) 크기의 배열을 선언하고 큰 값을 넣어 초기화시킨다.
• ‘노드 방문 여부 체크 배열’은 방문한 노드인지 아닌지를 기록하기 위한 배열로, 크기는 ‘최단 거리 테이블’과 같다. 기본적으로는 False로 초기화하여 방문하지 않았음을 명시한다.

플로이드 워셜

• 모든 최단 경로를 구하는 알고리즘
  • 모든 노드 간 최단 경로를 구하는 알고리즘
  • 다익스트라와 다르게 음의 간선도 사용할 수 있다.
• 2차원 인접 행렬을 이용한다.
• 시간 복잡도는 O(N^3)

동작

1. 그래프의 노드와 간선에 따라 최단 거리 테이블을 갱신한다.
2. 1번 노드를 거쳐가는 경우를 고려해서 테이블을 갱신한다.
3. 2번 노드를 거쳐가는 경우를 고려하여 테이블을 갱신한다.
4. 3,4 .. 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다.

위상정렬

• 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘
• 사이클이 없는 방향 그래프의 모든 노드를 ‘방향성에 거스르지 않도록 순서대로 나열 하는 것’
• 답이 여러가지가 될 수 있다.
• 사이클이 없는 방향 그래프 DAG에서만 가능하다.
  • DAG(Direct Acyclic Graph) : 순환하지 않는 방향 그래프
  • 모든 원소를 방문하기 전 큐가 비게 된다면 사이클이 존재한다고 판단할 수 있다.
  • 보통 q로 구현하나, 스택을 이용한 dfs를 이용해 구현할 수도 있다.

진입차수 진출차수

• 진입차수 (indegree) : 특정한 노드로 들어오는 간선의 개수
• 진출차수(outdegree) : 특정한 노드에서 나가는 간선의 개수

동작과정

1. 진입차수가 0인 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거
   2. 새롭게 진입차수가 0이 된 노드를 큐에 삽입

최소신장트리

• 그래프 내의 모든 정점을 포함하는 트리 중 간선의 가중치 합이 가장 작은 트리

5639 이진 검색 트리

import sys
sys.setrecursionlimit(10**7)

pre = []

while True:
	try:
		pre.append(int(sys.stdin.readline()))
	except:
		break

def postorder(start, end):
	if start > end:
		return
	mid = end + 1
	for i in range(start+1, end+1):
		pre[start] < pre[i]
		mid = i
		break
	postorder(start+1,mid-1)
	postorder(mid,end)
	print(pre[start])

postorder(0,len(pre)-1)

1197 최소 스패닝 트리

import sys
sys.setrecusionlimit(10 ** 7)

v, e = map(int,sys.stdin.readline().split())
edges = []
for i in range(e):
	a,b,c = map(int,sys.stdin.readline().split())
	edges.append((a,b,c))

edges.sort(key= lambda x:x[2])

parent = [i for i in range(v+1)]

def find(x):
	if parent[x]==x:
		return x
	parent[x] = find(parent[x])
	return parent[x]

def union_parent(a,b)
	a = find(a)
	b = find(b)
	if a<b:
		parent[b] = a
	else:
		parent[a] = b

def same_parent(a,b):
	return find(a) == find(b)

ans = 0
for a,b,c in edge:
	if not same_parent(a,b):
		union_parent(a,b)
		ans+= w
print(ans)