본문 바로가기

자료구조12

간단한 미로찾기 알고리즘(깊이탐색알고리즘, DFS) 깊이우선탐색(DFS) 알고리즘이란? 현재 위치와 붙어있는 간선들을 하나씩 검사하다가 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 따라 간다. 이걸 반복하면서 더 이상 갈 곳이 없다면 마지막에 따라왔던 간선을 따라 뒤로 돌아가면서 탐색이 이루어 진다. 쉽게 말해서 1~10번 우물을 파야한다면 1번부터 끝까지 다 파보고 2번으로 넘어가는 방법이라고 볼 수 있다. DFS를 이용해서 간단하게 미로찾기를 구현해보았다. #include int map[11][11]={ 1,1,1,1,1,1,1,1,1,1,1, 1,0,0,0,0,0,0,0,0,0,1, 1,0,0,1,1,1,1,1,1,0,1, 1,1,0,1,1,1,1,1,1,0,1, 1,1,0,1,1,1,1,1,1,0,1, 1,1,0,0,1,1,0,0,.. 2018. 4. 19.
c언어 퀵정렬 함수 퀵정렬(quick sort)의 시간복잡도는 nlogn으로 동작 원리는 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법이다. c언어로 구현하면 다음과 같다. void Swap(int arr[], int idx1, int idx2){int temp=arr[idx1];arr[idx1]=arr[idx2];arr[idx2]=temp;} int Partition(int arr[], int left, int right){int pivot = arr[left];int low = left+1;int high = right; while(low = arr[low] && low 2018. 4. 19.
c언어 병합정렬 함수 병합정렬의 시간복잡도는 O(nlogn)이고 말 그대로 병합(합병)하면서 정렬이 된다. 합병 정렬은 다음과 같이 작동한다.리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. c언어로 구현하면 다음과 같다. void MergeTwoArea(int arr[], int left, int mid, int right){int fIdx = left;int rIdx = mid+1; int * sortArr = (int *)malloc(sizeof(int)*(right+1));int sIdx = left;.. 2018. 4. 19.
c언어 삽입정렬 함수 삽입정렬(Insert Sort)이란 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식이다삽입정렬의 시간복잡도는 O(n^2)이다. c언어로 구현하면 다음과 같다. void InsertSort(int arr[], int n){int insData;for(int i=1;i=0;j--){if(arr[j]>insData)arr[j+1]=arr[j];elsebreak;}arr[j+1]=insData;}} 2018. 4. 19.

티스토리툴바