알고리즘76 백준(BOJ) 2468 안전 영역 ** # DFS 어렵지 않은 DFS문제이다.크기를 고려했을때 모든 홍수의 값에 대해서 돌려도 충분히 돌아가기 때문에 금방 풀 수 있다. #include #include #include #include #include #include #include #include #include #include #include #include #define MAX 105 #define INF 987654321 #define MOD 1000000 #pragma warning(disable:4996) using namespace std; typedef long long ll; typedef pair pi; typedef pair pf; int n,arr[MAX][MAX],mi=INF,mx=0,ans=1; int dy[4]={0,.. 2018. 5. 31. [알고리즘 정리] CCW(Counter Clock Wise) 알고리즘 CCW는 3점을 이은 선분의 방향성에 대해서 찾는 방법이다. 찾는 방법은 삼각형의 넓이 구하는 공식을 이용한다.공식은 생각보다 어렵지 않다. 2S의 절대값에 나누기 2를 한 값이 세점의 삼각형의 넓이가 된다. 여기서 세 점의 방향성을 알기위해 2S값을 주목한다.P1이 파랑, p2 주황, P3 초록 일 때, 시계방향이면 2S의 값이 +, 일직선이면 0, 반시계방향이면 - 값을 가지게 됩니다. 관련 문제 : 백준(BOJ) 2987 사과나무 ** 2018. 5. 31. [알고리즘 정리] 외판원 순회 문제(Traveling Salesperson Problem, TSP) 외판원 순회 문제란?어떠한 도시에서 출발하여 다른 모든 도시들을 거쳐 출발 했던 도시로 다시 돌아오는데 드는 최소 비용을 찾는 문제이다. 외판원 순회 문제의 경우 도시(N)의 개수가 10개 이하일때와 16이하일때 2가지로 나눠서 생각 할 수있다.(시간복잡도 문제로 해결방법이 다르다.) N 이를 통해 반복문 하나 정도는 줄여줄 수 있다. 두 번째, 중복되는 문제가 발생한다.이 중복 계산하는 문제를 DP를 이용하여 해결하면 16개 까지의 도시를 해결 할 수 있다. N 2018. 5. 31. 백준(BOJ) 1600 말이 되고픈 원숭이 *** # BFS 기본적인 bfs 문제에서 상당히 생객해 보아야 할 점이 많아서 까다로웠던 문제였다.넘나 머리가 아팠는데 재밌는 문제였다. 문제 푸는 과정에서 주의해야할 점은 1. visit배열을 만들 때 말처럼 이동 횟수를 기준으로 만들어 주어야한다.(전체 이동 횟수 기준으로 하면 안된다.) 2. 나머지는 자잘한 실수들 조심하기~(=대신 == 했다가 메모리 초과~ㅋㅋ) #include #include #include #include #include #include #include #include #include #include #include #define MAX 205 #define INF 987654321 #define MOD 1000000009 #pragma warning(disable:4996) usi.. 2018. 5. 31. 이전 1 ··· 16 17 18 19 다음
