재시민

void SelectionSort(int A[], int n) // input Array, index size
{
	int i, j, MinIndex;
    for(i = 0; i<n-1;i++){
    	MinIndex = i;
        for(j = MinIndex + 1; j<n;j++){
        	if(A[MinIndex] > A[j])
            	MinIndex = j;
                }
        if(MinIndex != i) swap(A[i], A[Minindex]);
       }
}

알고리즘 설명

1. MinIndex 로 배열의 비교 기준을 변화시켜 비교

2. A[MinIndex] > A[j] 이면 기준 인덱스와 비교 인덱스와 비교 후 MinIndex 변경

3. 두번째 포문이 끝나고 MinIndex 값이 바뀌었다면 스왑

i번째 단계에서 항상 n-i회 비교수행

평균시간복잡도 = O(n2)

최악시간복잡도 = O(n2)

제자리성 : 제자리 정렬

- i,j,MinIndex 상수크기 메모리

불안정한 정렬

- B b a c > a b B c

www.acmicpc.net/problem/1708

수업시간에 배운 내용이라 복습겸 풀어보았다.

짐꾸리기로 풀다가 3시간은 날린 것 같다. 

다른 사람들 코드를 보니 거의 다 아니 모두가 Graham Scan 으로 푼 것 같다.

탈진 상태가 되고 배우는 마음으로 코드를 학습했다.

#include<iostream> 
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long int ll;
struct pos
{
	ll x, y;
};
vector<pos> vec;
bool compare_pos(pos p1, pos p2)
{
	if (p1.y != p2.y)
	{
		return p1.y < p2.y;
	}
	else
	{
		return p1.x < p2.x;
	}
}
long long int ccw(pos p1, pos p2, pos p3)//외적공식
{
	//음수 시계 
	//양수 반시계 
	//0 평행
	return (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - (p1.y * p2.x + p2.y * p3.x + p3.y * p1.x));
}

bool compare_rad(pos p1, pos p2)// 라디안 비교 가장큰거
{
	long long int cc = ccw(vec[0], p1, p2);
	if (cc)//라디안이 비교가능
		return cc > 0;
	else//라디안이 동일 , 수평일때
		return p1.x + p1.y < p2.x + p2.y; // 가장큰순서대로
}

int N;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);


	cin >> N;
	for (int i = 0; i < N; i++)
	{
		ll y, x;
		cin >> x >> y;
		vec.push_back({ x,y });
	}
	stack<pos> sta;
	sort(vec.begin(), vec.end(), compare_pos);
	sort(vec.begin() + 1, vec.end(), compare_rad);
	sta.push(vec[0]);//비교를 위한 최소 점 셋팅
	sta.push(vec[1]);
	pos first, second;
	for (int i = 2; i < N; i++)
	{
		while (sta.size() >= 2)
		{
			second = sta.top();
			sta.pop();
			first = sta.top();
			if (ccw(first, second, vec[i]) > 0)
			{
				sta.push(second);
				break;
			}
		}
		sta.push(vec[i]);
	}
	cout << sta.size();
}

다른 분의 코드를 거의 배꼈다. 정말 수치심이 든다.

하지만 이렇게 배워간다면 다른 문제를 풀 수 있는 발판이 된다면 오히려 괜찮을지도..?

원 코드는 ccw 의 함수 때문에 테스트 값에서 오류가 나 long long int 로 재정의 하였다. 

사실 문제 안에 변들의 180도를 넘지 않는 가장 큰 각도를 선정해서 볼록껍질을 만들라는 말이 있었다.

나는 이것을 싸그리 무시하고 짐꾸리기를 배웠으니 그렇게 해야지 라고 해서 못한 것 같다.

일찌감치 인정하고 다른 방법으로 풀었어야 했는데..

알고리즘 설명

1. 벡터안에 입력한 순서쌍들을 push_back 한다.

2. 기준점을 설정할 정렬을 한다.

3. 기준점을 잡고 나머지 점들과 ccw 의 결과를 이용한 정렬을 한다. 이때, ccw = 0 인 점이 존재한다면 x+y 값이 더큰 점에 true 를 부여한다. 

4. 스택에 기준점, 비교할 점 두개를 push 한다. 왜냐하면, ccw 를 하기 위한 최소조건이다.

5. 스택의 맨 뒤 원소 두개와 벡터의 모든 원소 ccw 한 값을 비교하면서 ccw 값이 양수인 점을 찾고 맞으면 push 아니면 break 한다.

6. 반복문이 종료되면 스택에는 꼭짓점이 될 점들만 남는다. 

단순 폐쇄 경로 : N 개의 점이 주어졌을 때 이 점들을 모두 경유하고 출발점에 되돌아오는 비 교차 경로

우편배달부 문제를 예로 들어 단순 폐쇄 경로를 찾아보자

방법 

