1. 스택 - 선입 후출 구조 - 맨 처음에 들어간 원소를 top라고 지정한다. 1) 배열 ⓐ 구조체 선언 #define SIZE 1000 typedef struct { int key; // 다른필드 }element; element stack[SIZE]; ⓑ push int top = 0; void push(int* top_ptr, element item) { if (*top_ptr >= SIZE) { printf("스택이 다 찼습니다."); } stack[(*top_ptr)++] = item; } ⓒ pop void pop(int* top_ptr) { if (*top_ptr == 0) { printf("스택이 비어있습니다."); } stack[(*top_ptr)--]; } * push와 pop 모두 매..
자료구조
1. 연결 리스트 1) 정의 : 자료가 순서를 가지고 나열된 자료구조를 이야기 한다. 2) 리스트의 표현 ⓐ 배열 이용 - 이 방식은 리스트의 각 원소마다 배열의 원소에 대응시킨다. - A[k]를 읽거나 교체하는 연산은 상수시간이 걸리지만, 삽입과 삭제 연산은 순차매핑을 유지하기 위해 원소의 이동을 필요로 하므로 많은 시간이 소요된다. * 순차 매핑 : 배열이 메모리의 연속적인 공간을 차지함 ⓑ 연결 리스트 이용 - 연결 리스트란 화살표로 표시되는 링크를 가진 노드의 순서 리스트 이다. - 첫번째 노드를 가르키는 포인터의 이름이 연결 리스트의 이름이다. * 연결리스트의 노드들은 메모리에 순차적으로 놓여있지 않을 수 있다. 🟡 포인터를 이용하여 연결 리스트 표현하기 - 하나의 노드는 데이터를 갖고있는 데이..
1. 퀵 정렬(분할정복법) 1) 과정 - 리스트에 원소 하나를 고른다(피벗) - 피벗과 다른 n-1개 원소 각각을 비교하여, 피벗보다 작은 것과 큰 것으로 분할한다. - 분할된 두 개의 작은 리스트를 재귀적으로 정렬한다. 2) 피벗 선택방법 - 중앙값(최선 피벗) - 랜덤선택 - 리스트 맨앞, 중간, 맨뒤에 있는 세 원소의 중앙값을 선택 3) 코드 void Quick_sort(int arr[],int i, int j) { int n, cnt = 0; if (i >= j) return; int pivot = arr[(i + j) / 2]; int left = i; int right = j; while (left pivot) right--; if (left
1. 정렬 알고리즘 - 정렬알고리즘은 알고리즘 중에 가장 기본적인 알고리즘 이다. - 이 글에서 살펴볼 알고리즘은 삽입, 선택, 거품(버블), 퀵, 합병(merge), 힙, 이진탐색 트리를 이용한 정렬이다. 1) 삽입정렬 - O(n^2) - 배열의 모든 원소를 앞에서부터 차례대로 배열 부분과 비교하여, 삽입함으로써 정렬하는 알고리즘 - 처음 key 값(처음으로 뽑아 비교할 원소)은 두번째 원소이다 > 과정 두번째 원소 10을 뽑아 첫번째 원소와 비교하여 29보다 작으므로 29왼쪽으로 삽입된다. 세번째 원소 14를 뽑아 두번째 원소와 비교하여 29보다 작으므로 29왼쪽으로 삽입된다. 14는 10보다 크므로 바뀌지 않는다. 네번째 원소 37를 뽑아 세번째 원소인 29와 비교한다. 37이 29보다 크므로 바뀌..
1. 문제 * 길이가 n인 배열 A[0], A[1], ..., A[n-1] 이 입력으로 주어 질때, i번째부터 j번째까지 원소드로 이루어진 배열 A[i], ..., A[j] 를 부분배열이라고 하고, A[i, j] 로 나타낸다. - 부분 배열의 속한 원소들의 합이 최대가 되는 부분 배열을 구하는 것이 이 문제의 목적이다. 이 때 길이가 0인 부분배열도 허용하며, 이 부분배열의 원소들의 합은 0이라고 정의한다. 예를 들어, 아래와 같은 배열이 있다면, -2 -1 3 5 2 -5 0 2 이 배열의 최대부분배열의 합은 몇일까? 3+5+2 = 10 이다. 2. 해결방법 - 최대부분배열의 원소합을 구하는 알고리즘에는 크게 4개가 있다. - 완전탐색, 중복제거한 탐색, 분할정복법, 동적계획법 1) 완전탐색(브루트포스..
