To-do List

---

☑️ 정답 봤던거 직접 코딩해보기 | 사냥꾼, 하노이탑, nQueen
☑️ Do it! ~ 처음부터 읽기 | p.97 ~
☑️ Do it! ~ 읽고 구현 연습 #자료구조 | 큐, 스택

☑️ Do it! ~ 읽고 구현 연습 #정렬 | 퀵 정렬(피봇 3선발), 병합 정렬, 힙 정렬
☑️ Do it! ~ 읽고 구현 연습 #알고리즘 | 백트래킹, 하노이탑
☑️ 슈도 코드 변환 | 버블 정렬, 이분 탐색, 백트래킹

✅ CSAPP 읽기 | 3.5
✅ Do it! ~ 읽고 구현 연습 #자료구조 | 연결 리스트
✅ 백준 풀기 | 요세푸스 문제 0

배운 것들

---

while 대신 for문

while K > 0:
    ...
    K -= 1

gpt가 이 부분을 보더니

for _ in range(K-1):

이걸로 수정해버렸다. 이게 확실히 더 직관적인듯.

힙

(맨날 혼자 끙끙대며 이해하다가 처음으로 다른 사람한테 직접 물어봤는데 알기 쉽게 잘 설명해주셔서 순식간에 힙, 우선순위 큐, 힙 정렬에 대해 이해했다. 앞으론 모르면 바로 물어보러 가야될듯.)

• 완전 이진 트리 : 좌측 상단부터 차례로, 1레벨 높아지면 요소 수 x2 되는 트리. 구현 자체는 리스트로 한다.

• 힙 : 완전 이진 트리인데 모든 부모 노드의 숫자가 자식보다 항상 크거나(최대 힙) 작음(최소 힙). 힙의 시간 복잡도는 삽입과 삭제 연산이 모두 O(log n)

• 힙 정렬 : 루트를 꺼내고 남은 부분을 힙으로 만드는 과정을 반복한다.

CSAPP

---

3.5 산술연산과 논리연산

오퍼랜드는 길이에 따른 다양한 변형이 가능하다.
예를 들어, 인스트럭션 클래스 ADD는 네 개의 덧셈 인스트럭션
addb, addw, addl, addq-각각 바이트, 워드, 더블워드, 쿼드워드 덧셈-으로 이루어져 있다.

연산 분류 : 유효주소 적재, 단항(unary), 이항(binary), 쉬프트
이항 연산은 두 개의 오퍼랜드를 갖고, 단항 연산은 한 개의 오퍼랜드를 갖는다.

3.5.1 유효주소 적재

유효주소 적재 인스트럭션 leaq는 실제로는 movq 인스트럭션의 변형이다. 이것은 메모리에서 레지스터로 읽어들이는 인스트럭션의 형태를 갖지만, 메모리를 전혀 참조하지 않는다.

이 인스트럭션의 첫 번째 오퍼랜드는 일종의 메모리 참조처럼 보이지만, 가리키는 위치에서 읽기를 수행하는 대신에 유효주소를 목적지에 복사한다. 포인터 만들 때 씀.

3.5.2 단항 및 이항 연산

단항 연산은 하나의 오퍼랜드가 소스와 목적지로 동시에 사용된다. 이 오퍼랜드는 레지스터나 메모리 위치가 될 수 있다.

이항 연산은 두 번째 오퍼랜드가 소스이면서 목적지로 사용된다. 소스가 먼저 오고, 나중에 목적지가 나온다. 이 문법은 C에서의 할당 연산자인 x -= y 같은 문장과 유사하다.

3.5.3 쉬프트 연산

쉬프트 연산은 먼저 쉬프트하는 크기를 주고, 두번째엔 쉬프트할 값을 준다. 산술과 논리형 우측 쉬프트가 모두 가능하다.

x86-64에서는 w비트 길이의 데이터 값에 적용하는 쉬프트 연산은 레지스터 %cl의 하위 m비트로 쉬프트 양을 결정하며, 2^m = w의 관계가 성립한다. 상위 비트들은 무시된다.

