백준, boj) 2254. 감옥 건설 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/2254 2254번: 감옥 건설 첫째 줄에 N(1≤N≤1,000), Px, Py (-100,000≤Px, Py≤100,000)이 주어진다. 다음 N개의 줄에는 차례로 담 기둥의 좌표가 주어진다. 각각의 좌표는 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 2. 문제 개요 소들의 반란이 있은 뒤, 이 소들은 포로로 잡은 인간들을 감시해야 했다. 소들은 (Px, Py)의 위치에 감옥을 짓고 여러 겹으로 담을 쌓아 포로들이 도망가기 힘들도록 하려고 한다. 감옥은 하나의 점으로 표현된다. 소들은 감옥 주변에 N개의 담 기둥을 세웠다. 각각의 담은 감옥을 완전히 감싸야하고, 담 안에 포함되는 담이 있다면 완전히 ..
boj, 백준) 1708. 볼록 껍질 ( C / C++ )
1. 문제 링크 https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다고 가정해도 좋다. x�� www.acmicpc.net 2. 문제 개요 볼록 껍질(Convex hull)을 만드는 최소 점의 개수를 출력하는 프로그램을 작성하시오 3. 문제 힌트 알고리즘을 알고 있어야 한다. 간단히 설명하면, 0번점을 시작으로 2번점이 0->1을 이은 벡터의 시계 반대방향에 있는지, 시계방향에 있는지 구분하는 부분을 작성해야 한다. 다른 블로그에 알고리즘에 대한 설명이 잘 나와있으니까 코드는 아니..
boj, 백준) 19237. 어른상어 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 2. 문제 개요 상어에는 1에서 M이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다. N*N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자..
boj, 백준) 2670. 연속부분최대곱 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 N개의 양의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면, 색칠된 www.acmicpc.net 2. 문제 개요 N개의 양의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아 그 곱을 출력하는 프로그램을 작성하시오. 3. 문제 힌트 우선 모두 자기 자신만 곱한 걸 나타내기 위해 초기화는 자기 자신들로 해주자. 곱해 나갈 때, 곱한 결과가 자기 자신보다 크다면 누적하는 그런 형태로 나타내 주자. 음수가 없기 때문에 문제는 없다. 코드를 보는 편이 ..
boj, 백준) 1733.등번호 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/1733 1733번: 등번호 첫째 줄에 티셔츠의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 이후 N개의 행에 각 티셔츠의 정보가 두 개의 자연수로 주어진다. 이는 티셔츠의 안쪽과 바깥쪽에 적힌 등번호이다. 각 등번호는 1이상 www.acmicpc.net 2. 문제 개요 한 선수가 최대 두 가지의 번호를 부여받을 수 있다. 각 선수들이 어떤 번호를 선택해야 모든 선수들의 번호가 중복되지 않을 수 있을지 구하는 문제. 3. 문제 힌트 일반적인 O(VE)시간복잡도의 이분 매칭으로는 시간 초과다. 호프 크로프트 카프 알고리즘 O(V^(1/2) E)을 사용하자. 그리고 불가능하다면 불가능한 선수만 -1로 출력하지말고 전체 출력..
boj, 백준) 2051. 최소 버텍스 커버 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/2051 2051번: 최소 버텍스 커버 A와 B로 나누어져 있는 이분 그래프가 입력으로 주어진다. A에는 정점이 N개가 있고, B에는 정점이 M개가 있다. 정점은 A의 정점은 1번부터 N번, B의 정점도 1번부터 M번가지 번호가 매겨져 있다. A의 www.acmicpc.net 2. 문제 개요 이분 그래프의 최소 버텍스 커버(Minimum Vertex Cover)를 구하는 프로그램을 작성하시오. 단, 어떤 Node들이 Vertec cover를 구성하는지 출력할 것. 3. 문제 힌트 쾨닉의 정리에 의해서 최소 버텍스 커버 C의 개수는 이분 매칭의 최대 매칭 값 M과 같다. 어떤 노드들이 버텍스 커버C를 구성하는지 구하는 방법은 C = ..