노트정리/알고리즘
최소 신장나무 - 크루스칼 , 프림 알고리즘
최소 신장 나무- 그래프 G의 모든 정점들을 사이클이 생기지 않게 연결하면서 간선에 부여된 가중치의 합이 가장 적게 구성된 나무.- 만드는 방법에는 크루스칼 , 프림 알고리즘이 있다. 신장 나무가중 무방향 그래프에 대하여 신장 나무는 주어진 그래프의 모든 노드들을 포함하는 연결된 부분 그래프로 나무를 형성.신장 나무 중에서 가중치의 합이 가장 작은 신장 나무로 최소 신장 나무도 있음. 크루스칼 알고리즘- 욕심쟁이 방법 적용. 사이클을 만들지 않는 최단 간선을 하나씩 추가해 나감으로 최소 신장 나무를 구하는 방법- 간선을 가중치가 증가하는 순으로 한 번에 하나씩 사이클이 만들어 지지 않도록 추가함.123456789101112Kruskal (Adj(G), T){ /* 입력 : 그래프 g=(v,e)의 인접 리..
노트정리/알고리즘
그래프의 종류와 인접, 행렬 리스트
그래프그래프 G = (V,E) 이다. V : 정점의 집합을 의미하고 E : 간선의 집합을 의미한다. 2차원 배열을 이용하여 인접 행렬이나 연결 리스트 형태의 인접 리스트로 표현이 가능하다. 여러 가지 종류로 나뉘기도 하는데크게 무방향 그래프 , 방향 그래프로 나뉜다. 변이 방향성을 띠지 않는 그래프를 무뱡향 , 방향성을 띠는 그래프를 방향 그래프라고 함.방향 그래프는 보통 그림 보면 화살표 있음. 그래프의 종류인접 - 간선 v,w 가 e(g)에 속한 간선 > 점점 v와 정점 w는 인접부속 - v,w가 인접해 있을 떄, 간선v, w : 정점,v, w에 부속된 것단순 경로 - 경로상에 있는 정점들 중에서 첫 번째 정점과 마지막 정점을 제외한 모든 정점들이 서로 다를때사이클 - 첫 번째 정점과 마지막 정점이 ..
노트정리/알고리즘
[알고리즘] 기하 알고리즘
기하 알고리즘에 앞서기하학은 기본 요소로 점 , 선 , 다각형, 다면체가 있습니다. 기하문제를 풀기 위해선 기본 요소인 점 , 선, 다각형, 다면체 등을 어떻게표현할 것인가를 결정해야 하는데 간단판 표현법 으로 좌표를 사용합니다. 기하학의 기본요소- 점 : 1차원 물체- 선, 다각형 : 2차원 물체- 다면체 : 3차원 물체 기하학의 문제- 간단한 문제 : 선분교차, 직각 삼각형, 내접 다각형- 복잡한 문제 : 순환 외판원, CAD, 최소 신장 나무 두 선분의 교차 검사두 선분이 주어졌을 떄, 이 둘이 서로 교차하는지 아닌지를 검사하는 것은 가장 기본적인 기하 알고리즘 중에 하나입니다. 여기서 두 선분이 교차한다는 것은 그 두 선분이 적어도 한 점을 서로 공유함을 말하는 것이다. 기본적인 용어에는 - 선분..
노트정리/알고리즘
[알고리즘] 스트링 매칭
스트링 매칭주어진 텍스트에서 주어진 패턴이 어디에 나타나는지를 알아내는 문제를 스트링 매칭 문제라고 한다.어떤 문서에서 특정 단어를 찾을 때 이것이 스트링 매칭이 되고 여기서 문서를 텍스트라 하고 찾아낼 특정 단어를 패턴 이라고 합니다.즉 텍스트에서 패턴과 일치하는 모든 부분을 찾아내는 문제이죠. 직선적 알고리즘텍스트의 매 위치에서 패턴 일치가 발생하는지를 조사하는 방법입니다. T에서 P가 나타나는 부분을 찾는 직선적인 방법이 하나하나 차례대로 비교해 나가는 것 입니다. 즉T[0]과 P[0]으로부터 하나씩비교해 나가는데 이를 불일치가 발생할 때까지 반복합니다. 위예의 경우 처음부터 불일치가 발생하는데 다시 오른쪽으로한 번 이동시켜서 패턴의 처음부터 비교를 다시 반복합니다. 직선적 스트링 매칭 방법의 시간..
오늘도 삽질
