Red Salmon

출처 : https://www.acmicpc.net/problem/2672

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/2672.cpp

음..이문제는 정말 어렵게 풀었다. 사실 풀지 못하였고 다른사람의 코드를 보고 다시작성하였다. 그게 약 9개월 전이고 이번에 복습겸 다시 풀었다.

먼저 문제는 여러 직사각형의 전체 면적을 구하라고 하는데 입력이 소수이다. 배열에 다 때려박고 계산하는식의 계산을 할 수 없다. 이런걸  brute force라고 하는데 이건 알고리즘이 아니다. 

이 문제의 경우 이런식으로 생각하면 이해가 쉽다. 

이런식으로 도형이 나열되어 있다고 생각해보자. 전체 넓이이니 도형들을 세분화시켜서 그 합을 구해도 값은 같을 것이다.

즉 이런식으로 나누게 된다. 

필자는 귀찮아서 선을 전부 그리지 않았다. 더그려야한다. 대략적인 느낌만 알면 된다. 암튼 모든 점에 대하여 선을 나누면 무수히 많은 사각형이 나온다. 이 사각형들 중에 입력으로 들어온 사각형과 비교하여 포함이 된다면 그 값을 계속 더해주면 된다.

이 알고리즘의 경우 O(n^3) 이 되므로  n값이 크다면 역시 올바른 알고리즘이 되지 못한다. 그래서 과거 검색해보니 인덱스트리나 다른 알고리즘을 사용하면 O(lgn) 까지도 줄어든다고 한다. 그런데 너무 복잡하고 어려워서 포기했던 기억이 있다. 

그러나 이 문제를 풀기에는 n^3도 무방하니 이 알고리즘을 사용해도 되겠다. 그리고 범위를 찾는데 다음과 같이

bool chk(double x1, double x2, double y1, double y2, Rect rect)
{
    //return rect.x1x1 && rect.y1y1;
    return rect.x1<=x1 && rect.x2>=x2 && rect.y1<=y1 && rect.y2>=y2;
}
// 두가지 방법이 있다.

위 에 두가지 방법이 있는데 둘중 아무거나 써도 된다. 대부분의 코드를 보니 상단의 방법을 많이쓰고 과거 트리문제를 풀었을때도 저런 비교를 많이 한다. 하단의 방법도 맞으나, 가급적이면 상단의 방법을 쓰면서 이해하는게 응용하기 훨씬 쉬울거 같다.

출처 : https://www.acmicpc.net/problem/1018

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/1018.cpp

이 문제는 어려운 문제는 아니다. 입력 자체도 매우 작다. 그냥 단순 검색이면 끝난다. 내 생각에 이런 문제는 20~30분내에 반드시 풀어야 하는 문제이다. 문제는 올바른 체스판이 되기 위해서 바뀌어야 하는 블럭이 최소가 되는 경우이다.

알고리즘은 다음과 같다.

1. 완벽한 체스판을 만든다. (최상단 맨 왼쪽이 흰색일수도 검은색일수도 있다. 나는 흰색만 생각하여 오답을 맞았다.)

2. 입력받은 체스판의 한점을 기준으로 +8칸씩 하여 완벽한 체스판과 비교를 한다.

3. 완벽한 체스판과 다른점이 있는 최소값을 계속 계산한 후 출력한다.

원래 쉬운문제는 기록하지 않는데 대충 풀다가 놓친부분이 있어서 기록하였다.

출처 : https://www.acmicpc.net/problem/2512

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/2512.cpp

이 문제는 정보올림피아드 다운 문제였다. 어렵진 않지만 귀찮은 문제였다. 먼저 문제의 키포인트부터 보자.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 

첫번째 조건을 살펴보면 즉 이런말이다. 입력으로 들어온 n을 다합쳐도 m으로 입력한 값보다 작거나 같으면 요청한 금액을 그대로 집행한다는 말이다. 

두번째 조건은 상한선을 둔다는 말인데, 요청한 금액이 적은녀석들은 그대로 두면서 높은 요청은 전부 동일한 상한선을 두어 나눠준다는 말이다.

읽자마자 나누기가 생각났다. 이유는 모르겠다.

나의 알고리즘은 다음과 같다.

1. 입력값을 먼저 정렬해준다.

2. 입력값의 총 합과 m을 비교후 m이 더크거나 같으면 정렬된 값의 맨 마지막을 출력한다.(문제는 가장 큰값을 출력하라고 했다.)

3. 그 외의 경우에는 요소 하나를 m에서 빼고 나머지 값을 현재 남은 요청수대로 나눠준다. 근데 이 값이 만약 현재 요청값보다 크다면 그 값을 채택한다. 

만약 요청값보다 작다면 버려지는 금액이 발생하기 때문에 더 배정할 수 있다는 말이 된다. 
(이런 생각을 왜 했냐고 물으면 나도 모른다. 생각이 났다.)

4. 하지만 m값에서 요청한 n을 나눈값이 만약 채택한 값보다 크다면 m에서 n을 나눈 값을 출력한다. 그게 아니라면 3번에서 채택한 값을 출력한다.

왜냐면 만약 요청값이 전부다 크고, m값이 작을때는 채택한 값보다 단순히 나눠준값이 더 클수도있다. 그렇기 때문에 이런 조건을 추가해줘야한다.  이걸 찾는데 상당한 시간을 허비했다. 보통의 경우는 이런식으로 나눠주면 모든 요소에 공통적으로 배분할수있도록 값이 나오는데 당연히 그값은 크지 않다. 

정보 올림피아드 문제는 풀때마다 생각하지만, 항상 까다롭고 귀찮은 예외 케이스가 존재한다. 이걸 한번에 생각하고 코딩하거나 그런 예외따위 무시하게만들면 최고의 알고리즘이지만 이처럼 예외가 발생하는 경우가 허다하다. 혼자 예제만드는 것또한 기술이라고 생각한다.

출처 : https://www.acmicpc.net/problem/2357

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/2357.cpp

저번에 풀어본 최소값과 똑같은 문제이다. 다만 이번엔 최대값이 추가되었다. 알고리즘이 완전히 동일하기 때문에 생략한다.

약간의 팁아닌 팁을 적자면, 나는 함수의 인자로 vector<int> &tree라고 썼는데, 참조연산자를 빼버리고 vector<int> tree해도 정답은 나온다. 

차이는 메모리차이이다. 참조연산자를 주게되면 주소값이 계속 전달된다. 그러나 단순 tree만주면 재귀를 하는 과정에서 자꾸 복사를 하게 된다. 그러면 메모리를 더 사용하게 된다. 이는 알고리즘 문제풀때뿐만이 아니라, 실제 프로젝트를 진행함에 있어서도 주의를 해야한다.

자바로 하는 프로젝트의 경우 상관이 없겠지만, 타이젠처럼 C언어를 사용하거나, 안드로이드의 네이티비를 만들고 있
다면 이런점은 반드시 생각하며 코딩해야 한다. 메모리를 줄이는 것은 매우 중요한 일이다.

그리고 하나더 현재 입력이 10만인데, 10만번을 입력받으면 매우 느리다. 이럴때는 C++이라고 할지언정 cin, cout보다는 scanf와 printf를 사용해야 한다.

시간적으로 굉장히 큰 차이가 있다. 그리고 요번에 본 문서에는 endl의경우 버퍼를 자동적으로 비워준다고 하니 기억해둬야겠다.