전체 글 (34)
2024-08-06 05:04:40

1. 스택

  • 입출력 창구가 한개임
  • 가장 마지막에 들어간 데이터가 가장 먼저 나오고 가장 먼저 들어가면 가장 늦게 나오는 자료구조
  • 스택의 사용 용도: 자동 메모리, 프로토콜 등이 대부분 스택을 기반으로 구성되어 있음

1-1. 스택의 연산

  • 삽입(push): 새로운노드를 쌓음
  • 제거(pop): 최상위 노드를 걷어냄

1-2. 배열로 구현한 스택

  • ArrayStack.h
#ifndef ARRAYSTACK_H
#define ARRAYSTACK_H

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;

typedef struct tagNode {
  ElementType Data;
} Node;

typedef struct tagArrayStack {
  int Capacity;
  int Top;
  Node *Nodes;
} ArrayStack;

//함수 선언
void AS_CreateStack(ArrayStack **Stack, int Capacity);
void AS_DestroyStack(ArrayStack *Stack);
void AS_Push(ArrayStack *Stack, ElementType Data);
ElementType AS_Pop(ArrayStack *Stack);
ElementType AS_Top(ArrayStack *Stack);
int AS_GetSize(ArrayStack *Stack);
int AS_IsEmpty(ArrayStack *Stack);
  • ArrayStack.c
#include "ArrayStack.h"

//스택 생성
void AS_CreateStack(ArrayStack **Stack, int Capacity) {
  //스택을 자유 저장소에 생성
  (*Stack) = (ArrayStack*)malloc(sizeof(ArrayStack));
  //입력된 capacity만큼의 노드를 자유 저장소에 생성
  (*Stack)->Nodes = (Node*)mallocc(sizeof(Node)*Capacity);

  //초기화
  (*Stack)->Capacity = Capacity;
  (*Stack)->Top = -1;
}

//제거
void AS_DestroyStack(ArrayStack *Stack) {
  free(Stack->Nodes);
  free(Stack);
}

//push
void AS_Push(ArrayStack *Stack, ElementType Data) {
//최상위 노드의 인덱스에서 1을 더한 곳에
  Stack->Top++;
  //새 노드를 입력하도록 구성
  Stack->Nodes[Stack->Top].Data = Data;
}

//pop
ElementType AS_Pop(ArrayStack *Stack) {
    //최상위 노드에서 1만큼 낮춤
  int Position = Stack->Top--;
  //pop연산은 최상위 값을 반환하므로 리턴값 존재
  return Stack->Nodes[Position].Data;
}

ElementType AS_Top(ArrayStack *Stack) {
//pop연산처럼 빼내는 것이 아니라 최상위 값만 반환
  return Stack->Nodes[Stack->Top].Data;
}

int AS_GetSize(ArrayStack *Stack) {
  return Stack->Top+1;
}

2. 큐

  • 입력, 출력 창구가 따로 존재
  • 먼저 들어간 게 먼저 나옴
  • 구성: 가장 앞 요소(전단), 가장 마지막 요소(후단)
  • 스택의 연산은 모두 Top에서만 이루어지지만 큐의 삽입 연산은 후단, 제거 연산은 전단에서 수행됨.

2-1. 큐의 연산

  • 스택과 유사하게 삽입과 제거 연산
  • Enqueue(삽입), Dequeue(제거)로 표현

2-2. 순환 큐

삽입과 제거 연산이 후단과 전단 각각 다른 위치에서 일어남 -> 전단을 제거하고 나머지 앞 요소들을 한칸식 옮겨와야 하는 비효율 발생

전단의 위치를 하나씩 밀어도 되지만, 그러면 가용 용량이 줄어듦 -> 끝과 시작을 이어버리면 해결

  • 순환 큐: 시작과 끝을 연결해서 효율적인 삽입/삭제 연산이 가능하도록 고안된 큐
  • 포화 상태: 빈칸 없이 큐가 꽉찬 상태
  • 공백 상태: 빈칸이 존재함

