Study/WIL(Weekly I Learned)

크래프톤 정글 - 2Week 24.01.19 - 24.01.24 부제 : 치타는 웃고있다.

에린_1 2024. 1. 26. 00:10

728x90

2Week 24.01.19 - 24.01.24

회고

2주차가 다 끝나고 3주차가 바로 쉬지않고 시작됐다.

뭐랄까 난이도가 점점 올라가면서 쉴 틈 없이 몰아치는 기분. 크래프톤 정글보다 폭풍이라는 이름이 더 잘 어울릴 것 같다는 생각도 문득 문득 떠오른다.

하지만 많이 힘들었던 2주차 동안 정말 중요하다고 생각이 들었던 것이 동료학습에 관한 부분이 었다. 폭풍에서는 동료고 뭐고 다 날라가겠지만 정글에서 동료와 함께 라면 살아남을 수 있으니까 이름을 잘 짓긴 한 것 같다.

문제풀이에 적응되기 전에 계속 새로운 키워드가 나오고 그것에 또 적응하려니 많이 힘든 주간이었다.

하루 종일 문제와 답을 번갈아가며 보다가 하루가 끝나기도 하고, 그렇게 하루가 끝나면 내가 과연 오늘 무엇을 한 걸까? 잘했을까? 라며 자책을 하기도 하지만 그래도 동료가 있고, 오늘의 내가 어제의 나보다 발전했다는 것을 알고 있기 때문에 마냥 힘들기만 하지는 않았다.

우리 크래프톤 치타단 다른 사람들이 아무리 날뛰어봐야 치타 앞의 경주견일뿐…

치타는 지금 웃고 있다. 가자 치타단

CSAPP 3.4 - 3.10.1

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 .배율은 1,2,4,8의 값을 의미한다. 베이스 레지스터와 인덱스 레지스터는 64비트 레지스터다.
  - 유효주소는 lmm + R[rb] + R[ri] * s로 계산한다.

3.4.2 데이터 이동 인스트럭션

가장 많이 사용되는 인스트럭션은 데이터를 한 위치에서 다른 위치로 복사하는 명령이다.
MOV클래스 이 인스트럭션들은 소스 위치에서 데이터를 목적지 위치로 어떤 변환도 하지 않고 복사한다.
- 명령어 소스오퍼랜드 목적오퍼랜드
소스 오퍼랜드는 상수, 레지스터 저장 값, 메모리 저장 값을 표시한다.
목적 오퍼랜드는 레지스터 또는 메모리 주소 위치를 저장 한다.
x86-64는 데이터 이동 인스트럭션에서 두 개의 오퍼랜드 모두가 메모리 위치에 올 수 없도록 제한하고 있다. 하나의 메모리 위치에서 다른 위치로 어떤 값을 복사하기 위해서는 두개의 인스트럭션이 필요하다.
1. 소스 값을 레지스터에 적재하는 인스트럭션
2. 레지스터 값을 목적지에 쓰기 위한 인스트럭션
인스트럭션들의 레지스터 크기는 인스트럭션의 마지막 문자가 나타내는 크기와 일치해야한다.
movabsq는 64비트 상수를 다루기 위한 것이다. movq는 32비트 2의 보수 숫자로 나타낼 수 있는 상수 오퍼랜드 만을 갖는다. 이 값은 그 후 부호 확장되어 목적지를 위해 64비트 값을 생성한다. movabsq는 임의의 64비트 상수값을 소스 오퍼랜드로 가질 수 있으며, 목적지로는 레지스터만을 가질 수 있다.
MOVZ 클래스의 인스트럭션은 목적지의 남은 바이트를 모두 0으로 채워준다.
MOVS클래스는 소스 오퍼랜드의 가장 중요한 비트를 반복해서 복사하는 부호 확장으로 채운다. 이 명령들의 이름에는 마지막 두 개의 문자가 크기를 나타내는 지시자를 갖는다. 첫 번째는 소스의 크기, 두 번째는 목적지의 크기
cltq 인스트럭션 : 오퍼랜드가 없다. 언제나 레지스터 %eax를 소스로 , %rax를 목적지로 사용해서 부호 확장 결과를 만든다. movslq %eax %rax와 정확히 동일한 효과지만 조금 더 압축적인 인코딩을 갖는다.

어셈블리 코드에서 두 가지 특징

C언어에서 ‘포인터’라고 부르는 것이 어셈블리어에서는 단순히 주소다. 포인터를 역참조 하는 것은 포인터를 레지스터에 복사하고, 이 레지스터를 메모리 참조에 사용하는 과정으로 이루어진다.
- 역참조(Dereferencing) : 프로그래밍에서 데이터가 저장된 주소로 가서, 그 주소가 해당하는 데이터 값에 접근하는 것을 말한다.
지역변수들은 메모리에 저장되기 보다는 종종 레지스터에 저장된다. 레지스터 접근은 메모리 보다 속도가 훨씬 더 빠르다.

3.4.4 스택 데이터의 저장과 추출

