본문 바로가기

알고리즘11

c언어로 짠 띄어쓰기 기준으로 문자열 순서만 뒤집기 문자열의 순서를 뒤집어서 쓰되 문자열 개개는 순서를 유지하는 코드이다.예를 들어 문자열 "I am zeta "를 "zeta am I" 뒤집는 코드이다.쉽게 생각해서 띄어쓰기(스페이스 바) 기준으로 순서만 뒤집어보자. 코드는 다음과 같다. #include int main(void){char * str = "I am zeta"; char str2[100];int space=0;int len=0; while(str[len] != '\0'){ if(str[len] == ' ')space++;len++;}str2[len]='\0'; int k=0;int gan=0;int t=0;for(int i=len-1;i>=0;i--){gan++;if(str[i] == ' '){t=i+1;for(int j=0;j 2018. 4. 20.
간단한 미로찾기 알고리즘(깊이탐색알고리즘, 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.

티스토리툴바