이진탐색2 [알고리즘] Divide & Conquer (1) - Binary search [1. Binary search, 이진탐색] ● 방식 → A를 오름차순으로 정렬된 n개 요소들의 리스트라고 할 때, → 찾으려는 값 x가 A내에 몇 번째에 존재하는지 확인하는 알고리즘이다. → x를 A내의 요소들의 중앙값(A[m])과 비교하여 → x = A[m]이면 m을 반환, → x A[m]이면 다시 x를 A[m+1 ~ e]에서 탐색하는 방식이다. (* A내에 n개의 원소가 있다면 s=0, e=n-1) ● 알고리즘 → Divide : m = (s+e)/2를 기준으로 배열을 분할 → Conquer : A[s, m-1] 또는 A[m+1, e] → Degenerate case : A 또는 분할된 A 내에 원소가 하나인 경우 (s==e) ● .. 2022. 11. 5. [자료구조] 리스트&배열 1. 리스트 • 리스트의 개념 - 유한한 원소들을 한 줄로 나열한 구조 - 각 원소들은 인덱스에 대응됨 • 리스트의 구분 - 정렬되지 않은 리스트 : 위치 예측 불가능, 추가연산에 유리 - 정렬된 리스트 : 위치 예측 가능, 검색 연산에 유리 ⇒ 더 효율적 • 리스트의 종류 - 원소를 저장 : 배열, 연결 리스트 - 원소와 순서를 저장 : 스택, 큐 2. 배열 • 배열의 개념 - 인덱스를 활용하여 리스트를 구현한 구조 (배열의 모든 요소들은 인덱스에 대응됨) - 연속적으로 할당된 공간 (최소한 배열의 크기만큼 연속된 공간이 있을 때 사용 가능) - 하나의 주소로 n개의 자료에 접근 가능함 (첫 번째 원소인 A의 위치 0014를 알면, 연속된 공간을 사용하는 배열의 특성에 의해 그 다음 원소들의 위치 00.. 2022. 10. 9. 이전 1 다음
