To-do List

---

🔃 백준 문제 최소 1개 풀기
🔃 지금까지 썼던 TIL 옵시디언, 블로그에 정리할 거 정리

☑️ 정답 봤던거 직접 코딩해보기 | 사냥꾼, 하노이탑, nQueen
☑️ Do it! ~ 처음부터 읽기 | p.97 ~
☑️ Do it! ~ 읽고 구현 연습 #자료구조 | 큐, 스택
☑️ Do it! ~ 읽고 구현 연습 #정렬 | 퀵 정렬(피봇 3선발), 병합 정렬, 힙 정렬
☑️ Do it! ~ 읽고 구현 연습 #알고리즘 | 백트래킹, 하노이탑
☑️ 슈도 코드 변환 | 버블 정렬, 이분 탐색, 백트래킹

✅ CSAPP 읽기 | 3.1 ~ 3.4
✅ Do it! ~ 읽고 구현 연습 | 8queen
✅ 지금까지 썼던 TIL 옵시디언, 블로그에 정리할 거 정리 | 0706 ~ 0708
✅ 백준 풀기 | 1026 곱셈 (+ 추가문제 기초 문제들)

배운 것들

---

해시법

해시법 : '데이터를 저장할 위치' (= 인덱스) 를 간단한 연산으로 구하는 것을 말한다.

키	5	6	14	20	29	34	37	51	69	75
해시값 (키 % 13)	5	6	1	7	3	8	11	12	4	10

여기서 각각의 키를 13으로 나눈 값이 인덱스가 된다.

키를 해시값으로 변환하는 과정을 해시 함수라 하고,
해시 테이블에서 만들어진 인덱스를 버킷이라고 한다.

해시 테이블을 크게 만들면 충돌 발생 없지만 메모리 낭비 + 느리다.
해시 테이블 작게 만들면 충돌 발생하지만 검색, 추가, 삭제할 때 빠르다.

해시 충돌

위에 있는 해시 테이블에 18 넣으면 18 % 13 == 5 이므로 인덱스가 5가 되어야 한다.
하지만 인덱스 5는 자리가 이미 차 있다.

이렇게 인덱스가 중복되는 것을 해시 충돌이라 한다.

해시충돌 대처법

• 체인법 : 해시값이 같은 원소를 연결 리스트로 관리한다.
• 오픈 주소법 : 빈 버킷을 찾을 때까지 해시를 반복한다.

체인법

체인법에서는 중복값 나오면 노드로 연결해서 따로 뺀다.

key가 int형이 아닐 때

• sha256 알고리즘 : hashlib 모듈에서 제공하는 sha256은 RSA의 FIPS 알고리즘을 바탕으로 하며, 주어진 바이트(byte) 문자열의 해시값을 구하는 해시 알고리즘의 생성자(constructor)입니다. hashlib 모듈은 sha256 외에도 MD5 알고리즘인 md5 등 다양한 해시 알고리즘을 제공합니다.

• encode() 함수 : hashlib.sha256에는 바이트 문자열의 인수를 전달해야 합니다. 그래서 key를 str형 문자열로 변환한 뒤 그 문자열을 encode() 함수에 전달하여 바이트 문자열을 생성합니다.

• hexdigest() 함수 : sha256 알고리즘에서 해시값을 16진수 문자열로 꺼냅니다.

• int() 함수 : hexdigest() 함수로 꺼낸 문자열을 16진수 문자열로 하는 int형으로 변환합니다.

CSAPP

---

3장 프로그램의 기계수준 표현

• 컴퓨터는 데이터를 처리하고, 메모리를 관리하고, 저장장치에 데이터를 읽거나 쓰고, 네트워크를 통해 통신하는 등의 하위 동작들을 인코딩한 연속된 바이트인 기계어 코드를 실행한다.
• 컴파일러는 프로그램 언어의 규칙, 대상 컴퓨터의 인스트럭션 집합, 운영체제의 관례 등에 따라 기계어 코드를 생성한다.
• GCC C 컴파일러는 기계어 코드를 문자로 표시한 어셈블리 코드의 형태로 출력을 만들어 프로그램의 각 인스트럭션을 만들어 낸다.
• 그러고 나서, GCC는 어셈블러와 링커를 호출하여 어셈블리 코드로부터 실행 가능한 기계어 코드를 생성한다.

