[알고리즘] 0727 정리

해시 함수

• 임의의 데이터, 바이트열을 받아서 숫자로 반환하는 함수

• 해시함수 요건
  일관성 -> 같은 데이터에 대해 일관적으로 같은 숫자만 반환해야함
  서로 다른 데이터에 대해 모두 서로 다른 숫자가 나와야 좋음

• 해시 테이블 -> 해시맵, 맵, 딕셔너리, 연관배열으로도 불림
  키와 값을 가짐

• DNS 확인 작업에서도 해시 테이블을 사용함
  ex) naver.com -> 123.123.23.1

• 충돌
  서로 다른 키가 같은 공간에 할당되면 연결리스트를 만들어 넣음

• 연결리스트가 길어지면 해시 테이블의 속도도 느려짐

• 성능
  평균적으로 해시 테이블은 검색, 삽입, 추가에 O(1)이 걸림
  최악의 경우 모두 O(n) 이 걸림

• 사용률 -> 항목의 수 / 공간의 수
  예를들어 5개의 공간을 갖는 배열이 있고 항목이 2개가 있으면
  사용률이 40%가 됨

• 리사이징 -> 사용률이 커지기 시작하면 해시 테이블의 공간을 추가

• 정리

• 해시 테이블은 함수와 배열을 결합해서 만든다.
• 해시 테이블은 빠른 검색, 삽입, 삭제 속도를 가진다.
• 사용률이 0.7 보다 커지면 해시 테이블을 리사이징 할때다.
• 중복을 잡아내는데 뛰어나다.

너비 우선탐색(Breadth First Search)

• 그래프 -> 연결의 집합을 모형화 한것.

• 정점(node) 와 간선(edge) 로 이루어짐

• 너비 우선탐색이 진행될수록 탐색 범위는 출발점에서 멀어짐

• Queue -> First In First Out(선입선출)
  enqueue - > 큐에 항목을 더한다.
  dequeue - > 큐에서 항목을 제거한다.

• 방향 그래프 - > 방항성을 가지는 그래프

• 무방향 그래프 - > 방향성이 없다. 두 항목이 서로 이웃이 된다.

• 실행시간 O(V + E)
  V -> 정점의 수
  E -> 간선의 수

• 순서대로 탐색해야 하기 때문에 탐색목록은 Queue 여야 한다.

• 어떤것을 확인한 다음엔 두번다시 확인하지 않도록 해야함 (안그럼 무한반복할 수 있음)

다익스트라 알고리즘(dijkstra's algorithm)

• 너비 우선 탐색 -> 가장 적은 구간 탐색
• 다익스트라 알고리즘 -> 가장 빠른 경로 탐색

1. 가격이 가장 싼 정점을 찾는다.
2. 이 정점의 이웃 정점들의 가격을 조사한다.
3. 그래프 상의 모든 정점에 대해 이러한 일을 반복한다.
4. 최종 경로를 계산한다.

• 가중치 그래프 -> 다익스트라 사용

• 균일 그래프(가중치가 없음)-> 너비 우선 탐색 사용

• 방향성 비순환 그래프 또는 사이클을 가진 경우에는 가중치가 양수일때만 적용됨

• 부모 정점을 찾아가면 완전한 경로를 찾을 수 있다.

• 다익스트라 알고리즘에서는 정점을 처리하면 그 정점에 도달하는데 더 싼 경로는 없다고 가정함.