예를 들어, 레지스터 %cl이 16진수 0xFF를 가질 때, 인스트럭션 salb는 7만큼 쉬프트하고, salw는 15, sall은 31, salq는 63만큼 쉬프트하게 된다.

3.5.4 토의

xorq, leaq, salq, andl, subq 같은 어셈블리 코드 설명해줘. 그리고 %rsi, %rdi 이런게 뭐야?

어셈블리 명령어 설명

1. xorq

• 설명: XOR (배타적 OR) 연산을 수행합니다. 두 오퍼랜드의 비트가 서로 다를 때 1, 같을 때 0이 됩니다.
• 용법: xorq src, dest
• 예시: xorq %rax, %rax (레지스터 %rax의 값을 0으로 만듭니다).

2. leaq

• 설명: 메모리 주소를 계산하는 명령어입니다. Load Effective Address의 약자입니다.
• 용법: leaq src, dest
• 예시: leaq (%rax,%rbx,4), %rcx (%rax + 4*%rbx의 값을 %rcx에 저장).

3. salq

• 설명: 산술 좌측 시프트 (Shift Arithmetic Left) 연산을 수행합니다.
• 용법: salq count, dest
• 예시: salq $2, %rax (%rax의 값을 2비트 왼쪽으로 시프트).

4. andl

• 설명: AND 연산을 수행합니다. 두 오퍼랜드의 비트가 모두 1일 때 1이 됩니다.
• 용법: andl src, dest
• 예시: andl %eax, %ebx (%eax와 %ebx의 비트별 AND 결과를 %ebx에 저장).

5. subq

• 설명: 뺄셈 연산을 수행합니다.
• 용법: subq src, dest
• 예시: subq %rbx, %rax (%rax에서 %rbx를 뺀 결과를 %rax에 저장).

레지스터 설명

%rsi, %rdi 등 레지스터

• %rsi (Source Index Register): 데이터 소스 주소를 저장하는 데 사용됩니다. 특히, 문자열이나 배열 조작에 사용됩니다.
• %rdi (Destination Index Register): 데이터 목적지 주소를 저장하는 데 사용됩니다. 특히, 문자열이나 배열 조작에 사용됩니다.

주로 사용되는 64비트 레지스터

• %rax: 누산기 (Accumulator) 레지스터로 주로 연산의 결과를 저장하는 데 사용됩니다.
• %rbx: 베이스 레지스터로 사용됩니다.
• %rcx: 카운터 레지스터로 반복문에서 주로 사용됩니다.
• %rdx: 데이터 레지스터로 사용됩니다.
• %rsp: 스택 포인터로 현재 스택의 꼭대기를 가리킵니다.
• %rbp: 베이스 포인터로 현재 스택 프레임의 시작을 가리킵니다.
• %rsi: 소스 인덱스 레지스터.
• %rdi: 목적지 인덱스 레지스터.
• %r8 - %r15: 추가적인 범용 레지스터입니다.

예제 코드 설명

다음은 각 명령어와 레지스터를 사용한 예제 코드입니다:

.section .data
    msg: .ascii "Hello, World!\n"

.section .text
    .global _start

_start:
    # 메시지 주소를 %rsi에 저장
    leaq msg(%rip), %rsi

    # 문자열 길이를 %rdx에 저장 (14 바이트)
    movq $14, %rdx

    # 시스템 콜: write(1, msg, 14)
    movq $1, %rax        # 시스템 콜 번호 (sys_write)
    movq $1, %rdi        # 파일 디스크립터 (stdout)
    syscall              # 시스템 콜 호출

    # 시스템 콜: exit(0)
    movq $60, %rax       # 시스템 콜 번호 (sys_exit)
    xorq %rdi, %rdi      # %rdi를 0으로 설정 (exit code 0)
    syscall              # 시스템 콜 호출

이 예제는 "Hello, World!"를 출력한 후 프로그램을 종료하는 어셈블리 코드입니다. leaq, movq, xorq, syscall 명령어와 %rsi, %rdi, %rax, %rdx 등의 레지스터를 사용합니다.

