Study12 [알고리즘] 검색(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. [자료구조] 그래프(Graph) - 인접 행렬(Adjacent Matrix), 인접 리스트(Adjacent List), 깊이 우선 탐색(Depth First Search: DFS), 너비 우선 탐색(Breadth First Search: BFS) 선형 리스트란? [자료구조] 선형 리스트 (Linear List) ● 선형 리스트 (Linear List) - 데이터를 논리적인 순서대로 메모리에 연속하여 저장하는 구현하는 방식 - 데이터의 논리적인 순서와 기억 장소에 저장되는 물리적 순서가 일치하는 구조다. - 배열 toward-the-future.tistory.com 연결 리스트란? [자료구조] 연결 리스트 (Linked List) ● 연결 리스트 (Linked List) - 각 데이터에 저장되어 있는 다음 데이터의 주소에 의해 연결되는 방식 - 데이터의 물리적인 순서와 상관없이 포인터를 사용하여 논리적인 순서대로 연결하는 구조다 toward-the-future.tistory.com 스택이란? [자료구조] 스택(Stack) 선형 리스트란? [자료구조.. 2021. 7. 5. 이전 1 2 3 다음
