'배열' 태그의 글 목록

힙 정렬(Heap Sort)

힙(Heap) ?

최대값, 최소값을 찾아내는 연산을 빠르게 하기위해 고안된 완전트리를 기본으로 한 자료구조

힙정렬

힙 정렬은 분할정복 알고리즘으로 최대 힙 트리나 최소 힙 트리를 구성해 정렬 하는 방법 입니다.

어떠한 방법?

예제는 배열을 이용해서 트리구조를 구성했습니다.

배열을 이용한 트리구조에서 주의할 점은 균형 잡히지 않은 노드의 경우 실제로 없는 노드를 위해 배열 공간을 확보해야 하기 때문에 균형잡힌 노드에 한해서 사용 가능합니다.

아래와 같은 이진트리가 있을 때

A노드부터 1번부터 12번까지 숫자를 매기면 아래 그림과 같습니다.

이 때 i노드의 부모번호는 i/2

i노드의 왼쪽 자식노드는 2i 오른쪽 자식노드는 2i+1을 만족합니다.

예) 5번 노드의 부모노드 번호는 5/2=2(버림)

4번 노드의 왼쪽 자식노드는 4*2=8 오른쪽 자식도느는 4*2+1 = 9

이 개념을 이용하면 배열을 이용해서 트리를 구성할 수 있습니다.

배열을 이용한 힙 정렬 예제

upHeap함수

아래에서 위로 올라가면서 자리를 바꾸는 함수입니다.

void upHeap(int array[], int k){
    int v;
    v = array[k];
    array[0] = MAX;
    while (array[k/2]<=v) // 부모 <= 자식
    {
        array[k] = array[k/2];
        k/=2;
    }
    array[k] = v;
}

downHeap함수

upHeap함수와 반대로 아래로 내려가면서 비교하는 함수입니다.

자식노드 왼쪽과 오른쪽 노드를 비교해서 더 큰 노드를 이용합니다.

void downHeap(int array[], int n, int k){
    int i;
    int v = array[k];
    while(k<=n/2){
        i = k<<1; // 2*k
        if(i<n && array[i]<array[i+1]) i++; //왼쪽, 오른쪽 노드 비교
        if(v>=array[i]) break;
        array[k] = array[i];
        k=i;
    }
    array[k] = v;
}

insert, delete함수

insert는 입력받은 배열을 트리구조로 사용하기 위해 입력하는 함수

delete는 정렬된 데이터를 받아오는 함수 입니다.

void insert(int array[], int *hn, int v){
    array[++(*hn)] = v;
    upHeap(array, *hn);
}

int delete(int array[], int *n){
    int v = array[1];
    array[1] = array[(*n)--];
    downHeap(array, *n, 1);
    return v;
}

힙 정렬 함수

입력받은 배열을 정렬하는 함수입니다.

첫번 째 for문 : 배열을 순차적으로 삽입

두번 째 for문 : 정렬된 데이터를 꺼냄

마지막 for문 : 정렬시에 0번째에는 큰 수를 넣어놓고

1번째 인덱스부터 이용했기 때문에

한칸씩 당겨주는 for문

void heap_sort(int array[], int n){
    int hn = 0;
    int i= 0;
    for(i=1; i<=n; i++)
        insert(array, &hn, array[i]);
    for(i=hn; i>=1; i--){
        array[i] = delete(array, &hn);
    }
    for(int j=0; j<n; j++){
        array[j] = array[j+1];
    }
}

배열 출력 함수

void print_array(int array[], int size){
    for(int i=0; i<size; i++){
        printf("%-4d",array[i]);
    }
    printf("\n");
}

메인 함수

정렬 전 배열과 위의 기준대로 정렬한 결과를 출력합니다.

정렬을 하고나면 배열의 크기가 변하기 때문에

oldSize변수에 초기 크기를 저장해두고 진행했습니다.

void main(){
    int array[] = {11,1,83,202,55,4,119,81,15,47,19,28};
    int oldSize = sizeof(array)/sizeof(int);
    int size = sizeof(array)/sizeof(int);
    printf("########### Sorting before ###########\n");
    print_array(array, size);
    heap_sort(array, size);
    printf("########### Sorting after ###########\n");
    print_array(array, oldSize);
}

실행 결과

