나코더 방학 연습 2주차 풀이

2016. 8. 7. 12:55알고리즘 문제풀기/각종 OJ 풀이

1. 네 번째 점

네 번째 점의 x좌표는 주어진 점 중 단 하나에만 등장했을 것이고, y좌표 또한 마찬가지이다.
if문을 잘 써서 풀어도 되고, 좀 더 특이하게 혹은 편하게 풀고 싶다면, x좌표를 XOR(연산자 ^)시킨 것이 답의 x좌표와 같다. y좌표도 마찬가지.

2. 색종이

(p,q) 라는 지점에 색종이를 놓으면, x좌표가 p ~ (p+10), y좌표가 q ~ (q+10)에 있는 영역은 모두 색칠된다.
A[i][j] = (i,j), (i,j+1), (i+1,j+1), (i+1,j)가 이루는 정사각형이 색칠되어있는가?라는 boolean 배열을 잡고, 각각의 색종이에 대해서 A[p ~ (p+9)][q ~ (q+9)]를 true로 만들어주자.
그 후 true인 칸의 갯수를 세어주면 된다.

3. 악수

n=1일 때 답은 자명하게 한 가지이다.
n=2일 때 답은 자명하게 두 가지이다.

n번째 사람은 n-1번째 사람과만 악수할 수 있다.
만약에 악수를 한다면, n-1번째 사람은 n-2번째 사람과 악수할 수 없으므로, 1 ~ (n-2)번째 사람이 악수하는 방법의 수만큼의 방법이 있다.
만약에 악수를 하지 않는다면, n번째 사람은 있으나 없으나 상관이 없으므로, 1 ~ (n-1)번째 사람이 악수하는 방법의 수만큼의 방법이 있다.
즉, A[n] = n명의 사람이 악수하는 방법의 수라고 했을 때, 다음과 같은 식이 성립한다.

초기 항이 이므로, A는 피보나치 수의 꼴을 띄게 된다.
크기 10,000,000짜리 배열을 잡아도 되지만, 변수 세 개 정도만 잡고 계속 재활용해도 된다.
혹은 마지막 자리만 구하면 되므로, 여기서 규칙을 찾아도 된다.
1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0, 1 이 반복 단위이다.

4. 카드1

우리가 카드 더미를 어떻게 쓰고 있는지 생각해보자. 카드를 ‘꺼내는’ 위치는 제일 위이며, 카드를 ‘넣는’ 위치는 제일 밑이다. 카드를 넣으면, 그 위에 있던 카드가 점점 빠지며 자신은 위로 올라갈 것이다.

FIFO(First-In First-Out)
먼저 넣은 원소가 먼저 나오는 구조를 뜻한다. 이러한 성질을 만족하는 대표적인 자료구조로는 큐(queue)가 있다.

카드 더미를 큐라고 생각해보자. 카드를 꺼내는 것은 큐의 pop 연산에 해당하며, 카드 더미 밑에 카드를 넣는 것은 큐의 push 연산에 해당한다.
큐의 구현 방법은 크게 배열과 STL이 있겠다.

1. 큐의 배열 구현

큐의 원소들이 어떤 배열의 구간에 들어있다고 생각하는 방법이다.
큐를 나타내는 배열 A를 잡고, headtail, 두 개의 정수형 변수를 잡자.
정의는 이러하다.

큐의 원소는 A[head] ~ A[tail-1] 이며, pop할 때 나오는 원소는 A[head]이다.

코드
x라는 원소를 넣고 싶다면? A[tail++]=x;
큐의 가장 앞의 원소를 가져오고 싶다면? a = A[head];
큐의 가장 앞의 원소를 제거하고 싶다면? ++head;
큐의 원소의 갯수는? tail-head
큐에 원소가 남아있는가? head<tail

이렇게 사용할 수 있다.

2. 큐의 STL 구현

먼저 큐를 사용하기 위해 #include <queue>를 하자.
std::queue<타입> 변수명; 형태로 큐를 선언할 수 있다.
queue<int> q; 형태로 선언했다고 하자.

코드
x라는 원소를 넣고 싶다면? q.push(x);
큐의 가장 앞의 원소를 가져오고 싶다면? a = q.front();
큐의 가장 앞의 원소를 제거하고 싶다면? q.pop();
큐의 원소의 갯수는? q.size()
큐에 원소가 남아있는가? q.empty()

STL의 queue에서 주의할 점은, pop() 함수이다.
pop() 함수는 큐의 가장 앞의 원소를 (존재한다면) 없애주는 역할을 하며, 그 원소가 무엇인지는 반환하지 않는다. 즉 void형으로 선언되어있다.
가장 앞의 원소를 참조하려면 front() 함수를 사용해야 한다.

또한, 모든 STL(vector, queue, stack, deque, set, map, …)의 size() 함수의 반환형은 unsigned int 혹은 unsigned long long int형이다. 이것이 어떤 문제를 일으킬 수 있는지는 다음 예제를 통해 확인해보자.

