Study/Algorithm3 [알고리즘] 검색(Search) - 선형 검색(Linear Search), 이진 검색(Binary Search), 해시법(Hashing) ● 검색 (Search) - 컴퓨터에 저장한 데이터 중에서 원하는 항목을 찾는 작업 ● 선형 검색 (Linear Search) - 선형으로 늘어선 데이터 집합(선형 구조)에서 맨 앞 부터 스캔하여 키값을 찾을 때까지 순서대로 검색하는 방식 - 데이터의 정렬 여부와 상관없이 동작한다. - 데이터의 양이 많아지면 검색에 소요되는 시간이 비례하여 많아진다. ● 이진 검색 (Binary Search) - 데이터의 가운데에 있는 항목을 키값과 비교하여 다음 검색 위치를 결정하여 검색을 계속하는 방식 - 검색 범위를 반으로 줄여 가면서 빠르게 검색한다. - 정렬되어 있는 데이터를 검색할 때만 사용할 수 있다. ① 키값이 더 크면 오른쪽 부분을 검색한다. ② 키값이 더 작으면 왼쪽 부분을 검색한다. ● 해시법 (Ha.. 2021. 7. 8. [알고리즘] 정렬(Sort) - 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 버블 정렬(Bubble Sort), 퀵 정렬(Quick Sort), 셸 정렬(Shell Sort), 병합 정렬(Merge Sort), 기수 정렬(Radix Sort), 힙 정렬(Heap Sort) ● 정렬 (Sort) - 순서 없이 배열된 자료를 오름차순 혹은 내림차순으로 재배열하는 것이다. ● 버블 정렬 (Bubble Sort) - 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식 ● 선택 정렬 (Selection Sort) - 전체 원소 중에서 기준 위치에 맞는 원소를 선택해 자리를 교환하는 방식 ① 아직 정렬하지 않은 부분에서 가장 작은 키의 값을 선택한다. ② 선택된 가장 작은 키 값을 정렬하지 않은 부분의 첫 번째 요소와 교한한다. ● 삽입 정렬 (Insertion Sort) - 정렬되어 있는 부분집합에 새로운 원소의 위치를 찾아서 삽입하는 방식 ① 정렬되지 않은 부분의 맨 앞 원소를 선택한다. ② 선택한 원소를 정렬된 부분의 원소들과 비교하여 적절한 위치를 찾는다. ③ 찾은 위치부터.. 2021. 7. 6. [알고리즘] 알고리즘(Algorithm)이란? - 공간복잡도(Space Complexity) 시간복잡도(Time Complexity), 빅오 표기법(Big-O Notation), 빅오메가 표기법(Big-Omega Notation), 빅쎄타 표기법(Big-Theta Notation) ● 문제 (Problem) - 해답을 찾으려고 물어보는 질문 ● 알고리즘 (Algorithm) - 어떠한 문제를 해결하기 위해 정해 놓은 일련의 절차 ○ 알고리즘의 조건 - 입력 : 알고리즘을 수행하는데 필요한 데이터가 외부에서 입력되어야 한다. - 출력 : 알고리즘 수행 후 하나 이상의 결과를 출력해야 한다. - 명확성 : 수행할 작업의 내용과 순서를 나타내는 알고리즘의 명령어는 명확하게 명세되어야 한다. - 유한성 : 알고리즘은 수행 뒤에 반드시 종료되어야 한다. - 효과성 : 알고리즘의 모든 명령어들은 기본적이며 실행이 가능해야한다. ○ 알고리즘의 순서 - 문제정의 → 알고리즘 설명 → 정확성 증명 → 성능 분석 - 문제정의(Problem Definition) : 해결하고자 하는 문제를 컴퓨터를 이.. 2021. 7. 6. 이전 1 다음