큐가 포화 상태가 아니라 공백 상태일때도 전단과 후단이 같은 위치에 있어서 구분할 필요가 있음.
-> 큐 배열 생성 시 1만큼 더 크게 만들어서 전단과 후단 사이를 비우면 됨

2-3. 구현

  • CircularQueue.h
#ifndef CIRCULAR_QUEUE_H
#define CIRCULAR_QUEUE_H

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;

typedef struct tagNode {
  ElementType Data;
} Node;

typedef struct tagCircularQueue {
  int Capacity;
  int Front;
  int Real;
  Node *Nodes;
} CircularQueue;

void CQ_CreateQueue(CircularQueue **Queue, int Capacity);
void CQ_DestroyQueue(CircularQueue *Queue);
void CQ_Enqueue(CircularQueue *Queue, ElementType Data);
ElementType CQ_Dequeue(CircularQueue *Queue);
int CQ_GetSize(CircularQueue *Queue);
int CQ_IsEmpty(CircularQueue *Queue);
int CQ_IsFull(CircularQueue *Queue);
  • CircularQueue.c


void CQ_CreateQueue(Circular **Queue, int Capacity) {
  //큐를 자유 저장소에 생성
  (*Queue) = (CircularQueue*)malloc(sizeof(CircularQueue));

  //입력된 capacity+1 만큼의 노드를 자유 저장소에 생성
  (*Queue)->Nodes = (Node*)malloc(sizeof(Node)*(Capacity+1));

  (*Queue)->Capacity = Capacity;
  (*Queue)->Front = 0;
  (*Queue)->Rear = 0;
}

void CQ_DestroyQueue(CircularQueue *Queue) {
  free(Queue->Nodes);
  free(Queue);
}

void CQ_Enqueue(CircularQueue *Queue, ElementType Data) {
  int Position = 0;
  if (Queue->Rear == Queue->Capacity) {
    Position = Queue->Rear;
    Queue->Rear = 0;
  }
  else Position = Queue->Rear++;
  Queue->Nodes[Position].Data = Dta;
}

ElementType CQ_Dequeue(CircularQueue *Queue) {
  int Position = Queue->Front;
  if (Queue->Front == Queue->Capacity) Queue->Front = 0;
  else Queue->Front++;
  return Queue->Nodes[Position].Data;
}

int CQ_GetSize(CircularQueue *Queue) {
  return (Queue->Front == Queue->Rear);
}

int CQ_IsFull(CircularQueue *Queue) {
  if (Queue->Front < Queue->Rear) 
    return (Queue->Rear - Queue->Front) == Queue->Capacity;
  else
   return (Queue->rear + 1) == Queue->Front;
}
2024-08-06 01:38:02
  • 연결 리스트와 배열의 차이점
  • 단일 연결 리스트
  • 이중 연결 리스트
  • 환형 연결 리스트

1. 리스트와 배열 비교

배열: 생성하는 시점에 배열의 크기를 지정해줘야하고 생성한 후 크기를 변경할 수 없다.

-> 유연하게 크기를 바꿀 수 있는 자료구조: 리스트

2. 연결 리스트(linked list)

  • 연결 리스트(링크드 리스트): 노드를 연결해서 만든 리스트라고 해서 붙여진 이름

  • 다뤄야 하는 데이터 집합의 크기를 미리 알지 못해도 데이터가 늘어날 때마다 노드를 만들어 테일에 붙이면 됨!

노드

노드의 구성: 필드(데이터 보관), 포인터(다음 노드와 연결)

//노드 표현
typedef int ElementType;

typedef struct tagNode {
  ElementType Data; //데이터
  struct Node* NextNode; // 노드
} Node;

따라서 위와 같이 노드를 표현할 수 있다.

연산

연결 리스트의 주요 연산은 다음과 같다.

  • 노드 생성(CreateNode), 소멸(DestroyNode)
  • 노드 추가(AppendNode)
  • 노드 탐색(GetNodeAt)
  • 노드 삭제(RemoveNode)
  • 노드 삽입(InsertAfter, InsertnewHead)

