Blog Content

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

세 점이 있을 때 반시계 방향으로 움직이는지, 시계방향으로 움직이는지 찾는 알고리즘이다.2차원 좌표에 세 점 A,B,C가 있다고 가정했을 때AB 기준으로 C가 왼쪽에 위치해있다고 했을 때벡터의 외적을 계산하면 d[AB, AC] > 0 이 나오고,AB기준으로 C가 오른쪽에 위치해있다고 했을 때d[AB, AC] < 0이 나온다. 즉, 벡터의 외적의 값이 0 초과이면 ccw(반시계방향),0미만이면 cw(시계방향), 0이면 일직선상에 존재한다. 1234567891011121314151617181920212223242526272829303132333435363738394041import java.io.BufferedReader;import java.io.InputStreamReader; /*2차원 좌표 평면 위에..

1. list[] 에 있는 점들 중 가장 작은 것을 찾아서 기준점으로 선정한다.2. 기준점 기준으로 각각의 점들을 반시계 방향으로 기준점과 각도 순서대로 정렬한다.3. 점들을 하나씩 보면서 볼록껍질에 포함시킬지 말지를 결정한다.스택을 하나 만들고, 이 스택에는 점의 번호를 넣어주는데 스택 사이즈가 한개밖에 없으면일단 지금 잡고 있는 점을 넣는다.스택에 점이 두 개 이상이면 비교를 한다.점 두개를 기준으로 다른 점을 봤을 때 CCW를 하는데, 이 때 반시계 방향에 있으면 만족하므로 스택에 넣어준다.그리고나서 또 스택의 두개를 빼서 두 점 기준으로 다음 점을 CCW 한다.만약 반시계 방향에 없다면 오목하다는 의미이므로 만족하지 않는다. 따라서 이럴 경우에는 스택에서 빼준다.이렇게 계속 반복해준다. 12345..

무방향 그래프에 사이클이 존재하는지의 여부를 확인하는 java 코드입니다.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Stack;import java.util.StringTokenizer; // http://clearpal7.blogspot.kr/2016/10/cycle.html// 무방향 그래프 -> cycle찾..

트리 : 연결그래프이며 정점의 개수가 N개 일 때, 간선의 개수가 N-1인 트리스패닝트리 : 신장트리, 무향 연결 그래프가 있을 때 그 그래프에서 간선을 부분적으로 뽑아서 만들 수 있는,그래프의 정점 개수와 같은 정점 개수를 가지는 트리최소 스패닝 트리 (MST) : 트리의 간선마다 가중치(cost)가 있을 때, 간선의 가중치 합이 최소인 트리 하나의 그래프에 대해 스패닝 트리는 여러개일 수도 있다.또한 MST도 여러개일 수 있지만, 스패닝 트리 개수 이하이다. MST를 구하는 알고리즘은 프림알고리즘, 크루스칼 알고리즘 등이 있지만,크루스칼 알고리즘이 응용 가능성이 높다. 크루스칼 알고리즘의 작동 방식1. 간선들을 가중치 순으로 오름차순 정렬하고, 정점들을 각 컴포넌트로 초기화한다.2. 간선들을 훑으면서..