mojo's Blog

문제 링크 => 3190번: 뱀 (acmicpc.net) 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net Deque 를 이용하는 문제이다. 뱀의 초기 위치를 (1, 1), 방향은 오른쪽이라고 주어졌고, 사과를 먹으면 뱀의 길이가 증가하고 먹지 못하면 뱀의 길이는 그대로이다. 뱀의 머리 부분과 꼬리 부분을 Deque 의 front, back 이라고 두고 사과를 먹은 경우와 안 먹은 경우를 살펴보도록 한다. 사과를 먹은 경우 ) front 에 뱀이 다음으로 이동할 위치(nextX, nextY) 를 push 해주고 fro..

문제 링크 => 2254번: 감옥 건설 (acmicpc.net) 2254번: 감옥 건설 첫째 줄에 N(1≤N≤1,000), Px, Py (-100,000≤Px, Py≤100,000)이 주어진다. 다음 N개의 줄에는 차례로 담 기둥의 좌표가 주어진다. 각각의 좌표는 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 볼록 껍질을 이용한 문제이다. 볼록 껍질을 형성하는 과정은 Graham Scan 방식을 이용하여 접근하였다. 다각형을 형성할 때 가장 바깥쪽에 위치하는 점들을 이용하여 다각형을 형성하고 소의 위치가 다각형 내부에 존재하는지 파악하면 된다. 소의 위치가 다각형 내부에 존재하는지 파악하는 여부는 CCW(cow, pi, p(i+1)) 의 값이 모두 동일한 경우 존재하고 그렇지..

문제 링크 => 16491번: 대피소 찾기 (acmicpc.net) 16491번: 대피소 찾기 지구에서 보낸 화성표면 탐사로봇은 2032년 현재 100개 이상이고, 그 개수가 빠르게 증가하고있다. 그 이유는 지구에는 없는 귀중한 금속 자원이 화성표면에서 속 속 발견되고 있기 때문이다. 화 www.acmicpc.net CCW 를 이용하는 문제이다. 대피소를 연결할 수 있는 모든 경우의 수 N! 를 permutation 을 통해서 구할 수 있고, 로봇과 대피소를 연결한 벡터 N개에 대하여 ((N-1)N / 2) 개 일때 모두 선분 교차가 일어나지 않는 경우 해당 대피소의 번호를 출력하면 된다. 일직선 위에 점이 존재하지 않는다는 조건이 없으므로 [백준 17386] 선분 교차 1 :: M - J - C (ti..

문제 링크 => 17386번: 선분 교차 1 (acmicpc.net) 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net CCW 를 이용하여 해결하는 문제이다. CCW 를 이용하는 문제 링크 => [백준 11758] CCW :: M - J - C (tistory.com) 를 참고하면 좋을듯 하다. 세 점이 일직선 위에 있는 경우가 없으므로 다음을 만족하는지를 판단하면 끝이다. CCW(A, B, C) * CCW(A, B, D) < 0 이면서 CCW(C, D, A) * CCW(C, D, B) < 0 이여야 한다. 좌표 값이 1,000,0..

문제 링크 => 11758번: CCW (acmicpc.net) 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 외적을 이용하는 문제이다. 삼각형 ABC 가 있다고 할 때, 벡터 a를 점 A에서 B로 가는 벡터라 하고 벡터 b를 점 A에서 C로 가는 벡터라고 가정한다. 외적의 성질을 통해 a x b = |a||b| sin(t) 가 성립한다. 이때 sin(t) > 0 일때 점 C는 선분 AB 의 위에 존재하므로 반시계 방향이다. 반대로 sin(t)..

문제 링크 => 1701번: Cubeditor (acmicpc.net) 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net KMP 를 이용하는 문제이다. 임의의 문자열 S = "baacaa" 가 있다고 가정하자. KMP Table 를 다음과 같은 과정으로 만들도록 한다. "baacaa" => [ 0, 0, 0, 0, 0, 0 ] "aacaa" => [ 0, 1, 0, 1, 2 ] "acaa" => [ 0, 0, 1, 0 ] "caa" => [ 0, 0, 0 ] "aa" => ..