3.5.5 특수 산술연산

두 개의 64비트 부호형 또는 비부호형 정수들 간의 곱셈은 결과값을 표시하기 위해 128비트를 필요로 한다.

(chatgpt에 교재 내용 사진 찍어서 올리고 쉽게 설명 요청)

이미지의 내용을 바탕으로 imulq 명령어와 관련된 설명을 쉽게 풀어서 설명드리겠습니다.

imulq 명령어

imulq 명령어는 x86-64 아키텍처에서 사용되는 명령어로, 두 개의 64비트 정수를 곱하여 그 결과를 저장하는 역할을 합니다. 이 명령어는 두 가지 형태로 존재합니다:

1. 2 오퍼랜드 형태:

   • 두 개의 64비트 오퍼랜드를 곱하여 64비트 결과를 생성합니다.
   • 결과는 지정된 레지스터에 저장됩니다.

2. 3 오퍼랜드 형태:

   • 두 개의 64비트 값을 곱하여 128비트 결과를 생성합니다.
   • 하위 64비트는 rax 레지스터에, 상위 64비트는 rdx 레지스터에 저장됩니다.

비부호형 곱셈 (mulq)과 부호형 곱셈 (imulq)

• 비부호형 곱셈 (mulq):

  • 두 개의 64비트 값을 곱하여 128비트 결과를 생성합니다.
  • 오퍼랜드가 비부호형 정수일 때 사용됩니다.
  • 곱셈 결과의 하위 64비트는 rax 레지스터에, 상위 64비트는 rdx 레지스터에 저장됩니다.

• 부호형 곱셈 (imulq):

  • 두 개의 64비트 값을 곱하여 128비트 결과를 생성합니다.
  • 오퍼랜드가 부호형 정수일 때 사용됩니다.
  • imulq는 특정 조건에서 두 오퍼랜드 형태와 세 오퍼랜드 형태를 모두 지원합니다.

리틀 엔디안 머신이 뭐임

리틀 엔디안 머신

리틀 엔디안(Little Endian) 머신은 데이터를 메모리에 저장할 때, 가장 낮은 바이트(가장 덜 중요한 바이트)를 가장 낮은 메모리 주소에 저장하는 방식입니다. 엔디안(Endianness)은 컴퓨터 시스템이 다중 바이트 데이터를 메모리에 저장하거나 읽는 순서를 정의하는 방법입니다

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

---

8-1 연결 리스트

노드 : 연결 리스트의 원소
노드 구성요소 : 데이터, 포인터(pointer)
포인터 : 뒤쪽 노드를 가리킨다(참조한다)

머리 노드(head node) : 맨 앞에 있는 노드
꼬리 노드(tail node) : 맨 끝에 있는 노드

앞쪽 노드(predecessor node) : 각 노드에서 바로 앞에 있는 노드
뒤쪽 노드(successor node) : 각 노드에서 바로 뒤에 있는 노드

8-2 포인터를 이용한 연결 리스트

자기 참조(self-referential)형 : 자신과 같은 형의 인스턴스를 참조하는 필드가 있는 구조

# 포인터로 연결 리스트 구현

from __future__ import annotations
from typing import Any, Type

class Node:
    """연결 리스트용 노드 클래스"""

    def __init__(self, data: Any = None, next: Node = None):
        """초기화"""
        self.data = data # 데이터
        self.next = next # 포인터

# data: 데이터(데이터에 대한 참조: 임의의 형)
# next: 뒤쪽 포인터(뒤쪽 노드에 대한 참조: Node형)

class LinkedList:
    """연결 리스트 클래스"""

    def __init__(self) -> None:
        """초기화"""
        self.no = 0     # 노드의 개수
        self.head = None # 머리 노드
        self.current = None # 주목 노드

    def __len__(self) -> int:
        """연결 리스트의 노드 개수를 반환"""
        return self.no

no: 리스트에 등록되어 있는 노드의 개수
head: 머리 노드에 대한 참조
current : 현재 주목하고 있는 노드에 대한 참조.
리스트에서 노드를 검색하여, 그 노드를 주목한 직후에
노드를 삭제하는 등의 용도로 사용한다.

