mojo's Blog

문제 링크 => 6086번: 최대 유량 (acmicpc.net) 6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc.net 최대 유량 문제이다. Edmond-carp Algorithm 을 이용하여 해결하였다. 문제에서 활용될 노드는 'A' ~ 'Z', 'a' ~ 'z' 이므로 총 52개의 노드가 필요하다. Input 을 보면 from, to, capacity 가 제공되는데 여기서 from, to 가 중복해서 나타나는 경우가 존재한다. 따라서 capacity를 노드에서 노드로 이동하는 2차원 배열 c[x][..

문제 링크 => Problem - C - Codeforces Problem - C - Codeforces codeforces.com 그래프를 이용한 문제이다. 주어진 조건으로 얻은 그래프를 통해서 무조건 한번만 마을을 방문하여 모든 마을을 방문할 수 있는지를 묻는 문제이다. 문제에서 주어진 조건을 단순하게 요약하면 다음과 같다. n(1~10000, 정수)값이 주어질 때, (1) 1 번째 마을에서 2 번째 마을로 가는 도로 존재 2 번째 마을에서 3 번째 마을로 가는 도로 존재 ... (n - 1) 번째 마을에서 n 번째 마을로 가는 도로 존재 (2) ai = 0 ) i 번째 마을에서 (n + 1) 번째 마을로 가는 도로 존재 ai = 1 ) (n + 1) 번째 마을에서 i 번째 마을로 가는 도로 존재 확..

문제 링크 => Problem - B - Codeforces Problem - B - Codeforces codeforces.com dp + greedy 문제이다. 이 문제는 'R', 'B' 가 최소한으로 연달아 나타나도록 '?' 문자를 'R', 'B' 둘 중에 하나를 채워 넣는 문제이다. 그래서 임의의 문자열을 s1, s2를 둬서 s1 같은 경우는 'R' => 'B' => 'R' => ... 식으로 채우도록 하고 s2 같은 경우는 s1의 문자와 반대로 'B' => 'R' => 'B' => ... 식으로 채우도록 하였다. 문제에서 제공된 문자열 하나를 살펴보도록 한다. S = "?R???BR" 가 주어졌을때, s1, s2를 채워가는 과정을 보이도록 하면 다음과 같다. S[0] = '?' => s1 = "..

문제 링크 => 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..