스택은 프로시저 호출을 처리하는데 중요한 역할을 한다.
Top 에서 제거하거나 추가한다.
x86-64에서 프로그램 스택은 메모리의 특정 영역에 위치한다. 스택의 top원소는 모든 스택원소 중에서 가장 낮은 주소를 갖는 형태로 스택은 아래 방향으로 성장한다. 스택 포인터 %rsp는 스택 맨 위 원소의 주소를 저장한다.
popq, pushq는 한개의 오퍼랜드를 사용한다. 추가할 소스 데이터와, 추출을 위한 데이터 목적지. 쿼드워드 값을 스택에 추가하려면 먼저 스택포인터를 8감소 시키고, 그 값을 스택 주소의 새로운 탑에 기록 하는 것으로 구현한다.
스택이 프로그램 코드와 다른 형태의 프로그램 데이터와 동일한 메모리에 접근 되기 때문에 프로그램들은 표준 메모리 주소지정방법을 사용해서 스택 내 임의의 데이터에 접근할 수 있다.

3.5 산술연산과 논리연산

각 인스트럭션 클래스는 네 개의 서로 다른 크기의 데이터 연산을 갖는다. 연산들은 4개의 그룹으로 나누어진다.
- 유효주소 적재
- 단항(Unary)
- 이항(Binary)
- 쉬프트(Shift)
- 이항연산은 두개의 오퍼랜드를 가지는 반면, 단항연산은 한개의 오퍼랜드를 가진다.

3.5.1 유효주소 적재(Load Effective Address)

유효주소 적재 인스트럭션 leaq는 실제로는 movq 인스트럭션의 변형이다.
메모리에서 레지스터로 읽어드리는 인스트럭션의 형태를 갖지만, 메모리를 전혀 참조하지 않는다. 이 인스트럭션의 첫번째 오퍼랜드는 일종의 메모리 참조처럼 보이지만, 가리키는 위치에서 읽기를 수행하는 대신에 유효주소를 목적지에 복사한다.
인스트럭션은 나중에 메모리 참조에 사용하게 되는 포인터를 생성하기 위해 사용된다. 또, 일반적인 산술연산을 간결하게 설명하기 위해서 사용된다.
컴파일러는 자주 실제 유효주소 계산과 무관한 경우 leaq를 적절히 사용하곤 한다.
목적 오퍼랜드는 반드시 레지스터만 올 수 있다.
leaq는 일반적으로 간단한 산술연산을 사용한다.

3.5.2 단항 및 이항연산

두 번째 그룹 : 연산은 하나의 오퍼랜드가 소스와 목적지로 동시에 사용되는 단항 연산이다.
이 오퍼랜드는 레지스터나 메모리 위치가 될 수 있다.
- ex) incq(%rsp) : 스택 탑의 8바이트 원소 값 증가
세 번째 그룹 : 이항연산자로 구성되며, 두 번째 오퍼랜드는 소스이면서 목적지로 사용된다.
C언어에서 x+=y 같은 문장과 유사하다. 소스가 먼저오고 목적지가 나중에 오는 점에 유의
비교환성(noncommutative) 연산으로 특이하게 보인다.
- 연산의 순서를 바꾸면 부호가 반대가 되는 성질
첫 번째 오퍼랜드는 상수나 레지스터, 메모리 위치가 올 수 있다.
두 번째 오퍼랜드는 레지스터나 메모리가 올 수 있다. MOV인스트럭션처럼 두 개의 오퍼랜드가 모두 메모리 위치가 될 수는 없다.
두 번째 오퍼랜드가 메모리 위치일 때 프로세서가 메모리에서 값을 읽고, 연산을 하고 그 결과를 다시 메모리에 써야 한다는 점에 유의

3.5.3 쉬프트 연산(shift)

