Now or Never

Goal - 이진검색의 이해 - 이진검색 알고리즘 C언어 및 Java언어로 구현 - 정렬의 이해 및 시간복잡도 비교 1. 이진검색과 정렬 1-1 이진검색 (Binary Search) - 제어 검색의 일종인 이진 검색은 반드시 순서화된 파일이어야 검색할 수 있다. - 찾고자하는 값을 파일의 중간 값과 비교하며 검색함 - 반쪽을 찾아보고 없으면, 크기 비교를 통해 왼쪽 또는 오른쪽으로 방향을 설정하고 나머지 반쪽에서 찾아가면서 범위를 점점 반씩으로 줄여가는 방법 - 배열의 첫 값을 보통 First 마지막 값은 Last 중간값은 Middle이라고 함. 예제1) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15와 같이 레코드가 구성되어 있을 때, 이진 검색 방법으로 14를 찾는 경우 비교되는 횟수..

1. 삽입 정렬 (Insertion sort) - 오름차순을 기준으로 정렬 - 알고리즘 해석 -> 두 번째 자료부터 시작하여 key변수에 저장하고, 그 앞(왼쪽)의 자료들과 비교하여 비교대상 값이 key 값보다 크면, key변수에 더 큰값을 삽입하고, 첫 번째 자료의 위치까지 계속해서 큰값을 찾는 작업을 수행 후, 더이상 큰 값이 없거나, 인덱스가 0이 되면 반복을 마친 후 종료된 시점의 위치에 key값을 옮겨 정렬하는 알고리즘 - 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다. - 처음 key 값은 두 번째 자료부터 시작. 1) C언어..

Goal - 버블정렬 이해 - 버블정렬 알고리즘 C언어 및 Java언어로 구현 - 버블정렬의 특징 및 시간복잡도 1. 버블정렬 (bubble sort) - 각 회전마다 첫 번째 값을 시작으로 양옆 값을 비교후 교환 하여 자료내 가장 큰 값을 맨 뒤로 밀어냄. - 회전의 수행으로 가장 큰 값이 뒤에서부터 채워지기 때문에, 각 회전에서의 교환 작업은 이전 회전의 교환 작업수 -1. - 총 자료의 수(n) - 1번 회전 수행. 사진 1) 버블정렬 실행 방식 1) C로 구현 void bubbleSort(int data[], int n){ for (int i = n-1; i > 0; i--){ for (int j = 0; j data[j + 1]){ int tmp =..

1. 시간복잡도(time complexity)란? - 알고리즘의 자원(resource) 사용량을 분석 - 자원이란 실행 시간, 메모리, 저장장치, 통신 등 1-1 실행시간 - 실행시간은 실행환경에 따라 달라짐 ex) 하드웨어, 운영체제, 언어, 컴파일러 등 - 실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트 (같은 조건에서 연산의 실행 횟수를 본다는 의미) - 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현 (ex O(n)) - 데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐 - worst-case analysis 최악의 경우 시간 복잡도, average-case analysis 평균 시간복잡도 1-2 점근적(Asymptotic) 분석 - 점근적 표기법을 사용 : 데이터의 개수가 n..