Computer Science/Algorithm
-
[알고리즘] 최근접 점쌍 찾기Computer Science/Algorithm 2021. 12. 16. 03:06
최근접 점쌍 찾기 2차원 평면상에 있는 N개의 점들 중에서 서로의 거리가 가장 가까운 두 점을 찾는 문제 간단한 방법 모든 상의 거리를 모두 계산하여 가장 가까운 쌍을 찾는 것 시간 복잡도 O(N^2) 정렬을 사용한 방법 합병 정렬 알고리즘에서 사용하는 분할-정복 기법을 사용 시간 복잡도 O(N log N) 분할-정복 기법을 사용한 최근접 점쌍 찾기 알고리즘 X 좌표 값을 사용해 점을 정렬한 다음 반으로 나눔 가장 가까운 쌍을 이루는 두 점은 모두 한쪽 절반에 있든지 아니면 하나는 한쪽 절반에, 다른 하나는 나머지 절반에 있음 가장 가까운 쌍을 이루는 두 점이 분할선(dividing line)을 가로지르는 경우 효과적으로 검사할 수 있는 방법이 필요 알고리즘 동작 과정 동작 과정을 표로 나타 낼 수도 있..
-
[알고리즘] 그라함 스캔 알고리즘Computer Science/Algorithm 2021. 12. 15. 12:28
그라함 스캔 알고리즘 1972년 로날드 그라함에 의해 개발된 알고리즘 주어진 점 집합으로부터 단순 폐쇄 다각형을 만든 다음, y좌표 값이 가장 작은 점부터 시작해 다각형의 꼭지점들을 순서대로 방문하면서 볼록 껍질에 포함될지 여부를 검사하는 것이다. 볼록 껍질에 포함되는지 검사 방법 p[1], p[2], ..., p[M]이 부분 볼록 껍질이라 하고 새로운 점 p[i]를 추가하고자 할 때, ccw(p[M], p[M-1], p[i])≥ 0 이면 p[M]을 제거 p[M-1], p[M], p[i]가 우회전이면, p[M]을 제거하고, 좌회전이면 p[i]를 포함한다. 그라함 스캔 알고리즘 동작 과정 먼저 y 점이 가장 작은 점을 선택한 후, 그 점에서 부터 가장 작은 각도를 만드는 순서대로 번호를 매겨줍니다. 처음 ..
-
[알고리즘] 최적 이진 탐색 트리Computer Science/Algorithm 2021. 12. 14. 20:02
최적 이진 탐색 트리 트리 내의 키와 각 키가 탐색될 확률이 주어져 있을 때, 그 트리의 평균 탐색 비용, 즉 평균 비교 횟수를 계산하고 이를 최소화하는 탐색트리를 구축하는 문제 이진 탐색 트리 루트의 왼쪽 서브트리에 있는 원소의 키 값은 루트보다 작고, 루트의 오른쪽 서브트리에 있는 원소의 카 값은 루트보다 큰 이진 트리 점화식 최적 이진 탐색 트리 구하기 1. A[i, j] 테이블과 k 테이블을 그려줍니다. A테이블 대각선엔, 문제에서 주어진 확률을 K테이블 대각선엔, 순서대로 초기 값을 적어줍니다. 2. 점화식을 이용하여 테이블의 값을 채워줍니다. 3. 이진 탐색 트리 그리기 - k테이블에서 1행 가장 맨 끝 값을 가져옵니다. k[1, 4] = 3 값이 3이기 때문에, 이는 3번 노드가 최상단임을 ..
-
[알고리즘] 스트링 편집 거리Computer Science/Algorithm 2021. 12. 14. 19:19
스트링 편집 거리(string edit distance) 두 스트링의 유사도를 측정하기 위해 사용 Levenshtein distance(LD)라고도 함 원래 스트링을 S, 목표 스트링을 T S를 T로 변환하는 데 필요한 삽입, 삭제, 대치 연산의 최소 비용 편집 거리가 커질수록, 두 스트링의 유사도는 낮아지게 됨 논문이나 보고서의 표절 검사, DNA 염기 서열의 유사도 검사 등에 사용됨 동적 계획법의 적용 스트링 편집 거리 예시를 들어 설명하겠습니다. S = GUMBO T = GAMBOL U -> A 로 교체 L 을 추가 따라서, GUMBO를 GAMBOL로 변경하는 최소 편집 거리는 2임을 알 수 있습니다. 스트링 편집 거리를 구하기 위해선, 간단히 표로 작성하여 구할 수 있습니다. 1. 초기 테이블을 ..
-
[알고리즘] 기하 알고리즘 - 2차원 트리Computer Science/Algorithm 2021. 12. 14. 04:14
2차원 트리 이진 트리 형태를 가지며, 동적으로 변화하는 트리 범위 탐색에 편리하게 사용할 수 있도록 기하학적 공간을 나눔 만드는 과정 이진 탐색 트리를 만드는 과정과 유사 이진 탐색트리와 다른 점은 이진 트리의 레벨에 따라 y축과 x축을 번갈아 가면서, 한번은 y좌표값을 기준으로 삽입하고, 한번은 x좌표값을 기준으로 삽입하는 것임 2차원 트리 만드는 과정 1. 해당 위치가 x좌표 or y좌표인지 확인 2. 해당 위치에 맞는 좌표와 새로 삽입할 좌표와 비교 3. 위치 선정 4. x좌표 or y좌표자리인지 확인 5. 새로운 좌표를 알맞은 좌표모양으로 그려죽; 한번은 y좌표값을 기준으로 삽입하고, 한번은 x좌표값을 기준으로 삽입해야하므로, 삽입 시 쉽게 판별할 수 있도록 다른 모양으로 그려줍니다. 삽입 과정..
-
[알고리즘] AVL 트리Computer Science/Algorithm 2021. 10. 24. 03:26
AVL 트리 러시아의 수학자 Adelson - Velskii 와 Landis가 고안한 높이 균형 이진 탐색 트리 오른쪽 서브트리와 왼쪽 서브트리의 높이 차가 2이상이 되면 회전을 통해 트리의 높이 차를 1이하로 유지 높이차 = 오른쪽 서브트리의 높이 - 왼쪽 서브트리의 높이 이진 탐색 트리를 기반으로 하기 때문에 삽입 시엔 이진 트리 처럼 노드를 삽입한다. AVL 트리의 높이 차 AVL 트리에선 노드 삽입 시, 회전이 필요한 경우 2가지가 있습니다. 경우 1: 높이 차 2인 노드부터 삽입 경로 전까지의 모양이 1자인 경우 -> 단일 회전 단일 회전: 가운데 숫자가 위로 올라가면서, ㅅ자 모양으로 회전 경우 2: 높이 차 2인 노드부터 삽입 경로 전까지의 모양이 >, 이중 회전 이중 회..