24.01.15 CSAPP 3.1-3.3, 스택, 큐, 연결리스트,재귀, 정수론, 정렬, 검색

CSAPP

• 어셈블리 코드를 짤때 저급 인스트럭션을 명시해야 하는데, 대개의 경우 고급 언어가 제공하는 높은 수준의 추상화를 사용하는 것이 보다 더 생산적이고 안정적이다.

그렇다면 왜 WHY 기계어를 사용하고 공부할까?

• 컴파일러를 적절한 커맨드라인 인자와 함께 호출하면 컴파일러는 어셈블리 코드 형태의 파일로 출력을 생성한다.
• 이 코드를 이해하면 컴파일러의 최적화 성능을 알 수 있고, 코드에 내재된 비효율성을 분석할 수 있다.
• 프로그램이 얼마나 효율적으로 실행될지 이해하기 위해서 생성된 어셈블리 코드를 컴파일하고 분석해 보곤한다.
• 더욱이 고급언어에서 제공하는 추상화 계층 때문에 이해 가능한 프로그램의 런타임 동작이 감춰지는 경우도 종종 있다.
• 또 다른 예로 악성 프로그램이 시스템을 감염 시킬 수 있도록 프로그램을 공격하는 방법 중 상당수가 프로그램이 런타임 제어정보를 저장하는 방식의 미묘한 차이와 관련이 있다. 이런 취약성이 어디서 발생하는지, 이런 공격을 어떻게 막을 수 있는지 이해하려면 프로그램의 기계수준 표현에 대한 지식이 필요하다.

상세한 내용을 완벽히 이해하면 보다 심오하고 보다 근본적인 개념들을 이해할 수 있게 된다. ‘ 일반적인 원리는 이해해도 자세한 내용은 배우고 싶지 않다.’ 고 말하는 사람들은 자신을 속이는 것이다.

• 좀 많이 찔릴 수 있는 문장. 나태해질 때마다 자주 보자.

프로그램 인코딩

• 일반적으로 최적화 수준을 올리게 되면 최종 프로그램은 더 빨리 동작하게 되지만, 컴파일 시간이 증가하고 디버깅 도구를 실행하기가 어려워질 위험이 있다.
• 높은 수준 최적화를 적용하면 만들어진 코드가 너무 많이 변경되어서 본래의 코드와 생성된 기계어 코드 간 관계를 이해하기 어렵다.

GCC 컴파일러

• GCC명령은 소스코드를 실행코드로 변환하기 위해 일련의 프로그램 호출
• C전처리기 #include 명시된 파일을 코드에 삽입, #define 선언된 매크로 확장
• 컴파일러가 어셈블리로 변환
• 어셈블러가 어셈블리 코드를 바이너리 목적 코드로 변환
  • 바이너리 목적코드 - 기계어 코드의 한 유형
• 링커가 목적코드 파일을 라이브러리 함수를 구현한 코드와 합쳐 실행 파일 생성

기계수준코드

• 컴퓨터 시스템은 보다 간단한 추상화 모델을 이용해서 세부 구현 내용을 감추면서 추상화의 여러가지 다른 형태를 사용하고 있다. 이들 중 두가지가 기계 수준 프로그래밍에서 특히 중요하다.

1. 기계수준 프로그램의 형식과 동작은 인스트럭션 집합구조(instruction set architecture) 즉 ‘ISA’에 의해 정의된다. 이 ISA는 프로세서의 상태, 인스트럭션의 형식, 프로세서 상태에 대한 각 인스트럭션들의 영향을 정의한다. X86-64를 포함해 대부분의 ISA는 인스트럭션이 순차적인 실행을 하는것처럼 프로그램 동작을 설명한다. 프로세서 하드웨어는 훨씬 정교해서 여러 인스트럭션을 동시에 실행하지만 ISA에 의한 순차적 동작과 일치하는 전체동작을 보이도록 해주는 안전장치를 사용한다.
2. 기계수준 프로그램이 사용하는 주소는 가상주소이며, 메모리가 매우 큰 바이트 배열인 것처럼 보이게 하는 메모리 모델을 제공한다.

X86-64 기계어코드