노드 생성/소멸

  • 자동 메모리 사용?

Node *SLL_CreateNode(ElementType NewData) {
  Node NewNode; //자동 메모리 사용
  NewNode.Data = NewData;
  NewNode.NextNode = NULL:
  return &NewNode;
}

Node *MyNode = SLL_CreateNode(117);
// 할당되지 않은 메모리를 가리킴

위와 같이 코드를 짜게 되면 문제가 생기는데, NewNode가 존재하는 메모리의 주소를 반환하는 것이 아니라 현재는 제거된 과거의 메모리 주소를 반환한다.

따라서 malloc을 이용하여 정상 작동하는 생성 함수를 만들 수 있다.

Node *SLL_CreateNode(ElementType NewData) {
  Node *NewNode = (Node*)malloc(sizeof(Node));
  NewNode->Data = NewData;
  NewNode->NextNode = NULL;
  return NewNode;
}

void SLL_DestroyNode(Node *Node) {
  free(Node);
} //소멸 함수

free함수는 메모리 주소만 정확히 알면 알아서 처리하므로 소멸 함수는 간단하게 구현 가능하다.

노드 추가

  • 연결 리스트 테일 뒤에 새로운 노드를 만들어 연결하는 것.
void SLL_AppendNode(Node **Head,Node *NewNode) {
  if ((*Head) == NULL) *Head = NewNode;
    // 헤드가 없음
  else {
    Node *Tail = (*Head);
    while (Tail->NextNode != NULL) Tail = Tail->NextNode;
    Tail->NextNode = NewNode;
    // 테일(끝)을 찾아 NewNode를 연결.
  }
}
  • 매개변수로 Node **Head를 받는 이유

위 함수에서 매개변수를 *Head를 받았다고 가정하고 아래 코드를 실행해본다고 하자.

Node *List = NULL;
Node *NewNode = NULL;
NewNode = SLL_CreateNode(117);
SLL_AppendNode(List, NewNode);

결과적으로는 NewNode가 List에 추가되지 않는다.
코드의 실행 과정을 살펴보면

  1. List와 NewNode가 아무 메모리도 가리키지 않는 상태로 초기화
  2. NewNode = SLL_Createnode(117); 실행 후 자유 저장소에 117을 가진 노드 생성. NewNode는 이 노드의 주소를 가리킨다.
  3. SLL_AppendNode()를 호출하면서 매개변수들 _Head와 _NewNode가 자동 메모리에 생성되고 List는 _Head에 NewNode는 _NewNode에 메모리의 주소를 복사해서 넣는다.
  4. List포인터가 담고 있는 주솟값만 복사되고 List포인터 변수의 주소는 전달되지않는다.
  5. 함수 실행 전과 마찬가지로 List는 NULL로 남는다.

노드 탐색

배열은 인덱스를 통해 원하는 element에 바로 접근할 수 있으나 연결 리스트는 헤드부터 시작해서 노드들을 순차적으로 하나하나 건너와야 접근이 가능하다.

Node *SLL_GetNode(Node *Head,int Location) {
  Node *Current = Head;
  while (Current != NULL && (--Location) >= 0)
    Current = Current->NextNode;
  return Current;
}

Location이 0이 될때까지 노드를 순차적으로 이동한다.
이렇게 바로 접근이 불가능한 것은 연결 리스트의 단점으로 볼 수 있다.

노드 삭제

void SLL_RemoveNode(Node **Head, Node *Remove) {
  if (*Head == Remove) *Head = Remove->NextNode;
  else {
    Node *Current = *Head;
    while (Current != NULL && Current->NextNode != Remove) 
      Current = Current->NextNode;
    if (Current != NULL) 
      Current->NextNode = Remove->NextNode;
  }
}

삭제하고자 하는 노드를 찾고 해당 노드의 다음 노드를 이전 노드의 NextNode에 연결하면 노드를 삭제할 수 있다.