참고 : C로 배우는 알고리즘 (이재규)

위키백과(힙 ,힙 정렬)

관련 포스팅

[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)

저작자표시 비영리

'언어 > Data Strcuture' 카테고리의 다른 글

[C] 합병 정렬(Merge Sort) (0)	2019.05.04
[C] 기수 정렬(Radix Sort) (1)	2019.04.30
[C] 퀵 정렬(Quick Sort) (0)	2019.04.24
[C] 셸 정렬(Shell Sort) (2)	2019.04.23
[C] 버블 정렬(Bubble Sort) (0)	2019.04.20

큐(Queue)

큐(Queue)?

큐는 FIFO(First In First Out)구조로 가장 먼저 들어간 값이 가장먼저 나오는 구조입니다.

삽입하는 put 동작과 삭제하는 get 동작이 있습니다.

front(앞)에서 값을 얻어내고, rear(뒤)에 값을 넣습니다.

1. 큐 형태

2. 큐 종류

큐의 종류는 선형 큐, 원형 큐, 우선순위 큐 등이 있습니다.

- 선형 큐(Linear Queue) : 기본적인 큐의 형태로 막대모양의 큐로 빈 공간 사용 시 모든 자료를 꺼내거나 옮겨야 한다는 단점이 있음

- 원형 큐(Circular Queue) : 선형큐의 단점을 보완하는 구조로 front와 rear가 연결된 형태

- 우선순위 큐(Priority Queue) : 데이터 삽입 시 우선순위에 따라 정렬 후 저장하는 방식

배열을 이용한 원형 큐 예제

원형큐의 경우 front, rear 구분을 위한 공간이 하나 필요합니다.

그래서, 크기가 10인 큐의 경우 사용가능한 공간은 9가 됩니다.

큐로 사용할 int형 배열 선언 및 초기화 함수

#include "stdio.h"
#define MAX 10

int queue[MAX];
int front, rear;

void init_queue(){
    front = rear = 0;
}

초기화 함수

front와 rear값을 같게하면 초기화 가능

void clear_queue(){
    front = rear;
}

put 함수

(rear+1) % 큐 크기 == front 일 경우 오버 플로우 발생