1.  기준점 D 설정
   1. y 좌표가 가장 작은 값으로 설정하되 동일한 값이 있다면 x 좌표도 최소인 점으로 선정
2.  D에서 나머지 점들 P 각각에 대한 반직선 DP 라 할 때, 반직선 Dx 와 DP 사이의 각도들을 계산
3.  각도를 기준으로 P 점들을 오름차순으로 정렬
4.  기준점부터 시작해 정렬된 점들을 순서대로 직선 연결

각도를 구하는 방법을 생각해보자

• 아크탄젠트를 이용해 각도를 구하자
  • 가장 흔한방법이지만 계산속도가 느리다.
• 상대각도
  • 실제각도는 아니지만 효율적인 각도비교가 가능하다.

상대각도 구하는 방법

이 때 점의 사분면 위치에 따라 dx, dy 값이 음수가 되는 경우가 생긴다.

그렇게 되면 점의 정확한 상대각도를 구하기 어려워지기 때문에 식조작이 필요하다.

1사분면에서의 상대각도는 0과 1사이의 값이므로 360도의 상대각도가 4 이므로

2사분면 : 2 - 상대각도

3사분면 : 2 + 상대각도

4사분면 : 4 - 상대각도

이때 상대각도를 구하는 dx, dy 에는 절댓값을 씌워준다.

위의 식을 ComputeAngle 함수로 만들어 표현한 코드는 아래와 같다.

float ComputeAngle(struct point A, struct point B) {
	int Dx, Dy; float Angle;
	Dx = B.x - A.x; Dy = B.y - A.y;
	if ((Dx >= 0) && (Dy == 0)) Angle = 0;
	else {
		Angle = abs(Dy) / (abs(Dx) + abs(Dy));
		if ((Dx < 0) && (Dy >= 0)) Angle = 2 - Angle;
		else if ((Dx <= 0) && (Dy < 0)) Angle = 2 + Angle;
		else if ((Dx > 0) && (Dy < 0)) Angle = 4 - Angle;
	}
    return Angle * 90.0;
}

주어진 선분 AB, CD 가 서로 교차하는지 확인해보자

꺾은선 ABC 와 ABD 가 서로 다른 방향 ( 시계 와 반시계 ) 이며

CDA 와 CDB 가 서로 다른 방향일때 두 선분은 교차한다고 말할 수 있다.

이 때 꺾은선의 방향을 알려주는 함수를 정의하자.

함수 Direction 은 시계방향일 때  1, 반시계일 때 -1, 한 직선위에 세 점이 존재할 때 0 이라고 한다면

교차하기 위해서는 아래 식을 만족해야한다.

이 때 Direction 함수를 코드로 나타내 보자

int direction(struct point A, struct point B, struct point C) {
	int dxAB, dxAC, dyAB, dyAC, Dir;
	dxAB = B.x - A.x; dxAC = C.x - A.x;
	dyAB = B.y - A.y; dyAC = C.y - A.y;

	if (dxAB * dyAC < dyAB * dxAC) Dir = -1;
	if (dxAB * dyAC > dyAB * dxAC) Dir = 1;
	if (dxAB * dyAC == dyAB * dxAC) {
		if (dxAB == 0 && dyAB == 0) Dir = 0;
		if ((dxAB * dxAC < 0) || (dyAB * dyAC < 0)) Dir = 1;
		else if ((dxAB * dxAB + dyAB * dyAB) >= (dxAC * dxAC + dyAC * dyAC)) Dir = 0;
		else Dir = -1;

	}
	return Dir;
}

이 때 A, B, C 가 일직선 상에 있을 때 어떤 점이 중점이 되는지 파악해 줘야한다.

이 부분을 코드로 다시 나타내보면

if (dxAB * dyAC == dyAB * dxAC) {// AC, AB 기울기가 동일한 경우
		if (dxAB == 0 && dyAB == 0) Dir = 0; // A,B,C 중 동일점이 존재하는 경우
		if ((dxAB * dxAC < 0) || (dyAB * dyAC < 0)) Dir = -1; // AB 와 AC가 반대방향 확인
        // 맞으면 A 가 사이점
		else if ((dxAB * dxAB + dyAB * dyAB) >= (dxAC * dxAC + dyAC * dyAC)) Dir = 0;
        // AB, AC 같은방향이면서 |AB| >= |AC| 인지 확인
        // 맞으면 C 가 사이점
		else Dir = 1; // B가 사이점
	}

위의 Direction 함수를 이용해 Intersection 함수를 만들자

int intersection (strcut line AB, struct line CD){
	int LineCrossing;
    if((Direction(AB.A,AB.B,CD.C) * Direction(AB.A,AB.B,CD.D) <= 0) &&
    	(Direction(CD.C,CD.D,AB.A) * Direction(CD.C,CD.D,AB.B) <= 0))
        LineCrossing = true;
    else LineCrossing = false;
    return LineCrossing;
}