노드 삽입

노드와 노드 사이에 새로운 노드를 끼워넣는다.
이전 노드의 NextNode포인터가 새 노드를 가리키고 새 노드의 NextNode포인터가 다음 노드를 가리키게 하면 될 것이다.

void SLL_InsertAfter(Node *Current,Node *NewNode) {
  NewNode->NextNode = Current->NextNode;
}

와 같이 쉽게 구현된다.

노드 개수 세기

int SLL_GetNodeCount(Node *Head) {
  int Count = 0;
  Node *Current = Head;
  while (Current != NULL) {
    Current = Current->NextNode;
    Count++;
  }
  return Count;
}

그냥 끝까지 도달할 때까지 카운트 수를 늘려주면 된다.

3. 이중 연결 리스트 (double linked list)

  • 단일 연결 리스트: head에서 tail로만 탐색 가능

  • 이중 연결 리스트: 양방향 탐색 가능

  • 노드 구조: 포인터가 데이터의 앞뒤로 모두 존재함

typedef int ElementType;

typedef struct tagNode {
  ElementType Data;
  struct tagnode *PrevNode;
  struct tagNode *NextNode;
} Node;

단일 연결 리스트와 다르게 PrevNode포인터가 추가되었다.

노드 생성/소멸


Node *DLL_CreateNode(ElementType NewData) {
  Node *NewNode = (Node*)malloc(sizeof(Node));
  NewNode->Data = NewData;
  NewNode->PrevNode = NULL;
  NewNode->NextNode = NULL;
  return NewNode;
}
void DLL_DestroyNode(Node *Node) {
  free(Node);
}

단일 연결 리스트와 크게 다를 것이 없으나 PrevNode관련만 추가되었다. 노드 삭제는 동일하다.

노드 추가


void DLL_AppedNode(Node **Head, Node *NewNode) {
  if ((*Head) == NULL) *Head = NewNode;
  else {
    Node *Tail = (*Head);
    while (Tail->NextNode != NULL) Tail = Tail->NextNode;
    Tail->NextNode = NewNode;
    NewNode->PrevNode = Tail;
  }
}

기본적인 연산은 단일 연결리스트와 유사하나 새로운 노드의 PrevNode가 기존의 tail(끝)을 가리키도록 한다.

노드 삭제

이중 연결 리스트에서 노드 삭제는 다른 연산들보다 약간 복잡하다.

삭제할 노드의 포인터가 앞뒤 노드를 모두 가리키고 있으므로 노드의 양쪽 포인터, 앞 노드의 NextNode포인터 뒤 노드의 PrevNode포인터 모두를 건드려야한다.

void DLL_DeleteNode(Node **Head, Node *Remove) {
  if (*Head == Remove) {
    *Head = Remove->NextNode;
    if ((*Head) != NULL) ((*Head)->PrevNode = NULL);
    Remove->PrevNode = NULL;
    Remove->NextNode = NULL;
  }
  else {
    Node *Temp = Remove;
    if (Remove->PrevNode != NULL)
      Remove->PrevNode->NextNode = Temp->NextNode;

    if (Remove->NextNode != NULL) 
      Remove->NextNode->PrevNode = Temp->PrevNode;

    Remove->PrevNode = NULL;
    Remove->NextNode = NULL;
  }
}

노드 삽입

void DLL_InsertAfter(Node *Current, Node *NewNode) {
  NewNode->NextNode = Current->NextNode;
  NewNode->PrevNode = Current;
  if (Current->NewNode != NULL) {
    Current->NextNode->PrevNode = NewNode;
    Current->NextNode = NewNode;
  }
}

PrevNode로 이전 노드를, NextNode로 다음 노드를 가리키게 구성하면 된다. 삭제보다는 간단하다.

4. 환형 연결 리스트

일반적인 연결리스트와 크게 다르지는 않으나 그저 헤드가 테일과 연결되어있는 형태이다.

