Information of IT

개 념해시 함수를 이용하여 키 값을 버킷의 슬롯에 배열시켜 빠르게 탐색하는 알고리즘 I. 해시 탐색 (Hash Search)의 개요 가. 해시 탐색 (Hash Search)의 정의 - 해시 함수를 이용하여 키 값을 버킷의 슬롯에 배열시켜 빠르게 탐색하는 알고리즘 ※ 해시테이블(hash table) : 키 값을 저장하는 테이블 버킷(bucket) : 해시될 키 값의 범위, 테이블의 크기 슬롯(slot) : 한 개의 버킷에 저장될 키 값의 개수 나. 해시 탐색 (Hash Search)의 특징 - 고정길이, One Way- O(1)의 탐색 속도- 충돌처리 매커니즘 필요   Ⅱ. 해시 함수의 기법 가. 해시 함수의 기법 구 분내 용mid-square식별자의 제곱 값의 가운데 값을 취함.division나머지 연산..

합 병 정렬 (Merge Sort)리스트를 두 개로 나누어, 각각을 정렬한 다음, 다시 하나로 합치는 정렬 방법  I. 합병 정렬 (Merge Sort)의 개요  가. 합병 정렬의 정의- 리스트를 두 개로 나누어, 각각을 정렬한 다음, 다시 하나로 합치는 정렬 방법  나. 합병 정렬의 특징 - 분할과 정복 : 분할(Divide) -> 정복(Conquer) -> 결합(Combine) 과정 수행- 재귀적 수행 : 분할을 마친 후 분할된 부분의 반복적 수행- 정렬을 위한 별도의 공간이 필요- 수행시간 복잡도: O(n·log2n)  Ⅱ. 합병 정렬의 단계 및 사례 가. 합병 정렬의 단계  나. 합병 정렬 개념 void mergeSort(int arr[], int l, int r){ if (l { int m =..

개념정렬된 데이터 집합에서 탐색 범위를 1/2씩 줄여 나가면서 수행하는 방식 I. 이진 탐색 (Binary Search)의 개요 가. 이진 탐색의 정의- 정렬된 데이터 집합에서 탐색 범위를 1/2씩 줄여 나가면서 수행하는 방식 나. 이진 탐색의 특징- 분할과 정복 기반- 정렬된 데이터 집합에서 사용- 고속 탐색  Ⅱ. 이진 탐색 단계 및 사례 가. 이진 탐색 단계 및 사례- 데이터 집합의 가운데 있는 기준값과 찾는 키 값 비교 (1) 찾는 키 값 > 기준 값 : 오른쪽 부분 검색 (2) 찾는 키 값 - 키 값을 찾을 때까지 이진 검색을 순환적으로 반복/*searchnum 에 대해 list [0]찾으면 그 위치를 반환하고 못 찾으면 –1을 반환한다.*/int binsearch(int list[],int s..

개념첫번째 키는 정의된 것으로 보고 두번째 키부터 순서에 맞는 위치에 삽입시켜 정렬하는 방법 I. 삽입 정렬 (Insert Sort)의 개요 가. 삽입 정렬의 정의- 첫번째 키는 정의된 것으로 보고 두번째 키부터 순서에 맞는 위치에 삽입시켜 정렬하는 방법 나. 삽입 정렬의 특징- 간단하지만 레코드의 이동이 많은 알고리즘- 비교적 크기가 작은 데이터 집합 정렬에 유리함.- 수행시간 복잡도: O(n2)  Ⅱ. 삽입 정렬의 단계 및 사례 가. 삽입 정렬의 단계 - 삽입 대상 위치를 2번째부터 마지막까지 지정- 비교 대상을 처음부터 바로 전까지 지정- 정렬 대상의 값들과 뽑아낸 요소와 비교- 삽입할 값보다 큰 값을 가진 모든 요소들을 한 자리씩 오른쪽으로 이동- 새로 생긴 빈 자리에 해당 요소를 삽입- 전체 데..

개념정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법  I. 순차 탐색 (Sequential Search)의 개요가. 순차 탐색의 정의- 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법 나. 순차 탐색의 종류- 전진 이동법 (Move To Front): 탐색된 데이터는 가장 앞으로 이동- 전위법 (Transpose): 바로 앞 데이터와 탐색된 데이터의 위치 변경- 계수법 (Frequency Count): 데이터마다 탐색된 횟수를 새로 저장하며, 그 횟수를 내림차순 정렬  Ⅱ. 순차 탐색의 종류 및 사례 가. 전진 이동법 단계구현 사례LinkedList* FindDataMove( LinkedList* Node, in..

다익스트라 제안 알고리즘 - 개 념다익스트라를 비롯한 개념없는 철학자들의 한정된 포크를 공유하는 기아상태 유발의 식사 행태 I. 다익스트라가 제안한 기아상태가 가능한 철학자의 식사 가. 철학자의 식사의 개요다익스트라를 비롯한 개념없는 철학자들의 한정된 포크를 공유하는 기아상태 유발의 식사 행태 나. 철학자 식사의 테이블 구성도  II. 철학자 식사의 문제와 해결 구조 가. 철학자의 식사의 기본조건 구분설명실환경환경 원탁에서 둥글게 앉아서 사이에 포크를 공유 한다. 공유자원 선형조건행위 철학자는 먹거나 사색한다. 대기와 실행행위조건 반드시 2개의 포크로 식사를한다. 다른 상대의 포크는 뺏을수 없다. 왼쪽 포크를 항상 먼저집는다. 하나를 가지면 하나를 기다린다. 아무도 식사에 간섭하지 않는다. 식사를 마치면..