def search(self, data: Any) -> int:
    """data와 값이 같은 노드를 검색"""
    cnt = 0
    ptr = self.head
    while ptr is not None:
        if ptr.data == None:
            self.current = ptr
            return cnt
        cnt += 1
        ptr = ptr.next

# ptr: 스캔 중인 노드를 참조하기 위한 변수
# cnt: 맨 앞에서 몇 번째 원소를 스캔하고 있는지 

def __contains__(self, data: Any) -> bool:
    """연결 리스트에 data가 포함되어 있는지 확인"""
    return self.search(data) >= 0

def add_first(self, data:Any) -> None:
    """맨 앞에 노드를 삽입"""
    ptr = self.head # 삽입하기 전의 머리 노드
    self.head = self.current = Node(data, ptr)
    self.no += 1

머리와 현재 노드를 새로 만든 노드로 변경
리스트의 길이를 +1

def add_last(self, data: Any):
    """맨 끝에 노드를 삽입"""
    if self.head is None:   # 리스트가 비어 있으면
        self.add_first(data) # 맨 앞에 노드를 삽입
    else:
        ptr = self.head
        while ptr.next is not None:
            ptr = ptr.next
        ptr.next = self.current = Node(data, None)
        self.no += 1

head부터 시작해서 next가 none인 노드를 찾고 거기에 노드 삽입

def remove_last(self):
    """꼬리 노드를 삭제"""
    if self.head is not None:
        if self.head.next is None: # 노드가 1개 뿐이라면
            self.remove_first()    # 머리 노드를 삭제
        else:
            ptr = self.head        # 스캔 중인 노드
            pre = self.head        # 스캔 중인 노드의 앞쪽 노드

            while ptr.next is not None:
                pre = ptr
                ptr = ptr.next

            pre.next = None        # pre는 삭제 뒤 꼬리 노드
            self.current = pre
            self.no -= 1

노드가 2개 이상이라면 일단 ptr, pre 둘 다 헤드 노드로 설정
헤드 노드부터 스캔하다가 뒤가 연결 안된 노드 만나면 연결 끊기

def remove(self, p: Node) -> None:
    """노드 p를 삭제"""
    if self.head is not None:   # 헤드가 없다면 지울 것도 없으니 패스
        if p is self.head:      # p가 머리 노드이면
            self.remove_first() # 머리 노드를 삭제
        else:
            ptr = self.head

            while ptr.next is not p: # 포인터의 다음 노드가 p가 될때까지
                ptr = ptr.next       # 다음 노드로 계속 넘어가기
                if ptr is None:
                    return      # ptr은 리스트에 존재하지 않음
            ptr.next = p.next 
            # 포인터가 가리키는 다음 노드를 삭제할 노드의 다음 노드로 변경
            self.current = ptr
            self.no -= 1

def remove_current_node(self) -> None:
    """주목 노드를 삭제"""
    self.remove(self.current)

def clear(self) -> None:
    """전체 노드를 삭제"""
    while self.head is not None: # 전체가 비워질때까지
        self.remove_first()      # 머리 노드를 삭제
    self.current = None
    self.no = 0

def next(self) -> bool:
    """주목 노드를 한 칸 뒤로 이동"""
    # 현재 노드가 없거나 현재 노드의 다음 노드가 없다면
    if self.current is None or self.current.next is None:
        return False # 이동할 수 없음
    self.current = self.current.next
    return True

remove()에서 다음 노드가 p가 될 때까지 옮긴 후에
'포인터가 가리키는 다음 노드'를, '삭제할 노드의 다음 노드'로 변경

def __iter__(self) -> LinkedListIterator:
    """이터레이터를 반환"""
    return LinkedListIterator(self.head)

class LinkedListIterator:
    """클래스 LinkedList의 이터레이터용 클래스"""

    def __init__(self, head: Node):
        self.current = head
    
    def __iter__(self) -> LinkedListIterator:
        return self
    
    def __next__(self) -> Any:
        if self.current is None:
            raise StopIteration
        else:
            data = self.current.data
            self.current = self.current.next
            return

