이론공부/알고리즘4

• 

  Hash 충돌 회피 방법은 무엇이 있을까? Open Address 데이터를 삽입하려는 해시 버킷이 이미 사용중인 경우라면 다른 해시 버킷에 데이터를 삽입하는 방법이다. 데이터를 찾을때는 Linear Probing, Quadratic Probing 등의 방법을 이용한다. Separate Chaning에 비해 캐시 효율이 높다는 장점이 있어 데이터 개수가 적다면 효율이 좋다. 그렇지만 배열의 크기가 커진다면 캐시 효율이 낮아지기 때문에 장점이 사라진다. 데이터를 삭제할때 효율적이지 못하다는 단점이 있다. 저장된 데이터가 많아진다면 Separate Chaining 보다 느려진다는 단점이 있다. 해시 버킷을 채운 밀도가 높을수록 충돌이 발생할 확률이 높기 때문이다. 선형탐사 : 해시 충돌시 다음 버킷에 저장하는 방법이다. 이차 방정식 탐사 : 2차 방정.. 이론공부/알고리즘 2021. 10. 28.

• 

  BFS(Breadth First Search, 너비우선탐색) 자료출처 : https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVIoJqqfYDFAWg SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com BFS는 그래프 탐색 알고리즘 입니다. BFS는 탐색 시작점의 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 시작으로 하여 다시 인접한 장점들을 차례로 방문하는 방식이다. 인접한 정점들을 탐색한 후, 차례로 너비 우선 탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 Queue를 활용한다. 위의 내용은 어려움으로 개인적으로 추가 큐가 빌.. 이론공부/알고리즘 2020. 4. 13.

• 보이어-무어 알고리즘(문자열 검색, Python) 보통 문자열이 일치하는 방식을 생각하면 아래와 같이 나옵니다. 1 2 3 4 5 6 7 8 def pattonmatch(a, b): for i in range(len(b) - len(a) + 1): for j in range(len(a)): if b[i+j] != a[j]: break else: return i return -1 하나씩 비교하며 틀릴시 옆으로 쉬프트하여 비교합니다. 시간복잡도는 O(N^2)이 됩니다. 문자열 탐색범위가 작다면 괜찮지만 탐색범위가 커진다면 위와 같은방식은 부담스럽습니다. 그래서 문자열 탐색 알고리즘을 사용하게 되는데 보통 KMP와 보이어-무어 알고리즘을 사용한다고 합니다. 이번에는 보이어-무어 알고리즘에 대해 포스팅하겠습니다. 보이어-무어 알고리즘의 특징: 1. 오른쪽 끝부.. 이론공부/알고리즘 2020. 2. 19.

• 

  최소신장트리에 대해(신장트리, 크루스칼, 프림) 시작 하기전에 용어에 대해 적어보도록 하겠습니다. ▶노드, 정점 : A,B,C,D라고 적혀있는 부분을 노드 혹은 정점이라고 합니다. ▶간선 : 노드 끼리 연결하는 선을 간선이라고 합니다. ▶거리 : 위의 그림은 간선에 대한 가중치 혹은 값이 적혀있지 않는데, 이값이 적혀있다면 거리라고 합니다. 간선과 거리를 같이 사용할 때도 있습니다. ▶신장트리(spanning tree) : ★모든 노드를 포함하고, ★모든 노드가 서로 연결이 되어있고 ★싸이클이 발생하지 않은 트리 위 사진은 모든 노드가 포함 및 연결이 되어있고 사이클이 발생하지 않았으므로 신장트리 입니다. 이와 같은 경우는 A, B, D에서 사이클을 형성했기 때문에 신장트리가 아닙니다. 대신에 간선을 하나 지움으로써 3가지의 신장트리를 만들 수 있습니.. 이론공부/알고리즘 2019. 12. 9.