마지막 그룹 : 쉬프트 연산. 쉬프트 하는 크기를 먼저 주고, 쉬프트할 값을 두 번째로 준다. 산술과 논리형 우측 쉬프트가 모두 가능하다. 여러가지 쉬프트 인스트럭션들은 쉬프트할 양을 즉시 값이나 단일 바이트 레지스터 %cl로 명시할 수 있다.(이 인스트럭션들은 이 특정 레지스터만을 오퍼랜드로 허용하는 점이 일반적이지 않다.
x86-64에서는 w비트 길이의 데이터 값에 적용하는 쉬프트 연산은 레지스터 %cl의 하위 m비트로 쉬프트양을 결정하며 2^m = w 관계가 성립한다.
좌측 쉬프트 인스트럭션에는 두가지 이름이 있다 : SAL, SHL 이들은 모두 동일한 효과를 내며, 우측에서 부터 0을 채운다. 우측 쉬프트 인스트럭션은 SHR이 논리 쉬프트(0으로 채운다)을 수행하는 반면 SAR이 산술쉬프트(부호 비트를 복사해서 채운다)를 수행한다는 점에서 차이가 있다.
쉬프트 연산의 목적 오퍼랜드는 레지스터나 메모리 위치가 될 수 있다.

3.5.4 토의

대부분 인스트럭션들은 비부호형과 2의보수 산술 연산에 사용될 수 있다.
오직 우측 쉬프트만이 부호형과 비부호형 데이트를 구분하는 인스트럭션을 요구한다. 이것이 부호형 정수 산술연산을 구현하는 방식으로 2의 보수 산술연산을 선호하는 주요 특징이다. 일반적으로 컴파일러는 각각의 레지스터를 여러가지 프로그램의 값을 저장하는데 사용하고, 레지스터들 간에 프로그램 값을 이동하는데 사용한다.

3.5.5 특수 산술 연산

두개의 64 비트 부호형 또는 비부호형 정수들 간의 곱셈은 결과값을 표시하기 위해 12비트를 필요로 한다. x86-64 인스트럭션 집합은 128비트 숫자와 관련된 연산에 대해서는 제한적인 지원을 제공한다.
IMUL 인스트럭션 클래스의 멤버. 이 형식은 두 개의 64비트 오퍼랜드로 부터 64비트 곱을 생성하는 2 오퍼랜드 곱셈 인스트럭션을 제공한다.
추가적으로 x86-64에서는 두개의 다른 ‘단일 오퍼랜드’ 곱셈 인스트럭션을 제공하며, 두 64비트 값의 완전한 128비트 곱을 계산한다. - 하나는 비부호형(mulq) 하나는 2의 보수(imulq) 곱셈. 이들 모두 한개의 인자는 레지스터 %rax에 보관해야 하고, 다른 한개는 인스트럭션 소스 오퍼랜드로 주어진다. 곱은 %rdx(상위 64비트)와 %rax(하위 64비트)에 저장된다.

3.6 제어

보통 C와 기계어 인스트럭션들은 모두 프로그램에 나타나는 순서대로 순차적으로 실행된다.
기계어 인스트럭션들의 실행순서는 JUMP인스트럭션으로 변경될 수 있다.
점프 인스트럭션은 때에 따라서는 어떤 시험의 결과에 따라 프로그램의 다른 일부분으로 제어를 넘겨준다.

3.6.1 조건코드

정수 레지스터들과 함께 CPU는 가장 최근 산술 또는 논리연산의 특성을 설명하는 단일비트조건 코드로 구성된 레지스터들을 운영한다. 이 레지스터들은 조건부 분기를 수행하기 위해 시험될 수 있다.
- CF(Carry Flag) : 가장 최근의 연산에서 가장 중요한 비트로부터 받아 올림이 발생한 것을 표시. 비부호형 연산에서 오버플로우를 검출 할 때 사용.
- ZF(Zero Flag) : 가장 최근 연산의 결과가 0인 것을 표시
- SF(Sign Flag) : 가장 최근 연산이 음수를 생성한 것을 표시
- OF(Overflow Flag) : 가장 최근의 연산이 양수/음수의 2의 보수 오버플로우를 발생 시킨것을 표시
leaq 인스트럭션은 주소 계산에 사용하기 위한 것이므로 조건 코드를 변경하지 않는다.
반면 그림에 나열된 모든 인스트럭션들은 조건 코드 값을 변경한다.
CMP인스트럭션들은 두 오퍼랜드의 차에 따라 조건코드를 설정한다.
이들은 목적지를 갱신하지 않고 조건코드를 설정한다는 점을 제외하고는 SUB인스트럭션과 같은 방법으로 동작한다.
이 인스트럭션들은 만일 두 오퍼랜드가 같으면 영플래그를 1로 설정한다. 다른 플래그들은 두 오퍼랜드의 순서관계를 결정하는데 사용될 수 있다.

3.6.2 조건코드 사용하기

조건코드를 이용하는 보편적인 세가지 방법
1. 조건코드의 조합에 따라 0 또는 1을 한 바이트에 기록
2. 조건에 따라 프로그램의 다른 부분으로 이동하는 방법
3. 조건에 따라 데이터를 전송하는 방법
SET인스트럭션 조건코드의 일부 조건에 따라 하나의 바이트를 0또는 1로 기억한다. 이들 인스트럭션은 서로 다른 접미어를 가지고, 이에 따라 다른 조건코드의 조합을 사용하여 서로 다른 동작을 한다. 여기서 접미어는 오퍼랜드 크기가 아니라 조건코드의 어떤 조합을 사용할 것인지 나타내는 점이다.
SET 인스트럭션은 목적지로 하위 단일 바이트 레지스터 가운데 한 개나 단일 바이트 메모리 주소를 사용하며, 이 바이트를 0이나 1로 기록한다.

3.6.3 점프 인스트럭션

점프 인스트럭션은 프로그램이 완전히 새로운 위치로 실행을 전환하도록 한다. 이들 점의 목적지는 일반적으로 어셈블리 코드에서는 레이블(label)로 표시한다.
목적코드 파일을 만들기 위해서 어셈블러는 모든 레이블이 붙은 인스트럭션들의 주소를 결정하고, 점프 인스트럭션의 일부분인 ‘점프 목적지(jump target)’ : 목적지 인스트럭션의 주소를 인코딩한다.
jmp 인스트럭션은 점프 목적지가 인스트럭션의 일부로 인코딩되는 경우에는 직접 점프를, 점프 대상을 레지스터나 메모리 위치로부터 읽어 들어야 하는 경우 간접 점프를 사용한다.
- 직접점프는 점프대상을 레이블로 프로그램 내에 작성한다.
- 간접점프는 메모리 오퍼랜드 중의 하나를 이용한 오퍼랜드 식별자를 합쳐서 작성한다.
- jmp *%rax : rax에 값을 점프 목적지로 활용
- jmp *(%rax) : %rax에 저장된 값을 읽기 주소로 사용해서 메모리에서 점프 목적지로 사용

3.6.4 점프 인스트럭션 인코딩

점프를 인코딩하는 여러가지 방법 중 일반적인 방법 PC상대적(PC relative) 방법
- 대상 인스트럭션과 점프 인스트럭션 주소와의 차이를 인코딩한다.
두 번째 방법은 ‘절대’주소를 제공하는 방법
- PC상대 주소지정을 수행할 때 프로그램 카운터의 값은 점프 인스트럭션 자신의 주소가 아니라 점프 다음에 나오는 인스트럭션의 주소가 된다.
PC - 상대 방식으로 점프 목적지를 인코딩하면, 인스트럭션들이 간결하게 인코딩(2바이트) 될 수 있고, 목적코드는 수정없이 메모리상 다른 위치로 이동 될 수 있다

3.6.5 조건부 분기를 조건 제어로 구현하기

C에서 조건부 수식과 문장을 기계어 코드로 변역하는 가장 일반적인 방법은 조건부 및 무조건 점프를 함께 사용하는 것이다.(일부 조건문은 제어의 이동보다 데이터 이동으로 구현 할 수 있다.)
GOTO문을 사용하는 것은 코드를 해독하고 디버깅하기 어렵게 할 수 있기 때문에 일반적으로 나쁜 프로그래밍 스타일이다.

3.6.6 조건부 이동으로 조건부 분기 구현하기

조건부 동작을 구현하는 전형적인 방법은 조건이 만족되면 프로그램의 한 가지 실행 경로를 따르고, 아닌 경우에는 다른 경로를 따라가도록 하는 제어의 조건부 전환을 통해 이루어진다. 이 방법은 간단하고 일반적이지만 최신 프로세서들에서는 매우 비효율적 일수있다.
또 다른 전략은 데이터 조건부 전송을 이용하는 것이다. 조건부 동작의 산출물 모두를 계산하고 조건에 따라 하나만 선택하는 방식이다. 제한적인 경우에만 의미를 갖고 MOV인스트럭션으로 구현된다.
조건부 제어 이동기반 코드보다 조건부 데이터 이동 코드가 성능이 우수하다. 프로세서들은 각 인스트럭션을 일련의 단계로 처리하며, 이 단계들은 각각 요구된 동작의 작은 부분만을 실행하는 파이프 라인을 통해 높은 성능을 얻는다. 이 방법은 이전 인스트럭션의 산술 연산을 수행하는 동안에 다른 인스트럭션을 인출하는 것처럼 연속되는 인스트럭션들의 단계를 중첩시켜 고성능을 얻는다. 이를 위해서는 파이프라인을 실행할 인스트럭션들로 미리 채우기 위한 실행할 인스트럭션들의 순서를 훨씬 일찍 결정할 수 있어야한다. 프로세서가 조건부 점프를 만나게 되면 프로세서는 분기 조건에 대한 계산이 완료될 때 까지는 어느쪽으로 분기할지 결정할 수 없다.
프로세서는 각 점프 인스트럭션이 실행될지 추측하기 위한 복잡한 분기 예측 회로를 채택하고있다. 점프 하나를 잘못 예측하면, 미래의 인스트럭션을 위해 이미 실행한 작업 결과들을 상당 부분 버려야 하고, 정확한 위치에서 다시 인스트럭션들을 파이프라인에 채우는 작업을 수행해야 한다. 이러한 예측 오류는 약 15-30 클럭 사이클의 손실을 발생시켜 프로그램 성능에 상당한 감소를 야기한다.
분기 예측 오류 손실이 함수의 성능을 결정한다.
x86-64 코드에서 쉽게 예측할 수 있는 경우 함수당 약 8클럭, 분기 패턴이 랜덤인 경우 17.50 클럭 사이클을 소모한다 분기 예측 오류 손실은 약 19 클럭 사이클 정도이다. 이것은 함수 실행시간이 분기 예측에 따라 8에서 27 사이클의 범위를 갖는다는것을 의미한다. 반면 조건부 이동 명령을 사용해 컴파일한 코드는 테스트 하는 데이터와 상관없이 약 8 클럭 사이클을 필요로 한다. 이것은 프로세서가 파이프라인을 꽉 찬 상태로 유지하는 것을 더욱 쉽게 해준다.
조건부 이동 인스트럭션. 두개의 오퍼랜드를 가진다 : 소스 레지스터 또는 메모리 위치, 목적지 레지스터
SET과 점프 인스트럭션처럼 이 인스트럭션들의 결과는 조건코드 값에 따라 달라진다. 소스값은 메모리나 소스 레지스터로 부터 읽히지만, 목적지에는 명시된 조건이 만족될 때만 복사된다.
소스와 목적지는 16,32,64 비트 길이를 가진다. 단일 바이트 조건부 이동은 지원되지 않는다. 오퍼랜드의 길이가 명시적으로 인스트럭션의 이름에 인코딩되는 무조건형 인스트럭션들과는 달리, 어셈블러는 목적지 레지스터의 이름으로 부터 조건부 이동 인스트럭션의 오퍼랜의 길이를 추정한다. 그래서 동일한 인스트럭션 이름이 모든 오퍼랜드 길이에 대해 사용될 수있다.
조건부 점프와는 달리 프로세서는 테스트 결과를 예측하지 않고서도 조건부 이동 인스트럭션을 실행할 수 있다. 프로세서는 간단히 소스값을 읽고(대개 메모리로 부터) 조건코드를 검사하고, 목적지 레지스터를 갱신하거나 그대로 유지한다.
조건부 이동에서는 계산 결과에 따라 선택되는 최종값에 의해 모두 계산된다.
조건부 이동을 사용한다고 해서 언제나 코드 효율성을 개선할 수 있는 것은 아니다.

3.6.7 반복문

기계어에는 반복문 인스트럭션이 없다. 조건부 테스트와 점프를 사용해 효과를 구현한다.
- do while
- while
- for문

3.6.8 Switch문

switch문은 정수 인덱스 값에 따라 다중 분기 기능을 제공한다. 이것은 테스트 해야하는 경우의 수가 많은 경우 특히 유용하다.
점프 테이블이라는 자료구조를 사용해서 효율적으로 구현한다.
- 점프테이블은 그 원소 i가 switch문의 인덱스가 i일 때 프로그램이 실행해야 하는 동작을 구현하는 코드 블록의 주소가 되는 배열을 말한다.
- 점프 인스트럭션의 목적지를 찾아내기 위해 switch문의 인덱스를 사용하여 점프테이블을 배열처럼 참조한다.
- 점프테이블을 사용하면 다 단계의 if-else구문을 사용하는 것 보다 switch를 생행하는데 걸리는 시간이 case수에 관계 없는 점이 장점이다.

3.7 프로시저

프로시저 호출은 소프트웨어에서의 주요 추상화, 지정된 인자들과 리턴 값으로 특정 기능을 구현하는 코드를 감싸주는 방법을 제공한다.
잘 설계 된 소프트웨어는 무슨 값이 계산되고, 이 프로시저가 프로그램 상태에 무슨 효과를 갖는지에 대한 명쾌하고 간결한 인터페이스 정의를 제공하는 한편, 일부 동작의 구체적인 구현은 감춰주는 방식으로 프로시저를 추상화 매커니즘으로 이용한다. 프로시저는 서로 다른 프로그래밍 언어에서 여러가지 다른 모습 - 함수, 메소드, 서브루틴, 핸들러- 등으로 사용된다. 그러나 이 모두는 일반적인 특징들을 공유한다.
프로시저에 대한 기계어 수준 지원을 제공할 때 처리되어야 하는 특성
- 제어권 전달 : 프로그램 카운터는 진입할 때 q에 대한 코드의 시작주소로 설정되고 리턴할 때는 p에서 q를 호출하는 인스트럭션 다음의 인스트럭션으로 설정되어야한다.
- 데이터 전달 : p는 하나 이상의 매개변수를 q에 제공할 수 있어야 하며 q는 다시 p로 하나의 값을 리턴 할 수 있어야한다.
- 메모리 할당과 반납 : q는 시작할 때 지역변수들을 위한 공간을 할당할 수도 있고, 리턴할 때 이 저장소를 반납할 수도 있다.

3.7.1 런타임 스택

대부분 언어에서 프로시저 호출 동작 방식의 주요 특징은 스택 자료 구조가 제공하는 후입선출 메모리 관리 방식을 활용할 수 있다는 점이다. 프로그램은 스택을 사용해서 프로시저들이 요고하는 저장장소를 관리할 수 있으며, 여기서 스택과 프로그램 레지스터들은 제어와 데이터를 전송하기 위해, 메모리를 할당하기 위해 필요한 정보를 저장한다.
x86-64 포로시저가 레지스터들에 저장할 수 있는 개수 이상의 저장공간을 필요로 할 때 공간을 스택에 할당한다. 이 영역은 프로시저의 스택프레임 이라고 부른다.
- 현재 실행중인 프로시저에 대한 프레임은 항상 스택의 맨 위에 위치한다.
프로시저 p가 프로시저q를 호출할 때 리턴주소를 스택에 푸시해서 q가 리턴할 때 p에서 프로그램이 실행을 재시작 해야하는 위치를 가리킨다. 리턴주소가 p에 관계된 상태를 저장하기 때문에 리턴주소는 p에 스택프레임에 속하는 것으로 간주한다. q에 대한 코드는 현재 스택 경계를 확장해서 자신의 스택프레임을 위한 공간을 할당한다. 이 공간 내에서 레지스터 값들을 저장하고, 지역변수들을 위한 공간을 할당하며, 자신이 호출하는 프로시저들을 위한 인자들을 설정할 수 있다. 대부분의 프로시저의 스택프레임들은 프로시저가 시작될 때 할당되는 고정 크기를 갖는다. 그러나 일부 프로시저는 가변 크기 프레임을 필요로 한다.
시간과 공간 효율성을 위해 x86-64프로시저는 요청받은 스택프레임의 부분만을 할당한다. 사실 많은 함수들은 심지어 스택 프레임을 요청하지도 않는다. 이런 경우는 모든 지역변수들을 레지스터에 보관할 수 있고, 이 함수가 다른 함수를 하나도 호출하지 않을 때 발생한다.

3.7.2 제어의 이동

제어를 함수 p에서 함수 q로 전달하는 것은 단순히 프로그램 카운터를 q를 위한 코드의 시작 주소로 설정하는 것과 관련된다.
x86-64에서 call인스트럭션 q로 프로시저q를 호출해서 기록한다. call인스트럭션은 호출된 프로시저가 시작하는 인스트럭션 주소를 목적지로 갖는다. 점프와 유사하게 명령은 직접 혹은 간접 형태를 갖는다. 어셈블리 코드에서의 직접 호출의 목적지는 레이블로 주어지는 반면, 간접호출의 목적지는 ‘*’ 와 그 뒤에 따라오는 식별자에 의해 주어진다.
리턴주소를 스택에 푸시하는 방법을 사용해서 함수가 나중에 프로그램의 적절한 위치로 리턴 가능하게 된다는 것을 알 수 있다.

3.7.3 데이터 전송

프로시저로 부터 데이터 전달은 레지스터를 통해 일어난다.
x86-64에서는 최대 여섯개의 정수형(정수와 포인터) 인자가 레지스터로 전달 될 수 있다. 이 레지스터들은 전달되는 데이터 형의 길이에 따라 레지스터 이름을 이용해서 정해진 순서로 이용된다.
인자들은 인자리스트에서 각자의 순서에 따라 이들 레지스터에 할당된다.
함수가 여섯개 이상의 정수형 인자를 가질 때, 다른 인자들은 스택으로 전달된다.
매개변수들은 스택에 전달할 때, 모든 데이터 길이는 8의 배수로 반올림 된다.
인자들이 배치되면, 프로그램은 프로시저로 제어를 전달하기 위해 call인스트럭션을 실행할 수 있다. 프로시저는 레지스터와 스택을 통해 자신의 인자들에 접근할 수 있다. 프로시저 6개가 넘는 인자를 호출하려면 자신의 스택프레임에 argument build area라고 이름 붙인 영역으로 이들을 위한 공간을 할당할 수 있다.

3.7.4 스택에서의 지역 저장 공간

지역 데이터가 메모리에 저장 되어야 하는 경우
- 모두를 저장하기에 레지스터 수가 부족한 경우
- 지역변수에 연산자 ‘&’가 사용되었으며, 이 변수의 주소를 생성할 수 있어야 한다.
- 일부 지역 변수들이 배열 또는 구조체여서 이들이 배열이나 구조체 참조로 접근 되어야 하는 경우

3.7.5 레지스터를 이용하는 지역저장소

프로그램 레지스터들은 모든 프로시저들이 공유하는 단일 자원의 역할을 한다.
레지스터 %rbx, %rbp, %r12- %r15는 피호출자 - 저장 레지스터로 구분한다.
프로시저p가 프로시저 q를 호출할 때, q는 q가 p로 리턴될 때, q가 호출되었을 때의 값들과 동일하도록 보장할 수 있게 이 레지스터의 값을 보존해야한다. 프로시저 q는 이 값이 전혀 변경하지 않거나 원래의 값을 스택에 푸시해두고 이 값을 변경하며, 리턴하기 전에 스택에서 이전 값을 pop해오는 방식으로 레지스터를 보존한다.
안전하게 값을 저장할 수 있으며 이 값이 위험없이 레지스터에서 사용할 수 있다. 스택포인터 %rsp를 제외한 다른 모든 레지스터들은 호출자 - 저장 레지스터로 구분된다. 이것은 이들이 함수에 의해 변경될 수 있다는 것을 의미한다.

3.7.6 재귀 프로시저

함수를 재귀적으로 호출하는 것도 다른 함수의 호출과 마찬가지로 진행된다.
스택 기법을 사용해서 함수의 각 호출시 상태정보(리턴 위치의 저장값, 피호출자 - 저장 레지스터를 위한 자신만의 저장공간을 제공한다)가 필요한 경우 지역변수를 위한 저장 공간도 제공할 수 있다.

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선언을 통해 변수명과 숫자를 연관지어 일괄적으로 변수명을 사용하는 것이 가장 좋다.

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

3.8.5 가변 크기 배열

int A[expr1][expr2]

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

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

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

3.9 이기종(Heterogeneous) 자료구조

C는 서로 다른 유형의 객체를 연결해서 자료형 만드는 두 가지 방법을 제공하다. Struct 키워드를 사용해서 선언하는 구조체는 다수의 객체를 하나의 단위로 연결한다. 키워드 union으로 선언하는 공용체는 하나의 객체를 여러개의 다른 자료형으로 참조 될 수 있도록 한다.

3.9.1 구조체

C Struct 선언은 서로 다른 유형의 객체들을 하나의 객체로 묶어주는 자료구조를 생성한다. 하나의 구조체 내의 서로 다른 컴포넌트들은 이름을 이용해서 참조된다. 구조체의 구현은 구조체의 모든 컴포넌트들이 메모리의 연속된 영역에 저장되며, 구조체의 포인터가 첫번째 바이트 주소라는 점에서 배열과 유사하다. 컴파일러는 각 필드의 바이트 오프셋을 가리키는 각 구조체 유형에 관한 정보를 관리한다. 컴파일러는 메모리 참조 인스트럭션에서의 변위로 이 오프셋을 사용하여 구조체 원소 참조를 생성한다.
기계어 코드는 필드 선언이나 이름에 관한 정보를 포함하지 않는다.

3.9.2 공용체

공용체 union는 C언어의 자료형 체제를 회피해서 하나의 객체가 다수의 자료형에 따라 참조될 수 있도록 해준다. 공용체를 선언하는 문법은 구조체와 동일하나 그 의미는 매우 다르다. 다른 필드들이 메모리의 다른 블록을 참조하는 것이 아니라 동일한 블록을 참조한다.
공용체의 전체 크기는 유용할 수 있지만, C언어의 자료형 체제에서 제공하는 안전망을 피해가기 때문에 오히려 치명적인 버그를 발생 시킬 수도 있다. 한가지 응용은 어떤 자료구조의 서로 다른 두 개의 필드를 상호배타적으로 사용한다는 점을 미리 알고 있는 경우다.
이 경우 구조체보다는 공용체로 이 두개의 필드를 선언하면 전체 할당된 공간을 줄일 수 있다
일반적인 방법으로 공용체에서 다른 여러가지 선택을 정의하는 열거형(Enumerated) 자료형을 사용하고, 태그 필드와 공용체를 포함하는 구조체를 만드는 것이다.

3.9.3 데이터의 정렬

많은 컴퓨터 시스템들은 기본 자료형들에 대해 사용 가능한 주소를 제한하고 있어서 어떤 객체의 주소는 어떤 값 k의 배수가 되도록 요구한다. 이러한 정렬 제한은 프로세서와 메모리 시스템간의 인터페이스를 구성하는 하드웨어 설계를 단순화 한다.
정렬은 자료형 내의 모든 객체들이 각각의 정렬 제한 사항을 만족하는 방법으로 조직되고 할당되도록 강요된다.
구조체가 관련된 코드에서 컴파일러는 구조체의 각 원소들이 각각의 정렬 요구사항을 만족하도록 필드 할 당시 빈 공간을 삽입한다. 그러면 구조체는 자신의 시작주소가 가져야하는 정렬요건이 정해진다.
컴파일러는 구조체의 마지막에 0을 채워 구조체 배열에서 각 원소가 각각의 정렬요건을 만족하도록 해준다.

3.10 기계수준 프로그램에서 제어와 데이터 결합

3.10.1 포인터 이해하기

포인터는 C프로그래밍 언어에서 핵심 특징이다. 이들은 다른 자료구조 내 원소들에 대한 참조를 생성하는 통일된 방법으로서의 역할을 수행한다.
- 포인터는 연관된 자료형을 갖는다. 이 자료형은 어떤 종류의 객체를 이 포인터가 가리키는가를 의미한다.
  - int *ip;
  - char **cpp;
- 변수 ip는 int형 객체로의 포인터지만, cpp는 자기 자신이 포인터인 객체를 가리키는 포인터이다. 일반적으로 객체가 자료형 T를 가지고 있다면, 포인터는 자료형 T를 갖는다. 특수한 void형은 범용(generic) 포인터를 표시한다. 예로 malloc 함수는 범용 포인터를 리턴하며, 이것은 할당연산의 명시적 또는 암묵적 형변환(casting)을 통해서 자료형을 갖는 포인터로 변환된다.
- 모든 포인터는 특정 값을 가진다. 이 값은 특정 자료형을 갖는 어떤 객체의 주소다. 특수 값인 NULL(0)은 포인터가 아무곳도 가리키지 않는 것을 의미한다.
- 포인터는 & 연산자를 사용해서 만든다. 이 연산자는 lvalue로 구분되는 C언어의 모든 수식에 적용될 수 있으며, lvalue는 할당문 좌측에 올 수 있는 식을 의미한다.
- 여기에는 변수, 구조체, 공용체, 배열의 원소들이 해당한다.
- 포인터 *연산자를 사용해서 역참조한다. 그 결과 포인터와 연관된 자료형을 갖는 값을 가져온다. 역참조는 정해진 주소에 저장하거나 주소로 부터 값을 가져오는 등의 메모리 참조를 사용하여 구현한다.
- 배열과 포인터는 밀접한 관련이 있다. 배열의 이름은 마치 포인터 변수처럼 참조 될 수 있다.(그러나 변경될 수는 없다) 배열의 참조(a[3])은 포인터 연산이나 역참조와 동일한 효과를 갖는다. 배열 참조와 포인터연산은 객체의 크기에 따라 오프셋을 조절해야 한다.
- 포인터 p에 대한 식을 p+i를 값 p를 사용해 작성할 때 최종주소는 p + L * i 로 계산된다.
- 한 종류의 포인터에서 다른 종류로의 자료형 변환은 그 종류만 바뀔 뿐 값은 변화가 없다. 형변환의 한가지 효과는 포인터 연산의 크기 변환을 변경하는 것이다. 만일 p가 값 p를 갖는 자료형 char* 의 포인터라면 (int*)p + n 은 p+28을 계산하며 (int*)(p+7)은 p+n을 계산한다.(형변환이 덧셈보다 우선순위를 갖는다.)
- 포인터는 함수를 가리킬 수도 있다. 이것은 프로그램의 다른 부분에서 호출할 수 있는 코드에 대한 참조를 저장하거나 넘겨 줄 수있는 강력한 기능을 제공한다.

자료구조

그래프(Graph)

그래프의 정의와 특징

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

그래프 용어

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

특징

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

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

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

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

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

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

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

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

트라이(Trie)

문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조
우리가 검색할 때 볼 수 있는 자동완성 기능, 사전검색등 문자열을 탐색하는데 특화 되어있는 자료구조

트라이 장단점

장점
- 트라이는 문자열 검색을 빠르게 한다.
- 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색을 하는 것보다 시간복잡도 측면에서 더 효율적이다.
단점
- 각 노드에서 자식들에 대한 포인터들을 배열 모두 저장하고 있다는 점에서 저장공간의 크기가 크다는 단점도 있다.
트라이 생성 시간 복잡도는 O(M*L) : 탐색 시간복잡도 O(L)
- 가장 긴 문자열 길이 L
- 총 문자열의 수 M

신장트리(Spanning Tree)

그래프 내의 모든 정점을 포함하는 트리
그래프의 최소 연결 부분 그래프다.
- 최소연결 : 간선의 수가 가장 적다
- n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 spanning tree가 된다.
- 그래프에서 일부 간선을 선택해서 만든 트리

특징

BFS, DFS 를 이용해서 그래프에서 신장트리를 찾을 수 있다.
- 탐색 도중에 사용된 간산만 모으면 만들 수 있다.
하나의 그래프에서 많은 신장 트리가 존재할 수 있다.
Spanning tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다.
Spanning Tree 는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결해야 한다.

최소 신장트리 MST(Minimum Spanning Tree)

Spanning Tree 중 사용된 간선들의 가중치 합이 최소인 트리
각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는건 아니다.
MST는 간선에 가중치를 고려해서 최소 비용의 Spanning tree를 선택하는 것을 말한다.
즉, 네트워크(가중치 그래프)에 있는 모든 정점들은 가장 적은 수의 간선과 비용으로 연결하는 것

특징

간선의 가중치 합이 최소여야 한다.
n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야한다.
사이클이 포함되어서는 안된다.

Algorithm

DFS(Depth-First Search)

깊이 우선 탐색 알고리즘
특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문 한 후 다시 돌아가 다른 경로로 탐색하는 알고리즘
DFS는 스택 자료구조를 이용한다(보통 재귀함수를 이용해 DFS를 구현한다)

BFS(Breadth-First Search)

너비 우선 탐색 알고리즘
가까운 노드부터 탐색하는 알고리즘
큐를 이용해서 구현하는 것이 정석이다.

위상정렬(Topological Sorting)

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

진입차수와 진출차수

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

위상정렬의 특징

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

B-Tree

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

삽입

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

삭제

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

인터널에서 삭제시

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

다익스트라

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

동작과정

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

‘최단거리 테이블’은 1차원 배열로 N개의 노드까지 오는데 필요한 최단거리를 기록한다. N개 크기의 배열을 선언하고 큰 값을 넘어 초기화 시킨다.

특징

가중치가 양수일 때만 사용가능하다.
- 그래야 한번 방문한 정점에 대해서는 값을 업데이트 하지 않아도 된다.
방문하지 않은 노드 중 거리 값이 가장 작은 노드를 선택해 다음 노드로 삼는다.
순차탐색 O(n^2)

플로이드 워셜

모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘
단계마다 ‘거쳐가는 노드’를 기준으로 알고리즘을 수행한다. 하지만 매 단계마다 방문하지 않은 노드 중에서 최단거리를 갖는 노드를 찾을 필요가 없다.
2차원 테이블에 최단 거리 정보를 저장한다.
노드 개수가 n이라고 할 때, n번만큼의 단계를 반복하며 ‘점화식에 맞게’ 2차원 리스트를 갱신하기 때문에 DP라고 볼 수 있다.
시간복잡도 O(N^3)

크루스칼(Kruskal)

탐욕적인 방법을 이용해서 네트워크의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것
동작
1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다.
  1. 즉, 가장 낮은 가중치를 먼저 선택한다.
  2. 사이클을 형성하는 간선을 제외한다.
3. 해당 간선을 현재의 MST의 집합에 추가한다.

특징

간선선택을 기반으로 하는 알고리즘
다음 간선을 이미 선택된 간선들의 집합에 추가할 때 사이클을 생성하는지 체크
- 새로운 간선이 이미 다른 경로에 의해 연결되어 있는 정점들을 연결할 때 사이클이 형성 된다.
- 즉, 추가 할 새로운 간선의 양 끝 정점이 같은 집합에 속해 있으면 사이클이 형성된다.
사이클 생성 여부를 확인하는 법
- Union-find 알고리즘 이용
시간복잡도
- 간선 e개를 퀵정렬과 같은 효율적인 알고리즘 정렬한다면 O(eloge)
- prim 알고리즘의 시간복잡도는 O(n^2)

Union-Find

서로 중복되지 않는 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조

Prim 알고리즘

시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장해 나가는것

동작

시작 단계에서는 시작 정점만이 MST에 포함
앞 단계에서 만들어진 MST집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다.
위의 과정을 트리가 (N-1)개의 간선을 가질 때 까지 반복한다.

정점선택 기반 알고리즘