// using namespace std; 된 상태
queue<int> q;
q.push(1);
while(q.size()-2 > 0){
    cout << q.front() << endl;
    q.pop();
}

얼핏 보면 아무 것도 실행되지 않을 것 같지만, 실제로는 무한 루프를 돌거나 런타임 에러가 발생한다.
q.size()unsigned이기 때문에, -2에 의해 음수가 되려고 하면 자동으로 (혹은 )가 더해진다.

즉 이 상황에서 q.size()-2는 4294967295 혹은 18446744073709551615가 되는 것이다.
당연히 양수이므로 while문이 진행되고, pop()을 해서 큐가 비어있게 된 뒤에도 각각 4294967294 혹은 18446744073709551614가 된다.
계속 없는 원소를 참조하며 pop()을 시도하니 문제가 생길 수밖에.

이런 문제를 피하기 위해서는,

  • size() 함수를 쓸 때는 항상 int로 캐스팅한다.
    ex) while((int)q.size() - 2 > 0)
  • size() 함수의 값에서 다른 값을 빼지 말고, 반대편에 더해서 계산한다.
    ex) while(q.size() > 2)

만약 int형과 unsigned int형의 수를 비교하면 int형이 강제로 unsigned int형으로 바뀌며, 이 과정에서 음수는 그 값이 크게 변하게 된다.
이런 일이 일어날 수 있을 땐 컴파일러가 직접 경고(comparison between signed and unsigned integer expressions)해준다. 경고를 눈여겨보고, 위험한 부분이 있다면 꼭 고치자.

5. 가장 큰 증가 부분 수열

dp[i] = i번째 수가 마지막인 증가 부분 수열 중 합이 가장 큰 것의 합 으로 정의하자.
주어진 배열은 A라고 하자.
수 하나만 있는 것도 증가 부분 수열이므로, 일단 dp[i]가 될 수 있는 값은 A[i]가 있다.
j<i, A[j]<A[i]j가 있다면, A[j]에서 끝나는 증가 부분 수열에 A[i]를 이을 수 있으므로, dp[j]+A[i] 또한 dp[i]가 될 수 있다.
dp[i]가 될 수 있는 값중 최댓값을 dp[i]로 설정하면 된다.

출력할 답은 dp[i] 중 최댓값이다.

6. 겹치는 선분

현재 x좌표에 겹치는 선분이 몇 개 있는지를 알려주는 기계가 있다고 상상해보자. 이 기계를 에서부터 까지 쭉 민다고 생각해보자.
선분의 시작점을 만나면 기계의 값이 1 늘어날 것이고, 끝점을 만나면 1 줄어들 것이다.
즉 이 기계의 값이 바뀔 일(=사건, event)은 총 2N번 있다. 이 사건들을 x좌표를 기준으로 정렬해서 순서대로 보면, 특정 x좌표에서 몇 개의 구간이 겹치는지를 알 수 있을 것이다. 그러한 값 중 최댓값을 구하면 된다.

‘선분이 끝 점에서 겹치는 것은 겹치는 것으로 세지 않는다.’ 라는 조건이 있다. 같은 좌표에 여러 사건들이 있다면, 그 좌표에서 -1이 되는 사건과 +1이 되는 사건 중 -1을 먼저 보아야 한다는 이야기가 된다. 예를 들어 [1~2], [2~3]의 구간이 있다고 하면, x=2에서는 [1~2]가 빠진 후 [2~3]이 들어와야 정확한 갯수를 알 수 있다는 것이다. 이를 잘 고려하자.

7. 예산

글을 보자

8. 전봇대

삼분탐색을 할 수 있다.

9. 플로이드

Floyd-Warshall 알고리즘을 사용하면 된다.

10. 말

번째 해에 말을 팔면 만큼의 돈을 벌 수 있다.
여기서 가 매우 클 수 있기 때문에, 이 값에 를 취해보자.
그러면 가 된다.
이 값은 원래 값보다 훨씬 작고, double의 범위 안에 충분히 들어간다.
이때문에 세그먼트 트리를 이용하면 어느 해에 말을 파는 것이 가장 좋은지를 알 수 있다.
원래 값을 취한 값을 가지고 있는 별도의 세그먼트 트리를 유지하면서 그 해에 대한 답을 구하면 된다.
글로 쓰기에는 한계가 있기 때문에 자세한 설명은 생략.

'알고리즘 문제풀기 > 각종 OJ 풀이' 카테고리의 다른 글

AtCoder  (0) 2016.09.04
나코더 방학 연습 1주차 풀이  (0) 2016.07.28
1591: 수열 복원  (0) 2016.03.08
[algospot] [NUMB3RS] 두니발 박사의 탈옥  (0) 2014.05.30
[KOISTUDY] [017D] [381] 격자 읽기  (0) 2014.02.25