PS하는 깃털

문제 링크 : https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 풀이 이 문제는 이분 탐색을 사용하는 전형적인 문제이다. 랜선의 길이를 이용해서 이분 탐색을 하면 된다. 먼저, 왼쪽 포인터를 L, 오른쪽 포인터를 R라고 했을 때, 초기 값은 L=1, R은 랜선의 길이 중 최대 길이로 지정한다. 이제 이 둘의 평균인 M을 보면 두 가지 경우가 있다. 1. M의 길이로 랜선들을 나누었을 때 가능한 최대 개수가 N미만..

배열을 다루다보면 일정한 기준으로 그 배열을 정렬해야하는 상황이 생긴다. 이럴 때 C++ STL 에서 제공하는 sort()를 이용하면 편하다. sort()는 기본적으로 헤더파일에 속해있다. 그래서 이 함수를 쓰기 전에 먼저 헤더파일을 가져와야한다. #include 1) 배열(array) 배열을 정렬할 때는 sort()를 아래와 같이 사용한다. sort(시작주소, 끝주소 + 1) 시작주소는 (배열의 이름) + (번지수) 로 표기한다. 예를 들어 arr라는 배열의 1번지부터 시작하고 싶으면 arr+1로 나타낸다. 끝주소는 (배열의 이름) + (번지수)+1 로 표기하고, 예를 들어 n-1번지는 arr+n으로 표현한다. 2) 벡터(vector) 벡터를 정렬할 때에도 배열과 비슷한 방식을 사용한다. sort(v...

n²개의 정삼각형으로 이루어진 정삼각형 격자에서 정삼각형의 개수는 어떻게 셀까? 이 포스팅에서는 이에 대한 일반화를 해보려고 한다. 먼저 이러한 문제는 점화식으로 접근하는 것이 쉬울 것 같다. 먼저 사용할 점화식을 정의해주자. a(n,k) = |한 변의 길이가 n인 정삼각형 격자에서 한 변의 길이가 k인 정삼각형의 개수| 자명하게 a(n,1) = n², a(n,n) = 1이다. 이제 a(n,k)에 대해서 생각해보자. a(n,k) 을 계산할 때 위 그림에서도 볼 수 있듯이 a(n-1,k)에 새로 추가되는 정삼각형들을 더해주면 된다. 그럼 새로 추가되는 정삼각형의 개수를 구해보자. 1) 큰 정삼각형과 변이 평행한 정삼각형 이 경우는 구하는 정삼각형은 보라색 정삼각형이므로, n-k+1개가 된다. 2) 큰 정삼..

문제 링크 : https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 문제 풀이 이 문제에서는 사진틀의 개수와 추천횟수를 주고, 어떤 학생들을 추천했을 때 사진틀에 있는 사진들이 바뀌어 최종적으로 어떻게 되는지 묻고 있다. 나는 이 문제를 풀 때 여러 함수를 정의해서 풀었다. 먼저 사진틀에 사진들이 다 차있는지를 알아보는 full()과, 삭제할 학생을 찾는 remove(), 매 추천마다 사진틀의 시간을 더해주는 addTime()함수를 정의하였..

아마 대부분의 사람들이 픽의 정리를 들어본 적이 없을 것이다. 우리나라 교과과정에도 없고 KMO에서도 전혀 나오지 않는 내용이기 때문이다. 최근에 학원에서 이 정리에 대해 짧게 배운 적이 있다. 학원에서 들었을 때 꽤 흥미롭고 재미있어 보여서 추가로 찾아보았다. 여기서는 그런 내용들을 정리할 것이다. 또 이와 관련된 문제를 만들었는데, 그것도 풀어볼 것이다. 픽의 정리 꼭짓점이 격자점인 다각형에서 다각형의 내부에 있는 격자점의 수를 I 라고 하고, 다각형의 선분 위에 있는 격자점의 개수를 B라 할 때, 다각형의 넓이는 S = I + B/2 -1 로 나타낼 수 있다. 이것이 무슨 의미인지 직관적으로 이해가 가진 않지만 격자점에서 여러 도형의 넓이를 구해보면 픽의 정리가 성립함을 알 수 있다. 그럼 이제 증..

문제 링크 : https://www.acmicpc.net/problem/2628 2628번: 종이자르기 첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 www.acmicpc.net 문제 풀이 이 문제는 모눈종이의 가로, 세로의 길이와 모눈종이 상의 자르는 선을 주어줬을 때, 나눠진 부분 중 가장 넓이가 큰 부분을 구하는 문제이다. 최대 넓이를 구하려면 단순하게 가장 긴 가로 변과 가장 긴 세로 변의 길이를 구하면 된다. 구하는 방법은 먼저 column, row배열에 자르는 선인지에 대한 정보를 담고 각각의 배열에서 반복문을 1번씩만 돌아 최소길이를 구할 수 있다. ..

몬즈의 정리(Monge's Theorem)는 KMO 2차에 자주 나오는 정리로 근축에 대해 배울 때 꼭 배워야히는 정리 중 하나이다. 여기서는 몬즈의 정리와 이와 관련된 재미있는 문제 몇 개를 풀어볼 것이다. 몬즈의 정리 : 세 원 A,B,C가 두 점에서 서로 교차할 때, 세 공통현은 한 점에서 만난다. ( 세 원의 근축들은 공점선이다.) 참고하면 좋은 사이트 : https://en.wikipedia.org/wiki/Power_center_(geometry) Power center (geometry) - Wikipedia From Wikipedia, the free encyclopedia For 3 circles, the intersection of the radical axes of each pair ..

아마 KMO를 공부했던 사람이라면 페르마 포인트(Fermat Point)나 스타이너 포인트(Steiner Point)에 대해 들어본 적이 있을 것이다. 이들 모두 주어진 임의의 점들에 대한 기하 중앙값(Geometric median)과 관련이 있다. 이 글에서는 이들의 증명과 가중치가 주어질 경우에 대해서는 어떻게 하는지에 대한 내용을 정리하려고 한다. 아직 일반적인 증명을 할 정도까지의 수준은 아니기 때문에 삼각형과 사각형에 대해서 다룰 것이다. 기하 중앙값(Geometric median)의 정의 : 유클리드 평면에서 주어진 샘플 점들에 대해, 각각의 점들까지의 거리의 합이 최소가 되도록 하는 점 출처 : https://en.wikipedia.org/wiki/Geometric_median Geometr..

문제 링크 : https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 문제 풀이 이 문제에서는 좌석들의 정보(VIP여부)가 주어졌을 때 가능한 모든 좌석 배치의 경우의 수를 묻는 문제이다. 당연히 VIP 좌석 때문에 나눠진 좌석들끼리는 서로 영향을 주지 못하기 때문에 각각의 경우의 수를 구하고 곱해야겠다는 생각을 했다. 또 이 가능한 경우의 수는 DP를 이용하면 쉽게 구할 수 있었다. n명의 사람이 있고, VIP가 없을 때 가능한 좌석 배치를 D[n]이라고 하면,..

문제 링크 : https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 문제 풀이 문제에서는 볼들의 배열이 주어졌을 때 같은 색깔의 볼들을 한 쪽으로 모으는 최소 이동 횟수를 요구하고 있다. 처음 봤을 땐 왼쪽으로 빨간색을 다 모으는 경우, 파란색을 다 모으는 경우, 오른쪽으로 빨간색을 다 모으는 경우, 파란색을 다 모으는 경우 모두 나눠서 반복문을 4번 돌아 구한 다음, 최소를 출력하려고 했다. 근데 더 생각해보니 왼쪽이랑..