본문 바로가기

전체 글98

[3190번] 뱀 3190번: 뱀 www.acmicpc.net 뱀이 사과를 먹으면 길이가 늘어나는 게임이다. 규칙은 아래와 같다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include #include #include using namespace std;struct pnt { int r, c; };int Map[10.. 2020. 4. 4.
CCW 기하 알고리즘의 가장 기초가 되는 알고리즘이다.가르쳐주신 분 말씀으로는 "대부분의 기하 문제는 CCW로 풀이가 가능하다." 라고 하실 정도니 꼭 알아두자. CCW는 벡터의 외적을 이용하여 평면상에 세 점이 있을 때 점들의 위치관계를 판단할수 있는 알고리즘이며, 회전방향이 반시계인 경우 양의 값, 시계인 경우 음의 값, 일직선 상에 있는 경우 0의 값을 가지게 된다. 점이 3개인 경우, [ A(x1,y1), B(x2,y2), C(x3,y3) ] 일 때, CCW(A,B,C) = (x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3) 2020. 4. 4.
피보나치 수 피보나치 수를 구하는 알고리즘은 여러가지다. 그 중 대표적으로 1. 재귀를 통한 단순 구현 (Top-down) [ O(2^(N/2)) ] 2. 반복문을 통한 단순 구현 || 메모이제이션 (Bottom-up) [ O(N) ]2. 1 피사노의 주기 3. 행렬을 통한 분할 정복 [ O(logN) ] 4. 일반항을 통한 계산 [ O(logN) ] N이 엄청 큰 경우 1, 2번 방법으론 시간내 풀 수 없으니 시간 복잡도가 O(logN)인 방법으로 해결해야한다. 3번, 행렬을 통한 분할 정복을 보자. 피보나치 식을 행렬로 표현하면 위와 같이 표현이 가능하다. 증명은 (여기)에서 볼 수 있다. N번째 피보나치 수를 구하기 위해서 제곱을 하면서 찾아가게 되는데 어떤 수의 제곱수 X^n = X^(n/2) * X^(n/2.. 2020. 4. 4.
[17142번] 연구소 3 17142번: 연구소 3 www.acmicpc.net 조합 + 탐색 문제 재귀를 통해서 활성시킬 바이러스를 선택 후 BFS를 통해 바이러스를 확산시켜 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485 #include #include #include #include #include using namespace std; int map[50][50], visit[50][50], arr[50][50];int drc[] = { 0,0,-1,1,-1,1,0,0 };int .. 2020. 4. 4.

티스토리툴바