자바, C 같은 고급 언어로 프로그래밍하면 컴파일러가 어셈블리 코드 알아서 잘 짜주는데 왜 기계어 코드를 배워야 하는가? : 컴파일러 최적화 성능 알 수 있음. 코드에 내재된 비효율성을 분석할 수도 있다. 프로그램의 이해를 위해 런타임 동작을 알아야 하는데도 추상화 때문에 감춰지기도 함.

같은 느낌으로, chatgpt가 아무리 기똥차게 코드를 짠다고 하더라도 
두뇌에 직접적으로 설명을 꽂아서 이해시켜주지 않는 이상 
내가 원하는대로 코드를 짜줬는지 아닌지, 비효율적으로 짠 건지 아닌지,
애초에 내가 원하는 걸 정확히 어떤 방법과 선택지들을 이용해 만들어내야할지 알아야 하니
프로그래밍, 특히 컴퓨터 공학에 대한 전문성은 미래에도 (아예) 의미없어지진 않을듯?
미래의 AI는 모든 분야에서 최고 수준의 추상화를 제공하게 되는 것

3.2 프로그램의 인코딩

최적화 수준 올리면 프로그램을 더 빨리 동작하지만, 컴파일 시간이 증가하고 디버깅 도구 실행이 어려워짐

gcc 명령은 소스 코드를 실행 코드로 변환하기 위해 일련의 프로그램들을 호출한다.

• 먼저, C전처리기가 #include로 명시된 파일을 코드에 삽입해 주고, #define으로 선언된 매크로를 확장해 준다.

• 두 번째로, 컴파일러는 두 개의 소스파일의 어셈블리 버전인 p1.s와 p2.s를 생성한다.

• 다음으로 어셈블러는 어셈블리 코드를 바이너리 목적코드인 p1.o와 p2.o로 변환한다.
  - 목적코드 : 모든 인스트럭션의 바이너리 표현을 포함하고 있지만 전역 값들의 주소는 아직 안 채워짐
  

• 마지막으로 링커는 두 개의 목적파일을 라이브러리 함수들을 구현한 코드와 함께 합쳐서 최종 실행파일인 p를 생성한다.

3.2.1 기계수준 코드

1. 기계수준 프로그램의 형식과 동작은 인스트럭션 집합구조(instruction set architecture), 즉 "ISA"에 의해 정의된다. ISA는 프로세서의 상태, 인스트럭션의 형식, 프로세서 상태에 대한 각 인스트럭션의 영향들을 정의한다.

2. 기계수준 프로그램이 사용하는 주소는 가상주소이며, 메모리가 매우 큰 바이트 배열인 것처럼 보이게 하는 메모리 모델을 제공한다.

x86-64를 위한 기계어 코드는 본래의 C코드와는 상당히 다르다. 프로세서의 상태는 C 프로그래머에게는 일반적으로 감추어져 있다.

• 프로그램 카운터 : 실행할 다음 인스트럭션의 메모리 주소를 가리킴. 일반적으로 PC라고 하며, x86-64에서는 %rip라고 함.

• 정수 레지스터 파일 : 64비트 값을 저장하기 위한 16개의 이름을 붙인 위치를 가짐. 주소(C언어의 포인터에 해당)나 정수 데이터를 저장할 수 있다. 프로그램의 중요한 상태를 추적하거나, 함수의 리턴 값뿐만 아니라 프로시저의 지역변수와 인자 같은 임시 값을 저장하는 데 사용하기도 한다.

• 조건코드 레지스터 : 가장 최근에 실행한 산술 또는 논리 인스트럭션에 관한 상태 정보를 저장. if나 while문을 구현할 때 필요한 제어나 조건에 따른 데이터 흐름의 변경을 구현할 때 사용됨

• 벡터 레지스터들의 집합 : 하나 이상의 정수나 부동소수점 값들을 각각 저장할 수 있음

