수식 표기법, 해싱, 오버플로우 처리 방법

📌수식 표기법

표기법 종류

1. 중위 표기법 Infix notation
   • 우리가 사용하는 것. a + b
   • 연산자가 사이에
2. 전위 표기법 Prefix
   • +ab
   • 연산자가 앞으로
3. 후위 표기법 Post
   • ab+
   • 연산자가 뒤로

• 컴퓨터는 전위나 후위 표기법을 사용하게 된다 (효율성 때문에)

표기법 변환 ⭐⭐⭐

1. 중위 → 전위
   • A * ( B + C ) / D - E
     1. ( ) 먼저
        • +BC
     2. *A+BC / D - E
     3. /*A+BCD-E
     4. -/*A+BCDE
2. 중위 → 후위
   • A * ( B + C ) / D - E
     1. BC+ 먼저
     2. A * BC+ / D - E
     3. ABC+* / D - E
     4. ABC+*D/ - E
     5. **ABC+*D/E-**
3. 전위 → 중위
   • 연산자 데이터 데이터 가 나오는 식을 찾아 연산자를 가운데로 넣어주자
   • -/*A+BCDE
     1. -/*A+BCDE
        • B + C 이렇게 하나의 데이터가 된다
     2. -/*A B+C DE
        • A * (B + C)
     3. -/ A * (B + C) DE
        • A * (B + C) / D
     4. - A * (B + C) / D E
        • A * ( B + C ) / D - E
4. 후위 → 중위
   • 데이터 데이터 연산자 가 나오는 식을 찾아 연산자를 가운데로 넣어주자
   • ABC+*D/E-
     1. ABC+*D/E-
     2. A (B+C) *D/E-
     3. A * (B+C) D/E-
     4. A * (B+C) / D E-
     5. A * (B+C) / D - E

 

 

📌Hashing 해싱

해싱 구성요소

1. 해시 테이블
2. 해싱
3. 해시함수

해시 테이블

1. 버킷
2. 슬롯
3. 충돌
   • 같은 키를 가지는 현상
4. 동의어
   • 충돌난 것들끼리 묶은 것
   • 동의어가 슬롯 수보다 많으면 오버플로우 발생
     • 더이상 넣을데가 없다!
       • 오버플로우 = 넘치는 현상 (더이상 빈 공간이 없는)

해싱 함수 종류 ⭐

어떤 기준에 따라 버킷 값을 구해내는가~

1. 제산법 Division
   • 레코드의 값을 나누어 나머지 값을 취해 → 주소로 지정
2. 중간 제곱법 Mid Square
   • 키 값을 제곱 → 중간 몇 자리 선택 → 이걸 주소로 지정
3. 중첩법 Folding
   • 길이를 동일하게 여러 부분으로 나누고
   • 더하거나 XOR → 주소
4. 숫자 분석법 Digit Analysis
   • 균등한 분포의 숫자 선택
5. 기수 변환법 Radix Exchange
   • 다른 진법으로 변환 →주소
6. 무작위 방법 Pseudo Random
   • 난수 발생
   • 충돌 발생 시 다음 값을 난수로

오버플로우 처리 방법

1. 개방 주소법 ⭐
   • 순차적으로 다음 빈 버킷에 저장
   • 하나의 해시테이블 내에서 처리됨
2. 폐쇄 주소법 ⭐
   • 별도의 다른 공간(오버플로우 영역)을 이용
   • Chain(pointer)로 버킷에 연결
3. 재해싱
   • 해시 테이블의 주소를 다 새로 만듦.