• __init__(self, ...): 객체가 생성될 때 호출
• __iter__(self): 객체를 반복(iteration)할 때 호출
• __next__(self): 이터레이터의 다음 요소를 반환할 때 호출

각각의 호출들을 어떻게 알아차리고 불러오는지 궁금하다.

8-3 커서로 연결 리스트 만들기

class ArrayLinkedList:
    """연결 리스트 클래스(배열 커서 버전)"""

    def __init__(self, capacity: int):
        """초기화"""
        self.head = Null                  # 머리 노드
        self.current = Null               # 주목 노드
        self.max = Null                   # 사용 중인 꼬리 레코드
        self.deleted = Null               # 프리 리스트의 머리 노드
        self.capacity = capacity          # 리스트의 크기
        self.n = [Node()] * self.capacity # 리스트 본체
        self.no = 0

프리 리스트 : 삭제한 거 넣어놓는 리스트

def get_insert_index(self):
    """다음에 삽입할 레코드의 인덱스를 구함"""
    if self.deleted == Null: # 삭제 레코드가 존재하지 않음
        if self.max + 1 < self.capacity:
            self.max += 1
            return self.max     # 새 레코드를 사용
        else:
            return Null         # 크기 초과
    else:
        rec = self.deleted
        self.deleted = self.n[rec].dnext # 프리 리스트에서 맨 앞 rec를 꺼내기

def delete_index(self, idx: int) -> None:
    """레코드 idx를 프리 리스트에 등록"""
    if self.deleted == Null: # 삭제 레코드가 존재하지 않음
         self.deleted = idx
         self.n[idx].dnext = Null # idx를 프리 리스트의 맨 앞에 등록
    else:
        rec = self.deleted
        self.deleted = idx # idx를 프리 리스트의 맨 앞에 삽입
        self.n[idx].dnext = rec

삭제한 걸 프리 리스트에 넣고, 삽입할 때 프리 리스트에 있는 인덱스를 먼저 가져다 쓴다.

백준

---

요세푸스 문제 0

# 원형 큐 구현
from __future__ import annotations
from typing import Any, Type

Null = -1

class Node:
    def __init__(self, data: Any=None, next: Node=None):
        self.data = data
        self.next = next

class ArrayLinkedList:
    def __init__(self, max):
        self.head = Null                  # 머리 노드
        self.current = Null               # 주목 노드
        self.tail = Null
        self.max = max                      # 크기
        self.no = 0

    def __len__(self) -> int:
        return self.no
    
    def add(self, data: Any) -> None:
        if self.no == 0:
            self.head = Node(data, self.head)
            self.current = self.head
            self.tail = self.current
            self.no += 1
        elif self.no==max-1:
            self.head = Node(data, self.tail)
            self.current = self.head
            self.no += 1
        else:

            self.head = Node(data, self.head)
            self.current = self.head
            self.no +=1
            
    def deque(self, K: int) -> int:
        """현재 노드에서 인덱스 n만큼 더해서 나온 노드를 삭제"""
        while K > 0:
            pre = self.current
            self.current = self.current.next
            K -= 1
        result = self.current.data
        pre.next = self.current.next
        return result
    
N, K = map(int, input().split())
S = []
Q = ArrayLinkedList(N)

for i in range(N, 0, -1):
    Q.add(i)

for _ in range(N):
    S.append(Q.deque(K))

직접 만든 원형 큐로 풀어보려고 대충 다 구현해봤는데
오류가 생기길래 gpt한테 물어봄.

코드에서 발생한 TypeError는 max를 self.max로 변경하지 않아서 발생합니다. max는 파이썬의 내장 함수이기 때문에 self.max를 사용하여 인스턴스 변수로 접근해야 합니다. 이를 수정한 후, 원형 큐 구현의 일부 문제도 해결하겠습니다.

다음은 수정된 코드입니다:

from __future__ import annotations
from typing import Any

Null = -1