• 프로그램 카운터(X86-64 %rlp) - 실행할 다음 인스트럭션 메모리 주소를 가리킨다
• 정수 레지스터 파일 - 64비트 값을 저장하기 위한 16개의 이름을 붙인 위치를 가진다. 레지스터주소나 정수 데이터를 저장할 수 있다. 일부 레지스터는 프로그램의 중요한 상태를 추적하는데 사용할 수 있으며, 다른 레지스터들은 함수의 리턴 값 뿐만 아니라 프로시저의 지역변수와 인자 같은 임시값을 저장하는데 사용한다.
• 조건코드 레지스터 - 가장 최근에 실행한 산술 또는 논리 인스트럭션에 관해 상태정보 저장. if나 while문 구현할 때 필요한 제어나 조건에 따른 데이터 흐름의 변경을 구현하기 위해 사용한다.
• 벡터 레지스터 - 하나 이상의 정수나 부동소수점 값 저장
• C가 다른 종류의 데이터 타입을 선언하고 메모리에 할당할 수 있는 모델을 제공하는 반면 기계어 코드는 메모리를 단순히 바이트 주소 지정이 가능한 큰 배열로 본다.
• C에서 배열이나 구조체처럼 연결된 데이터 타입은 기계어 코드에서 연속적인 바이트로 표시. 심지어 포인터와 정수형 사이에도 구분을 하지않는다.
• 프로그램 메모리 - 프로그램의 실행 기계어 코드, 운영체제를 위한 일부 정보, 프로시저 호출과 리턴을 관리하는 런타임스택, 사용자에 의해 할당된 메모리 블록(heap)
• 운영체제는 가상주소 공간을 관리해서 가상주소를 실제 프로세서 메모리상의 물리적 주소값으로 번역해준다.
• 하나의 기계어는 매우 기초적인 동작만을 수행한다.
  • 레지스터들에 저장된 수를 더하고, 데이터 교환, 조건 분기
• pushq %rbx - 레지스터 rbx가 프로그램 스택에 저장 push 되어야 한다.
  • 지역변수나 데이터 타입에 관한 모든 정보는 삭제됐다.
• .O파일 16진수 데이터
• 컴퓨터에 의해 실제 실행된 프로그램은 단순히 일련의 인스트럭션을 인코딩한 일련의 바이트. 컴퓨터는 인스트럭션들이 생성된 코드에 대한 정보를 거의 가지고 있지않다.
• 기계어 코드 파일을 조사하려면, 역 어셈블러라고 하는 프로그램이 중요하다.

기계어코드 몇 특징과 이들의 역어셈블된 표현

• X86-64 인스트럭션은 1~15byte 길이를 가진다. 인스트럭션 인코딩은 자주 사용되는 인스트럭션들과 오퍼랜드가 적은것들이 짧은 길이를 갖도록 하고, 그 반대는 좀 더 긴 인스트럭션 길이를 갖도록 한다.
  • 오퍼랜드 - 연산을 수행하는데 필요한 데이터, 데이터 주소
• 인스트럭션 형식은 주어진 시작 위치에서부터 바이트들을 기계어 인스트럭션으로 유일하게 디코딩할 수 있도록 설계한다. pushq %rbx 인스트럭션만이 바이트값 53으로 시작할 수 있다.
• 역어셈블러는 기계어 코드 파일이 바이트 순서에만 전적으로 의존해서 어셈블리코드를 결정한다.
• 역어셈블러는 GCC가 생성한 어셈블리 코드와는 다른 명명법을 인스트럭션에 사용한다.

자료구조

스택(Stack)

• 스택이란 데이터를 임시 저장할 때 쓰는 자료구조
• LIFO 후입선출 방식이다.
• 스택 배열 : stk list형 배열
• 스택 크기 : capacity 스택의 최대 크기를 나타내는 int 형 정수
• 스택 포인터 : ptr
• push - 스택에 데이터를 넣는 작업
• pop - 스택에서 데이터를 꺼내는 작업

큐(Queue)

• 스택과 같이 데이터를 임시 저장하는 자료구조
• FIFO 선입선출 방식이다.
• 인큐(enqueue) - 큐에 데이터를 넣는 작업
• 디큐(dequeue) - 큐에서 데이터를 꺼내는 작업
• 리어(rear),tail - 데이터를 넣는 쪽
• 프런트(front),head - 데이터를 꺼내는 쪽

우선순위 큐(Priority_Queue)