int put(int k){

    if((rear+1) % MAX == front){

        printf("QUEUE OVER FLOW!\n\n");

        return -1;

    }else{

        queue[rear] = k;

        rear = ++rear % MAX;

        return 1;

}

원형큐는 아래 그림과 같이 모듈러를 생각하면 편합니다.

get 함수

front와 rear가 같을 경우 빈 값이므로 언더플로우 발생

int get(){
    int k;
    if(front == rear){
        printf("QUEUE UNDER FLOW!\n\n");
        return -1;
    }else{
        k = queue[front];
        front = ++front % MAX;
        return k;
    }
}

큐의 값을 출력하는 함수

void print_queue(){
    printf("\n");
    for(int i=front; i!=rear; ++i % MAX){
        printf("queue[%d]=%d\n",i,queue[i]);
    }
    if(front == rear){
        printf("queque is empty!!! \n");
    }
    printf("\n");
}

메인함수

큐의 크기가 10이므로 10번째 값을 넣을때에 오버플로우가 발생하고,

10번째 값을 가져올 때에는 언더플로우가 발생합니다.

void main(){
    init_queue();
    put(1);
    put(3);
    put(6);
    put(9);
    put(7);
    put(2);
    put(0);
    put(0);
    put(10);
    put(20); // 10번째 값
    printf("################################################################\n");
    print_queue();
    for(int i=0; i<3; i++){
        get();
    }
    printf("################################################################\n");
    print_queue();
    for(int i=0; i<7; i++){
        get();
    }
    printf("################################################################\n");
    put(0);
    put(0);
    put(10);
    clear_queue();
    print_queue();
}

실행결과

참고 : C로 배우는 알고리즘 (이재규)

'언어 > Data Strcuture' 카테고리의 다른 글

[C] 삽입 정렬(Insertion Sort) (0)	2019.04.19
[C] 선택 정렬(Selection Sort) (0)	2019.04.19
[C] 트리(Tree) (0)	2019.04.07
[C] 스택(Stack) (1)	2019.03.29
[C] 연결리스트(LinkedList) (0)	2019.03.28

스택(Stack)

스택(Stack)?

스택은 LIFO(Last In First Out)구조로

가장 나중에 들어간 값이 가장먼저 나오는 구조입니다.

삽입하는 PUSH와 삭제하는 POP 동작이 있습니다.

1. 스택 형태

2. PUSH

3. POP

배열을 이용한 예제

스택으로 사용할 int형 배열 선언 및 초기화 함수

#include "stdio.h"
#define MAX 10

int stack[MAX];
int top;

void init_stack(void){
    top = -1;
}

스택에 push하는 함수

스택 크기보다 크면 오버플로우 발생

int push(int t){
    if(top >=MAX-1){
        printf("########### STACK OVER FLOW ###########\n");
        return -1;
    }else{
        stack[++top] = t;
        return t;
    }
}

스택에서 pop하는 함수

스택 크기보다 작으면 오버플로우 발생

int pop(void){
    if(top<0){
        printf("########### STACK UNDER FLOW ###########\n");
        return -1;
    }
    return stack[top--];
}

스택의 값을 출력하는 함수

void print_stack(void){
    printf("PRINT STACK \n");
    for(int i=top; i>=0; i--){
        printf("%-6d",stack[i]);
    }
    printf("\n");
}

메인함수

11개의 값을 push할 경우 10개는 정상적으로 push 되지만,

나머지 1개의 값은 스택 오버플로우가 발생합니다.

두번째 pop을 수행할 때 5개의 값은 정상적으로 pop 되지만,

나머지 1개의 값은 스택 언더플로우가 발생합니다.

void main(){
    init_stack();
    printf("########### PUSH ###########\n");
    for(int i=0; i<11; i++){
        push(i);
    }
    print_stack();
    printf("########### POP ###########\n");
    for(int i=0; i<5; i++){
        pop();
    }
    print_stack();
    for(int i=0; i<6; i++){
        pop();
    }
}

실행 결과

참고 : C로 배우는 알고리즘 (이재규)

'언어 > Data Strcuture' 카테고리의 다른 글

[C] 삽입 정렬(Insertion Sort) (0)	2019.04.19
[C] 선택 정렬(Selection Sort) (0)	2019.04.19
[C] 트리(Tree) (0)	2019.04.07
[C] 큐(Queue) (2)	2019.04.01
[C] 연결리스트(LinkedList) (0)	2019.03.28

배열(Array)과 포인터(Pointer)

제목을 배열과 포인터라고 한 이유는, 배열을 이용해 포인터를 사용하고 포인터를 이용해 배열을 사용하기 때문입니다. 포인터는 주소를 가리키는 것인데, 배열은 메모리 일정공간에 연속으로 존재하기때문에, 배열을 이용해 포인터를 사용할 수 있습니다.

배열의 주소는 어떻게 표현할까요? 변수의 주소처럼 &를 붙여 &arr[0]이렇게도 표현할 수 있지만, 배열의 이름 자체가 배열의 첫번째 원소의 주소입니다. 배열의 이름을 포인터 상수 라고도 하는데, 포인터 상수는 주소값의 변경이 불가능합니다.

아래 코드는 정수형 변수와 배열의 주소 비교입니다.

----------------------------------------------------------------------------------------

#include <stdio.h>

int main()

{

int a, b, c;

int d[3];

printf("a : %d, b : %d, c : %d \n",&a,&b,&c);

printf("d[0] : %d d[1] : %d d[2] : %d \n", &d[0], &d[1], &d[2]);

return 0;

}

----------------------------------------------------------------------------------------

배열의주소는 int형이라 4바이트씩 즉 4씩 차이가나고, int형 변수 a,b,c는 규칙없이 각기 다른 주소에 저장되었습니다.

이제 배열을 이용해 포인터를 사용해 보겠습니다. 아래 코드는 배열에 hello 라는 문자열을 넣고 포인터 변수를 선언해 주소를 가리킨뒤에 포인터를 출력해보는 코드입니다.

----------------------------------------------------------------------------------------

#include <stdio.h>

int main()

{

char text[6] = "hello"; // 널값을 포함한 문자열의길이 6바이트

char *pointer; // 포인터 변수 선언

pointer = text;

printf("text : %s \n", text); // 배열주소의 값 출력

printf("pointer : %s \n", pointer); // 포인터가 가리키는 주소의 값 출력

printf("--------------- \n");

int i;

for (i = 0; i < 5; i++){

printf("%.1s \n",pointer+i); // 맨 앞글자만 출력

}

----------------------------------------------------------------------------------------

아래 결과를 보면 포인터 변수 역시 배열의 주소를 가리켜서 같은 hello가 출력이 됩니다. 원소를 한글자씩 출력하기위해서 반복문안에 출력문을 포맷을 %.1s로 지정했는데, %s로 지정 하면 포인터가 가리키는 주소도 1씩 증가해서 hello, ello, llo, lo, o가 출력이됩니다.

포인터 변수는 사용자의 입력을 받을때의 변수로도 사용할 수도 있습니다.

----------------------------------------------------------------------------------------

#include <stdio.h>

#pragma warning(disable:4996)

int main()

{

int input;

int *pointer;

pointer = &input;

printf("정수 입력 : ");

scanf("%d", pointer);

printf("입력된 정수 : %d \n", *pointer);

}

----------------------------------------------------------------------------------------

마지막으로, 포인터 변수를 이용해서 문자열을 입력받아 대문자는 소문자로 소문자는 대문자로 바꾸는 코드를 작성해 봤습니다. 포인터 변수로 입력을 받고, 출력은 배열로 했습니다.

----------------------------------------------------------------------------------------

#include <stdio.h>

#pragma warning(disable:4996)

int main(){

char change[10];

char *input;

input = &change;

printf("영문을 입력하시면 대소문자가 서로 변환됩니다. 입력 : ");

scanf("%s", input);

while (*input){

if (*input >= 'A' && *input <= 'Z') // 대문자일 경우

{

*input = *input + 32;

}

else if (*input >= 'a' && *input <= 'z') // 소문자일 경우

{

*input = *input - 32;

}

input++;

}

printf("변환된 문자 : %s \n", change);

}

----------------------------------------------------------------------------------------

조건문에서 왜 +32, -32 연산을 하는지 이해가 안되시는분은 조건문 게시글 http://parkdream.tistory.com/11 을 참고하시면 됩니다.

→ *input+32, -32 대신 *input-'A'+'a' *input-'a'+'A'를 사용하셔도 됩니다.

결과는 아래와 같이 대소문자가 서로 바뀌어서 출력됩니다.

* 출처 : 한국기술교육대학교 온라인평생교육원 C 프로그래밍_2

스타일 C프로그래밍 저.김종훈,김종진 출.WellBook

저작자표시 비영리

'언어 > C' 카테고리의 다른 글

[C] 공용체 (0)	2016.12.27
[C] 구조체 (2)	2016.12.26
[C] 포인터 (0)	2016.12.23
[C] 배열 (0)	2016.12.23
[C] 디버깅 (0)	2016.12.21

배열(Array)

배열은 변수들을 연속으로 선언해서 일괄적으로 사용하는 자료형입니다. 배열은 일차원 배열과 다차원 배열로 나뉘며, 앞에서 공부할 때 몇번 활용한 적이 있습니다. 배열 없이 정수형 변수 5개를 선언할 경우 int a,b,c,d,e; 처럼 일일이 직접 선언해야하는데 배열을 사용하면 int a[5]; 처럼 한번에 선언할 수 있습니다. 배열을 전달할 경우 참조 전달이 되기 때문에 *이나 &를 붙이지 않아도 됩니다.

- 배열

배열의 사용은 아래와 같습니다. 인덱스는 0부터 시작하며, 변수도 사용 가능합니다. 한가지 주의할 점은 배열은 한가지 자료형으로만 구성해야하며, 선언된 배열의 길이를 초과하는 인덱스를 사용하면 안됩니다.

----------------------------------------------------------------------------------------

타입 변수명[인덱스]

int a[5];

int b[];

int c=5;

int d[c];

------------------------------------------------------------------------------------------

배열에 값을 넣을 때, 초기화하면서 선언할수는 있지만, 선언한뒤에 값을 한번에 넣지는 못합니다.

------------------------------------------------------------------------------------------

int a[3]={1,2,3}; (가능)

int b[3];

b={1,2,3}; (불가능)

→ b[0]=1; b[1]=2; b[2]=3; (가능) b[3]=4: // 배열의 길이를 초과하므로 불가능

------------------------------------------------------------------------------------------

- 다차원 배열

다차원 배열은 배열을 원소로 가지는 배열을 뜻합니다. 아래와 같이 사용하며 부분적으로 초기화가 가능합니다.

------------------------------------------------------------------------------------------

int a[3][3]={1,2,3,4,5,6,7,8,9};

위와 같이 초기화 하는 경우 배열에는 아래 표와같이 값이 들어갑니다.

int a[][3]={1,2,3,4,5,6,7,8,9}로 초기화할 경우, 자동으로 초기화된 값을 보고, int[3][3]과 같은 배열의 길이를 가집니다.

구분	첫번째	두번째	세번째
a[1]	1	2	3
a[2]	4	5	6
a[3]	7	8	9

------------------------------------------------------------------------------------------

아래와 같이 부분적으로 초기화할 경우 값이 순서대로 들어가는 것이 아니라 빈자리에는 0이 채워집니다.

------------------------------------------------------------------------------------------

int a[3][3]={{1},{4,5},{7,8,9}};

구분	1번째	2번째	3번째
a[1]	1	0	0
a[2]	4	5	0
a[3]	7	8	9

------------------------------------------------------------------------------------------

문자열은 정수와 다르게, 문자열의 끝에 \0(널문자)를 넣어줘야 합니다. \0를 넣는 이유는 문자열의 끝을 구분하기 위해서 입니다. 문자열은 부분적으로 초기화 할경우에 0대신 \0가 채워집니다.

------------------------------------------------------------------------------------------

char a[3][8] ={"red","skyblue","mint"}

구분	1번째	2번째	3번째	4번째	5번째	6번째	7번째	8번째
a[1]	r	e	d	\0	\0	\0	\0	\0
a[2]	s	k	y	b	l	u	e	\0
a[3]	m	i	n	t	\0	\0	\0	\0

------------------------------------------------------------------------------------------

배열을 이용해 16진수를 입력받아 10진수로 변환해주는 소스코드를 작성해 봤습니다.

------------------------------------------------------------------------------------------

#include <stdio.h>

#pragma warning(disable:4996)

int main()

{

char a[] = { '0','1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E' ,'F'}; //16진수 배열

char input[3]; // 입력을 받는 배열

int i, j;

int num = 0;

printf("10진수로 변환할 16진수를 입력하세요 : ");

scanf("%s", input);

for (i = 0; input[i] != '\0'; i++) // 입력한 배열의 문자가 널문자가 아닐때까지 반복

for (j = 0; j < 16; j++) // 0~16까지 같은수를 찾을때까지 반복

if (input[i] == a[j])

num = num * 16 + j;

printf("십진수 : %d \n", num);

return 0;

}

------------------------------------------------------------------------------------------

위의 코드를 실행하면 아래와 같은 결과가 출력됩니다. A1을 입력했을때, 'A'는 배열 a의 10번째 이므로 j가 10이되고 num=0*16+10이되서 10이되고, '1'은 배열a의 1번째이므로 다시 num=10*16+1이되서 161이 출력됩니다.

* 출처 : 한국기술교육대학교 온라인평생교육원 C 프로그래밍_2

스타일 C프로그래밍 저.김종훈,김종진 출.WellBook

저작자표시 비영리

'언어 > C' 카테고리의 다른 글

[C] 배열과 포인터 (3)	2016.12.25
[C] 포인터 (0)	2016.12.23
[C] 디버깅 (0)	2016.12.21
[C] 매개변수 전달 방식 (0)	2016.12.20
[C] 함수(2) (0)	2016.12.20

꿈꾸는 개발자 박혜웅

배열

[C] 힙 정렬(Heap Sort)

'언어 > Data Strcuture' 카테고리의 다른 글

[C] 큐(Queue)

'언어 > Data Strcuture' 카테고리의 다른 글

[C] 스택(Stack)

'언어 > Data Strcuture' 카테고리의 다른 글

[C] 배열과 포인터

'언어 > C' 카테고리의 다른 글

[C] 배열

'언어 > C' 카테고리의 다른 글

+ Recent posts

티스토리툴바