C가 다른 종류의 데이터 타입을 선언하고 메모리에 할당할 수 있는 모델을 제공하는 반면,
기계어 코드는 메모리를 바이트 주소지정이 가능한 큰 배열로 본다.

C에서 배열과 구조체 같은 연결된 데이터 타입들은 기계어 코드에서는 연속적인 바이트들로 표시된다. 스칼라(scalar) 데이터 타입의 경우에도 어셈블리 코드는 부호형과 비부호형, 다른 타입의 포인터들, 심지어 포인터와 정수형 사이에도 구분을 하지 않는다.

프로그램 메모리가 포함하는 것들

• 프로그램의 실행 기계어 코드
• 운영체제를 위한 일부 정보
• 프로시저 호출과 리턴을 관리하는 런타임 스택
• 사용자에 의해 할당된 (ex. malloc 라이브러리 함수) 메모리 블록

운영체제는 가상 주소공간을 관리해서 가상주소를 실제 프로세서 메모리 상의 물리적 주소 값으로 번역해 준다.

하나의 기계어 인스트럭션은 매우 기초적인 동작만을 수행한다.

• 레지스터들에 저장된 두 개의 수를 더하거나,
• 메모리와 레지스터 간에 데이터를 교환하거나,
• 새로운 인스트럭션 주소로 조건에 따라 분기하는 등

컴파일러는 일련의 인스트럭션을 생성해서 산술연산식의 계산, 반복문 프로시저 호출과 리턴 등의 프로그램 구문을 구현해야 한다.

3.2.2 코드 예제

목적코드로부터 배울 수 있는 중요한 교훈은 컴퓨터에 의해 실제 실행된 프로그램은 단순히 일련의 인스트럭션을 인코딩한 일련의 바이트라는 점이다. 컴퓨터는 인스트럭션들이 생성된 소스 코드에 대한 정보를 거의 갖고 있지 않다.

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

• x86-64 인스트럭션들은 1에서 15바이트 길이를 갖는다.
• 인스트럭션의 형식은 주어진 시작 위치에서부터 바이트들을 기계어 인스트럭션으로 유일하게 디코딩할 수 있도록 설계한다. 1대1 대응이 된다는 뜻. 예제 보니까 할당되는 주소 자체는 컴파일 할 때마다 다르게 나오는듯?
• 역어셈블러는 기계어 코드 파일의 바이트 순서에만 전적으로 의존해서 어셈블리 코드를 결정한다. 소스 코드나 프로그램의 어셈블리 코드 버전을 사용하지 않는다.

3.4 정보 접근하기

x86-64 주처리장치(CPU)는 64비트 값을 저장할 수 있는 16개의 범용 레지스터를 보유하고 있다. 이들 레지스터는 정수 데이터와 포인터를 저장하는 데 사용한다.

일련의 표준 프로그래밍 관습에 의해 스택을 관리하고, 함수의 인자를 넘겨주고, 함수에서 값을 리턴하고, 로컬 데이터와 임시 데이터를 저장하기 위해 어떻게 레지스터가 사용되는지가 정해진다.

3.4.1 오퍼랜드 식별자(specifier)

대부분의 인스트럭션은 하나 이상의 오퍼랜드를 가진다.
오퍼랜드는 연산을 수행할 소스 값과 그 결과를 저장할 목적지의 위치를 명시한다.
소스 값은 상수로 주어지거나 레지스터나 메모리로부터 읽을 수 있다.
결과 값은 레지스터나 메모리에 저장된다.

오퍼랜드의 종류

• immediate : 상수 값.
• register : 레지스터의 내용.
• 메모리 참조 : 유효주소(effective address)라고 부르는 계산된 주소에 의해 메모리 위치에 접근

3.4.2 데이터 이동 인스트럭션

• 소스 오퍼랜드 : 상수, 레지스터 저장 값, 메모리 저장 값을 표시
• 목적 오퍼랜드 : 레지스터, 메모리 주소의 위치 지정

