CS

스택은 배열 또는 연결리스트로 구현할 수 있다. 연결리스트로 구현해보면 다음과 같은 헤더파일과 실행파일을 통해 스택을 구현할 수 있다. 코드 부분설명▼ void StackInit(Stack* pstack) { pstack->head = NULL; } 스택 초기화 부분 (포인터 변수 head는 NULL 로 초기화한다.) int SIsEmpty(Stack* pstack) { if (pstack->head == NULL) return TRUE; else return FALSE; } 스택이 비어있는지 확인하는 함수 (head가 NULL 이면 True 반환 아니면 False 반환) void SPush(Stack* pstack, Data data) { Node* newNode = (Node*)malloc(sizeo..

스택이란 가장 먼저 들어간 것이 나중에 나오는 특성을 가진 자료구조를 말한다. 다음 그림처럼 가장 나중에 들어간 Data 가 나올 때는 가장 먼저 나온다. 이러한 구조를 Last In First Out(LIFO) 또는 First In Last Out(FILO) 라 한다. 스택의 ADT는 다음과 같은 연산들을 정의한다. - 자료를 삽입하는 push - 가장 마지막에 삽입된 자료를 꺼내는 pop - 가장 마지막에 삽입된 자료를 조회하는 peek - 스택이 비어 있는지 확인하는 empty - 스택 내 자료의 수를 확인하는 size 여기서 스택은 배열 또는 연결리스트로 구현할 수 있다. 먼저 배열로 구현해보면 다음과 같은 헤더파일과 실행파일을 통해 스택을 구현할 수 있다. 코드 부분설명▼ void StackIn..

앞서 우리가 구현한 연결 리스트의 마지막 노드는 NULL 을 가리켰다. 바로 이 마지막 노드가 첫 번째 노드를 가리키게 하면 이것이 바로 원형 연결리스트가 된다. 위 사진처럼 노드를 머리에 추가하나 꼬리에 추가하나 두 연결리스트 모두 8→1→2 형태로 가리키기 때문에 원형 연결리스트에서는 머리와 꼬리의 구분이 없다고도 볼 수 있다. 위의 그림상에서 꼬리에 노드를 추가하려면 head를 시작으로 리스트의 끝을 찾아가는 과정을 거쳐야만 한다. 하지만 여기서 tail 이라는 포인터 변수를 노드 끝을 가리키도록 하면 새로운 노드를 추가하기에 어려움이 없다. tail 이라는 포인터 변수는 꼬리를 가리키고 tail → next 는 리스트에서 머리를 가리키게 된다. 다음 그림의 왼쪽 편은 새로운 노드가 생성되었지만 아..

이는 0 이하의 값이 입력될 때까지 입력이 계속되는 간단한 예제이다. 다음과 같은 형태로 자연수를 입력으로 받고 0이하의 값이 입력되면 while 문을 빠져나와 배열을 출력한다. 하지만 이처럼 배열은 메모리의 특성이 정적이여서 메모리의 길이를 변경하는 것이 불가능하다. 위 예제를 실행한 후 0 이하의 값을 입력하지 않고 계속 입력하면 할당된 배열의 크기인 10을 넘어가는 문제가 발생한다. 이 문제를 해결하기 위해 정적인 배열이 아닌 동적으로 메모리를 구성하여 다음과 같은 연결리스트를 구성할 수 있다. ▼코드 설명 1. 노드 형태 구현 여기서 data는 데이터를 담을 공간이며 struct _node *next 는 아래 그림처럼 노드의 연결을 위한 포인터이다. head는 연결 리스트에서 머리를 가리키는 포인..

리스트는 구현방법에 따라 순차 리스트, 연결 리스트로 나눌 수 있다. ▶순차리스트 - 배열을 기반으로 구현된 리스트 ▶연결리스트 - 메모리의 동적 할당을 기반으로 구현된 리스트 또한 리스트 자료구조는 데이터를 나란히 저장하며 중복된 데이터의 저장을 막지 않는다. 그리하여 리스트를 활용하는 예를 코드로 살펴보면 다음과 같다. 코드 부분 설명 ▼ 다음 코드에서는 먼저 리스트를 생성 및 초기화한 후 11, 11, 22, 22, 33 라는 값을 저장한다. 그리고 LCount 함수를 통해 현재 리스트 안에 있는 데이터의 수를 출력하고 LFirst 함수로 첫 번째 데이터를 조회한 후 while 문을 통해 다음으로 넘어가면서 데이터를 출력한다. LFirst 함수를 통해 첫 번째 데이터부터 조회하는데 22 라는 값을 ..

1. 피보나치 수열로 재귀함수 알아보기 피보나치 수열 : 재귀적인 형태를 띠는 대표적인 수열 코드 #include int fibo(int n) { if (n == 1) return 0; else if (n == 2) return 1; return fibo(n - 1) + fibo(n - 2); } int main() { for (int i = 1; i B), 맨 아래 원반을 C로 옮기는 상황(A->C), 그리고 나머지 원반 2개를 C로 옮기는 상황(B->C) 총 3개로 볼 수 있으며 A->C 를 제외한 두 개의 상황은 각각 3개의 상황으로 나눌 수 있다. 이를 코드로 표현하면 다음과 같다. 코드 실행결과

▶이진 탐색 알고리즘을 적용하기 위한 조건 : 배열에 저장된 데이터는 정렬되어 있어야 한다. 다음과 같이 정렬된 상태로 데이터가 저장되어 있다고 가정할 때 이 배열에 숫자 3이 저장되어 있는지 확인하기 위하여 이진탐색 알고리즘을 적용해보자. 더보기 ▶ 이진 탐색 알고리즘의 첫 번째 시도: 1. 배열 인덱스의 시작과 끝은 각각 0과 8이다. 2. 0과 8을 합하여 그 결과를 2로 나눈다. 3. 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인한다. 첫 번째 시도 결과 arr[4]에 3이 저장되지 않았음을 확인하였다. 더보기 ▶ 이진 탐색 알고리즘의 두 번째 시도: 1. arr[4]에 저장된 값 9와 탐색 대상인 3의 대소를 비교한다. 2. 대소의 비교결과는 arr[4]..

자료구조 - '데이터의 저장' 을 담당하는 것 알고리즘 - 저장된 데이터를 대상으로 하는 '문제의 해결 방법' 시간 복잡도 - 알고리즘의 수행시간 분석결과 공간 복잡도 - 메모리 사용량에 대한 분석결과 메모리를 적게 쓰고 속도도 빨라야 최적의 알고리즘 하지만 일반적으로 알고리즘을 평가할 때는 메모리의 사용량보다 실행속도에 초점을 둔다.

메모리의 구조 프로그램이 실행되기 위해서는 먼저 프로그램이 메모리에 로드(load)되어야 합니다. 또한, 프로그램에서 사용되는 변수들을 저장할 메모리도 필요합니다. 따라서 컴퓨터의 운영체제는 프로그램의 실행을 위해 다양한 메모리 공간을 제공하고 있습니다. 프로그램이 운영체제로부터 할당받는 대표적인 메모리 공간은 다음과 같습니다. 1. 코드(code) 영역 2. 데이터(data) 영역 3. 스택(stack) 영역 4. 힙(heap) 영역 다음 그림은 운영체제가 제공하는 메모리 공간을 표현하고 있습니다. 코드(code) 영역 메모리의 코드(code) 영역은 실행할 프로그램의 코드가 저장되는 영역으로 텍스트(code) 영역이라고도 부릅니다. CPU는 코드 영역에 저장된 명령어를 하나씩 가져가서 처리하게 됩니다..