여러가지 검색의 종류 검색이란 컴퓨터를 이용해서 기억공간에 보관중인 특정 레코드를 찾아내는 작업이다. 선형 검색(Linear Search) 1. 선형 검색은 순서화되어 있지 않은 파일에서 순차적으로 검색하는 방식으로 찾고자 하는 Key값을 첫번째 레코드 Key값으로부터 차례로 비교하여 검색하는 방식이다. 2. 순차검색(Sequential Search)라고도 한다. 3. 프로그램 작성이 비교적 간단하다. 제어 검색(Control Search) 1. 제어 검색은 반드시 순서화된 파일이어야 검색할 수 있다. 2. 한번의 비교 동작이 끝난 후 비교 대상이 된 레코드를 다음에 비교할 대상을 선택하는 기준으로 이용하여 검색하는 방식이다. 이분 검색(이진 검색, Binary Search) 1. 이분검색은 전체 파일을..
트리(Tree)의 정의 트리는 정점(Node)과 선분(Branch)을 이용하여 사이클을 이루지 않도록 구성한 Graph의 특수한 형태이다. 가족의 계보(족보), 연산수식, 회사 조직 구조도, 히프등을 표현하기에 적합하다. 트리(Tree) 관련용어 노드(Node) : 트리의 기본요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것 EX : A, B, C, D, E, F, G, H, ,I ,J ,K ,M 근 노드(Root Node) : 트리의 맨 위에 있는 노드 EX : A 디그리(Degree, 차수) : 각 노드에서 뻗어나온 가지의 수 EX : A=3 , B=2, C=1 단말 노드(Terminal Node) : 자식이 하나도 없는 노드 EX : K, L, F, G, M, I, J 비단말 노..
큐(Queue) 1. 선형 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조이다. 2. 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO)방식으로 처리한다. 3. 시작과 끝을 표시하는 두 개의 포인터가 있다. 프런트(F) 포인터 1. 가장 먼저 삽이된 자료의 기억공간을 가리키는 포인터이다. 2. 삭제 작업을 할때 사용한다. 리어(R) 포인터 1. 가장 마지막에 삽입된 자료가 위치한 기억장소를 가리키는 포인터이다. 2. 삽입 작업을 할 때 사용한다. Queue의 응용분야 1. 창구 업무나 택시 정거장처럼 서비스 순서를 기다리는 등의 대기행렬의 처리에서 사용한다. 2. 운영체제의 작업 스케줄링에 사용한다. 데크(Deque) 1. 삽입과 삭제가 ..
스택의 개념 1. 스택은 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조이다. 2. 스택은 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO)방식으로 자료를 처리한다. Overflow : 스택으로 할당받은 메모리 부분의 마지막 주소가 M번지라고 할 때, Top Pointer의 값이 M보다 커지면 스택의 모든 기억장소가 꽉 채워져 있는 상태이므로 더 이상 자료를 삽입할 수 없어 Overflow를 발생시킨다. Underflow : Top Pointer가 주소 0을 가지고 있다면 스택에는 삭제할 자료가 없으므로 Underflow를 발생시킨다. ※ Stack에 기억되어 있는 자료를 삭제시킬 때는 제일 먼저 삭제할 자료가 있는지 없는지부터 확인해야 한다. Stack의 응용분야 ..
ArrayList(선형리스트) 선형 리스트는 배열과 같이 연속되는 기억장소에 저장되는 리스트를 말한다. 연접 리스트(Dense List) 또는 축차 구조(Sequential Structure)라고도 한다. 선형리스트의 특징 1. 가장 간단한 자료구조이다. 2. 접근속도가 빠르다. 3. 중간에 자료를 삽입하기 위해서는 연속된 빈 공간이 있어야 한다. 4. 기억장소를 연속적으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1로서 가장 좋다. 5. 자료의 개수가 n개일 때 삽입 시의 평균 이동 횟수는 (n+1)/2이고, 삭제 시에는 (n-1)/2이다. 6. 삽입, 삭제 시 자료의 이동이 필요하기 때문에 작업이 번거롭다. LinkedList(연결리스트) 연결 리스트는 자료들을 반드시 연속적으로 배열시키지는 않고..
자료구조의 정의 효율적인 프로그램을 작성할 때 가장 우선적인 고려사항은 저장공간의 효율성과 실행시간의 신속성이다. 자료구조는 프로그램에서 사용하기 위한 자료를 기억장치의 공간내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의 관계, 처리방법 등을 연구하여 분석하는 것을 말한다. 자료구조란? 1. 자료구조는 자료의 표현과 그것과 관련된 연산이다. 2. 자료구조는 일련의 자료들을 조직하고 구조화하는 것이다. 3. 어떠한 자료구조에서도 필요한 모든 연산들을 처리하는 것이 가능하다. 4. 자료구조에 따라 프로그램 실행시간이 달라진다. 자료구조의 분류 자료 구조의 이용 정렬(Sort) : 기억장치 내의 자료를 일정한 순서에 의해 나열하는 것 검색(Search) : 기억장치 내의 자료를 찾는 것 파일 편성 ..
정렬 속도 비교 이때까지 포스팅했던 정렬들의 시간복잡도에 대해 알아보도록 하겠습니다. 아래는 정렬속도 비교에 사용하였던 코드입니다. 정렬속도 비교 프로그램 (C언어/C++) 출처 #include #include #include #define MAX_SIZE 60000 //데이터의 개수 지정 #define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t)) //SWAP함수 설정 int original[MAX_SIZE]; //랜덤함수로 만든 데이터를 저장할 원본 배열 int list[MAX_SIZE]; //각 정렬 알고리즘에서 사용할 데이터 배열 int n; //데이터의 개수를 받는 전역변수 설정 int sorted[MAX_SIZE]; //합병정렬에서 사용할 데이터를 저장할 배열 cloc..
계속해서 o(n log n) 시간복잡도를 가지는 정렬방법에 대해 알아보겠습니다. 이번에는 퀵정렬입니다. 실무에서도 가장 많이쓰이고 속도와 효율성이 가장 좋다고도 할수있는 정렬 방식입니다. 퀵정렬 이번에도 그림을 통해 설명해드리겠습니다. ☞ 먼저 PVIOT을 정합니다. 대부분 정렬속도를 위하여 가운데 숫자를 PIVOT으로 정하는게 효율적입니다. ☞ PVIOT값과 LEFT값을 비교하여 LEFT값이 PIVOT보다 크다면 PIVOT값과 RIGHT값을 비교합니다. RIGHT값이 PIVOT보다 크다면 RIGHT커서를 왼쪽으로 이동시킨후 다시 PIVOT값과 비교합니다. ☞ RIGHT값이 PIVOT보다 작다면 LEFT값과 RIGHT값을 바꿉니다. 그런뒤 LEFT값을 오른쪽으로 한칸 옮깁니다. ☞ LEFT값과 RIGHT..
앞선 포스팅 3개에서 버블정렬, 삽입정렬, 선택정렬에 대해서 알아보았습니다. 하지만 위의 3정렬방법은 굉장히 기초적인 정렬방법으로 시간복잡도는 O(N^2)를가지며 실무에서 잘 쓰이는 정렬방법은 아닙니다. 이번 포스팅부터는 시간복잡도 O(N * LogN)을 가지는 정렬방법에 대해 알아보겠습니다. 먼저 이번포스팅에서는 병합정렬에 대해 알려드리겠습니다. 병합정렬은 정렬할 배열을 반으로 나누어 좌측과 우측 배열을 계속하여 분할해 나간 후 각 배열내에서 정렬 후 병합하는 과정을 통해 정렬하는 알고리즘입니다. 병합정렬(합병정렬) 그림을 통해 설명해드리겠습니다. ①분할과정 먼저 정렬할 숫자들을 원소단위로 분할합니다. ②병합과정 그런 뒤 분할한 원소들을 합치면서 정렬합니다. 병합정렬 소스 코드 (C언어/C++) #in..
정렬에는 버블정렬, 선택정렬, 삽입정렬이 있습니다. 앞서 버블정렬, 선택정렬은 포스팅을 끝냈고 이번 포스팅은 마지막 정렬방법인 삽입정렬에 대해 한번 알아보도록 하겠습니다. 삽입정렬 삽입정렬은 기준이 되는 숫자와 그 앞에있는 숫자를 비교하여 조건에 맞게 정렬을 하는 방법입니다. 0번째 인덱스는 앞쪽에있는 숫자가 없기 때문에 정렬의 시작은 1번째 인덱스로 시작을 합니다. 삽입정렬로 배열 문자(알파벳)값 아스키순서로 차례대로 정렬하기 (C언어/C++) #define num 7 char number[num] = {'C','A','D','G','F','E','B'}; for (int i = 1; i < num; i++) { int target = number[i]; // 기준 int cur = i - 1; // ..
저번 포스팅에서는 버블 정렬에 대해 알아보았는데요 이번 포스팅에서는 선택 정렬에 대해 한번 포스팅해보려 합니다. 버블 정렬이 뒤에서부터 차례대로 정렬하는 방법이라면 선택 정렬은 버블 정렬과는 반대로 앞에서부터 차례대로 정렬하는 방법입니다. 예제는 배열에 있는 정수 값을 내림차순으로 정렬하는 방법을 들고 왔습니다. 오름차순으로 바꾸려면 예제 문의 IF문의 부등호를 반대로 바꿔주시면 간단하게 구현 가능합니다. 선택 정렬 선택 정렬은 배열 내의 기준이 되는 수(A[0]) 와 나머지의 수를 비교하여 오름차순일 경우 낮은 수, 내림차순일 경우 높은 수를 앞으로 보내는 방식입니다. 첫 번째 FOR문 위와같은 방법으로 첫번째 for문에서 기준값 [0]번째 Index의값과 나머지 값을 비교하여 가장 낮은수를 앞으로 보..
정렬(Sort)하는 방법을 포스팅합니다. 정렬하는 방법은 대표적으로 버블정렬,선택정렬,삽입정렬 이렇게 3가지가 있습니다. 차례대로 한번 알아보도록 하죠 먼저 이번 포스팅에서는 버블정렬에 대해 포스팅하도록 하겠습니다. 예제는 배열에 있는 정수값을 오름차순으로 정렬하는 예제를 들고왔습니다. 내림차순으로 정렬하실경우 예제의 IF문의 부등호방향만 바꿔주시면 됩니다. 버블정렬 버블정렬은 배열내의 두개의 인접한 Index를 비교하여 더 큰 숫자를 뒤로 보내 차곡차곡 쌓아 정렬하는 방법입니다. 결론적으로 말하자면 배열의 뒷쪽부터 정렬하는 방법이라고 생각하시면 될 듯 합니다. ① for문에서 [0]번째 Index와 [1]번째의 Index값을 비교하여 더 큰 숫자를 뒤로 보내줍니다. ② for문에서도 마찬가지로 [1]번..