알고리즘 기초 입문을 위해 공부한 DO IT! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬편을 통해 새로 알게 된 내용을 정리

1. 검색 알고리즘 종류

1-1. 배열 검색

• 선형 검색 : 무작위 데이터 집합에서 유일한 검색 수행 방법
• 이진 검색 : 일정 규칙이 있는 데이터 집합에서 빠른 검색 수행 방법
• 해시법 : 데이터 추가 및 삭제가 자주 일어나는 데이터 집합에서 빠른 검색 방법
  - 체인법 : 같은 해시값 데이터를 연결리스트로 연결
  - 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시

1-2. 연결 리스트 검색

1-3. 이진 검색 트리 검색

2. 선형 검색 (배열검색)

: 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘

2-1. 종료 조건

1. (검색 실패) 배열의 끝을 지나간다.
2. (검색 성공) 키 값과 동일한 원소를 발견한다.

2-2. 보초법

: 선형검색의 종료조건은 데이터 양이 많을 수록 비용이 커진다
: 검색이 맨 끝에 도달했는 지 판단을 제외하므로써, 선형검색의 비용을 반으로 줄이는 방법이다.

검색 키 값을 배열의 마지막에 추가하여, 검색이 맨끝에 도달했는 지 판단하는데 드는 비용을 줄일 수 있다.
def seq_search(arr:Sequence, key:Any) -> int :
  a = copy.deepcopy(arr)
  a.append(key)
  
  for i in range(len(arr)):
    if arr[i] == key : 
      return -1 if i == len(arr)-1 else i

2-3. 복잡도 : O(n)

3. 이진검색 (배열검색)

: 데이터가 오름차순, 내림차순으로 정렬되어 있는 경우 선형검색보다 빠르게 검색하는 알고리즘

3-1. 종료 조건

pl = 0 // pr = len(arr)-1 // pc = (pl+pr) //2
1. (검색 성공) a[pc]와 검색 키 값이 일치하는 경우
2. (검색 실패) 검색 범위가 더 이상 없는 경우(pl > pr)

3-2. 예시

def binary_search(arr:Sequence, key:Any) -> int :
  pl = 0
  pr = len(arr)-1

  while True:
    pc = (pr+pl) //2
    if pl > pr :
      return -1
    if arr[pc] == key :
      return pc
    elif arr[pc] > key : 
      pr = pc-1
    else : 
      pl = pc+1   

3-3. 복잡도 : O(log(n))

4. 해시법

: 데이터 검색 및 추가, 삭제도 효율적으로 수행할 수 있는 알고리즘

4-1. 기본 개념

• 해시값 : 원소 값 % 원소 개수
• 버킷 : 해시 테이블에서의 원소(노드)
• 해시 테이블 : 해시값을 인덱스로하여 원소(버킷)을 저장한 배열

4-2. 해시 충돌

: 한 해시값에 저장할 버킷이 중복되는 현상
=> 이런 해시 충돌을 최소화하기 위해서, 해시테이블의 원소 개수는 '소수'를 추천!!

: 해결 방식

• 체인법 : 해시값이 같은 원소를 연결리스트로 관리
• 오픈 주소법 : 빈 버킷을 찾을 때까지 해시 반복

4-3. 체인법

1) NODE 구성(key / value / next(node))

: 키와 값이 짝을 이루고, 연결리스트로 연결된 다음 값을 next에서 참조

2) 중요 포인트

1. 키를 해시값을 변환한다. (공통)
2. 해시값을 인덱스로 하는 버킷에 주목한다. (공통)
3. 추가의 경우, 리스트의 맨 앞부터 쌓인다.
4. 제거의 경우, 주목하는 버킷의 이전 버킷을 참조하는 변수도 필요하다.

3) 예시

# 1. hash값 변환
    hash = self.hash_value(key)
    
# 2. hash를 인덱스로 하는 버킷 구하기
    p = self.table[hash]
    
# 3. 연결리스트 개념을 응용하여 검색, 추가, 제거 
   while p is not None:
        if p.key == key:
          return p.value
        p = p.next

4-4. 오픈주소법

: 해시 충돌 발생 시, 재해시를 수행하여 빈 버킷을 찾는 방법

1) 주요 특징 : 버킷의 상태

: 오픈주소법에서 버킷의 구성은 '키, 값, 상태'이다. 이는 체인법에서 버킷의 구성이 키, 값, next(다음 버킷)인 것과 비교된다.

class Status(Enum):
  OCCUPIED = 0
  EMPTY = 1
  DELETED = 2

2) 중요 포인트

1. 키를 해시값을 변환한다. (공통)
2. 해시값을 인덱스로 하는 버킷에 주목한다. (공통)
3. 상태를 확인하면서, 원하는 key값이 나올 때까지 rehash한다. (공통)

[SEARCH 알고리즘]

hash = self.hash_value(key)
p = self.table[hash]
for i in range(self.capacity):
	if p.stat == Status.EMPTY : 
		return None        
	elif p.stat == Status.OCCUPIED and p.key == key:
		return p
	hash = self.rehash_value(hash)
	p = self.table[hash]    
return None

[ADD 알고리즘]

hash = self.hash_value(key)
p = self.table[hash]
for i in range(self.capacity):
	if p.stat == Status.EMPTY or p.stat == Status.DELETED :
		self.table[hash] = Bucket(key, value, Status.OCCUPIED)
        return True
	hash = rehash_value(hash)
	p = self.table[hash]    
return False

[REMOVE 알고리즘]

p = self.search(key)
if p is None:
	return False
p.set_status(Status.DELETED)
return True