• 인큐할 때는 데이터에 우선순위를 부여하여 추가하고, 디큐할때 우선순위가 가장 높은 데이터를 꺼내는 방식
• python heapq 모듈에서 제공

링버퍼(Ring_Buffer)

• 디큐할때 배열 안의 원소를 옮기지 않는 큐. 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조
• 링버퍼로 큐를 구현하면 원소를 옮길 필요없이 front와 rear의 값을 업데이트 하는 것만으로 인큐 디큐를 수행한다.

덱(double-ended_queue)

• 맨 앞과 맨 끝 양쪽에서 데이터를 삽입,삭제할 수 있는 자료구조
• 2개의 포인터를 사용

연결리스트(LinkedList)

• 리스트(list)는 데이터에 순서를 매겨 늘어놓은 자료구조이다.
  • 선형리스트(linear_list)
  • 연결리스트(linked_list)
• 연결리스트에서 각각의 원소(element)를 노드(node)라고 한다. 노드는 데이터와 뒤쪽노드를 가리키는(참조하는) 포인터를(pointer)를 가지고 있다. 맨앞 노드를 head노드 맨뒤를 tail노드 라고한다. 또 각 노드에서 바로 앞 노드를 앞쪽노드(predecessor node) 바로 뒤를 뒤쪽노드(successor node) 라고한다.
• 자신과 같은 형의 인스턴스를 참조하는 필드가 있는 구조. 자기참조(self-referential)형

Node의 필드

• data - 데이터
• next - 뒤쪽 포인터

프리리스트(FreeList)

• 삭제된 레코드 그룹을 관리할 때 사용. 삭제 후 비어있는 배열의 문제를 해결 가능하다.

Node클래스에 추가된 필드

• dnext - 프리리스트의 뒤쪽 포인터(프리리스트 뒤쪽을 참조하는 커서)

ArrayLinkedList에 추가된 필드

• deleted - 프리리스트의 머리노드를 참조하는 커서
• max - 배열에서 맨 끝쪽에 저장되는 노드의 레코드 번호

원형 이중 연결리스트(Circular_doubly_LinkedList)

• 원형리스트와 이중연결리스트 합친 것
• 각 노드에 뒤쪽노드와 앞쪽노드에 대한 포인터가 주어진다.

Algorithm

재귀(Recursion) 알고리즘

• 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우 재귀(recursion)이라고 한다.
• 자연수의 정의
  • 1은 자연수이다.
  • 어떤 자연수에 1을 더해도 자연수이다.
• 무한히 존재하는 자연수를 재귀적 정의(recursion definition) 을 사용해서 정의
• 팩토리얼 n! 정의(n은 양의정수)
  • 0! = 1
  • n! = n * n-1 !
  • 자신과 똑같은 factorial() 함수를 호출 - 재귀 호출 recursive call
• 재귀 알고리즘의 2가지 분석 방법
  1. 하향식 분석 (top-down analysis)
  2. 상향식 분석 (bottom-up analysis)
• 하노이의 탑(Hanoi’s Tower)
  • 받아온 원반의 개수보다 하나 적은 원반들을 목적지가 아닌곳으로
  • 가장 큰 원반을 목적지로
  • 나머지 원반을 목적지로

정수론(Number_Theory)

• 정수의 성질을 다루는 수학의 한 분야이다.
  • 왜 why 공부하는가?
    • 컴퓨터에서 정수는 정확한 값을 가질 수 있다. 실수형 타입의 경우 반올림 오차(round off error)가 발생하기 때문에 이로 인한 문제가 발생할 수 있다.
• 정수와 소수를 중심적으로 다룬다.

소수(PrimeNumber)

• 정수론에서 가장 중심적으로 연구하는 것
• 1과 자기자신만을 약수로 가지는 수

에라토스테네스의 체

• 소수를 찾는 방법 - 배수를 지운다 √n까지
• 노가다 방식이라 상당히 무식한 방식이지만 특정범위가 주어지고 그 범위내의 모든 소수를 찾아야하는 경우 에라토스테네스의 체보다 빠른 방법이 없다.

골드바흐의 추측

• 4이상의 모든 짝수는 두 소수의 합으로 나타낼 수 있다.
• n/2 까지 소수를 역순으로 찾아 문제 해결