class Node:
    def __init__(self, data: Any = None, next: Node = None):
        self.data = data
        self.next = next

class ArrayLinkedList:
    def __init__(self, max: int):
        self.head = Null                  # 머리 노드
        self.current = Null               # 주목 노드
        self.tail = Null
        self.max = max                      # 크기
        self.no = 0

    def __len__(self) -> int:
        return self.no
    
    def add(self, data: Any) -> None:
        new_node = Node(data)
        if self.no == 0:
            self.head = new_node
            self.current = self.head
            self.tail = self.current
            self.tail.next = self.head  # 원형 연결리스트로 만듬
            self.no += 1
        elif self.no == self.max - 1:
            self.tail.next = new_node### 변경 사항 설명

1. **`self.max` 사용**:
   - `self.max`를 사용하여 클래스 인스턴스 변수를 참조하도록 변경했습니다.

2. **원형 연결 리스트 설정**:
   - 원형 연결 리스트의 특징을 반영하여 노드를 추가할 때 `tail.next`를 `head`로 연결하는 부분을 추가했습니다.
   - `add` 메서드에서 새로운 노드를 추가할 때 `tail.next`를 업데이트하여 원형 연결 리스트를 유지했습니다.

3. **노드 삭제**:
   - `deque` 메서드에서 `K-1`번 이동하여 `current` 노드를 업데이트한 후, 다음 노드를 삭제하도록 했습니다.
   - `self.no`가 0이 될 때 `head`, `tail`, `current`를 `Null`로 설정하여 빈 리스트 상태를 나타내도록 했습니다.
            new_node.next = self.head
            self.tail = new_node
            self.no += 1
        else:
            new_node.next = self.head
            self.tail.next = new_node
            self.tail = new_node
            self.no += 1

    def deque(self, K: int) -> int:
        """현재 노드에서 인덱스 K만큼 더해서 나온 노드를 삭제"""
        if self.no == 0:
            return Null
        for _ in range(K-1):
            self.current = self.current.next
        result = self.current.next.data
        self.current.next = self.current.next.next
        self.no -= 1
        if self.no == 0:
            self.head = self.tail = self.current = Null
        return result
    
N, K = map(int, input().split())
S = []
Q = ArrayLinkedList(N)

for i in range(1, N+1):
    Q.add(i)

for _ in range(N):
    S.append(Q.deque(K))

print(S)

변경 사항 설명

1. self.max 사용:

   • self.max를 사용하여 클래스 인스턴스 변수를 참조하도록 변경했습니다.

2. 원형 연결 리스트 설정:

   • 원형 연결 리스트의 특징을 반영하여 노드를 추가할 때 tail.next를 head로 연결하는 부분을 추가했습니다.
   • add 메서드에서 새로운 노드를 추가할 때 tail.next를 업데이트하여 원형 연결 리스트를 유지했습니다.

3. 노드 삭제:

   • deque 메서드에서 K-1번 이동하여 current 노드를 업데이트한 후, 다음 노드를 삭제하도록 했습니다.
   • self.no가 0이 될 때 head, tail, current를 Null로 설정하여 빈 리스트 상태를 나타내도록 했습니다.

이제 수정된 코드로 원형 큐를 구현하고 요세푸스 문제를 해결할 수 있습니다. S 리스트에 결과를 저장하고 출력하면 올바른 결과를 얻을 수 있습니다.

gpt에 여러번 다시 결과 틀렸다고 수정하라고 하고 출력 형식도 예시랑 똑같이 만들었는데 계속 틀려서 배웠다, 그냥 해봤다 치고 이렇게 푸는건 포기

N, K = map(int, input().split())
S = [i for i in range(1,N+1)]
A = []

idx = 0
for j in range(N):
    idx += K - 1
    idx = idx % N
    A.append(S[idx])
    del S[idx]
    N-=1

print('<' + ', '.join(map(str, A)) + '>')

idx += K를 했었어서 틀렸었다.
"번째"니까 2번째는 인덱스 +1
구질구질하게 또 gpt한테 물어보고 수정하여 정답.