하나의 메모리 위치에서 다른 위치로 어떤 값을 복사하기 위해서는 두 개의 인스트럭션이 필요하다
1. 소스 값을 레지스터에 적재하는 인스트럭션
2. 레지스터의 값을 목적지에 쓰기 위한 인스트럭션

3.4.3 데이터 이동 예제

1. C언어에서 "포인터"라고 부르는 것이 어셈블리어에서는 단순히 주소다. 포인터를 역참조하는 것은 포인터를 레지스터에 복사하고, 이 레지스터를 메모리 참조에 사용하는 과정으로 이루어진다.
2. x 같은 지역변수들은 메모리에 저장되기보다는 종종 레지스터에 저장된다. 레지스터의 접근은 메모리보다 속도가 훨씬 더 빠르다.

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

popq 인스트럭션이 데이터를 추출하는 반면, pushq 인스트럭션은 데이터를 스택에 추가하는 기능을 제공한다. 이들 인스트럭션은 한 개의 오퍼랜드를 사용한다 - 추가할 소스 데이터와 추출을 위한 데이터 목적지.

그림에서 보는 것처럼 값 0x123은 다른 값이 덮어써질 때까지 메모리 주소 0x100에 여전히 남아있다. 그렇지만, 스택 탑은 언제나 %rsp가 가리키는 주소를 의미한다. 스택 탑보다 윗부분에 저장된 값은 모두 무효인 값들이다.

3.5 산술연산과 논리연산

Do it! 자료구조와 함께 배우는 알고리즘 입문

---

8queen

한정 작업 : 필요하지 않은 분기를 없애서 불필요한 조합을 열거하지 않는 방법
분기 한정법 (branching and bounding method) : 분기 작업과 한정 작업을 조합하여 문제를 풀이하는 방법

# 8퀸 문제 알고리즘 구현하기

pos = [0] * 8           # 각 열에 배치한 퀸의 위치
flag_a = [False] * 8    # 각 행에 퀸을 배치했는지 체크
flag_b = [False] * 15   # 대각선 방향(좌하, 우상) 퀸 배치 체크
flag_c = [False] * 15   # 대각선 방향(좌상, 우하) 퀸 배치 체크

def set(i: int) -> None:
    """i열의 알맞은 위치에 퀸을 배치"""
    global sum
    for j in range(8):
        if(     not flag_a[j]       # j행에 퀸이 배치되지 않았다면
            and not flag_b[i+j]     # 대각선 좌하, 우상에 퀸이 없다면
            and not flag_c[i-j+7]): # 대각선 좌상, 우하에 퀸이 없다면
            pos[i] = j
            if i == 7:
                sum += 1
            else:
                # 퀸 공격 범위 추가
                flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = True
                # 다음 열에 퀸을 배치
                set(i+1)
                # 퀸 공격 범위 삭제
                flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = False

sum = 0
set(0)
print(sum)

책에서 나온 코드.

1. 0열에 퀸을 배치한다
2. 	for문을 돌려서 각 행에서 공격당할 수 있는지 확인한다.
3.	공격을 당하지 않는 행에 퀸을 놓는다.## Do it! 자료구조와 함께 배우는 알고리즘 입문
---
4. 8열까지 배치했다면, 경우의 수를 1 더한다.
5. 퀸을 놓았다면, 다음 열에 퀸을 배치한다 (재귀)
6. 다음 열에 퀸을 배치하고 왔다면, 놓았던 퀸을 꺼낸다.

슈도 코드로 분해해보았다.

백준

---

1629 곱셈

A, B, C = map(int, input().split())

R = A % C

def remainder(A, B, C):
    R = A % C
    if B == 1:
        return R
    elif B % 2 == 0: # 지수가 짝수면
        R = remainder(R*R, B//2, C)
        return R
    else:
        R = remainder(R*R,B//2,C) * R
        return R

print(remainder(A,B,C)%C)

A를 C로 나눈 나머지가 R이라 하면,
A^B % C == R^B % C 이다.

A = (몫*C) + R 이므로,
{(몫*C) + R} * {(몫*C) + R} * {(몫*C) + R}... 일때,
R^B를 제외한 나머지 항들은 C에 의해 깔끔히 나눠지기 때문이다.