프로그래밍노리터

정렬 알고리즘은 자료구조에서 가장 중요한 부분입니다. 중요하고 종류가 많아서 정렬 알고리즘을 잘 이해하고 것이 컴퓨터공학에서는 매우 중요합니다. 여러 가지 특징으로 정렬 알고리즘을 비교하면서 장단점을 비교해 보는 것이 공부에 도움이 됩니다. 또한 정렬 알고리즘의 성질 중에서 안정성이라는 것이 있는데요, 이게 뭔지, 왜 중요한지 한번 정리해 보겠습니다. 정렬 알고리즘의 안정성 어떤 정렬 알고리즘은 안정적이다(stable) 또는 안정성(Stability)을 만족한다고 얘기하는데요, 이것은 동일한 요소에 대해 정렬할 때 어떻게 처리하는가를 다루는 문제입니다. 안정적 알고리즘은 동일한 값의 순서가 정렬에 의해 바뀌지 않습니다. 즉 같은 값이라면 앞에 있던 것이 먼저 나오게 정렬하는 것입니다. 원래 값의 순서를 ..

연결리스트의 기본을 이해하고 나면 다양한 연산을 구현해 보아야 한다. 파이썬에 있는 리스트 명령을 전부 구현해 볼 수 있는데, 연결리스트는 자꾸 연습하다 보면 어느 순간에 편안해지는데, 그 시간이 빨리 오지는 않는다. 프로그램이 중지되거나 포인터가 말썽을 일으키는 긴 시간을 견디어낸 사람에게만 그 편안해지는 순간이 올 수 있다. 이를 위해 연결리스트의 여러 가지 기능을 연습할 수 있는 명령문 기반의 프로그램을 만들어보려고 한다. 이 프로그램은 append, extend, contains, compare 등 다양한 연산을 내맘대로 정의하여 실행해 볼 수 있다. 간단하게 하기 위해 리스트에는 int 정수값만 들어있다고 보자. 예시 실행화면은 아래와 같다. (1) append (2) extend (3) con..

연결리스트란? 연결리스트란 노드가 연쇄적으로 연결되어 있는 구조로 각 노드는 데이터(data)와 다음 링크(next, 다음 노드의 주소)라는 두개의 필드를 가진다. data 필드는 리스트의 실제 요소를 가지고 next는 리스트의 다음 노드를 가리키는 주소를 가집니다. 그러므로 next 필드는 다음 노드에 대한 포인터가 된다. 전체 연결리스트는 제일 앞의 노드에 대한 포인터로 나타낼 수 있다. 즉 첫 번째 노드를 가리키는 변수 하나만 있으면 리스트 전체를 접근할 수 있다. 여기서는 그것을 head라고 부른다. 마지막 노드의 next는 NULL이라고 알려진 특수한 값을 가진다. 이것은 더이상 다음 노드가 없음을 나타내는 역할을 한다. 노드가 없는 리스트를 널 리스트라고 한다. 그 경우 head=NULL이 된..

스택은 데이터의 순서를 뒤집어야 하는 경우에 유용하게 쓰인다. 스택을 임시 메모리로 사용하면 코드가 간결해진다. (1) 문자열 뒤집기 문자열의 글자 순서를 뒤집는 문제는 스택을 이용하여 다음과 같이 해결할 수 있다. (널문자는 그대로 있음) void reverse(char* word) { stack_t stack; int i; for (i = 0; i < strlen(word); i++) push(&stack, word[i]); i = 0; while (!is_empty(&stack)) word[i++] = pop(&stack); } (2) 2진수로 바꾸기 2진수로 바꾸는 문제는 2로 나눈 나머지를 거꾸로 이어 붙여서 2진수를 만들 수 있다. 이 문제도 스택을 이용해서 다음과 같이 간단하게 바꿀 수 있다..

