수식 표기법
중위 표기법(Infix notation) A + B
전위 표기법(Prefix notation) +AB
후위 표기법(Post notation) AB+
-
중위 표기법 -> 전위 표기법
연산자 우선순위에 따라 데이터, 연산자, 데이터가 나오게 되면 연산자를 앞으로 넣어준다 -
중위 표기법 -> 후위 표기법
연산자 우선순위에 따라 데이터, 연산자, 데이터가 나오게 되면 연산자를 뒤로 넣어준다. -
전위 표기법 -> 중위 표기법
연산자, 데이터 ,데이터가 나오는 식을 찾아 연산자를 가운데로 넣어주면서 중위식으로 변경 -
후위 표기법 -> 중위 표기법
데이터 ,데이터, 연산자가 나오는 식을 찾아 연산자를 가운데로 넣어주면서 중위식으로 변경
연산자 우선순위
- 괄호
- 곱하기,나누기
- 더하기 빼기
해싱의 개념
키(key)값을 해시 함수(Hash Function)에 대입시켜, 나온 결과를 주소로 사용하여 바로 값(Value)에 접근할 수 있게 하는 방법
검색(search), 삽입(insert), 삭제(delete)를 단시간O(1)에 할 수 있게 만들어주는 기법
해시 테이블(hash table) - 키와 값으로 구성되어 있는 자료구조
해싱(Hashing) - 해시 테이블을 이용한 탐색
해시함수(hash function) - 임의의 길이의 데이터를 고정된 길이의 데이터로 만드는 함수
해시 테이블
- 버킷(bucket) - 해시 테이블의 행 인덱스
- 슬롯(slot) - 해시 테이블의 열 인덱스
- 충돌(Collision) - 다른 레코드가 같은 키를 가지는 충돌현상
- 동의어(Synonym) -
- 충돌이 일어난 레코드의 집합
- 키 값이 같은 레코드의 집합
- 동의어가 슬롯의 개수보다 많으면 오버플로우 발생
- 오버플로(Overflow) - 더 이상 빈 공간이 없는 상태
해싱 함수 종류
- 제산법(Division)
- 레코드의 값을 나누어 나머지 값을 지정하는 방법
- 중간 제곱법(Mid Square)
- 키 값을 제곱한 후에 중간의 몇 자리를 선택하고 그 중간 값을 주소로 이용
- 중첩법(Folding)
- 길이를 동일하게 여러 부분으로 나누고, 더하거나 XOR 하여 주소로 이용
- 숫자 분석법(Digit Analysis)
- 각 숫자의 분포를 이용해서 균등한 분포의 숫자를 선택해서 사용
- 기수 변환법(Radix Exchange)
- 주어진 키의 값을 다른 진법으로 변환하여 얻은 값을 주소로 사용
- 무작위 방법(Pseudo Random)
- 난수를 발생, 탐색을 위한 해시의 경우 충돌이 발생하면 다음 난수를 이용
오버플로우 처리 방법
- 개방 주소법(Open Addressting)
- 선형 방법(Linear Method)이라고도 함
- Collision이 발생했을때 순차적으로 다음 빈 버킷을 찾아 저장
- 폐쇄 주소법(Close Addressing)
- Overflow 된 레코드들을 별도의 Overflow영역에 저장하고 Chain(Pointer)으로 버킷에 연결
- 재해싱(Rehashing)
- Collision이 발생하면 새로운 해싱 함수로 새로운 주소를 구하는 방식
안녕하세요!