CS:APP
1.1 정보와 비트는 컨텍스트로 이루어진다.
프로그래머가 작성한 소스 파일로 부터 프로그램이 시작하며, hello.c라는 텍스트 파일로 저장된다.
소스 프로그램은 비트들의 연속이며, 8바이트 단위로 구성된다.
컴퓨터 시스템은 텍스트 문자를 아스키(ASCII) 표준을 통해 표현한다. 프로그램은 연속된 바이트들로 파일에 저장되고 각 바이트는 특정 문자에 대응하는 정수값을 갖는다.
hello.c처럼 아스키 문자로만 이루어진 파일을 텍스트 파일이라고 하며, 나머지 다른 파일들을 바이너리 파일이라고 한다.
프로그램을 통해 우리에게 전달될 때 시스템 내부의 정보 / 디스크 파일 / 메모리상 프로그램 / 데이터 네트워크를 통해 전달되는 데이터들은 모두 비트로 표현된다.
서로다른 객체를 구분하는 유일한 방식은 컨텍스트다. 다른 컨텍스트에 존재하는 바이트에 명령을 할 수 없다.
1.2 프로그램은 다른 프로그램에 의해 다른 형태로 번역된다.
텍스트 파일을 시스템에서 실행시키기 위해서는 다른 언어, 기계가 이해할 수 있는 언어로 번역이 필요하다.
C 소스코드의 경우 각 문장들이 다른 프로그램에 의해 저급 기계어 인스트럭션으로 번역되고, 이 인스트럭션들ㅇ이 합쳐져 실행가능 목적 프로그램( a.k.a 실행가능 목적 파일 )의 형태로 바이너리 디스크에 저장된다.
소스 코드를 실행하기 위해 4가지 단계( 전처리기, 컴파일러, 어셈블러, 링커 )를 거치는데 이를 모두 합쳐 컴파일 시스템이라고 부른다.
- 전처리 단계 : C 프로그램의 # 문자로 시작하는 디렉티브에 따라 코드를 수정한다.
# include<stdio.h>에 대해서 직접 해당 프로그램 문장을 삽입한다. 전처리 단계가 끝난 후.i확장자의 새로운 프로그램이 생성된다. - 컴파일 단계 :
.i파일을.s로 번역하며, 이 때 파일 내에는어셈블리어 프로그램이 저장된다. 어셈블리어는 상위수준 언어의 컴파일러를 위한 공통의 출력 언어를 제공하기 때문에 유용하다. - 어셈블리 단계 : 어셈블러가 .s 파일을 기계어 인스트럭션으로 번역하고, 재배치 가능 목적 프로그램으로 묶어 .o 확장자의 목적 파일로 저장한다.
- 링크 단계 : 프로그램 내부에서 이미 C언어의 표준 라이브러리를 사용하고 있다면, 표준 라이브러리의 목적 파일과 결합하는 형태가 이루어져야 한다. 링커 프로그램을 통해 해당 작업이 이루어지며 그 결과로 프로그램을 실행할 수 있는 목적 파일로 메모리에 적재되고 실행된다.
1.3 컴파일 시스템이 어떻게 동작하는지 이해하는 것은 중요하다.
- 프로그램 성능 최적화 하기 : 최신 컴파일러들은 우수한 성능을 보여주고 있어, 프로그래머가 효율적인 코드를 작성하기 위해 컴파일러 내부동작을 알 필요가 없긴 하다. 하지만 C언어 뿐만아니라 프로그램 작성시 올바른 판단을 하기 위해서 기계어 수준 코드에 대한 이해 기반이 있으면 도움이 된다.
- 링크 에러 이해하기 : 링커가 동작하면서 발생하는 에러를 이해가기 위해서 컴파일 시스템에 대해서 알고 있는 것이 중요하다.
- 보안 약점 피하기 : 버퍼 오버플로우느 인터넷, 네트워크 상 보안 문제의 원인으로 설명되고 있다. 이런 취약점은 신뢰할 수 없는 곳에서 얻은 데이터의 양과 형태를 제한하는 필요성을 못느끼기 때문이다. 프로그래밍 스택과 데이터가 저장되는 방식에 의한 영향을 이해하는 것이 중요하다.
1.4 프로세서는 메모리에 저장된 인스트럭션을 읽고 이해한다.
1.4.1 시스템의 하드웨어 조직
- 버스 (Buss) 컴포넌트간 바이트 정보를 시스템을 관통하여 전송하는 역할을 한다. 버스는 일반적으로 워드라고 하는 고정 크기의 바이트 단위로 데이터를 전송한다.
- 입출력 장치 시스템과 외부와 연결하는 역할을 한다. 각 장치들은 입출력 버스, 컨트롤러, 어댑터 등을 통해서 연결된다.
- 메인 메모리 프로세서가 프로그램을 실행하는 동안 데이터와 프로그램을 모두 저장하는 임시 장치를 말한다. 물리적으로 메인 메모리는 DRAM칩으로 구성되어 있으며, 논리적으로는 연속적인 바이트들 배열로 0부터 시작해 고유 주소를 가지고 있다.
- 프로세서 주처리장치(CPU)는 메인 메모리의 인스트럭션을 처리, 실행하는 엔진이다. 프로세서의 중심에는 프로세스 카운터(PC)가 존재한다. PC는 메인 메모리의 기계어 인스트럭션을 가리킨다.(다음 명령어) CPU는 PC가 가리키는 인스트럭션을 따라 실행하고, 프로세서는 PC가 가리키는 메모리로 부터 인스트럭션을 읽어온다. 이 인스트럭션에서 비트 해석을 통해 인스트럭션이 지정하는 동작을 수행하고, PC의 위치를 수정한다. 인스트럭션에의해 CPU가 실행하는작업
- 적재 (Load) : 메인 메모리에서 레지스터에 한 바이트 또는 워드를 이전 값에 덮어쓰는 방식으로 복사
- 저장(Store) : 레지스터에서 메인 메모리로 한 바이트 또는 워드를 이전 값을 덮어쓰는 방식으로 복사
- 작업(Operate) : 두 레지스터 값을 ALU로 복사하고 두 개의 워드로 수식연산을 수행한 후, 결과를 덮어쓰기 방식으로 복사
- 점프(Jump) : 인스트럭션 자신으로부터 한개의 워드를 추출하고 PC에 덮어쓰는 식으로 복사한다.
1.4.2 프로그램의 실행
- 쉘 프로그램이 자신의 인스트럭션을 실행하며 사용자 명령 입력을 기다린다.
- 쉘 프로그램은 입력받은 각각의 문자를 레지스터에 들인 후 메모리에 저장한다.
- 입력 명령이 끝나면 쉘은 파일 내 코드를 복사하는 인스트럭션을 실행하고 실행 파일을 디스크에서 메인 메모리로 로딩한다.
- 직접 메모리 접근(DMA)를 통해 데이터는 프로세서를 거치지 않고 메인 메모리로 직접 이동한다.
- 목적 파일의 코드와 데이터가 메모리에 적재하고 프로세서는 프로그램 main 루틴의 기계어 인스트럭션을 실행한다.
- 인스트럭션들은 메모리로부터 레지스터 파일을 복사하고. 입출력 장치에 전송하여 화면에 표기한다.
검색 알고리즘
검색의 종류
자료구조 알고리즘에 따라 3가지 검색 방식이 존재한다.
- 선형 검색 ( 배열 검색 ) - 무작위로 늘어놓은 데이터 내에서 검색을 수행한다.
- 이진 검색 - 일정한규칙으로 늘어놓은 데이터에서 아주 빠른 검색을 수행한다.
- 해시법 - 추가 삭제가 자주 일어나는 데이터에서 아주 빠른 검색을 수행한다.
- 체인법: 같은 해시값 데이터를 링크드 리스트로 연결하는 방법
- 오픈 주소법: 해시값이 충돌할 때 재해시 하는 방법
선형 검색
반복문을 통해서 정렬되지 않은 배열을 검색하는 유일한 방법
검색이 끝나는 조건
- 검색 대상을 찾지 못하고 배열을 벗어나는 경우
- 겸색 대상을 찾은 경우
보초법
검색 대상을 찾지 못한 경우 검색을 종료하는 조건에 대해서 비용을 절약할 수 있는 방법.
임의로 검색하는 값을 검색 대상 배열의 맨 마지막에 삽입해서 어떠한 경우에서도 검색이 되도록 해서 종료조건을 하나로 만들 수 있다.
import copy
def seq_search(seq: Sequence, key: Any) -> int:
a = copy.deepcopy(seq)
a.append(key)
i = 0
while True:
if a[i] == key:
break
i += 1
return -1 if i == len(a) else i이진 검색
오름차순, 내림차순에 정렬된 배열에서 효율적인 검색을 수행할 수 있는 방법
검색이 끝나는 조건
- a[pc]와 key가 일치하는 경우
- 검색 범위가 더이상 존재하지 않는 경우
def bin_search(a: Sequence, key: Any) -> int:
pl = 0
pr = len(a) - 1
while True
pc= (pl + pr) // 2
if a[pc] == key:
return pc
elif a[pc] < key:
pl = pc - 1
else:
pr = pc - 1
if pl > pr:
break
return -1해시법
검색, 데이터 추가, 삭제를 효율적으로 할 수 있다.
해시법은 ‘데이터를 저장할 위치 = 인덱스’를 간단한 연산으로 구하는 것을 말한다. 이 때 이 값을 해시 값이라고 하며 데이터 접근의 기준이 된다. 그리고 해시 값을 인덱스로 하여 원소를 새롭게 저장한 배열이 해시 테이블(Hash Table)이라고 하며, 키를 해시값으로 변환하는 과정을 해시 함수(Hash Function)이라고 한다. 해시테이블에서 마들어진 원소를 버킷이라고 한다.
해시 충돌
버킷이 중복되는 현상을 해시 충돌이라고 한다. 키와 해시 값은 n:1을 가져 잘못된 방식은 아니지만 최대한 고르게 값이 분포될 수 있도록 하는 것이 중요하다.
해시 충돌을 해결할 수 있는 방법은 ‘체인법’과 ‘오픈 주소법’이 있다.
체인법
해시값이 같은 데이터를 링크드리트로 연결하는 방법이다. 이때 버킷에 저장되는 값은 각 링크드 리스트의 맨 앞쪽 노드의 참조값을 가지게 된다.
class ChainedHash:
def __init__ (self, capacity: int) -> None:
self.capacity = capacity
self.table = [None] * self.capacity
def hash_value(self, key: Any) -> int:
if isinstance(key, int):
return key % self.capacity
return(int(hashlib.sha256(str(key).encode()).hexdigit(), 16) % self.capacity)
def search(self, key: Any) -> Any:
hash = self.hash_value(key)
p = self.table[hash]
while p is not None:
if p.key == key:
return p.value
p = p.next
return None
def add(self, key: Any, value: Any) -> Any:
hash = self.hase_value(key)
p = self.table[hash]
while p is not None:
if p.key == key:
return False
p = p.next
temp = Node(key, value, self.table[hash])
self.table[hash] = temp
return True
def remove(self, key: Any) -> bool:
hash = self.hash_value(key)
p = self.table[hash]
pp = None
while p is not None:
if p.key == key:
if pp is not None:
self.table[hash] = p.next
else:
pp.next = p.next
return True
pp = p
p = p.next
return False오픈 주소법
충돌이 발생했을 때 재해시를 수행해서 빈 버킷을 찾는 방법을 말하며, 닫힌 해시법이라고도 한다.
Python sorted() vs .sort()
sorted()는 배열을 인자로 받아 정렬한 후 새로운 배열을 return해준다.
.sort()의 경우 list 타입의 내장 함수로 기존 리스트를 정렬하여 사용한다.
매개변수 탐색
이진 탐색(Binary Search)와 유사한 알고리즘 : 시간 복잡도 ( O(logN)
매개 변수 탐색을 사용하는 시기
- 결정문제로 풀면 쉽게 문제를 풀 수 있을 때
- 어떤 시점까지 조건을 만족하지만, 그 후 조건을 만족하지 못하는 경우에 대한 최대값/최소값 찾기
매개변수 param과 결정함수 fn(param)
- 매개변수 param 매개변수 param은 ‘조건에 만족하는 최대/최소값’을 찾는 문제이다. 이때 param은 조사 범위의 중간값 ( pl + pr ) // 2 가 된다.
- 결정함수 fn(param) 조건을 만족하면 true, 만족하지 못하면 false를 반환하는 함수이다. 반환 값에 따라 검사 범위를 변경하게 된다.
이진 탐색(Binary Search)와의 차이점
- 이진 탐색은 조건을 만족하는 값을 찾으면 함수를 종료한다.
- 매개변수 탐색은 살펴볼 범위가 없을 때까지 (최대 / 최소가 결정되었을 때)까지 반복한다.