큐에서 디큐한 후에 남는 공간을 비워두지 않기 위해 원형 큐를 사용할 수 있는데, 스택으로 큐를 구현하는 방법도 있다. 여기서는 스택 두 개를 이용해서 큐를 구현하는 방법을 살펴본다. 먼저 큐 구조체의 정의를 살펴보자. (요소의 타입(typedef ... element)은 스택에서 정의된다.) typedef struct queue_t { // 큐 타입 stack_t instack; stack_t outstack; } queue_t; 그러면 큐의 연산들은 다음과 같이 정의된다. init_queue: 두 개의 스택을 초기화한다. transfer: instack의 것을 pop하여 모두 outstack으로 옮겨 push한다. enqueue: 요소를 instack에 넣는다. instack이 꽉차있으면 ERROR...

트리 정보를 입력하여 생성하는 것은 쉽지 않은 일이다. 일반적으로 많이 사용되는 이진 트리 형태로 데이터를 읽어 구축하는 프로그램을 생각해 보자. 먼저 후위표기식 형태의 이진연산자로 구성된 수식을 읽어들여 트리를 구축할 수 있다. 다음과 같은 후위표기식을 입력으로 받아 이진 트리를 구축하는 문제를 생각해 보자. 94-385%+*435+2*++ 이 수식에 대한 이진트리는 다음과 같은 형태로 나타낼 수 있다. 이것은 트리의 출력기능을 통해 출력한 결과다. 트리의 노드는 연산자인 경우 넌터미널로 자식을 가진 노드가 되고 숫자는 터미널 노드여서 자식을 갖지 않는다. 그리고 숫자의 경우는 그 숫자를 노드의 데이터로 가진다. 다음 코드는 스택을 이용해 후위표기식의 계산과 같은 방식으로 숫자는 푸시하고 연산자가 나오..

선형큐 큐는 들어온 순서대로 처리되어 나가는 자료구조다. 배열 기반 큐의 구조체 정의는 다음과 같다. #define MAX_Q_SIZE 10// 큐의 최대 크기 typedef int elem_t; typedef struct queue_t { elem_t data[MAX_Q_SIZE]; int front; int rear; } queue_t; 여기서도 요소타입을 typedef int element;와 같이 선언하였음을 확인할 수 있다. 위와 같이 정의된 큐의 데이터에 대해 적용가능한 기능을 다음과 같이 함수 선언으로 미리 정의한다. (이것을 추상데이터타입(ADT)이라고 한다) void init(queue_t* q); int is_full(queue_t* q); int is_empty(queue_t* q);..

이번에는 스택을 이용하여 중위표기식을 후위표기식으로 바꾸는 것을 해보자. 실행결과는 다음과 같이 보여주고 싶다. 중위표기식에서 후위표기식으로 바꾸기 위해서는 다음과 같은 사항을 고려해야 한다. (1) 괄호를 처리할 수 있어야 한다. 괄호는 이항연산자가 아니므로 별도로 처리되어야 하고 괄호로 묶인 부분은 최우선으로 실행된다. (2) 이항연산자의 우선순위가 고려되어야 한다. 일단 우리는 다음과 같은 우선순위를 고려한다. 우선순위 연산자 1 &, | (and, or) 2 >, =, 2 - b * c ... 라는 수식을 생각해 보자. >는 -보다 낮고 -는 *보다 낮으므로 *가 수행되고 나서 -와 >가 수행될 수 있다. ... 부분에 >보다 더 낮은 우선순위 연산(&나 |)이 오면 드디어 >는 출력될 수 있다...

앞의 글에서 살펴본 스택의 기본 코드에 입력과 출력을 추가해 보자. 다음과 같은 형식으로 스택 명령을 처리하는 프로그램을 만들어보자. 앞 글에서 살펴본 stack.h와 stack.c를 이용하여 작성하면 된다. typedef int element; 로 정의되어 있으므로 스택의 요소 타입은 int다. #include "stack.h" stack_t stack; // 스택을 지역변수 객체로 선언. 이 변수가 스택객체를 나타낸다. char command[10]; void doit() { elem_t val; scanf_s("%s", command, 10); // 명령을 한 줄씩 읽어서 if (strcmp(command, "end") == 0) { return; } if (strcmp(command, "push"..

후위표기식은 수식을 표현하는 한 방법이다. 일반적으로 우리가 쓰는 표기식은 중위표기식, 즉 이항연산자를 두 개의 피연산자 가운데 쓰는 방법인데, 이것은 사람이 보기에 편리하지만 컴퓨터가 수식을 계산하기에는 매우 불편한 형태다. 그 이유는 우리가 수식을 계산할 때 사용하는 순서를 보면 알 수 있다. 7 + 3 * (5 - 2) + 4 이러한 수식을 계산하기 위해서 우리는 우선순위를 고려해야 한다. 즉 +보다 *가 우선순위가 높고 괄호는 가장 먼저 해야 한다. 그러므로 5-2가 먼저 계산된 후 3*3을 계산하고 그 다음에 7+9를 계산해야 한다. 이 때 수식을 왼쪽부터 차례로 읽어가면서 이러한 순서를 판단하여 계산하려면 매우 복잡한 코드가 필요하다. 이 문제를 해결하기 위해 조상 프로그래머들이 발견한 방법이..