유클리드 호제법

• 두 양의 정수, 두 다항식에서 최대 공약수를 구하는 방법
• 두 양의 정수 a,b(a>b)에 대해 a=bq+r (0≤r<b) 라면 a,b의 최대공약수는 b,r의 최대 공약수와 같다. gcb(a,b) = gcb(b,r) , r= 0 이면 a,b 최대공약수는 b가 된다.

정렬(Sorting)

정렬은 조회를 위해서 < 코어타임에 만석님이 알려준 중요 내용.

• Key를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업
• 오름차순(ascending order) - 값이 작은 데이터를 앞쪽에 놓는다.
• 내림차순(decending order) - 값이 큰 데이터를 앞쪽에 놓는다.

정렬 알고리즘의 안정성

• 정렬알고리즘은 안정적인(stable) 안정적이지않은(unstable)로 나뉜다.
• 안정적인 정렬 알고리즘은 값이 같은 원소의 순서가 정렬한 후에도 유지된다. unstable은 순서가 유지된다는 보장을 할 수 없다.

내부정렬과 외부정렬

• 내부정렬(internal sorting) - 정렬한 모든 데이터를 하나의 배열에 저장할 수 있는 경우 사용하는 알고리즘
• 외부정렬(external sorting) - 정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는 경우 사용하는 알고리즘

정렬 알고리즘의 핵심은 교환, 선택, 삽입이다

버블정렬(BubbleSort)

• 이웃한 두 원소에 대소관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘.
• 단순 교환 정렬이라고도 한다
• 일련의 비교, 교환 과정을 패스(pass)라고 한다.
• 시간복잡도 O(n²), 공간복잡도 O(n)

단순 선택 정렬(Straight Selection Sort)

• 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업
  1. 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택합니다.
  2. a[min]과 아직 정렬하지않은 부분에서 맨앞에 있는 원소를 교환한다.

단순 삽입 정렬(Straight Insertion Sort)

• 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘
• 아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입합니다.
• 종료조건
  1. 정렬된 배열의 왼쪽 끝에 도달한 경우
  2. tmp보다 작거나 키값이 작은 원소 a[j-1]을 발견한 경우
• 계속조건
  1. j가 0보다 큰 경우
  2. a[j-1]의 값이 tmp보다 큰 경우
• 장단점
  • 장점 - 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서 속도가 아주 빠르다.
  • 단점 - 삽입할 위치가 멀면 이동횟수가 많아진다.
• 시간복잡도 O(n²), 공간복잡도 O(n)

셸정렬(ShellSort)

• 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘
• 먼저 정렬할 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬수행 그후 정렬된 그룹을 합치는 작업을 반복하여 원소의 이동횟수를 줄이는 방법

퀵정렬(QuickSort)

• 가장 빠른 알고리즘
• pivot을 기준으로 배열을 두 그룹으로 나눈다.
  • pivot을 선택하는 방법은 여러가지 크게 첫번째 요소, 중간요소, 마지막 요소, 랜덤으로 선택하는 방식
• 진행방식
  1. 피벗을 선택한다.
  2. 오른쪽에서 왼쪽으로 가면서 피벗보다 작은수를 찾는다.
  3. 왼쪽부터 오른쪽으로 가면서 피벗보다 큰 수를 찾는다.
  4. 각 인덱스 i,j에 대한 요소를 교환한다
  5. 2,3,4 과정을 반복한다
  6. 2,3 을 진행할 수 없다면 현재 피벗과 교환한다.
  7. 그 결과 피벗을 기준으로 왼쪽은 피벗보다 작은 수들이 존재하고, 오른쪽에는 큰수들이 존재한다.

병합정렬(MergeSort)

• 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업 반복
  1. 리스트 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
  2. 그렇지 않으면 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  3. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.
  4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다,.
• 분할(Divide) - 입력 배열을 같은 크기의 2개의 부분 배열로 분할
• 정복(Conquer) - 부분 배열을 정렬한다. 부분배열 크기가 충분히 작지 않으면 순환호출을 이용해 다시 분할 정복 방법을 적용한다.
• 결합(Combine) - 정렬된 부분 배열들을 하나의 배열에 병합
• 2개의 정렬된 리스트 병합(merge) 과정
  1. 2개의 리스트 값들을 처음부터 하나씩 비교하여 두개의 리스트의 값중에서 더 작은 값을 새로운 리스트로 옮긴다.
  2. 둘 중 하나가 끝날 때 까지 반복한다.
  3. 하나가 끝나면 남은 리스트를 새로운 리스트로 복사한다.
  4. 새로운 리스트를 원래 리스트로 옮긴다.

