(알고리즘 -1) 알고리즘 과 기본자료구조 배열 연결리스트 스택 큐 코드

알고리즘이란 

주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 유한개의 일련의 명령들을 순서적으로 구성한 것이라고 할 수 있습니다. 

 

1. 알고리즘 표현방법 

2. 기본 자료구조 

 

알고리즘 표현방법

알고리즘 표현방법에는 예를 들자면 최댓값을 찾는 알고리즘을 구현할 때 일상적인 언어로 표현하는 방법이 있고 코딩으로 표현하는 방법이 있고 순서도로 표현하는 방법이 있습니다. 

 

일상적인 언어를 예로 들자면 

1. 첫 숫자를 최댓값으로 저장한다. 

2. 다음 숫자를 읽고 저장된 최댓값과 비교한다. 

3. 비교 후 더 큰 숫자를 최댓값으로 다시 저장한다. 

4. 다음에 읽을 숫자가 남아 있으면 2번으로 간다. 

5. 저장된 숫자를 최댓값으로 출력한다 

 

이런 순서가 있고 이걸 코드로 표현하면 

 

다음과 같습니다. 또한 이걸 순서도로 표현하면 

 

순서도

기본 자료구조

자료구조란 

컴퓨터 기억공간 내에 자료를 표현하고 조직화하는 방법을 말합니다. 사용하는 데이터 양과 연산, 필요한 기억장치의 양 원하는 작업에 대한 처리 시간 데이터의 성격 등을 고려해서 문제에 맞는 적절한 자료구조를 선택해야 좋은 프로그램을 만들 수 있습니다. 

 

자료구조에는 선형자료구조인 배열, 연결리스트,큐,스택 그리고 비선형 자료구조인 트리와 그래프가 있습니다. 

배열

배열은 같은 자료형을 갖는 여러 원소를 하나의 변수이름으로 모아 놓은 데이터의 집합입니다. c언어로 예를 들자면 

int a[3]; 와 같은 자료구조를 말합니다. 

 

이렇게 배열을 선언하면 변수를 여러 개 선언하지 않아도 되는 장점이 있습니다. 그리고 순차적 원소 접근이 아닌 인덱스를 이용해 빠른 임의 접근이 가능하다는 점입니다. 

 

int a[3] = {1,2,3};

이라는 배열을 선언하고 할당했을 시 

 

a [2]를 출력하면 3이 나온다는 거죠 3이라는 값을 한 번에 접근하려면 인덱스의 값을 넣어주면 됩니다. 

하지만 단점이 존재합니다. 배열의 삽입 삭제를 했을시 모든 원소를 한 자리씩 뒤나 앞으로 이동해야 됩니다. 

굉장히 시공간 측면에서 불리하죠 모든원소를 움직여야 되니까요 이로 인해 오버플로나 저장공간의 낭비가 발생할 수 있습니다. 

 

배열의 이러한 문제를 보완한 형태의 자료구조가 바로 연결 리스트 입니다. 

 

연결리스트

데이터의 논리적 순서와 물리적 순서를 반드시 일치시킬 필요 없이 물리적으로는 데이터를 기억장치 어느 곳에 저장해도 됩니다. 하지만 기억장치의 임의 위치에 저장된 데이터 간의 논리적인 순서를 유지하는 것이 필요합니다. 이를 위해 하나의 데이터를 저장할 때 논리적으로 다음 데이터가 어디에 저장되어 있는지를 함께 나타내야 합니다. 

 

이를 위해 데이터 필드와 링크 필드로 이루어진 노드라는 저장구조를 이용합니다. 

 

연결리스트 구조

c언어로 작성하면 다음과 같습니다.

 

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

// 연결 리스트의 노드 구조체
struct node {
    int data;           // 저장할 데이터
    struct node* next;  // 다음 노드의 주소를 저장하는 포인터
};

