노트정리/알고리즘
[알고리즘] 기하 알고리즘
기하 알고리즘에 앞서기하학은 기본 요소로 점 , 선 , 다각형, 다면체가 있습니다. 기하문제를 풀기 위해선 기본 요소인 점 , 선, 다각형, 다면체 등을 어떻게표현할 것인가를 결정해야 하는데 간단판 표현법 으로 좌표를 사용합니다. 기하학의 기본요소- 점 : 1차원 물체- 선, 다각형 : 2차원 물체- 다면체 : 3차원 물체 기하학의 문제- 간단한 문제 : 선분교차, 직각 삼각형, 내접 다각형- 복잡한 문제 : 순환 외판원, CAD, 최소 신장 나무 두 선분의 교차 검사두 선분이 주어졌을 떄, 이 둘이 서로 교차하는지 아닌지를 검사하는 것은 가장 기본적인 기하 알고리즘 중에 하나입니다. 여기서 두 선분이 교차한다는 것은 그 두 선분이 적어도 한 점을 서로 공유함을 말하는 것이다. 기본적인 용어에는 - 선분..
노트정리/알고리즘
[알고리즘] 스트링 매칭
스트링 매칭주어진 텍스트에서 주어진 패턴이 어디에 나타나는지를 알아내는 문제를 스트링 매칭 문제라고 한다.어떤 문서에서 특정 단어를 찾을 때 이것이 스트링 매칭이 되고 여기서 문서를 텍스트라 하고 찾아낼 특정 단어를 패턴 이라고 합니다.즉 텍스트에서 패턴과 일치하는 모든 부분을 찾아내는 문제이죠. 직선적 알고리즘텍스트의 매 위치에서 패턴 일치가 발생하는지를 조사하는 방법입니다. T에서 P가 나타나는 부분을 찾는 직선적인 방법이 하나하나 차례대로 비교해 나가는 것 입니다. 즉T[0]과 P[0]으로부터 하나씩비교해 나가는데 이를 불일치가 발생할 때까지 반복합니다. 위예의 경우 처음부터 불일치가 발생하는데 다시 오른쪽으로한 번 이동시켜서 패턴의 처음부터 비교를 다시 반복합니다. 직선적 스트링 매칭 방법의 시간..
노트정리/알고리즘
균형나무와 외부 탐색법
2-3-4 트리는 모든 중간 노드들의 자식수가 2,3,4이면서 모든 단말 노드가 같은 레벨에 있는 나무입니다.2-3-4 나무 특징- 2-3 나무를 확장 하여 다양한 나무를 만들수 있다.- 데이터베이스에서 사용하는 색인구조의 형태- 한 노드에 있을 수 있는 값의 수가 많다면 나무의 높이 감소.- 나무의 높이가 감소하면 할수록 검색 향상됨.2-3-4 나무의 삽입- 단말 노드에서 이루어집니다. 삽입할 노드를 찾는동안 4-노드를 만나면 분할합니다.2-3-4 나무의 삭제- 먼저 삭제할 값을 포함한 노드를 찾아야 한다.- 그 노드가 단말 노드가 아니면 그값과 그것의 중위 순위상에서 바로 앞 값을 교환함. (이 값은 항상 단말 노드에 있음) n개의 노드로 구성된 2-3-4 나무가 있을때 나무의 높이 = 최대 logn..
노트정리/알고리즘
탐색 알고리즘 - 다양한 탐색법
컴퓨터의 기억공간 내에 저장한 특정 항목의 위치를 찾거나 자료가 집합 내에 없을 경우에는 특정한 메시지를 출력하여 주는운영 방법을 탐색이라고 합니다. 컴퓨터를 이용하는 최고의 목적은 정보를 저장하고 정리한 후 탐색하는 것이죠. 탐색에 들어가기전알아야할 용어들이 있습니다. 기본적인 용어는키 : 키는 파일 내의 레코드를 다른 레코드와 구별할 수 있는 항목기본키 : 특별히 각 레코드를 완전히 구분할 수 있는 검색키레코드 : 1개 이상의 항목들을 서로 관련 있는 것끼리 짝을 지어 모은 형태딕셔너리 : 검색이라는 자료 처리를 하기 위하여 키와 레코드 및 기본 연산들을 자료 구조 형태로 표현해 놓은 것심벌 테이블 : 프로그램에 대한 딕셔너리로 자료 구조에 대한 모든 명세들을 가지고 있으며 보통 이름과 값으 쌍으로 ..
오늘도 삽질