void CDLL_RemoveNode(Node **Head, Node *Remove) {
  if (*Head == Remove) {
    (*Head)->PrevNode->NextNode = Remove->NextNode;
    (*Head)->NextNode->PrevNode = Remove->PrevNode;
    *Head = Remove->NextNode;
    Remove->PrevNode = NULL;
    Remove->NextNode = NULL;
  }
  else {
    Remove->PrevNode->NextNode = Remove->NextNode;
    Remove->NextNode->PrevNode = Remove->PrevNode;
    Remove->PrevNode = NULL;
    Remove->Nextnode = NULL;
  }
}

void CDLL_AppendNode(Node **Head, Node *NewNode) {
  if ((*Head) == NULL) {
    *Head = NewNode;
    (*Head)->NextNode = *Head;
    (*Head)->PrevNode = *Head;
  }
  else {
    Node *Tail = (*Head)->PrevNode;
    Tail->NextNode->PrevNode = NewNode;
    Tail->NextNode = NewNode;
    NewNode->NextNode = (*Head);
    NewNode->PrevNode = Tail;
  }
}

연산이 크게 다를 것은 없고 헤드와 테일이 어떤 끝이 아니라 노드를 추가할 때도 헤드와 테일 사이에 삽입하는 느낌으로 접근하면 된다.

2024-07-30 19:30:23

0. intro

오늘 포스팅할 내용은 어셈블리다.

사용환경은 윈도우10, 사용 도구는 x32dbg이고 인텔 x86어셈블리를 포스팅할 것이다.

물론 리눅스 터미널에서도 nasm써서 프로그래밍하거나 sasm이라는 어셈블리 ide를 사용할 수도 있으나 디버거를 사용하는 것이 레지스터의 값이라든가 그런 것을 보기 좋다.

 

간단한 사용법을 정리하자면 file에서 exe파일을 가져와서 열고 step over를 사용해 한 줄씩 실행하면서 결과를 볼 수 있다.

어셈블리 실습을 위해서는 그냥 기능이 없는 파일을 가지고와서 명령어를 직접 작성해가면서 레지스터, 메모리 칸을 관찰하면 된다.

1. mov

x32dbg에서 각 줄 선택 후 우클릭->Assemble하거나 스페이스바를 누르면 어셈블리 명령어를 쓸 수 있다.

그럼 첫 명령어를 작성해보자. mov라는 것을 쓸 것인데 그게 뭐냐하면 값을 덮어쓰는 느낌이다.

명령어를 집어넣고 실행하면 다음과 같다.

 

mov reg, num ; reg에 num을 넣음
mov reg, reg

어째서 코드블럭에 어셈블리가 없는가

 

숫자(즉각값)을 넣을 수도 있고 다른 레지스터의 값도 넣을 수 있다.

 

2. 레지스터

  • eax, ebx, ecx, edx....
    레지스터는 이런 모양으로 생겨먹었다.(32비트 기준)

인텔이 16비트이던 시절 ax를 썼음.
16비트 = 2바이트이므로 바이트별로 ah, al 이런 식으로 썼음.
높은 놈이 h, 낮은 놈이 l...

 

현재는 extended 붙여서 32비트일떈 eax, 64비트는 rax라고 부름.
a 대신 다른 알파벳 붙은 놈들도 구성은 똑같다.

따라서 이런 식으로 eax가 아니라 ah에 값을 넣어볼 수도 있고 실행 결과는 옆과 같음.

mov명령어는 기본적으로 mov reg, reg으로 다른 레지스터의 값을 옮겨올 수는 있지만
mov eax, bh처럼 크기가 다르면 안됨. 즉각값을 넣을 때는 상관없으나 레지스터 간 값 덮어쓰기(?)는 바이트 사이즈를 일치시켜줘야 한다.

al과 ah이런 놈들은 1바이트로 크기가 같기 때문에 mov al, bh 이런 것은 가능함.

 

+)x32dbg기능: 레지스터 우클릭 후 change value로 직접 값을 바꿀 수 있다.