// 연결 리스트에 데이터를 추가하는 함수
void add(struct node** head_ref, int new_data) {
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

// 연결 리스트의 내용을 출력하는 함수
void print_list(struct node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}


// 연결 리스트에서 데이터를 삭제하는 함수
void remove_node(struct node** head_ref, int key) {
    struct node* temp = (*head_ref), *prev;

    if (temp != NULL && temp->data == key) {
        (*head_ref) = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL)
        return;

    prev->next = temp->next;
    free(temp);
}



int main() {
    struct node* head = NULL;
    
    // 데이터 추가
    add(&head, 3);
    add(&head, 7);
    add(&head, 1);
    add(&head, 4);
    
    // 리스트 출력
    printf("Initial list: ");
    print_list(head);
    printf("\n");
    
    // 데이터 삭제
    remove_node(&head, 1);
    
    // 리스트 출력
    printf("List after removing node with value 1: ");
    print_list(head);
    printf("\n");
    
    return 0;
}

위코드를 보면 node라는 구조체를 설정하고 그안에 저장할 데이터랑 다음 노드의 주소를 저장하는 포인터가 있습니다. 

그다음 연결리스트에 데이터를 추가하는 add함수가 있고  데이터를 삭제하는 remove_node함수가 있습니다. 마지막으로 

리스트 내용을 출력하는 print_list함수가 있습니다. 

 

 

스택

스택이란 리스트 한쪽 끝에서만 데이터의 삽입과 삭제가 수행되는 자료구조입니다. 

가장 나중에 삽입된 데이터가 가장 먼저 삭제되기 때문에 후입선출(LIFO: Last-In-First-Out)리스트라고도 합니다. 스택에서는 쌓아 올린 데이터의 개수를 표시하기 위해서 일반적으로 top이라는 변수를 사용하며, 특별히 스택에서의 삽입과 삭제 연산은 각각 push 연산과 pop연산이라고 합니다. 

 

코드

#include <stdio.h>
#define MAX_SIZE 100 // 스택의 최대 크기

int stack[MAX_SIZE]; // 스택을 저장할 배열
int top = -1; // 스택의 가장 위에 있는 요소의 인덱스

void push(int value) { // 스택에 요소를 추가하는 함수
  if (top >= MAX_SIZE - 1) { // 스택이 가득 찬 경우
    printf("Error: Stack is full\n");
    return;
  }
  stack[++top] = value; // 스택의 가장 위에 요소 추가
}

int pop() { // 스택에서 요소를 제거하고 반환하는 함수
  if (top < 0) { // 스택이 비어있는 경우
    printf("Error: Stack is empty\n");
    return -1;
  }
  return stack[top--]; // 스택의 가장 위에 있는 요소 제거 후 반환
}

int peek() { // 스택의 가장 위에 있는 요소를 반환하는 함수
  if (top < 0) { // 스택이 비어있는 경우
    printf("Error: Stack is empty\n");
    return -1;
  }
  return stack[top]; // 스택의 가장 위에 있는 요소 반환
}

int main() {
  push(1);
  push(2);
  push(3);

  printf("Peek: %d\n", peek()); // Peek: 3

  printf("Pop: %d\n", pop()); // Pop: 3
  printf("Pop: %d\n", pop()); // Pop: 2

  push(4);

  printf("Peek: %d\n", peek()); // Peek: 4
  printf("Pop: %d\n", pop()); // Pop: 4
  printf("Pop: %d\n", pop()); // Pop: 1
  printf("Pop: %d\n", pop()); // Error: Stack is empty, Pop: -1

  return 0;
}

 

위의 코드를 보면 

MAX_SIZE를 100으로 설정하고 스택을 저장할 배열이랑 가장 위의요소가 있는 인덱스를 설정한 뒤

스택에 요소를 추가하는 함수 push랑 요소를 삭제하는 함수 pop이 있습니다.

이때 pop을 할시 마지막에 push 되었던 요소가 먼저 삭제되는 걸 볼 수 있습니다.

큐

큐는 한쪽 끝에서는 데이터의 삽입만 수행되고 다른 한쪽 끝에서는 데이터의 삭제만 수행되는 리스트입니다. 

일반적으로 데이터가 삭제되는 끝을 앞(front, head) 삽입되는 다른 한쪽의 끝을 뒤(rear, tail)이라고 합니다.  큐는 양쪽이 모두 열려 있는 모양으로 기차표를 사기 위해 매표창구 앞에 줄을 길게 서있는 모습이라고 생각하면 됩니다. 

 

먼저 삽입된 원소가 먼저 삭제되므로 선입선출(FIFO : First-In-First-Out) 리스트 라고 합니다. 

 

 

코드 

#include <stdio.h>
#define MAX_SIZE 100 // 큐의 최대 크기

int queue[MAX_SIZE]; // 큐를 저장할 배열
int front = 0; // 큐의 맨 앞 요소 인덱스
int rear = -1; // 큐의 맨 뒤 요소 인덱스

void enqueue(int value) { // 큐에 요소를 추가하는 함수
  if (rear >= MAX_SIZE - 1) { // 큐가 가득 찬 경우
    printf("Error: Queue is full\n");
    return;
  }
  queue[++rear] = value; // 큐의 맨 뒤에 요소 추가
}

int dequeue() { // 큐에서 요소를 제거하고 반환하는 함수
  if (front > rear) { // 큐가 비어있는 경우
    printf("Error: Queue is empty\n");
    return -1;
  }
  return queue[front++]; // 큐의 맨 앞에 있는 요소 제거 후 반환
}

int peek() { // 큐의 맨 앞에 있는 요소를 반환하는 함수
  if (front > rear) { // 큐가 비어있는 경우
    printf("Error: Queue is empty\n");
    return -1;
  }
  return queue[front]; // 큐의 맨 앞에 있는 요소 반환
}

int main() {
  enqueue(1);
  enqueue(2);
  enqueue(3);

  printf("Peek: %d\n", peek()); // Peek: 1

  printf("Dequeue: %d\n", dequeue()); // Dequeue: 1
  printf("Dequeue: %d\n", dequeue()); // Dequeue: 2

  enqueue(4);

  printf("Peek: %d\n", peek()); // Peek: 3
  printf("Dequeue: %d\n", dequeue()); // Dequeue: 3
  printf("Dequeue: %d\n", dequeue()); // Dequeue: 4
  printf("Dequeue: %d\n", dequeue()); // Error: Queue is empty, Dequeue: -1

  return 0;
}

 

선입선출의 과정을 보여주고 있습니다. 먼저 들어온 게 먼저 나간다는 거죠 1 2 3 넣고 빼면 1부터 빠져나가는 걸 볼 수 있습니다.