Computer Science/Algorithms3 Sorting I - Insertion Sort 정렬된 데이터는 정렬되지 않은 데이터에 비해 여러가지 장점이 있다. 탐색도 정렬되지 않은 데이터는 O(n), 정렬된 데이터는 O(logn)으로 정렬된 데이터가 훨씬 빠르다. 이 외에도 여러 장점 때문에 데이터를 정렬할 필요가 있다. 정렬 방식에 어떤 것들이 있고, 복잡도는 어떤지 하나씩 알아보자. Insertion Sort 삽입 정렬은 element 하나씩 적절한 위치로 삽입하며 정렬하는 알고리즘이다. Example 위와 같은 정수 배열을 삽입 정렬을 통해 오름차순으로 정렬해보자. 먼저 첫번째 element는 정렬이 되어있다고 가정한다. 다음으로 정렬되지 않은 element, 2를 올바른 위치에 삽입해준다. 배열의 맨 앞에 오거나(index=0) 앞의 element보다 key 값이 클 때까지(E[cur-.. 2021. 4. 15. Searching - Sequential Search, Binary Search 배열에서 원하는 값을 찾는 탐색 방법은 여러가지가 있다. 배열 안의 데이터가 정렬되어 있는지, 아닌지에 따라 많은 시간 차이가 발생하기도 한다. 어떤 탐색 방법들이 있고, 각각의 상황에 어떤 방법이 적합한지 분석해보자. Sequential Search 가장 단순히 생각할 수 있는 방법인 순차 탐색 알고리즘이다. 순차 탐색은 말 그대로 목표한 값을 찾을 때까지 배열 안의 모든 데이터를 순차적으로 비교하는 방법이다. int seqSearch(int* E, int n, int K) { int ans = -1; for (int i = 0; i 6 찾고자 하는 값이 더 작기 때문에 가운데 값 7의 왼쪽까지로 구역을 좁혀 다시 반복한다. 다음 중간값은 2로 찾고자 하는 값 6이 더 크기 때문에 중간값 2의 오른쪽까.. 2021. 4. 14. Algorithm Analysis - Correctness, Complexity, Optimality 컴퓨터 알고리즘이란 문제를 해결하기 위해 정의한 Instruction Sequence를 말한다. 알고리즘을 작성했다면 알고리즘이 문제의 요구조건을 만족하는지(Correctness), 얼마나 많은 연산이 필요한지(Complexity), 문제의 복잡도와 얼마나 가까운지(Optimality) 분석해야 한다. 그럼 이제 알고리즘을 세워보고 어떻게 분석하는지 알아보자. Algorithm n개의 entry를 갖는 non-ordered array E에서 index 값이 K인 entry를 찾는 문제를 해결해보자. int seqSearch(int* E, int n, int K) { int ans, index; ans = -1; for (index = 0; index < n; i++) { if (K == E[index]).. 2021. 4. 10. 이전 1 다음