힙정렬(HeapSort) - 아직 잘 이해못함

• 완전 이진트리의 일종 우선순위 큐를 위하여 만들어진 자료구조
• 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조
• 최대 힙트리나 최소 힙트리를 구성해 정렬을 하는 방법
• 내림차순을 위해서는 최대힙 구현, 오름차순을 위해서는 최소 힙 구현.
  1. 정렬 해야 할 n개의 요소들로 힙을 만든다.
  2. 한번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장한다.
  3. 삭제 되는 요소들은 값이 감소되는 순서로 정렬되게 된다.

검색(Search)

검색과 키

• 키(Key) - 데이터의 일부

검색의 종류

• 배열검색
  1. 선형검색 - 무작위로 늘어놓은 데이터 집합에서 검색수행
  2. 이진검색 - 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색 수행
  3. 해시법 - 추가 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색 수행
     1. 체인법 - 같은 해시값 데이터를 연결리스트로 연결
     2. 오픈 주소법 - 데이터를 위한 해시값이 충돌할 때 재해시 하는 방법
• 연결리스트 검색
• 이진 검색 트리 검색

선형 검색(LinearSearch)

• 직선 모양(선형)으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을때까지 맨앞부터 스캔하여 순서대로 검색하는 알고리즘
• 선형 검색의 종료조건
  1. 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우 - 검색 실패
  2. 검색할 값과 같은 원소를 찾은 경우 - 검색 성공

보초법(Sentinel Method)

• 선형검색은 반복할 때 마다 2가지 종료조건을 체크한다. 단순하지만 비용(cost)를 무시할 수 없다. 이 비용을 반으로 줄이는 방법.
• 검색하고자 하는 키값을 끝에 추가한다. 이때 저장하는 값을 보초(Sentinel)이라고 한다. 그러면 선형 검색의 종료 조건 1을 체크 하지 않아도 돼서 코스트가 절감된다.

복잡도

• 시간복잡도(Time Complexity) : 실행하는데 필요한 시간을 평가
• 공간복잡도(Space Complexity) : 메모리(기억공간)와 파일공간이 얼마나 필요한지

해시법(hashing)

• ‘데이터를 저장할 위치 = 인덱스’ 간단한 연산으로 구하는 것
• 해시값(hash value) - 해시값은 데이터에 접근할 때 기준이 된다.
• 해시값을 인덱스로 하여 원소를 새로 저장한 배열이 해시테이블(hash table)이 된다. 이렇게 키를 해시값으로 변환하는 과정을 해시함수(hash function) 라고 한다.
• 일반적으로 해시함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용한다.
• 해시테이블에서 만들어진 원소를 버킷(buket)이라고 한다.
• 키와 해시값은 일반적으로 다대1(n:1)이다.

해시충돌

• 저장할 버킷이 중복되는 형상을 충돌(collision)이라고 한다.
• 충돌이 발생한 경우 2가지로 대처한다.
  1. 체인법 - 해시값이 같은 원소를 연결리스트로 관리
  2. 오픈주소법 - 빈 버킷을 찾을 때까지 해시를 반복

체인법(Chaining)

• 해시값이 같은 데이터를 체인(chain) 모양의 연결리스트로 연결하는 방법 오픈 해시법(open-hashing)이라고도 한다.
• 배열의 각 버킷에 저장하는 것은 인덱스를 해시값으로 하는 연결리스트의 앞쪽노드를 참조하는것
• 노드(Node)
  • Key - 키
  • Value - 값
  • Next - 뒤쪽 노드를 참조

오픈 주소법(Open addressing)

• 오픈 주소법은 충돌이 발생했을때 재해시(Rehashing)을 수행하여 빈 버킷을 찾는 방법을 말하며 닫힌 해시법(Closed hashing)이라고도 한다.
• 오픈 주소법은 빈 버킷이 나올 때까지 재해시를 반복하므로 선형탐사법(Linear Probiny)이라고 한다.