프로그래밍/자료구조14 [C언어와 함께 자료구조를] 큐(Queue)의 개념, 배열로 큐 구현하기 큐의 개념 큐는 스택과 비슷한 모양을 하고 있지만, 조작방식은 다릅니다. 큐의 구조도 간단한데,스택과 달리 앞 뒤가 뚫린 통이라고 보시면 됩니다. 이 통은 뒤에서 뭔가를 집어넣고 앞에서 빼냅니다. 즉, 먼저 들어온 것은 먼저 나오는 구조로 FIFO(First In First Out)이라고 부릅니다. 큐의 연산은 put과 get이 있습니다. 큐에 자료를 집어 넣을 때는 뒤(rear)에서 처리하고, 이를 put 이라고 합니다. 반대로 큐에서 자료를 빼낼 때는 앞(front)에서 처리하고 이를 get이라고 합니다. 그림을 보시면 쉽게 이해하시겠죠? 배열로 큐 구현하기 배열을 이용한 큐의 구현은 스택의 구현과 비슷한 난이도일 것 같지만, 조금 더 생각해보면 문제가 아주 많습니다. 먼저 저장할 자료의 앞과 뒤를 .. 2015. 3. 21. [C언어와 함께 자료구조를] 스택의 개념, 배열로 스택구현 스택(stack)과 다음에 공부할 큐(queue)와 같은 자료구조는 특정한 접근방식이 있고, 이를 응용한 알고리즘이 매우 다양합니다. 특히 스택은 아주 중요한 자료구조로 시스템 내부의 기본동작에서 고급 알고리즘까지 다양하게 활용되고 있습니다. 스택의 개념 스택의 구조는 매우 간단합니다. 스택은 밑이 막혀있는 긴 통이라고 보면 됩니다. 즉, 입구와 출구가 같은 긴 통이므로 먼저 들어간 것은 밑에 있게 되고, 나중에 들어간 것은 제일 먼저 나오게 됩니다. 그래서 스택을 LIFO(Last In First Out)구조라 고 합니다. 스택을 조작하는 방법(연산이라고 합니다.) 은 두가지가 있습니다. 하나는 스택에 값을 집어 넣는 연산인 push이고 다른 하나는 스택에서 값을 빼내는 pop 동작입니다. 위 그림을 .. 2015. 3. 15. [C언어와 함께 자료구조를] 동적 기억장소 할당 C언어에서 배열은 길이를 미리 알 수 있을 때 고정된 크기의 정적배열을 사용합니다. 만약에 길이의 상한을 알 수 없을 때는 동적 배열을 사용할 수 있습니다. 동적 배열을 사용하기 위해서는 배열의 공간 확보를 위해 메모리 할당 (memory allocation)을 해야합니다. 동적 문자열 할당 C언어에서는 메모리 할당을 위해 아래와 같은 함수를 사용합니다. #include void *malloc (size_t size); void free(void *ptr); malloc()은 size bytes만큼의 메모리를 할당하고, 할당된 메모리의 포인터를 반환합니다. 만약, 메모리 할당에 실패하면 NULL을 반환합니다. 할당된 메모리는 초기화되어 있지 않으므로 사용전에 반드시 초기화를 하여야 합니다. 그리고 더이상.. 2015. 3. 12. [C언어와 함께 자료구조를] 구조체 알아보기 정수형, 문자형, 부동소수점 타입 등은 C언어에서 사용되는 전형적인 기본 자료형입니다. 그러나, 이러한 기본 자료형만으로 프로그래밍을 할 수는 없습니다. 프로그래머는 스스로 타입을 정의하고 이 타입에 대한 변수를 만들 수 있습니다. 타입정의 (typedef) typedef는 어떤 변수의 역할을 명확히 하기 위해서 사용됩니다. 예를 들어, 다음과 같은 문장을 살펴봅시다. typedef int boolean; #define FALSE 0 #define TRUE !FALSE 첫번째 문장은 boolean을 int와 똑같이 변수의 타입을 정의하는데 사용하고, 아래 두 문장은 boolean 변수의 값을 나타내는 상수를 정의합니다. 이렇게 선언하는 것은 정수 변수가 TRUE와 FALSE를 가진다는 것을 명확하게 알려.. 2015. 3. 11. [C언어와 함께 자료구조를] 문자열과 배열 이름, 단어, 문장 등을 저장하기 위해서는 문자열을 사용합니다. C언어에서 문자열은 문자의 배열입니다. 최대 10개의 문자를 가지는 문자열 str은 다음과 같이 선언합니다. char str[10]; C언어의 배열은 인덱스가 0부터 시작하므로 문자열 str의 첫번째 문자는 s[0], 마지막 문자는 s[9]가 됩니다. 예를 들어 문자열 str에 "Hi"를 저장하려면, 배열 str의 처음 두개의 위치에 문자를 저장하고, 이 두개의 문자만이 유효하다는 표시를 해야 합니다. C언어에서 문자열의 마지막 문자 다음에 Null 문자로 문자의 마지막을 표시합니다. 아래의 예에서 Null문자는 '\0'을 사용했는데요, 이는 문자 '0'이 아닌 Null (아무것도 안들어 있다. 즉 코드값은 0x00) 문자를 의미합니다. s.. 2015. 3. 10. [C언어와 함께 자료구조를] 포인터 활용 포인터를 이용한 값 교환 두개의 정수 변수의 값을 교환하는 함수를 생각해 보죠. 그냥 소스를 먼저 보겠습니다. void intswap (int a, int b) { int t; t = a; a = b; b = t; } void main () { int x, y; x = 1; y = 2; printf ("변경 전 : x=%d y=%d\n", x, y); intswap (x, y); printf ("변경 후 : x=%d y=%d\n", x, y); } 자... 그럼 출력은? 변경 전 : 1 2 변경 후 : 1 2 이런 결과가 나오는 이유는 C언어에서 인수를 함수에 전달할 때, 인수 자체를 전달하지 않고 인수의 복사(copy)본을 전달하기 때문입니다. 이런 방법을 값에 의한 호출(call by value) 라.. 2015. 3. 10. 이전 1 2 3 다음
