2016년 12월 23일 금요일

BOJ 2311 왕복 여행

mcmf로 풀 수 있는 문제이다.
1 -> N -> 1 에 소요되는 최소 시간을 구해야 하는데, 한 번 지나간 길은 다시 갈 수 없다.
한 번 지나간 길을 다시 갈 수 없다는 것을 각 길에 대해서 capacity를 1로 놓음으로써 해결할 수 있고, 왕복하는 것은 src->1->N->sink 에서 src->1, N->sink 의 capacity를 2로 놓음으로써 1에서 N까지 각 길을 한 번만 거치고 갈 수 있는 두 가지 경로를 구하는 것과 왕복하는 경로와 같다는 것을 이용해서 푼다. 정말 멋진 풀이다...

그런데, 양방향 간선인 점에서 좀 헷갈리는 부분이 있었다. 양방향 간선이므로 양방향으로 capacity를 1씩 주게 되는데, 그렇게 되면 한 번 지나간 길을 반대 방향으로 한 번 더 지나가게 될 수 있지 않을까? 라는 생각이 들었다.

오랜 고민 끝에, 그럴리 없다는 것을 알게 되었다. 바로 한 번 지나간 길(cost)의 반대 방향의 residual capacity는 1이되고 코스트는 -cost이다. 그렇기 때문에 capacity가 1이고 cost인 것을 선택하지 않고 -cost인 것을 선택하게 될 것이다.(mcmf에서는 bfs나 dfs가 아닌 최단 거리를 구하는 알고리즘으로 augment path를 찾기 때문에!) 즉, 만약 한 번 지나간 길의 반대 방향으로 한 번 더 지나가게 된다면 사실 그것은 한 번 더 지나가는 것이 아니라 상쇄하는 것이 된다. 즉, 그 길은 지나가지 않은 셈 치게 되는 것이다.

이 문제로 인해 좀 network flow에 대해 좀 더 이해할 수 있었다.

그리고 mcmf를 사용하지 않고도 풀 수 있는 방법이 있다. appa님이 질문게시판에 소개한 방법인데, 생각해보면 network flow의 원리와 비슷한 것 같기도 하고, 정말 멋있는 방법이다. 링크 -> https://www.acmicpc.net/board/view/8285
-1을 곱하는 것은 N에서 1로 가는 경로를 찾을 때, 어떤 길을 가지 않은 셈 치는, 즉 상쇄하는 효과를 주는 것 같다.

직접 예제를 가지고 해보면 이해가 더 빠르다.

내가 사용했던 예제
5 8
1 4 1
4 3 1
1 2 1
2 3 1
3 5 1
2 5 3
1 5 10
5 4 10

답은 7



2016년 12월 21일 수요일

BOJ 9576 책 나눠주기

이 문제는 greedy 로 풀어야 한다.
일단 이분 매칭으로 풀어도 풀리긴 하는데 시간이 매우 오래 걸리고... O(VE) 이므로 데이터가 빡빡하게 들어오면 시간초과가 날 것 같다.

일단 greedy... 생각을 많이, 신중하게 하고 확실한 근거를 가지고 해야 하는데 대충 짐작으로 짰더니 틀렸다. 그리고 한 동안 왜 틀렸는지도 전혀 깨닫지 못했다... (애초에 내가 푼 방법에 대한 명확한 근거가 없었으니...)
(a번, b번)을 sorting하되 a번을 기준으로 sorting하고 a값이 같은 경우 b를 기준으로 sorting해서 앞에서부터 하나씩 선택하는 식으로 했는데, 반례를 찾았다.

1 ->test case 개수
3 3 -> n, m
//a, b값
1 3 
1 3
2 2

인 경우 이다. 생각해보면... 어렵다.
일단 드는 생각이... 그렇다면, b-a값이 작은 순으로 sorting을 해야하는 것인가?
몇몇 분의 코드를 봤는데 기억나는 코드가 b값을 기준으로 sorting하고, b값이 같으면 a값을 기준으로 sorting한 것 같은데... 이렇게 해도 되는 것인지 확실하게 입증을 못하겠다.
물론 b-a값이 작은 순으로 한다고 해서 맞는 것인지도 확실하게 증명은 못 하겠다.

일단 제출해 봐야겠다.... 틀렸다...
반례가 있는 것인가... 반례는 비교적 빨리 찾을 수 있었다.

n : 4, m : 4
//a, b값
1 1
2 2
1 3
3 4

인 경우이다. 일단 1 1, 2 2 인 경우를 먼저 처리하고 3 4를 처리할 때, 내 코드에서는 앞에 것을 먼저 선택하기 때문에 3을 선택하게 되고, 자연히 뒤에 오는 1 3을 처리할 때 아무 것도 선택할 수 없게된다. 
그렇다고 뒤에서부터 선택하는 것은 해결책이 될 수 없다. 유사한 반례가 생긴다.

그리고 다른 분 코드를 봤는데, 
b값을 기준으로 오름차순 sorting, b값이 같을 경우 a값 기준으로 내림차순 sorting...

일단 나중에 좀 더 공부하고 다시 풀어 봐야겟다...

2016년 12월 8일 목요일

BOJ 12785 토쟁이의 등굣길

토쟁이가.... 등교하면서 토스트를 사먹어서 토쟁이였다!!!

항상 최단 거리로 가야하고, 토스트 가게를 거쳐가야 하므로... 이 문제는
초, 중 학교 수학시간에 자주 본 문제같다.

즉 (집에서 토스트 가게까지의 경로의 수 * 토스트 가게에서 학교까지의 경로의 수) 가 답이 될 것인데, 예전에 이런 걸 계산할 때 보면 1, 1, 을 가장자리에 적어놓고 더하고 또 더하는 식으로...
즉, d[x][y] = d[x-1][y] + d[x][y-1] 로 나타낼 수 있겠다.

한 번 코드를 짜봐야겠다.
결국 AC를 받긴했는데... 좀 틀렸다.
long long값이 나오는 것과, x, y의 각각의 길이에 맞게 초기화를 잘 해줘야 하는데 x에 해당하는 길이만 초기화 한 것도 문제였다...

2016년 12월 6일 화요일

BOJ 1049 기타줄

기타줄이 N개 필요한데, 기타줄을  6개씩 묶어서 팔거나 낱개로 팔기도 한다.
6개씩 묶어서 파는 가격과 낱개의 가격이 주어질 때, 기타줄을 적어도 N개 사기 위해 필요한 돈의 최소값을 구하는 문제이다.

N개만 사는 최소 비용을 구하는 문제라면 동전dp처럼 풀면 될 것 같은데... 음 이건 N개 이상을 사는 최소 비용을 구하는 문제라고 볼 수 있으니
d[N] = N개 이상의 기타줄을 구매하기 위해 필요한 최소 비용 ...
음... 문제 분류를 얼떨결에 봐버렸다.
그리디 알고리즘으로 돼있다... 아...

그렇다. 다시 생각해보니 굳이 dp를 쓸 필요가 없다...
지금 브랜드 별로 6개짜리 묶음 가격과 낱개 가격이 주어지는데, 6개 묶음 가격중에서, 낱개 가격중에서 각각 제일 싼 가격을 택하면 된다.
즉, 이 문제는 6개 묶음 가격과 낱개 가격이 하나씩만 주어지는 문제가 되는 것이다.

그리고 6개 묶음 가격이 낱개로 했을 때는 얼마인지 보고, 6개 이상의 기타줄에 대해서는 낱개로 사는 것이 나은지 6개묶음으로 사는 것이 나은지 판단해본다.

그리고 낱개로 사는 것이 더 낫다면 바로 답을 구할 수 있을 것이고,
그게 아니라면 좀 더 생각해 봐야한다.
6개묶음으로 사는 것이 더 쌀 경우 N이 6의 배수라면 답이 나올 것인데, 그렇지 않다면 좀 더 생각해 봐야한다.

N이 6의 배수가 아니라면
 (N/6+1) * (묶음 가격) 이 더 싼지, (N/6) * (묶음 가격) + (N%6) * (낱개 가격) 이 더 싼지 비교해봐서 답을 구하면 될 것이다.


2016년 12월 5일 월요일

LeetCode OJ - 446. Arithmetic Slices II - Subsequence

N개의 숫자로 구성된 수열이 주어지면 그 수열의 부분 수열(연속되지 않아도 되고 순서만 맞게 선택되면 된다.)이면서 등차 수열인 수의 개수를 구하는 문제이다.

dp로 풀어야 한다.
d[cur][pre] = 현재 수가 arr[cur]이고 이전의 수가 arr[pre]인 경우의 등차 수열인 부분 수열의 개수

입력으로는 서로 다른 오름차순의 수가 들어오는 것 같으니...(해석을 잘 못해서 정확치는 않다.)
d[cur][pre] = pre-ppree==cur-pre 인 경우, d[pre][ppre]+1 (원래 ....pppre-ppre-pre-cur 로 이루어진 수열의 개수와 ppre-pre-cur 수열의 1개를 더해준 것)

근데 이렇게 할 경우 O(N의 세제곱)정도의 시간복잡도가 나오기 때문에 좀 힘들어보인다... 일단 C++로는 99개의 테스트 케이스 대부분을 통과했지만 내 기억으로는 98번째 데이터에서 시간초과를 받았다. 그런데 그 코드를 그대로 자바 코드로 옮겨서 제출했더니 통과했다...

음.. 일단 이 문제 관련 discussion 게시판에 가서 O(N제곱)이 걸리는 풀이를 봤다.
힌트에는 binary tree라고 되어있었는데... 보니까 map을 쓰는 것이었다.
그럼 정확히는 O(N제곱*logN)인가... 여튼, 예전에 이런 식으로 푸는 문제를 본 적이 있는 것 같은데...  전혀 생각도 못했다.

d[cur][by] = arr[cur]를 마지막으로 하고 차이가 by인 등차수열의 개수
로 하는 것 같다. 이 방법은 사실 처음에 생각했던 방법인데, 차이값이 최대 int형 범위까지 나올 수 있어서 너무 크기 때문에, 그리고 음수가 나올 수도 있기 때문에 배열을 못 잡을 것이라고 생각했다... 아 그런데 map이 있었지... map을 이용한 dp... 예전에 풀었던 것 같은데... 그래도 지금이라도 봤으니 다행이다.

d[cur][by] = SUM(arr[cur]-arr[pre]==by인 pre에 대하여, d[pre][by]+1)
이 될 것이다.
그리고 by는 최대 N개가 나올 수 밖에 없으므로 모든 수에 대해 다 돌리지 말고 N개의 by에 대해서만 보면 된다.

이게 구현하는 과정에서 좀 고려해야할 것이 있다. 이 문제에서 요구하는 등차수열은 길이가 3이상이어야 한다. 그렇기 때문에 길이가 2인 등차수열을 잘 처리해줘야 하는데...
1, 1, 2, 3 이 주어지면 아마 1, 2, 3을 두 개 만들 수 있으므로 2가 나와야 하는데 나는 보통은 두 개 짜리의 개수는 항상 0으로 처리해서 이 경우 1이 나왔다.
그리고 최종 답은 cur, by에 대해 모든 경우를 다 더해봐야 하는데, 두 개인 경우가 0일 때는 괜찮았는데, 두 개인 경우도 개수를 부여하면 이제는 두 개인 경우가 뭔지 구분을 해야하는데... 어렵다..

그래서 고민 끝에 재귀로 한 번 짜보기로 했다. 재귀로 해도 여전히 어렵다...

결국 다시 discussion의 정답 코드를 분석해보다가 이해했다.
지금 문제가 두 개인 경우는 등차수열이 아니기 때문에 0으로 처리할 경우 1, 1, 2, 3 같은 예제에서 cur==2, by==1일 때 경우의 수가 0이되어 답이 1이 나오게 되는 것인데...
(문제를 다시 잘 읽어보면 1, 2, 3이라고 경우의 수가 1이 되는 것이 아니다. 인덱스상으로 1, 2, 3은 두 가지가 나온다. 문제에서는 인덱스를 기준으로 해서 등차수열의 개수를 구하라고 하고 있다.) 정답 코드들은 길이가 2인 경우를 0으로 치지 않고 개수가 있는 것으로 친다. 즉, 길이가 2인 경우도 센다(count한다).
그러면 또 위에서 고민했던 두 개인 경우가 뭔지 구분해서 최종 답에는 합산하지 않아야 한다. 하지만 그렇게 처리하지 않는다. 등차수열이 되는 경우를 보자. 길이가 3인 어떤 등차수열X의 개수는 (수열X에 포함되는 길이가 2인 등차수열 개수)들의 합이된다. 결국 길이가 3인 등차수열의 개수를 구하면서 최종 답 ans 변수에는 길이가 3인 등차수열의 개수를 구할 때 이용되는 길이가 2인 등차수열의 개수를 더해준다.
그리고 코드상으로는 길이가 3인 등차수열의 개수에 +1을 해준다.
그렇다면 길이가 3인 등차수열의 개수는 어디에 쓸까? 바로 길이가 4인 등차수열의 개수를 구할 때 쓸 것인데, 이제 여기서부터는.. 길이가 4인 등차수열의 개수는 (길이가 3인 등차수열 개수 + 1) 들의 합이다. +1이 의미하는 것은 길이가 하나 늘어나면서 끝에서부터 길이가 3개짜리인 등차수열이 하나 더 생긴다는 의미이다.  하지만 +1은 나중에 해주고, ㅇ위에서 처럼 (길이가 3인 등차수열 개수)들의 합을 최종 답ans에 더해주고, 길이가 4인 등차수열의 개수로 저장한다.

현재 길이가 2인 등차수열의 개수를 인정했기 때문에 길이가 2인 등차수열의 개수는 사실 길이가 3인 등차수열의 개수를 뜻하게 되고, 길이가 3인 등차수열의 개수는 (길이가 2인 등차수열의 개수+1한 값들의 합이기 때문에) 길이가 4인 등차수열의 개수를 가리키게 된다... 즉, 이렇게 계속 길이가 n인 등차수열의 개수를 구해 나가되, 실제로는 길이가 n+1인 등차수열의 개수를 의미하므로 최종답 ans에는 길이가 2인 등차수열의 개수부터 n-1인 등차수열의 개수만 저장하면 되는 것이다.

(참고로 이해를 위해 등차수열의 길이를 언급했지만 사실 등차수열의 길이를 이용해서 푸는 것은 아님.)

여기서 중요한 것은 같은 등차수열이여도 인덱스 구성이 다르면 다른 것으로 쳐서 count해줘야 하고 길이가 3이상인 등차수열부터 인정이 되므로 길이가 2인 등차수열의 개수는 0인데, 이렇게 할 경우 인덱스 구성이 다른 것을 카운트하지 못하게 되는 문제가 있었고, 그렇다고 길이가 2인 등차수열의 개수를 count해 버리면 나중에 답을 구할 때, 길이가 2인 것을 어떻게 구별해서 제거할 것인가 하는 문제가 있었는데,
길이가 2인 등차수열의 개수를 count하고 원래 구하는 방식대로 구해나가되, 길이가 2인 등차수열의 개수는 (길이가 2인 그 수열들을 포함하는) 길이가 3인 등차수열의 개수와 같고, 길이가 n인 등차수열의 개수는 길이가 n인 등차수열을 구하기 위해 사용되는 길이가 n-1인 등차수열의 개수의 합이라는 것을 이용해서 결국 길이가 2인 등차수열의 개수부터 길이가 n-1인 등차수열의 개수만 답에 포함시켜 정답을 구할 수 있다.

좀 감격스럽다. 정말 하루 종일 이것만 생각한 것도 아니고 이것 때문에 아무것도 못했다고 해야되나 물론 내가 노력이 부족했지만... 그래도 끈기있게 붙들고 있었던 보람이 있는 것 같다. 비록 내가 생각을 못했지만 남의 코드를 이해했고, 새로운 접근 방식을 깨닫게 되었다. 난 무조건 길이가 n인 경우를 구해야 한다고 생각했는데... 길이가 2인 경우는 경우의 수를 무조건 0으로 둬야 한다고 생각했는데... 발상의 전환인가... 원리를 파고든 것인가.. 여튼 멋지다.

그런데 저렇게 구현해도 틀린다. 아무래도 map이 느려서 그런 것 같다. 이제 unordered_map을 공부할 차례다.... 음 어렵다.
일단 unordered_map에 대해 알지는 못하지만 unordered_map을 사용해서 (사실 사용하는 것도 어려웠다, 그리고 C++11에서 사용 가능) 구현했다.

그리고 깨달은 것이 이 문제에서 map의 기능은 2차원 배열에 대해서 필요한 것이 아니라 1차원 배열에만 필요하다. 그렇기 때문에 이 것을 이진탐색으로 구현해 봐도 될 것 같다... 막상 해보려고 하니까 이진탐색으로 하려면 정렬이 되어있어야 하는데.. 쉽지 않다. 그래서 map이 이진 트리를 사용하나보다...





2016년 12월 3일 토요일

BOJ 5012 불만 정렬

< 출처 >
http://xoding.tistory.com/158
http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220806808977

일단 구하고자 하는 세 수에서 가운데 수를 잡고, 가운데 수를 지정한 후 그 수보다 왼쪽에 있으면서 더 큰 수의 개수 오른쪽에 있으면서 더 큰 수의 개수를 곱해나가면서 답을 구할 수 있다고 한다.... 생각도 못했는데 대단하다...

그런데 여기서 어떻게 세그먼트 트리나 팬윅트리를 이용할 것이냐?

풀이와 코드를 봤지만 아직도 이해가 완벽히 되지 않았다.

일단 가운데 수를 앞에서부터 주어진 위치의 순서대로 보면서 나가보자.
가운데 수를 기준으로 왼쪽의 그 수보다 큰 수, 오른쪽의 그 수보다 작은 수가 각각 몇 개 있는지 알고 싶다. 세그먼트 트리나 팬윅트리에 무엇을 저장할 거냐면 처음에 입력받은 수의 개수를 저장할 것이다. 즉, 트리의 범위는 1에서 n까지가 되는 것이다.
그렇게 입력받은 수의 개수를 저장해두고 query(x, y)를 하면 주어진 수열에서 x이상 y이하의 수의 개수를 얻을 수 있는 것이다.

자, 왼쪽, 오른쪽을 각각 담당하는 트리 두 개를 만들자.  처음에는 일단 오른쪽 수들에 해당하는 트리를 입력받으면서 입력받은 수의 개수를 저장해 놓는다. 그리고 순서대로 볼 때, 왼쪽에 있는 자신보다 큰 수의 개수를 알고싶다. 맨 처음 수는 일단 왼쪽에 아무것도 없을 것이다. 그리고 실제로 왼쪽을 담당하는 트리에는 처음에는 아무것도 들어가있지 않다. 그럼 오른쪽을 보자. 오른쪽에 있는 수 중 자신보다 작은 수의 개수는 어떻게 구할까? 아까 만들어 놓은 오른쪽 담당 트리에서 현재 위치한 가운데 수보다 작은 수들의 합을 구하면 된다.
즉, query(1, cur-1)하면 될 것이다. 그러면 자신보다 오른쪽에 있으면서 작은 수들의 개수를 구할 수 있다.

그리고 다음이 중요하다. 이제 다음 가운데 수 후보를 볼텐데 넘어가기 전에 방금 가운데 수로 가정했던 수는 더 이상 다음 가운데 수보다 오른쪽에 있지 않기 때문에 오른쪽을 담당하는 트리에서 그 수에 해당하는 개수를 -1해서 지워버린다. 그리고 이제 다음 가운데 수 기준으로 왼쪽에 그 수가 들어가기 때문에 왼쪽을 담당하는 트리에서 그 수에 해당하는 개수를 +1해준다!

그렇다. 바로 트리 두 개로 왼쪽, 오른쪽에서 각각 어떤 수보다 크고 작은 수의 개수를 O(logN)만에 계산하되, 주어진 수들을 순서대로 보면서 더이상 어떤 수 기준으로 오른쪽에 있지 않은 수, 이제 왼쪽에 있게되는 수를 업데이트 해주면서 어떤 가운데 수를 기준으로 해서 원하는 값을 구할 수 있는 것이다.


그리고 트리를 하나만 사용하려면 왼쪽, 오른쪽의 개수를 따로 따로 구해서 배열에 넣어놓고 계산은 나중에 해주면 된다. 따로 구할 때 좋은 방법이 있는데, 트리에 값을 넣어놓지 말고 왼쪽의 경우 앞에서부터 보면서 집어넣고, 오른쪽의 경우 뒤에서부터 보면서 집어넣으면 된다. 아직 트리에 들어가지 않은 값들은 가운데 값보다 크다고 해도 왼쪽에 있는 값이 아니거나 작다고해도 오른쪽에 있는 값이 아니므로, 트리에 넣어주면서 즉 여태까지 살펴본 값들 중에서만 자신보다 작거나 큰 값의 개수를 세주면 된다!

그리고 이 문제는 +1, -1을 하기 때문에 Fenwick Tree가 편해보이는데, Segement Tree를 쓰더라도 조금 변형을 하면 된다. 여태까지 update(index, newValue...)에서 index에 해당하는 곳(leaf node)을 newValue로 교체했는데, index에 해당하는 leaf node에 +1, -1을 해주고 올라가면서 상위 노드들을 업데이트 해주면 되는 것이다. 간단한 것인데도 나는 블로그를 보고 알았다. 생각도 못했었다. 확실히 내가 아직도 세그먼트 트리에 대한 이해와, 응용력이 부족하다는 것을 느낀다.

< 출처 >
http://xoding.tistory.com/158
http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220806808977









2016년 12월 2일 금요일

BOJ 1275 커피숍

일반적인 세그먼트 트리 문제이길래, 세그먼트 트리를 구현하고 당연히 맞을 줄 알았는데 틀렸다. 문제에서 입력은 int형 범위랬지만 구간 합은 long long이 될 수 있을테니 long long을 사용했는데도... 그래서 다른 분의 블로그를 찾아봤는데, x번째에서 수에서 y번째 수까지의 합을 구하는 것에서 x<=y가 아닐 수도 있다....고 한다.

예전에 처음 세그먼트 트리를 풀고 다른 분의 코드에서 x<=y가 아닌 경우를 가정해서 구현된 것을 보고 나도 주의해야지 생각했던 것인데...
x>y인 경우 swap을 해서 냈는데, 또 WA를 받았다. 원인을 보니... swap함수를 만들 때, parameter를 포인터나 참조자를 쓰지않고 그냥 복사해서 넘기는 식으로 해버렸다...

결국 AC를 받았다.

FenwickTree로도 풀어봐야겠다.
오히려 FenwickTree로 할 때 더 고생했는데... 여러가지 함정이 있겠지만 가장 찾기 힘든 함정에 대해 써보겠다.
FenwickTree의 경우 point update를 할 때, 해당하는 숫자를 바꿔주는 것이 아니라 원래 숫자와의 차이만큼 더해주는 식으로 하는데, 입력으로 int형 정수가 주어져도 양의 정수와 음의 정수로 주어질 경우 그 차이값이 int형 범위를 넘을 수 있다! 그렇기 때문에 그 부분을 long long으로 처리해 줘야 한다.

물론 이런 문제들은 모든 변수를 long long으로 처리하면 일어나진 않겠지만... 주의해야할 점이다.


2016년 12월 1일 목요일

BOJ 13907 세금 - 벨만 포드, 다익스트라 공부하고 다시 풀어보기...

여러 도시들과 그 도시들을 잇는 도로와 통행료가 주어진다. 그리고 출발점 도시A와 목적지 도시B가 주어지는데 이 때, A에서 B로 가는 길의 통행료의 합이 가장 작은 경로를 구해야 한다. 정확히는 최소의 통행료를 구해야 하는데, 이럴 경우 다익스트라를 이용하면 쉽지만, 이 문제에서는 매 단계별로 모든 도로의 통행료가 입력에 각 단계별로 주어진 만큼 인상된다. 이 때, 각 단계별 A에서 B로 가는데 드는 통행료의 최소값을 구하는 문제이다.

매 단계별로 다익스트라를 다 돌려보는 것이 가장 쉬워보이지만 그럴 경우 TLE를 받게 된다. 어떻게 해야할까? 여러 방법이 있겠지만 난 다익스트라를 이용해서 풀어봤다.

이 문제에서 핵심은 A에서 B까지 몇 개의 길을 거쳐 갔는지이다. 각 단계에서 세금을 인상할 때, 모든 도로의 통행료가 인상되기 때문에 A에서 B까지 거쳐간 길이 많을 수록 전체 통행료가 많이 올라가게 된다. 즉, 몇 단계에 걸친 세금 인상마다 통행료가 최소인 경로가 달라질 수 있는 것이다. 
좀 더 생각해보면 세금이 인상됨에 따라 현재 최소인 경로보다 거쳐간 길의 개수가 적은 경로들이 최소가 될 가능성이 있는 경로들이다. 거쳐간 길이 많은 경로들은 그럴 가능성이 없다. 
그런데 여기서 더 이상 나아가진 못하고 일단은 다익스트라를 이용하되, 일반적인 다익스트라 알고리즘에서는 한 정점에서 다른 정점까지의 최단 거리를 구했다면, 이 문제를 풀 때는 한 정점에서 다른 정점까지 x개의 길을 거쳐가는 최단 거리를 구하는 식으로 생각해 봤다.

d[node] = src에서 node까지의 최단 거리... 였다면,
d[node][x] = src에서 node까지 x개의 길을 거쳐서 가는 최단 거리로 놓는다.

d[node][x] > d[node][x-1] + cost 이면 d[node][x]를 업데이트 해주는 식으로 다익스트라를 구현한다. 근데 도시의 개수가 1000개 그 도시들을 잇는 길의 개수가 30만개라서 처음에 
d[1001][300000]로 잡았다가 메모리 초과가 났는데, 생각해보니 저렇게 잡을 필요가 없다.
d[1001][1000]이면 된다. 왜냐하면 최단 경로는 최대 node-1개로 이루어질 수밖에 없기 때문이다. node-1개의 경로보다 많은 경로를 거치면 한 점을 두 번 이상 방문하게 되므로 불필요한 방문을 한 것이고 최단 경로가 될 수 없으므로 고려할 필요가 없다.

그리고 저렇게 구현하고도 또 틀렸는데, 내가 방문한 경로가 node-1을 넘어가는 경우도 그냥 나둬서 그런 것이었다. 중간에 node-1개를 방문했으면 그 node까지의 최단 거리는 더 이상 구할 필요가 없다.

그래서 결국 AC를 받았는데, 맞은 사람 목록에서 다른 사람들의 코드와 시간이 10배 정도 차이가 난다. Baekjoon Online judge게시판에 이 문제에 대한 풀이(서강대 대회 문제였다.)가 올라와 있다고 하니 보고 공부하고 다시 풀어봐야 겠다.

풀이를 봤는데 일단 접근은 비슷한 것 같은데 구현이 다익스트라가 아닌 벨만포드 비슷한 방식으로 한 것인데... 벨만포드를 까먹어서..(아..복습ㅠ) 왜 다익스트라보다 10배 정도나 빠른건지...제대로 이해하지는 못하고 다른 분들 코드도 보다가.. 다익스트라를 쓰신 것 같은데도 불구하고(게다가 자바로 구현하셨는데도...) 속도가 매우 빠른 분이 계셔서, 그 코드를 이해는 못했지만 다익스트라도 시간을 단축시킬 수 있다는 희망을 가지고 나도 내 코드에서 좀 더 시간을 단축시킬 방법을 고민해 봤다.

생각해보면 어떤 점 V까지의 최단 거리를 구할 때, V까지 n개의 길을 거쳐서 가는 최단 거리를 구했다고 치자. 근데 매번 세금이 오를 때마다 통행료가 길의 개수만큼 인상되기 때문에 V까지 같은 최단거리라면 길의 개수가 더 많은 경우는 볼 필요가 없다.
다익스트라 알고리즘에서 난 priority queue를 사용했기 때문에 최대한 pq에 들어가는 간선을 줄이면 시간과 메모리를 단축시킬 수 있을 것이다. 
V까지의 n개의 경로를 거쳐 간 최단 거리가 V까지의 n-1개 이하의 경로를 거쳐 간 최단 거리보다 같거나 혹은 크다면 더이상 V까지의 n개의 경로를 거쳐 간 경우와 그 경우에서 파생되는 경우는 볼 필요가 없어서 큐에 넣지 않았다. n-1개 이하의 경로를 거쳐간 최단 거리와 거기서 파생된 경우만 보면된다.
근데 n-1개 이하의 경로를 거쳐간 경우를 보기 위해서 for문을 n번 돌려주기 때문에(break을 넣긴 했지만) 오래 걸리지 않을까 걱정도 했지만... 제출해보니 시간이 무려 20배정도 단축됐다(메모리는 3배정도)... 내가 이 다익스트라에서 2차원 배열을 쓰는 경우의 시간 복잡도를 모르겠는 것도 있고 지금 다익스트라, 벨만포드등을 다시 공부해봐야 할 것 같아서 왜 이런 결과가 나왔는지 정확히 내 알고리즘의 개선이 얼마나 된건지 아니면 테스트 케이스가 약해서 그런건지.. 잘 모르겠다.  풀이는 dp로 이해하면 될 것이다.
일단 공부를 더 해보고 이 문제는 다시 풀어봐야 겠다.
-------------------------------------------------------------------------------------
풀이를 봤더니 dp였다.
d[n][r] = n번도시 까지 r개의 길을 거쳐 갈 수 있는 최단 거리
d[n][r] = min(d[pre][r-1], pre는 n번도시와 연결된 도시들) 혹은
d[here][r]을 이용해서 d[there][r+1]을 구할 수 있을 것이다.
d[src][0]=0으로 두고 배열을 채워 나가면 최단 거리가 구해질 것이다.

이렇게 dp로 구현하면서 어떻게 시간을 단축시킬까 고민하다가
위에서 이용한 원리를 또 사용해봤다.
d[n][r]배열을 구하는 곳에는 적용 못할 것 같아서 마지막에 세금을 올리는 단계별로 최소값을 구해서 출력하는 과정에서 적용했는데, 세금을 올릴 수록, 답이 되는 최소경로는 반드시 지나는 길의 개수가 같거나 작아질 수 밖에 없다. 세금이 지나는 길의 개수에 비례해서 늘어나기 때문에 세금을 부과하는 단계가 높아질수록 최소경로는 이전과 지나는 길의 개수가 같거나 작을 수밖에 없는 것이다.
이 사실을 이용해서 최소 경로를 구할 때, 지나는 길의 개수를 저장해두고, 최소 경로를 구할 때마다 이전 최소 경로의 길의 개수이하인 경우만 보는 식으로 구현했다.  이전 최소 경로의 길의 개수보다 큰 경우는 절대 최소 경로가 될 수 없다.

그리고 이것을 이전에 다익스트라로 구현한 코드에 추가했더니 또 시간이 단축되었다.


생각하는데 도움이 된 질문 게시판 답변 : https://www.acmicpc.net/board/view/10855


2016년 11월 29일 화요일

BOJ 13912 외계 생물

이 문제는 외계 생물에게 번호를 매긴다고 되어있지만 결국 full binary tree에 부모의 번호를 자식의 번호보다 작게 매기는 경우의 수를 구하는 문제이다.

모든 경우를 다 해봐야 하는... dp같다. 하지만 dp로 어떻게 접근해야할 지 쉽게 떠오르지 않는다. 모든 경우를 다 해본다....
음 d[r][num] : root를 (서브)트리의 루트 노드인 노드 r에 번호 num을 매겼을 때, 번호를 매기는 경우의 수... 로 해도 문제가 좀 있다.
부모의 번호보다 자식의 번호가 커야 하는데, 이게 루트 노드부터 시작해서 그 자식들에게 번호를 매기는 식으로 내려가면 왼쪽 서브트리에서 어떻게 하냐에 따라 오른쪽 서브트리에 영향을 미친다. 즉, 왼쪽 서브트리에서 어떤 번호를 썼는지 알아야 오른쪽 서브트리에 배치할 수 있는 경우의 수를 구할 수 있다... 번호는 최대 2048-1 = 2047까지 있는데... 상태 dp를 할 수도 없고...어렵다.

일단 오늘은 접고 다음에 좀 더 고민하다가 풀이를 봐야겠다. 이 문제처럼 전혀 감이 안 오는 문제는 너무 오래 고민하지 말자. 대신 풀이를 보면 확실하게 내 것으로 만들고 정리하자.



BOJ 13911 집 구하기

이 문제는 고민 좀 했는데... 알고보니 내가 예전에 풀었던 유형이었다.
SCPC 예선에도 나왔었고, JM book에 나와있는 유명한(?) 문제 유형이다.

문제를 잘 읽어보면 결국은 맥날과 스벅 사이의 최단 거리를 구하는 문제로 볼 수 있는데, 맥날이랑 스벅의 수도 여러 개이고 정점의 수도 10000개라 다익스트라를 여러번 돌려서는 시간 초과가 날 것이다.
하지만 그래프를 조금만 변형 해보면 맥날과 스벅사이의 최단 거리를 다익스트라 한 번으로 구할 방법이 있다. 바로 새로운 출발점을 하나 만들고 거기에 가중치 0의 간선으로 모든 맥날(또는 모든 스벅)과 연결하는 것이다. 그리고 그 출발점에서 출발하여 각 정점까지의 최단 거리를 구하는 다익스트라 알고리즘을 이용하면 각 맥도날드에서 각 스벅까지의 거리 중 최단 거리를 찾을 수 있다. 참 처음에 이 방법을 JM book에서 봤을 때, 정말 기가막히다고 생각했는데 지금 다시 봐도 멋진 방법이다.

그런데 이 문제는 조금 더 생각해야 할 것이 있다.
바로 맥날과 스벅사이의 경로에 맥날과 스벅이 아닌 일반 집 하나가 꼭 있어야 한다. 예를 들어 맥날 - 스벅 이렇게 최단 거리일 경우 답이 될 수 없다.
음 맥날과 스벅이 정점 번호로 여러 개 주어지는데, 이걸 다 일일이 비교해서 집인지 아닌지 판별해야 하나? 그럼 너무 오래 걸릴텐데...

다익스트라 알고리즘을 생각해보면 일단 시작하자마자 각 맥날까지의 최단 거리는 0이다. 그렇기 때문에 다른 맥날에서 맥날을 거쳐갈 일이 없다.(그 맥날까지의 거리가 더 짧은 거리로 갱신돼야 하는데 이미 0이므로 갱신될리가 없다.) 즉, 맥날에서 어떤 정점까지의 경로는 출발점 바로 다음의 맥날 하나 뿐이다. 그 외의 맥날은 없다.

그렇다면 스벅은 어떨까? 맥날부터 어떤 스벅까지의 경로에는 분명 다른 스벅이 있을 수 있다. 하지만 다른 스벅을 거쳐 도착한 스벅까지의 경로는 절대 맥날-스벅 간의 최단 거리가 될 수 없다. 왜냐하면 이미 그 전에 거친 스벅 바로 거기까지의 거리가 더 짧을 것이기 때문이다.

즉, 맥날부터 스벅까지의 최단 거리를 구하되, 맥날부터 스벅까지 몇 개의 길을 거쳐갔는지 기록해서 .... 가 아니라.. 안된다. 몇 개의 길을 거쳤는지 기록해서 원래 2개 이상 거친 것 중에서 최단 거리를 찾으려 했지만 그럴 경우 중간에 스벅이 끼어있고 일반 집은 없을 수도 있다. 이런 경우를 커버할 수 없다.

꽝이다! 잘못 생각했다.
그리고 다시 생각해보니 이 문제는 무작정 맥날과 스벅사이의 최단 거리를 구하는 문제는 아닌 것 같다. 왜냐하면 어떤 집이 꼭 맥날과 스벅 사이에 있어야 할까? 아니다
맥날 - 집 - 스벅 이 아닌 맥날 - 스벅 - 집 일 수도 있다!!! 왜냐하면 문제에서 구하라는 것은 집의 맥도날드까지의 최단거리와 스타벅스까지의 최단거리 합이므로...

그렇다면 어떻게 해야할까?
생각해봤다.
다익스트라를 두 번 돌린다. 처음에는 새로운 출발점을 맥날들에 연결하고 시작해서 일단 일반 집까지의 최단 거리를 다 구하고, 또하나의 새로운 출발점을 일반 집들에 연결하되 간선의 가중치는 앞서 구한 맥날에서 각 집까지의 최단 거리로 놓는다. 그리고 dist배열을 다익스트라 처음 시작할 때 처럼 다 초기화한 후 그 출발점에서 시작해서 최단 거리를 구해서 스벅까지의 최단 거리를 보면 결국 맥날 - 집 - 스벅까지의 최단거리를 알 수 있게 될 것이다.

위와 같이 하면 첫 다익스트라에서 각 집에서 맥날까지의 최단 거리를 구했을 것이고 두번째 다익스트라에서 각 집에서 스벅까지... 아!!!

이것도 맞지만 그냥 각 집에서 처음부터 시작하면 되는 거 아닌가? 그럼 다익스트라를 한 번만 돌리면 될 것이다. 각 집에 새로운 출발점을 간선 가중치 0으로 연결하고 각 집에서 출발한다. (아니면 각 집들을 거리 0으로 바로 큐에 다 넣고 시작해도 똑같다.)
그렇게 다익스트라를 돌리면 집에서 맥날까지의 최단거리, 집에서 스벅까지의 최단거리가 구해져 있을텐데... 음 아 이럴경우는 어떤 집에서 출발했는지 알 필요가 있으므로 같은 집에서 출발한 최단거리끼리 합치고 그 중 최소값을 구하면 될 것이다. 다익스트라를 한 번만 돌리는 대신 출발점이 어딘지를 기록해야 하고 비교해서 같은 것 끼리 더하고 그 중 최소값을 찾는 과정이 필요하다.

두 방법 모두 다 해봐야겠다. 아 그리고 맥세권, 스세권 모두 되는지 확인하는 것도 필요하다!

집에서 출발하는 것으로 구현중인데, 같은 집에서 출발한 것을 찾는게 O(N제곱)짜리 밖에 떠오르지가 않는다... 처음에 생각한 방법처럼 맥날들 부터 시작해서 다익스트라를 2번 돌려야겠다.
아 근데... 또 하나의 문제에 직면했다. 바로 맥세권 스세권을 따져주는 것인데, 각각 멕세권인지 스세권인지 따져야 하므로 좀 까다롭다...
일단 처음에 맥날에서 집까지의 거리는 맥세권 제한 x이하인 경우만 보는 걸로 처리하면 되는데, 각 집에서 (맥날에서의 최단 거리를 가지고) 출발해서 스벅까지의 최단거리를 구하는 과정에서가 문제다. 이 것을 해결하기 위해 아까 했던 것 처럼 출발점이 어딘지를 기록해서 최단거리를 다 구한 후 답을 구할 때, 스벅까지 최단거리-(출발점까지의 거리)의 값이 스세권 제한 y이하인지 판별해야 할 것 같다.

일단 그렇게 해서 AC를 받았다....
이 문제... 쉬운 줄 알았는데 그렇지 않았다.

그리고 생각해보니 집에서 출발해서 각 최단 거리를 구하고 출발지가 같은 것을 합하는 방식은 반례가 있다. 안된다...
예를 들어 맥날까지의 최단 거리는 집1에서 부터의 거리이고, 스벅까지의 최단 거리는 집2에서부터의 거리이고 답은 맥날 - 집1 - 집2 - 스벅 인 경우를 처리할 수 없다...
 
하지만 내가 맥날에서 집까지의 최단 거리를 구하고 그 값들을 가지고 각 집들에서 스벅까지의 최단 거리를 구하는 것은 잘 생각해보면, 집을 경유하는 (맥날에서 스벅까지의) 최단 경로를 구하는 것과 같기 때문에 가능한 것 같다.

좀 헷갈리기도 하고, 정말 좋은 문제였다.

그리고.. 다른 분들의 풀이를 보고 있는데.... 헉... 더 좋은 방법이 있었다.
맥날에서 각 집까지의 (맥세권인)최단 거리를 구하고, 스벅에서 각 집까지의 (스세권인)최단 거리를 구한 후 각 집을 기준으로 두 최단 거리를 합쳐서 그 중 최소값을 구하면 된다...

와... 이거 어디서 본 것 같은데.. 익숙한 방법인데 난 전혀 생각도 못하고 괜히 어렵게 생각하고 있었다. 이렇게 하면 또 좋은 것이 맥세권인지 스세권인지 판단하기 편하다 그냥 다익스트라 함수 내부에서 바로 각 집까지의 거리가 맥세권이나 스세권인 경우만 처리하면 된다.
그리고 훨씬 이해하기도 좋은 방법같다. 문제를 많이 풀어보고 공부도 많이 해야한다...






BOJ 13908 비밀번호

어렵다. 생각이 잘 안난다.
그래서 떠오르는 건 brute force밖에 없다...
일단은 최대 7자리 숫자이기 때문에, 모든 숫자를 다 만들면 1000만 번이 필요하다.
그리고 각 숫자에 대해서 주어진 m개의 숫자를 포함하는지 확인하는데 7번이면 된다.
즉, 모든 경우를 다 해봐도 7천만 번에 다 처리할 수 있다.
해보자. 좀 더 효율적이고 좋은 방법이 있을 법도 한데... 일단 이렇게 해보자.

각 숫자에 대해 주어진 m개의 숫자를 포함하는지 확인하는 부분에서 살짝 까다로웠지만 일단 구현은 했다.
AC는 받았는데, 시간이 역시 엄청 걸렸다. 그리고 맞은 사람 목록을 보니 나보다 훨씬 시간이 적게 걸린 분들이 많고 심지어 0ms로 푸신 분들도 꽤 있다.

어떤 분의 코드를 봤는데 그 분의 코드는 n, m만 입력 받길래 도대체 다른 입력은 어디서 받는 건가 궁금해서 실행해봤더니 다른 입력은 받지 않고 그냥 n, m만 입력하면 답이 나온다...?! 헉.. 아... 그렇다.. 그런 것이다. 바로 m만 알면 m개의 수가 어떤 수이든 간에(문제에서 서로 다른 수라고 했으니) 경우의 수는 똑같이 나오는 것이다...!!!
와...생각도 못했었네...  그 분의 코드를 살펴보니 매우 짧고 간결한데 분석해본 결과 다음과 같다.
일단, 모든 수를 구하시긴 하는데 bit연산과 재귀를 이용해서 구한다. 예를 들어 3자리 수라고 하면 각 자리에서 어떤 수를 선택했는지를 표시하는 것이 아닌 0부터 9중 어떤 수를 선택했는지만 표시한다. 각 자리별로 dfs 깊이를 들어가면서 (즉 깊이는 자리 수 만큼 들어가게 된다) 0부터 9중에 어떤 수를 선택하는지 기록한다. 결국 모든 경우를 다 보게 되고, 마지막 자리까지 다 선택한 후 위의 m개의 수가 어떤 수든 간에 똑같다는 것을 이용해서 미리 만들어 놓은 (1<<m)-1 즉  0, 1, .., m-1까지의 수 자리를 1로 채워놓은 것과 &연산을 통해서 (1<<m)-1이 그대로 나온다면 0부터 m-1까지의 수 즉, m개의 수가 포함되었다는 것이므로 카운트를 한다....

와우.. 위의 방법은 모든 경우를 구하되 정말 딱 필요한 것만 쓴 그런 방법 같다. 멋지다. 재귀를 통해 모든 경우를 다 구하고 (그렇게 안 보이지만 다 구하는 거나 마찬가지) 비트 연산을 적절히 활용해서 m개의 수가 포함되었는지 계산하는 정말 멋있는 방법같다.

자 이제 0ms 코드를 분석해 봐야겠다.
근데 이해는 잘 못하겠다.
대충 식을 써보면
10^n - nC1 * 9^n + nC2 * 8^n - nC3 * 7^n + .... 이런 식으로 덧셈 뺄셈을 번갈아 가면서... 가는 왠지 어디선가 본 모양의 식이다. 익숙하긴 한데.. 모르겠다. 아 수학 공부 열심히 할 걸... 후회할 건 후회하고 지금부터 열심히 하면된다. 늦었지만 안 하는 것보단 훨씬 낫다.

이 문제는 수학 공부좀 해보고 다시 도전해보자. 정수론, 이산수학, 고등수학...

BOJ 13906 대문자

소문자로만 이루어진 문장이 주어지고, 인접한 세 개의 동일한 소문자를 하나의 대문자로 바꿀 수 있다. 그리고 어떤 소문자든지 지울 수 있고 안 지워도 상관없다. 이 때, 주어진 소문자 열로 만들 수 있는 모든 대문자로만 이루어진 문장의 개수를 구해야 한다.

dp로 접근해보자.
d[xth] = xth번째에서 n번째까지의 문자열에서 만들어 질 수 있는...

모르겠다. 나중에 다시 풀어보자.

Plane Sweeping BOJ 3392 화성 지도 7626 직사각형

plane sweeping(평면 스위핑, line sweeping이라고도 함) 에 대해 공부해보려 한다.
일단 JM book에 나와있는 평면 스위핑은 O(N제곱)의 시간복잡도를 가진다. 이 것으로 3392 화성 지도 문제는 통과됐지만 아마 7626번 문제를 풀기위해선 좌표압축을 하고 O(NlogN)의 플레인 스위핑이 필요하다. 
O(NlogN)짜리 평면 스위핑을 위해서는 segment tree를 써야하는데 감사하게도 검색해보면 잘 정리된 블로그가 몇 개 있다.

 그 중 내가 참고한 블로그인데
그림과 함께 매우 잘 설명이 되어있다. 하지만 아마 O(N제곱)짜리 plane sweeping도 이해 못한 상태에서 본다면 전혀 이해가 안될 수도 있다...(내가 그랬다.) 그리고 위의 블로그에는 좌표 압축을 하는 경우와 하지 않는 경우 둘 다 코드가 있다.
일단 난 좌표압축이 필요한 경우를 공부해 보려고 한다.

JM book 의 O(N제곱) plane sweeping 이해 -> 세그먼트 트리, 좌표 압축에 대해 공부 -> O(NlogN)짜리 plane sweeping 공부 

일단 위의 블로그에서 설명하는 plane sweeping알고리즘의 원리 자체는 O(N제곱)짜리와 같지만 segment tree를 사용하는데, segment tree가 일반적인(내가 여태 사용해 왔던) segment tree와 좀 다르다.

라인 하나로 왼쪽에서부터 오른쪽으로 평면을 쓸면서 봐야하는데 보면서 만나는 직사각형의 세로 선들을 구별해서(직사각형의 왼쪽 세로선인지 오른쪽 세로선인지..) count를 해줘야 한다. 그리고 이 세그먼트 트리에서는 count에 따라 상위 노드를 업데이트 할지 말지 결정하게 된다.

좌표 압축을 한 상태에서 봐도 세그먼트 트리는 y축의 모든 구간을 다 커버한다. 즉 라인이 움직이면서 만난 직사각형의 y축 범위가 어느 범위든 간에 다 커버된다. 그리고 세그먼트 트리를 이용하면 세그먼트 트리에서 y축 범위에 해당하는 부분을 logN만에 업데이트하는데, 원래 세그먼트 트리에서 range update는 lazy propagation을 쓰지 않으면 range * logN만큼 걸렸다. 
그래서 어찌보면 여기서 사용하는 segment tree의 방식이 lazy propgation과 형태가 조금 비슷..?..하다고 볼 수 있겠다.

어쨌든, update를 할 때, 해당 범위의 leaf node들까지 다 업데이트 하는 것이 아니라 해당 범위에 해당하는 가장 위쪽의 node들만 업데이트 한다. 그리고 직사각형의 시작 부분에 해당하면 +1, 끝부분에 해당하는 세로 선이면 -1을 해서 count를 기록한다.
이 세그먼트 트리의 노드들은 count값과 y축의 크기값을 가지고 있는데, count가 1이상인 것은 현재 라인이 y축의 크기만큼 직사각형과 겹쳐있다는 뜻이고 count는 겹쳐있는 직사각형의 개수를 뜻한다. 
count가 1이상이면 해당 범위에 해당하는 가장 위쪽의 node에 해당하는 것으로 보면되고, y축의 크기값은 존재하는데 count 가 0이면 count가 1이상인 노드들의 합을 저장하고 있는 것으로 보면된다. 그리고 우리가 필요로 하는 것은 현재 라인이 직사각형들과 겹쳐 있는 총 길이이고 그 값은 전 범위를 나타내는 세그먼트 트리의 루트 노드에 저장되어 있다.

바로 그 루트 노드값이 logN만에 업데이트 될 수 있도록 segment tree를 사용하는 것이다.

그래서 좀 자세한 동작 과정을 보면 어떤 노드의 count값이 0에 해당하면 자식 노드들의 합으로 업데이트를 해준다. 하지만 count가 1이상이면 자식 노드들의 합으로 업데이트 하지 않고 자신의 값을 가지고 있는다. 즉, count값이 1이상인 것은 해당 범위에 직사각형이 존재한다는 것을 의미하고, 그 직사각형의 세로길이(y축 크기)를 기록해야 한다. 예를 들어, 그 노드의 자식 노드에 해당하는 부분에 있던 직사각형이 없어진 것을 반영해서 그 노드를 업데이트 해버리면, 그 노드에 해당하는 직사각형은 존재하는데, 그 직사각형의 일부가 사라지게 되는 잘못된 결과를 내게 된다.

라인을 움직이면서 어떤 직사각형의 시작 선이나 끝 선을 만날 때마다 변화가 생기므로 그 때마다 변화가 생기기전의 넓이 값을 계산해서 더해주는 식으로 나가는 것이다.

사실 내가 완벽히 이해하진 못했는데, 계속 고민하기 보다 일단 내가 이해한 데까지만 기록해두고 직접 짜보는 것이 좋을 것 같다. dfs, bfs가 그랬던 것처럼 dp가 그랬던 것처럼... 언젠가는 더 이해하게 될 날이 올 것이다. 너무 시간 끌지말고 앞으로 나아가자.


2016년 11월 28일 월요일

BOJ 13902 개업 2

항상 주어진 웍에 딱 맞게 요리해야 하고, 한 번에 두 개의 웍으로 동시에 요리가 가능하다.
주어진 양을 처리하기 위해 필요한 최소 요리 횟수를 구하는 문제이다.

같은 크기의 웍이 여러개 주어질 수도 있으므로 웍의 크기별 개수도 기록해야 할 것 같다...
일단 웍에 딱 맞게 요리해야 하므로... 느낌이 동전 문제와 비슷한 느낌이 든다.
dp...!! 그리고 생각해보면 두 개의 웍으로 동시에 요리가 가능하므로 같은 크기의 웍이 3개이상 있는 것은 의미 없다.

d[n] = 짜장면 n개 주문을 처리하기 위해 필요한 최소 요리 횟수

d[n] = min(x1, x2 가능한 모든 경우.. | d[n-x1-x2] + 1)
웍의 개수가 최대 1000개인데, 이 중 2개를 골라서 쓰는 경우와 1개만 쓰는 경우가 있는데, 1개만 쓰는 경우는 1000가지이고, 2개를 골라서 쓰는 경우는 최대 1000C2 = 1000*999/2 = 약 50만... 
n제한은 10000이기에.. 시간초과가 날 것 같다.
저 50만을 좀 줄여볼 방법으로... 1개를 골라쓰고, 2개를 골라쓰는 경우로 볼 것이 아니라 한 번에 얼마나 요리하는지로 보면 될 것 같다. (어차피 n이 1이상 10000이하이므로)
대신 미리 50만번 정도의 연산을 통해 한 번에 요리할 수 있는 양의 경우를 다 구해놓고 
d[n] = min(x의 가능한 모든 경우 | d[n-x] + 1) 이런 식으로 dp를 해보면 될 것 같다. 

AC를 받고 다른 분들의 코드를 보는데 어떤 분의 코드는 나와 방식은 비슷한데, 나처럼 미리 한 번에 요리할 수 있는 양의 경우를 다 구하는 것을 그냥 바로 d배열에 한 번에 요리할 수 있는 양의 경우x에 대해 d[x]=1로 초기화를 해주도, d[n] = min(d[n-x]+d[x]) ... 이런 식으로 구현돼있다. 결국 나랑 연산하는 수도 비슷하고 거의 똑같아 보이는데 시간차이는 꽤 많이 난다. 내 코드가 더 느리다...

이 문제는 처음 볼 때는 어려워 보였지만 dp로 접근해서 시간 초과 문제에 직면했을 때, 시간을 줄이기 위해 어떻게 해야할까 고민해서 풀었고 좋은 문제같다.

2016년 11월 24일 목요일

BOJ 13905 세부 주의할 점과 간략 풀이

이 문제는 1939 중량 제한 문제와 거의 같은 문제인데,
주의해야할 점이 있다.
내가 처음에 이분 탐색을 이용해서 구현했는데, WA를 받았다.
내 코드를 아무리 살펴봐도 틀린점이 없어 보이는데... 뭐 틀린점이 없어보여도 틀린 경우가 많긴하지만...
알고보니 난 이분 탐색을 구현할 때, l=0, r=1000000로 두고, 답은 r을 출력하는 식으로 했는데, 그것이 틀린 원인이었다. l=1로 두면 AC를 받는다. 엥?? 뭐지 그래서 이번에는 r을 출력하는 방식이 아닌 ans라는 변수를 따로 두고 했는데 ans를 -1, 1로 초기화해 봤는데 둘 다 틀리게 나오는 것이었다. 그래서 ans를 0으로 초기화했더니 AC를 받았다...!?...

생각해보니... 출발지에서 목적지까지 갈 수 없는 경우가 있는 것 같다.
위에서 l, r을 사용할 경우 l=0으로 두고 할 경우, r=mid-1이 계속 되어 결국 r=-1이 되고 끝나게 된다. 그래서 목적지까지 갈 수 없는 경우는 0을 출력해야 되는데 그렇지 못한 것이다.
하지만 같은 경우에 l=1로 둘 경우, r=0이 되고 끝난다.

분명 이분 탐색으로 모든 경우를 다 볼 수는 있지만, 아예 경로가 존재하지 않는 경우를 전혀 생각못했다.

l, r을 이용해서만 풀려고 했던 것과, ans를 -1로 초기화하는 습관때문에 알아낼 수 있었다.
감사합니다.

다익스트라나 MST+LCA로 풀 경우에도 주의해야 할 것 같다.
다익스트라는 할 만할 것 같은데, 목적지까지 가는 경로가 없는 경우 MST를 만들 때 목적지가 포함이 안될 것이고... 그럼 MST에서 depth를 구할 때 -1로 초기화하고, 출발점이나 도착점의 depth가 제대로 구해지지 않으면 거기서 바로 끊어서 0을 출력하든지 해야할 것 같다.
크루스칼로 MST를 만든 후에 출발점과 도착점이 같은 그래프에 속해있는지를 살펴보고 같은 그래프가 아니면 바로 0을 출력하는 것이 더 좋아보인다.

MST + LCA로 풀었는데, WA를 받았다. 도대체 뭐가 문제인지 모르겠어서 랜덤 데이터로 비교해 보는데도... 계속 정답 코드와 같은 결과가 나오다가.. 결국 다른 데이터를 발견했다!!!
아... 다행히 데이터 크기도 작아서 직접 MST를 그려보고 했는데...
이 문제에서는 경로가 존재하지 않는 경우도 있다고 했는데, 바로 그래프가 여러개로 나눠져 있을 수 있다는 것이고, 정점이 동떨어져 있을 수도 있다.
나는 MST에서 depth를 찾기 위해서 dfs를 할 때, root를 1로 두고 했는데... 1이 MST에 포함 안 되었을 수도 있다. 그래서 안전하게 출발점 or 도착점을 root로 하면 될 것 같다.
AC를 받았다!! 아 진짜 이런 건 생각도 못했다.. 진짜 그래프가 나눠져 있으니 주의해야 할 것이 많은 것 같다. 아마 랜덤 데이터가 나오지 않았다면 못 찾았을 것이다... 감사합니다!

이제 dijkstra, MST+LCA로 풀었으니
MST+dfs로 풀어 봐야겠다.
dfs가 쉬울 줄 알았는데 막상 해보니 까다롭다... 오히려 MST+다익스트라 돌리는 게 더 쉬울지도... dfs로 구현하기가 힘들어서 일단 전역변수 ans를 두고, dfs를 s에서 시작해서 return값은 도달한 노드번호로 해서 return값이 e이면 ans에 해당 cost를 비교해서 최소값을 넣고 return e를 해준다... 그냥 아래에 적어놓은 질문 게시판의 어떤 분의 방법이 젤 좋을 듯하다. MST를 만들면서 찾아주는 게 제일 나을듯... 한 번 그렇게 구현해 봐야겠다.
이 방법이 제일 간단하고 멋지고 빠른 것 같다.

그리고 MST로 할 경우 LCA외에 dfs로 해도 되겠지만, 질문 게시판에 올라온 어떤 분의 글을 보니 그 분은 크루스칼 알고리즘으로 MST를 만들면서 출발점과 도착점이 같은 부모를 가지게 되는 순간(같은 그래프에 속하는 순간)의 간선의 가중치 값을 출력하는 식으로 구현하셨다. 그 순간이 출발점과 도착점 사이를 잇는 경로가 완성되는 순간이면서 그 때의 가중치가 최소값이기 때문이다. 물론 이 경우도 마지막에 0을 출력해줘야 한다.
1939 중량제한 문제도 이렇게 풀어봐야겠다.

이 문제는 데이터로 여러 개로 나눠져 있는 그래프가 들어오기 때문에 고려할 부분이 좀 있는 문제였다. 좋은 문제 였고 많은 공부가 되었다.

참고 : https://www.acmicpc.net/board/view/10880

2016년 11월 22일 화요일

BOJ 13904 과제

하루에 하나의 과제를 끝낼 수 있고, 각 과제마다 마감일까지 남은 일수가 주어진다. 마감일을 넘으면 과제에 대한 점수를 못받는다. 이 때, 받을 수 있는 점수의 최대값을 구하는 문제인데, 어디서 많이 본듯한 그리디 문제이다.

점수를 최대한으로 받으려면, 점수가 큰 과제를 우선적으로 하거나 많은 과제를 해야 한다.
여기서 마감일이 주어지는데, 일단 점수가 크든 작든 마감일이 많이 남은 과제는 나중에 생각해도..   일단 하루에 한 과제씩 할 수 있으므로 주어진 최대 마감일까지 하루에 한 과제씩 꼭 해야한다. 그리고 한 과제씩 하되 점수가 큰 과제를 해야한다.
그리고 마감일이 주어지면 어떤 과제든 마감일 안에 아무때나 해도 점수는 같기 때문에 마감일이 길면 마감일이 짧은 작업에 양보해주고 그 작업은 나중에 하는 것이 좋다.

그렇지만 마감일이 짧은 작업을 먼저 하느라 더 큰 과제를 놓치면 안되기 때문에 점수 순으로 정렬을 해서 점수가 큰 과제부터 본다.
그리고 어차피 하루에 한 과제가 최대이기 때문에 이왕 하는 거 점수가 큰 과제를 하는 것이 이익이다. 그리고 점수가 큰 과제부터 하되, 그 과제의 마감 기한의 마지막 날에 해야 마감일이 짧은 작업들을 최대한 많이 할 수 있다.

그래서 점수가 큰 과제부터 하되, 마감 기한의 마지막 날에 배정하면서 점수를 계산하면 될 것이다.

BOJ 2109 순회 강연 문제와 비슷한 문제이길래 내가 블로그에 정리해놓은 것을 봤는데,
다시 정리해보면 어떤 날에 과제를 할 것이라면 가장 큰 점수의 과제를 하는 것이 좋고, 앞의 날들일수록 과제들끼리 공유되는 부분이 크므로(즉, 가능한 과제의 경우가 많으므로) 그 과제의 기한의 마지막 날에 하는 것이 가장 좋은 방법이다. 그리고 만약 가장 큰 점수의 과제 대신 작은 점수의 과제를 한다고 해서 이익이될 것이 없다. 왜냐하면 그날 할 수 있는 과제는 어차피 1개이고, 그날 과제를 함으로써 영향이 발생하는 것은 그날이 기한 안에 있는 과제들을 못하게 된다는 것인데, 앞서 말했듯이 그 날 하나의 과제를 할 것이라면 가장 큰 점수를 하는 것이 이익이므로 가장 큰 점수의 과제를 그 과제의 기한의 끝에 하는 것이 가장 큰 점수를 얻는 방법이 될 것이다.

BOJ 13903 출근

음 일반적인 bfs문제이다. 처음 시작점이 될 수 있는 1행의 세로블럭들을 큐에 다 넣어두고 bfs탐색을 시작한다. 하지만 내가  bfs문제를 오랜만에 풀어서 그런지... 틀렸다. 그리고 도저히 원인을 찾을 수 없다가 도움을 받아 겨우 원인을 찾았다. 바로 .... 처음에 1행의 세로블럭들(출발점들)을 큐에 넣을 때, 방문했다는 표시를 하지 않은 것이다... 아 이런 실수를... 전에도 이런 실수를 했었는데... 으악...난 내 코드에는 문제 없다고 생각하고 그냥 문제에 내가 생각치 못한 함정이 있는 것인가 생각하고 있었다.

만약 처음 출발점을 방문했다는 표시를 하지 않을 경우, 생길 수 있는 문제에 대해 생각해보자. 그 출발점에서 출발해서 다시 돌아오는 건 별 상관없어보인다. 도착점까지의 최단거리만 구하면 되니까... 하지만 출발점이 여러개이기 때문에 한 출발점에서 다른 출발점으로 이동해서 그 시작점의 dist를 0에서 1로 바꿔버릴 수 있다. 그렇게 되면 도착점까지의 최단거리를 제대로 구할 수 없을 수도 있다.

앞으로 조심하자.

BOJ 13900 순서쌍의 곱의 합

주어진 N개의 정수로 만들 수 있는 순서쌍의 각각의 곱들의 합을 구하는 문제이다.
주어진 N개의 정수들로 만들 수 있는 조합의 각각의 곱들의 합을 구하는 문제로 보면 되는데, 내가  이 문제에 대해 생각한 것은 아니고 풀기전에 미리 풀이와 주의할 점을 들었기 때문에 바로 풀이와 주의할 점을 정리하겠다.

일단 주의할 점은 N개의 정수 중에서 2개를 뽑는 조합으로 보면 편하지만, 예를 들어 2, 2, 4가 주어지면 (2, 2), (2, 4) 로 끝이 아니라 (2, 2), (2, 4), (2, 4) 이렇게 3개이다.
그리고 오히려 이 주의할 점때문에 구하기가 편해진다.

만약 그냥 모든 순서쌍에 대해 일일이 다 구하려면 n이 10만개이기 때문에 O(n제곱)으로 시간초과가 날 것이다. 하지만 정말 멋진 방법이 있다.

이 문제에서 구하라는 것을 잘 보자.
각 조합에 속한 수의 곱의 합인데
2, 3, 4를 예로 들어보면
(2, 3), (2, 4), (3, 4) 이 세가지 조합에서 2*3 + 2*4 + 3*4 가 답이 된다.
잘 보면 2*(3+4) + 3*4로 나타낼 수 있다!!

그렇다. 미리 prefix sum을 구해놓게 되면 부분합을 O(1)만에 구할 수 있게 되고, 부분합을 알면 어떤 수x로 시작하는 조합의 곱들의 합을 O(1)만에 구할 수 있게 된다. 결국 문제에서 구하라고 하는 것을 O(n)만에 구할 수 있을 것이다.

AC를 받고 다른 분들의 풀이를 보니 이해는 잘 안 되지만 O(1)만에 구하신 분들도 있다... 그리고 어떤 분은 위의 과정을 그냥 입력받으면서 바로 처리하신 분도 있다... 별거 아닌 것 같아도 나는 생각도 못했는데...엄청나신 것 같다 다들...

추가 : 슬랙에 질문 게시판에 올라온 질문이 떠서 우연히 봤다.
이런 풀이도 있다  : https://www.acmicpc.net/board/view/10848

BOJ 13909 창문 닫기

N개의 창문이 있고, 1번부터 N번까지의 사람이 있고 모든 창문은 닫혀있다.
1번 사람은 1의 배수 번째의 창문들을, 2번 사람은 2의 배수 번째의 창문들을, ..., n번 사람은 n의 배수 번째 창문들을 열려있으면 닫고, 닫혀있으면 여는 행동을 취한다.
1번 사람부터 n번 사람까지 이렇게 했을 때, 마지막에 열려있는 창문의 개수를 구하는 문제이다.

직접 어느정도 해보다 보면 감이 온다.
n번째 창문은 n의 약수의 개수에 따라 열리고 닫히게 된다. n의 약수의 개수가 홀수개이면 마지막에는 열리게 되고, 짝수개라면 마지막 상태는 닫힌 상태가 된다.

약수가 짝수개인지, 홀수개인지 어떻게 알 수 있을까?
어떤 수 n의 약수를 구해보면, 일단 1이 있을 것이고 그에 상응하는 n이 있을 것이다. 이처럼 어떤 약수x가 있으면 반드시 그에 상응하는 약수(n/x)가 하나 존재한다. 그렇다면 항상 짝수개일 수 밖에 없을까? 아니다. 바로 어떤 수의 제곱으로 나타낼 수 있는 수는 그렇지 않다. 어떤 수 n이 x의 제곱이라면 n의 약수의 개수는 x를 기준으로 왼쪽, 오른쪽의 약수는 서로 대응되어 짝수개이지만 x는 x자신과 대응되므로 한 개이다. 결국 홀수개가 된다.

결국 이 문제는 1부터 n까지의 수 중에서 완전 제곱수의 개수를 구하는 문제가 된다.

구현은 여러 방법이 있겠지만.. 음 일단 가장 먼저 생각난 것은 n의 범위가 최대 21억까지인데, 5만 * 5만이 25억이므로 5만부터 대충 5만보다 좀 작은 수에서 시작해서 그 수의 제곱이 주어진 n과 같거나 작아지는 순간을 찾는 방법이나 sqrt(n+1)값을 버림한 정수 값과 그 값에서 1을 뺀 값 중 답을 찾는 방법을 쓰면될 것 같은데.. AC를 받고 다른 분의 코드를 보니 그냥 1부터 시작해서 그 제곱이 n보다 같거나 작은 경우까지 돌리는 경우도 꽤 있는 것 같다.

BOJ 2336 굉장한 학생

N명의 학생이 세 번의 시험을 치룬 결과가 주어지는데, 세 번의 시험에서 한 학생이 다른 한 학생보다 세 번 모두 성적이 좋으면 더 "대단한" 것인데, 어떤 학생보다 "대단한" 학생이 없다면 그 학생은 "굉장한" 학생이다. 이 때, 굉장한 학생의 수를 구하는 문제이다.

즉, 자신보다 세 번 다 성적이 좋은 학생이 없는 학생의 수를 구하는 문제이다. (0번, 1번, 2번 성적이 좋은 학생들의 수)

문제 분류가 '세그먼트 트리'로 되어있는데, 쉽게 떠오르지 않는다. 처음부터 세그먼트 트리로 생각하려 해서 그런가? 한 번 그냥 푼다면 어떻게 풀 것인지 생각해 봐야겠다.
갑자기 떠오른 생각이, 굉장한 학생의 수를 바로 구하는 것보다, 굉장하지 않은 학생의 수를 구해서 빼는 게 나을 것 같다.
굉장하지 않은 학생의 수는 자신보다 세 번 모두 성적이 좋은 학생이 있는 학생의 수를 구하면 된다.

집중도 안되고 딴생각만 들고... 결국 풀이를 봤는데도 잘 이해가 안된다. 어렵다.
정신 차리고 차근차근히 풀이를 정리해 보자. 독서백편 의자현. 이해될 때까지...
일단 굉장한 학생의 수를 구해야 한다. 굉장한 학생은 자신보다 세 번 모두 성적이 좋은 학생이 없어야 한다. 문제에서는 등수 순으로 주어진다.

2 5 3 8 10 7 1 6 9 4
1 2 3 4 5 6 7 8 9 10
3 8 7 10 5 4 1 2 6 9
블로그도 보고, 백준님의 코드도 보고 하면서 생각도 하고 예제를 가지고 직접 써보다가 겨우 깨달았다. 정말 헷갈린다.
일단 각 학생별로 1번 학생이 세 시험에서 각각 몇등을 했는지, 2번 학생이 세 시험에서 가각 몇 등을 했는지,... n번 학생이 세 시험에서 각각 몇 등을 했는지를 기록한다.
그리고 세 개의 시험 중 하나의 시험의 등수를 기준으로 정렬한다. 여기서 많이 헷갈렸는데, 정렬해버리면 몇 번 학생이 몇 등했는지는 알 수 없다. 하지만 알 필요없다. 우리는 굉장한 학생의 수만 구하면 된다. 정렬했기 때문에 몇 번 학생인지는 몰라도 첫번째 시험에서 1등한 사람이 두번째 시험과 세번째 시험에서 몇 등을 했는지를 알 수 있다.
즉, 누군지는 몰라도 한 사람이 각 시험에서 몇 등을 했는지에 대한 정보가 하나의 시험을 기준으로 정렬되어 있다. 2번째 시험을 기준으로 정렬했다고 하고 예를 들어보겠다.
왼쪽부터 한 사람씩(한 열씩) 보면 두번째 시험에서 1등을 한 사람은 첫번째, 세번째 시험에서 각각 2등, 3등을 했다는 사실을 알 수 있다. 일단 사람1은 두번째 시험에서 1등이므로 첫번째, 세번째 시험에서 자기보다 잘한 학생이 있어도 굉장한 학생이다. 이제 사람2를 보자. 이제 사람2부터는 (정렬을 했으므로) 항상 두번째 시험에서 자기보다 잘한 사람이 1명 이상 있다. 굉장한 학생은 자신보다 세 시험 성적이 모두 좋은 사람이 없어야 하는데, 사람2부터는 두번째 시험에서 자신보다 잘 본 사람이 있다. 그리고 정렬했기 때문에 두번째 시험에서 자신보다 잘 본 사람들은 앞에 존재하고, 그 사람들이 첫번째와 세번째 시험에서도 자신보다 성적이 좋다면 그 사람은 굉장한 학생이 될 수 없지만, 첫번째 시험과 세번째 시험 둘 중 하나에서라도 자신이 성적이 제일 좋다면(자신보다 성적이 좋은 사람이 없다면) 그 학생은 굉장한 학생이 될 것이다.

많이 헷갈린다. 지금 두번째 시험을 기준으로 정렬하고 앞에서부터 보기 때문에 항상 자신의 앞사람들은 자신보다 두번째 시험은 잘 본 사람들이고, 이제 그 사람들의 첫번째 시험과 세번째 시험의 성적이 자신보다 좋아야 자신은 굉장한 학생이 될 수 없는 것이다. 두번째 시험을 자신보다 못 본 사람들은 첫번째 시험과 세번째 시험 성적이 아무리 좋아도 볼 필요가 없다. 세 시험에서 모두 자신보다 성적이 좋은 사람이 한 사람이라도 있는지 봐야하고 만약 있다면 자신은 굉장한 학생이 아니게 된다.
그래서 두번째 시험을 기준으로 정렬하고 나서는 두번째 시험에서 자신보다 앞에 있는 사람에 대해서 그 사람들의 첫번째, 세번째 시험 성적을 보면되고, 여기서 첫번째 시험 성적 중 가장 좋은 성적과 자신의 첫번째 성적을 비교하고 , 세번째 시험 성적 중 가장 좋은 성적과 자신의 세번째 성적을 비교해서 첫번째, 세번째 모두 자신의 성적보다 좋으면 그 사람은 굉장한 학생이 될 수 없고, 그 중 하나라도 자신의 성적보다 안 좋다면 그 사람은 굉장한 학생이 된다! 왜냐하면 각 성적 중 가장 좋은 성적을 가져왔기 때문에 그 가장 좋은 성적이 자신의 성적보다 좋지 않다면 자신이 그 사람들 모두보다 성적이 더 좋은 것임을 바로 알 수 있기 때문이다. 즉 그 중에 자신보다 세 시험 모두 성적이 좋은 사람이 한 사람도 없다는 것을 바로 알 수 있기 때문이다.
그래서 구간의 최소값을 빠르게 구할 수 있어야 하는데, 풀이를 좀 더 보니 내 방법에서 좀 더 나아가 segment tree를 이용해야 하는 것 같다. 하지만 일단 n제한이 50만이니까 O(N)만에 누적 최소값을 계산해두고(첫번째 부터 n번째 까지의 최소값이 필요하므로) 사용하면 될 것 같다. 일단 내가 생각한대로 풀어봐야겠다.

근데 내 방법으로 계속 틀리길래... 계속 고민하고 풀이를 찾아 읽어봤지만 도무지 알 수가 없던 차에
5
1 2 3 4 5
5 4 3 2 1
1 2 3 5 4
라는 예제를 가지고 백준님의 코드와 내 코드의 실행 결과를 비교해 봤더니 달랐다. 감사합니다... 바로 찾다니 그리고 저 예제로 생각해보고 내 풀이의 문제점을 알게되었다.

내가 대충 이해한 것은 맞다. 하지만 내 풀이처럼 첫번째 따로, 세번째 따로 찾게되면 한 학생의 첫번째, 세번째 점수가 아닌, 예를 들면 학생1의 첫번째 점수, 학생2의 세번째 점수와 비교하게 될 수 있다. 왜 이걸 전혀 생각 못했지... 정말 요즘 더 실력이 떨어진 것 같다... 노력하자.

그래서 이제 다시 생각해 봐야한다.... 음 이제 내가 참고했던 여러 풀이가 이해가 된다.
왜 굳이 세그먼트 트리를 쓰는지조차 이해가 잘 안됐는데, 아... 다시 정리해 보겠다.

일단 위에서 설명했던 것처럼 두번째 시험을 기준으로 성적이 좋은 순으로(오름차순) 정렬하고 첫번째와 세번째를 보는데 위에서 잘못한 것 처럼 따로 보면 안되고 한 사람 한 사람 단위로 봐야한다!! 일단 두번째 시험을 기준으로 정렬하고 앞에서부터 보기 시작하면 자신의 앞에 있는 사람은 두번째 시험의 경우 항상 자신보다 성적이 좋다. 그리고 자신보다 뒤에 있는 사람은 두번째 시험 성적이 항상 자신보다 안 좋으므로 첫번째, 세번째 성적이 아무리 좋아도 자신보다 "대단할" 수 없다. 그래서 일단 자신보다 앞에 있는 사람들이 첫번째, 세번째 성적이 모두 자신보다 좋은 "대단한" 사람이 될 수 있는 후보들이다. 이 중에서 자신(현재 학생)보다 대단한 사람이 없다면 현재 학생이 굉장한 사람이 되는 것이다.

두번째를 정렬해서 봐야할 곳을 첫번째와 세번째 두 곳으로 줄였지만, 여전히 첫번째와 세번째 모두 현재 학생보다 성적이 좋은 것을 찾는 것이 쉽지 않다. 바로 이 때 세그먼트 트리를 써줄 것인데, 이번에는 첫번째 성적을 기준으로 정렬을 하는 효과를 내보자.
바로 첫번째 시험의 성적(등수)을 해당하는 세번째 시험 등수값의 인덱스로 지정한다. 그리고 그것으로 세그먼트 트리를 만들어서 range minimum query를 할 수 있게 하고 현재 학생의 첫번째 시험 성적보다 좋은 성적에 해당하는 구간의 최소값(즉, 그 구간에 해당하는 세번째 시험의 성적중 가장 좋은 성적)을 구해서 현재 학생의 세번째 시험 성적과 비교하고 그 성적이 현재 학생의 세번째 성적보다 좋으면 현재 학생보다 "대단한" 학생이 존재하는 것이고, 만약 아니라면 "대단한" 학생이 없는 것이므로 현재 학생은 "굉장한" 학생이 된다.

엄청난 풀이다...

그리고 처음에는 segement tree를 매우 큰 값으로 초기화 해두고, 학생을 한 명씩 볼 때마다, 즉, 두번째 시험 기준으로 정렬된 순서에 따라 첫번째 성적에 해당하는 부분을 업데이트를 시켜줘야 한다. 왜냐하면 현재 학생의 첫번째 시험 성적보다 좋은 성적에 해당하는 구간이여도 이미 정렬했던 두번째 시험 성적을 기준으로 볼 때, 두번째 성적이 더 좋은 성적이 아닐 수 있기 때문에 그럴 경우에는 세그먼트 트리에 실제 첫번째 성적과, 세번째 성적에 대한 정보대신 매우 큰 값이 들어가 있어서 더 "대단한"학생이 아닌 것으로 제대로 판단하게 된다.

어렵다. 내가 너무 나태해져서 머리가 잘 안 돌아가는 것 같기도 하다. 맥그리거의 말 처럼 멈추지 말고 쉬지도 말고 끊임없이 노력하자.

음 근데, 구현하면서도 문제가 좀 있었다.
일단 init을 INF로 해주는 것에서 leaf node만 INF로 해주었다던가... 또한 update를 구현할 때, update하려는 index가 구간의 범위 밖이면 그 구간의 rangeMin값을 반환해줘야 하는데, 마치 query처럼 INF를 반환해준 것... 정말 실력 부족이다...

그리고 일반 정수가 아닌 struct는 bool cmp(struct, struct)를 쓸 때, 그냥 쓰면 복사하는데 비용이 커지므로 const struct& 식으로 참조자를 사용해서 구현하자.

위의 것도 다 고쳤는데...근데 도대체 뭐에서 틀렸을까...
정말 랜덤데이터를 생성해서 여러번 시도해 봤는데도.. 틀린 경우를 찾을 수가 없어서 고민하다가 문득.. tree를 INF로 초기화해야 하는데, init함수를 그냥 for문으로 고치고 0번 노드부터 n*4-1번노드까지 무작정 INF로 초기화하고 제출했다. 그러니까 AC를 받았다.

헉... 분명 이 것은 아까 테스트를 해봤던 것이다. 혹시 제대로 안 들어가나 해서 rangeMin값이 잘 초기화 되었는지 출력해서 확인까지 해봤었는데... 뭐지...그래서 코드를 다시 봤는데..

헉...init함수 마지막줄에 rangeMin=min(leftMin, rightMin)만 해주고 return을 안하고 있다...근데 아까는 어떻게 INF값으로 초기화 된 것이지..??? 그냥 내 local환경에서만 된 것인가.. 설마 그래서 아무리 틀린케이스를 찾으려해도 못 찾았던 것인가... 아.. 의문이 하나 둘씩 풀린다. 진짜 이 문제만큼 (백준님의 정답 코드가 있음에도 불구하고, 풀이를 이해했음에도 불구하고) 틀린 이유를 찾기 힘든 적은 처음인 것 같다.

결국 init함수에서 내 실수로 인해... 제대로 초기화가 안됐고.. 계속 틀렸던 것이다.
다시 짜봐야 겠다.

이 문제를 풀게 되면서, 그리고 다시 짜보면서 init이나 update함수부분을 좀 더 잘 이해하게 된 것 같다. 아직 완벽히 이해했다고는 생각치 않지만...
그리고 bool cmp(struct, struct)에서 &(참조자)를 써야 더 빠를 것 같았는데 제출해보니 찍히는 시간상으로는 차이가 없어보인다. 그냥 int형이라면 포인터나 int형이나 크기가 비슷하니까 상관없겠지만 struct의 경우 int형이 지금 코드에서 3개라.. 12byte짜리를 복사할텐데.. 음 BOJ 가 64비트 시스템으로 바뀌고 나서 포인터가 8byte 가 되서 큰 차이가 없는 것인가... 여튼 웬만하면 const struct& 형식으로 쓰는 게 좋을 것 같다.


<참고>
http://blog.naver.com/kks227/220791986409
http://cloge.tistory.com/7
백준님 강의 자료, 코드

2016년 11월 21일 월요일

BOJ 7626 직사각형

이 문제는 segment tree lazy propagation을 연습해볼 문제로 추천받은 문제인데,
아무리 생각해도... 어떻게 segment tree를 활용할지 떠오르지가 않는다.

일단 이 문제는 좌표위에 여러 직사각형들이 차례로 주어지는데, 범위는 무려 0부터 10의 9제곱까지... 그리고 이 직사각형들이 좌표평면을 덮는 면적을 구하는 문제이다. 즉 겹치든 말든 일단 좌표평면을 얼마나 덮는지 구하는 문제이다. 그리고 직사각형은 20만개가 들어온다.

일단 x좌표를 기준으로...하는 것은 메모리 초과이다. 
잘 생각해보자. 세그먼트 트리는 구간합이나 구간의 최소, 최대값을 O(log N)만에 구할 수 있고, 업데이트 또한 O(log N)만에 할 수 있는 자료구조이다. 
이 문제에서는 왠지 구간합을 구해야 할 것 같은데, 단순히 구간합만 구할 것이라면 굳이 세그먼트 트리와 lazy propagation을 쓸 필요가 없을 것이다. 

업데이트가... 그것도 구간 업데이트가 빈번히 있을 가능성이 큰데.. 입력을 잘 보면 직사각형을 구성하는 x좌표의 구간, y좌표의 구간이 주어진다.

하지만 각 구간을 일일이 업데이트 한다고 생각해보면... 일단 범위가 너무 커서 segment tree를 만들 수 없다. 좌표 압축? 내가 좌표 압축을 해본적이 없기도 하지만... 이 문제에서는 면적을 구해야하는데, 만약 좌표 압축을 한다면 직사각형의 각 변의 길이나 넓이를 따로 기록해 둬야하나?...음...


2016년 11월 18일 금요일

BOJ 10999 구간 합 구하기 2 와 Lazy Propagation

segment tree와 lazy propagation을 이용해야 하는 문제다.
원래는 segment tree에서 update를 할 때, 하나의 수에 대해서 update를 logN만에 할 수 있었는데, 이 문제에서는 구간을 update해야 한다. 즉 (구간의 길이)*logN의 시간이 걸리는 것이다. 

Range update를 O(logN)만에 할 수 있는 방법이 있다.
segment tree + lazy propagation을 활용하는 것이다.
lazy propagation을 이용하면 범위에 포함되는 트리의 leaf node까지 다 업데이트를 해주지 않는다. 일단은 그 범위를 대표하는 node까지(node의 위에 있는 노드들도)만 업데이트 한다. 그리고 lazy라는 배열에 그 node의 자식 node들에 얼마나 업데이트 해줘야 하는지 기록해놓는다. 대충 여기까지 하면 일단 O(logN)만에 구간 업데이트가 된 것이다. 엥? 그렇다면 다른 쿼리가 들어오면 어쩌려고... 다음에 업데이트한 구간에 조금이라도 관련있는(걸쳐있는) 쿼리나 업데이트가 필요할 경우, 필요한 노드들의 lazy배열을 살펴본다. 그래서 lazy배열에 얼마나 업데이트 해줘야할지 있는 기록을 보고 그 노드를 업데이트 해주고, 그 lazy배열을 0으로 만든 후 자식 노드에게 전파해준다. 이렇게 필요한 경우 lazy배열을 살펴보고 업데이트 해줘서 필요한 노드의 값만 챙기고 그 자식노드의 업데이트는 다음으로 미루는 식이다. 
물론 이렇게 하면 그냥 point update할 때보다 아주 조금 더 시간이 들긴하겠지만 O(logN)이다.
특이한 점은 쿼리를 할 때도 업데이트가 진행되는 것이다. 그리고 어떤 노드의 업데이트가 진행되면 그 노드 위의 노드들의 업데이트는 원래 재귀 업데이트 방식으로 되면 된다.

달라지는 것은 필요한 것까지만 취하고, 그 아래 자식들의 업데이트를 뒤로 미뤄놓고 필요할 때만 해주거나, 필요한 걸 찾으면서 어차피 지나가는 김에 해주고 가는 식이다.
그래서 O(logN)만에 가능한 것이다.

정말 멋있는, 대단한 방법이다. 이런 방법을 어떻게 생각해 냈을까...나도 완벽히 이해한 것은 아니기 때문에 좀 더 공부해보고 직접 짜봐야겠다. 그리고 아래에 적어놓은 두 사이트의 도움을 많이 받았다.

자동차 공장 문제를 풀 때 처럼, Fenwick Tree의 range update, range query를 이용해서도 풀 수 있을 것 같은데 일단 lazy propagation을 해본 후에 도전해 보고, 거꾸로 자동차 공장 문제도 segment tree+lazy propagation을 이용해서 풀어봐야겠다.

Segment Tree + Lazy Propagation 을 공부한 곳인데, 정말... 단계별 그림과 친절한 설명과 코드로 완벽에 가깝게 설명이 돼있다. 물론 그래도 내 실력에서느느 이해하는 게 쉽지는 않았다. 이것을 이해하려면 Segment Tree에 대해서도 잘 이해해야 하고, 아래의 자료를 오랜 시간 보면서 여러번 읽어보고 해야할 것이다. 

2016년 11월 17일 목요일

BOJ 13703 물벼룩의 생존 확률

수면 k센티미터 아래에 위치한 물벼룩이 1초마다 위 또는 아래로 1센티미터 이동하고 수면에 닿으면 물매암이에게 먹혀서 죽는다. n초후의 경우의 수는 2의 n제곱가지가 있을것인데, 그 중 생존할 경우의 수를 구하는 문제이다.

처음부터 생존할 경우의 수를 구하려는 것 보다 죽는 경우(수면에 도달하는 경우)의 수를 구해서 전체 경우의 수에서 빼는 것이 나아보인다.

좀 더 생각해보면 k<=n인데, 
k==n인 경우는 수면 k센티미터 아래에서 시작해서 n초뒤에 수면에 도달하려면 계속 위로 올라가야 한다. k==n인 경우는 수면에 도달하는 경우의 수는 1가지이다.
k<n인 경우는 어떨까? 일단 한 번 수면에 도달하면 그 이후로는 의미가 없다. 즉, 그 이후는 볼 필요가 없다. 그 이후는 2^(남은 시간) 의 경우의 수 일 것이다. 그리고 현재 위치보다 남은 시간이 더 작으면 수면에 도달할 수 없다.

음...dp로 접근해보면, d[pos][rsec] = 현재 위치 pos, 남은 시간 rsec일 때의 수면에 도달할 수 있는 경우의 수.(벼룩이 죽는 경우의 수)

한 번 구현해 봐야겠다.
오.. AC를 받았다. 다른 분들을 보니 나처럼 죽는 경우를 전체에서 뺀 경우도 있지만 바로 생존할 경우의 수를 구한 분들이 더 많아 보인다.

처음에는 dp로 생각하기 힘들었는데, 차근 차근 적고 정리해보다 보니 운좋게 생각이 떠오른 것 같다. 감사합니다.

BOJ 13702 이상한 술집을 풀다가...

이 문제는 이분 탐색으로 풀 수 있는 문제이다.
이분 탐색으로 나눠줄 수 있는 막걸리 용량을 정해보면서 검사하고 최대가 되도록 조절해 나가면 된다.

그런데 이분 탐색을 할 때, 헷갈리는 것이, l, r중 어느 것에 정답이 들어가냐이다.
그냥 ans 변수를 따로 쓰면 쉽긴하지만, 이분 탐색을 좀 더 이해하고 싶어서(?) l, r중에 어디에 정답이 들어갈지 생각해보는 중이다.

이번에 구현할 때는 생각해보니 r에 들어가서 r을 출력했는데,

예전에 다른 문제를 풀 때는 l에 들어가는 경우가 많았는데.. 그렇다면 l에 정답이 들어가게 하려면 어떻게 해야할까? 다른 고수분의 코드를 보고 깨달은 것인데, 여러 방식이 있겠지만,
check(mid)>=k인 경우 mid가 정답일 수도 있으므로 l=mid+1을 할 게 아니라, l=mid를 해주면 된다. else에 해당하는 check(mid)<k인 경우는 mid가 답이 될 수 없으니 r=mid-1을 해줘야 한다. 그런데 이렇게 할 경우 무한루프에 빠질 수 있다. while(l<=r)이기 때문이다.
l=3, r=5이고 정답이 4라면, l=4에서 멈출것이다... mid= (4+5)/2 = 4가 되므로..
while(l<r)로 고친다해도 l=4, r=5이므로 무한 루프일 것 같은데.. 음...
다른 분의 코드를 보니 while(r-l>1) 처럼 하신 분도 있는데, 그 분은 r=mid-1이 아니라 r=mid로 하셨다.
일단 생각해보니 그냥 내 방식대로 하면서 그 때 그 때 l이냐 r이냐를 생각해서 찾거나, ans변수를 따로 사용해서 하는 것이 좋을 것 같다.

BOJ 13701 중복 제거

이 문제는 N개의 정수가 주어지면, 이들 중 중복되는 것을 제거하고 주어진 순서대로 출력하는 문제인데, N은 최대 500만이고, 주어지는 정수의 크기는 최대 2^25 - 1 이다.
일단 바로 먼저 떠올리는 것이 boolean배열로 체크하는 것인데, 정수의 크기가 너무 커서 어림도 없다. 그렇다면 500만개니까 map을 쓰면 어떨까? map이 메모리를 얼마나 차지 하는지는 모르지만, 그냥 int형 배열만써도 500만개면 메모리 제한이 8MB를 초과할 것이다.

이거 참.. 그냥 int형 배열이라도 쓸 수 있으면 sorting이라고 해서 해볼텐데..(다행히 시간제한은 5초) 어떻게 해야할지 고민이다. 혹시 map으로 되는건가?
스택 오버플로우 맵 메모리 사용량 관련 사이트를 보니 int자료가 들어간 map을 쓰면 int형 배열보다 메모리를 더 많이 쓴다는 것을 알 수 있다.

맞은 사람 목록을 보니 코드가 매우 짧다... 그래서 혹시나해서 map을 썼는데 역시나 메모리 초과.

질문 게시판을 보니 https://www.acmicpc.net/board/view/10692


오.. 그래서 위의 힌트에 따라 좀 더 생각해 보기로 했다....
일단 int 형은 4byte.. boolean형도 1byte인데, 1bit면.. bit연산을 이용해야 하나...
확실히 이 숫자가 존재하는지 아닌지만 판단하면 되므로 0 or 1만 있으면 될 것 같긴한데, 어떻게 그런 자료구조를 써야할지...
일단 3000만 비트를 사용한다고 하면 대략 4MB가 든다. 오..

http://www.cplusplus.com/reference/bitset/bitset/ 을 보니 bitset의 각 요소는 1bit만 차지하고, 그래서 char보다 8배 작다고 나와있다.
사용법도  http://www.cplusplus.com/reference/bitset/bitset/operator[]/ 을 보면 배열과 비슷해 보인다...그리고 처음에는 0으로 초기화가 돼있어 보인다.

한 번 구현해 봐야겠다.
AC를 받고 다른 분들의 코드를 봤는데...bitset이 없어도 가능하다...!!! 와...!!

int형 배열은 32 bit, char형 배열은 8bit...
int형 배열을 쓴다고 할 때, 만약 어떤 수 num이 들어오면, num은 arr[num/32]의 num%32번째 비트에 기록해두면 되는 것이다!!! 아 이런 방법이.. 분명 처음 보는 방법은 아니지만.. 멋지다. 아름답다.

char형 배열을 쓴다면 num/8번째 배열의 수의 num%8번째 비트가 num에 해당하는 비트!

아 그리고 혹시 맨 끝의 비트 하나는 부호를 가리키는 비트 아니냐..니까 unsigned로 해야되지 않나 생각할 수 있는데 전혀 상관없는 것이 signed이든 unsigned이든 배열안에 저장되는(표현되는) int(또는 char)값만 달라지는 것이지 결국 비트를 사용하는 것은 똑같다.

정말 놀라운 방법이다. 구현해 봐야겠다.
AC를 받았다. 좋은 문제였다.

2016년 11월 16일 수요일

BOJ 12874 괄호 문자열

"(" 와 ")" 로만 이루어진 문자열이 주어지면 그 문자열의 부분 문자열(연속될 필요 없음, 문자열에서 일부 문자를 지워서 만들 수 있는 문자열) 중에서 서로 다른 올바른 괄호 문자열의 개수를 구하는 문제이다.

백준님의 풀이를 봤다.

그래도 어렵다. 이해가 잘 안된다.
겨우겨우 이해한 것을 정리해 보겠다.

올바른 괄호 문자열을 찾긴 해야하는데, 그 중에서 중복되지 않는 즉 서로 다른 것들의 개수를 찾아야 한다.
()() 가 주어지면 여기서는 ()와 ()()로 2개이다.
일단 올바른 괄호 문자열의 최소 단위는 ()이고, 항상 "("와 ")"가 왼쪽 오른쪽에 같은 개수로 존재해야 한다. 즉, "("가 하나 있으면 ")"도 하나 있어야 한다.
어떤 것은 그리고 ()()()()나 (())(())처럼..올바른 문자열이 합쳐진 것도 올바른 문자열이다. 여튼 결국은 "("가 반드시 먼저 나와야하고, 그 이후에 같은 개수의 ")"가 필요하다.

먼저 가장 앞에 있는 "("를 찾는다. "("가 없을 때는 ")"가 아무리 많아도 의미 없는 문자열이다. "("를 찾았으면, 그 이후에 오는 가장 앞에 있는 "(", ")"을 둘 다 찾아본다.
만약 "("뒤에 ")"가 바로 오면 ()가 만들어져서 1개이다.
만약 "("뒤에 "("가 오면 뒤에 ")"가 2개 오기를 기다리게 된다. 이렇게 보면서 "("의 개수와 ")"의 개수가 같아지면 1개의 올바른 문자열을 만든 것이 된다.

"("나 ")"을 찾을 때, 가장 앞에 있는(가까운) 것부터 처리하고 계속해서 누적해가기 때문에 중복이 발생할 수 없다. ()가 한 번 만들어지면 그 이후로는 ()의 뒤에 덧붙여진 것이 만들어질 것이고 ((가 만들어지면 그 이후에도 ((뒤에 덧 붙여진 것이 만들어지므로 중복되지 않는다.

그리고 가장 앞에 있는(가까운) 것부터 처리하면서 뒤에 "("가 오는 경우, ")"가 오는 경우를 모두 보기 때문에 "("와 ")"를 최대한 많이 붙여볼 수 있어서, 즉 올바른 문자열은 뒤에 "("나 ")"가 오는 경우밖에 없고 가장 앞에 있는 것부터 처리해서 누적해 나감으로써 최대한 많이(모든 경우를) 보게 되어 모든 경우를 다 커버할 수 있다.

그래서 d[xth][open] = xth번째 문자를 볼 때(보기 시작할 때), 그 때까지 누적된 열린 괄호가 open개일 때의 서로 다른 올바른 부분 문자열의 개수.

d[xth][open] = d[next_open_xth][open+1] + d[next_close_xth][open-1]
(next_open_xth와 next_close_xth는 바로 다음에 오는 "(", ")" 의 위치)
그리고 open이 0이 되면 즉, "("와 ")"의 개수가 같아지면 count +1

구현해 보자.
구현하면서 dp구현의 편의를 위해 char str[102]로 놓고 str+1부터 채웠는데, char배열을 전역변수로 선언해놓으면 '\0' (NULL)로 초기화되는 것 같다. 그래서인지 답이 항상 0이 나왔다. 그래서 그냥 str[0]위치에 'x'를 채우고 했다.

출처 : BOJ 캠프 백준님 강의 자료 및 풀이

2016년 11월 15일 화요일

코드 그라운드 Rectangles문제를 풀면서...

음 이 문제는 종만북의 트리단원에 나와있는 요새라는 문제처럼 풀려고 했다.
먼저 여유있게 가장 큰 네모로 둘러싸고 그 네모를 root로 하는 트리를 만들되, 어떤 부모 노드의 자식이 되려면 자식 네모가 부모 네모가 둘러싼 다른 네모들에 포함되지 않고, 부모 네모에 포함될 경우 부모 노드의 자식으로 해서... 트리를 만들면 만들어진다.

처음에는 양방향으로 트리를 만들다 보니... 원래 종만북의 문제나 BOJ 어린왕자 문제같은 경우는 양방향으로 만들어도 괜찮은 것이, 원끼리 겹치는 것이 없기 때문에 한 노드는 부모를 하나만 가지는데, 이 문제의 경우 겹치는 것이 있어서 한 노드가 부모를 여러개 가질 수 있다. 그래서 양방향으로 하면 런타임 에러를 받는 것 같다. 그래서 부모가 자식만 가리키도록 트리를 만들었더니 런타임 에러는 안나고 TLE를 받았다. 아 그리고 참고로 부모가 자식만 가리키게 단방향으로 해도 이 문제는 트리를 만들고 트리의 높이를 구하면 되는 문제이기 때문에 괜찮다.

시간초과... 일단 k가 50개 이하일 때, 즉 사각형이 50개 이하로 입력으로 들어올 때는 통과하는데, 그보다 큰 데이터에 대해서는 시간초과였다.

그래서 풀이도 좀 찾아보고, 공유된 코드를 봤다. 대부분 dp로 풀었는데, 공유된 코드를 보니, 굳이 트리를 만들 필요가 없었다는 걸 깨달았다. 난 종만북의 코드처럼 트리를 만들고, 트리를 탐색했는데, 그냥 트리를 만드는 과정에서 높이를 구하면 된다...(종만북에도 그런 말이 있었는데, 그 때는 이해를 못했지만 지금 깨달았다...) 그래서 그렇게 했는데 역시 시간초과... 근데 내가 높이를 구하는 과정도 결국은 dp랑 비슷해 보였다. 아니 정확히 말하면 높이를 구할 때, dp를 쓰면 더 빨라질 것 같았다. 음 근데 나는 dp랑은 좀 다른 것이, 어떤 노드의 자식이 될 수 있는 노드만 O(n)만큼 시간을 들여서 선별하기 때문에 괜찮지 않을까...(dp로 하는 경우 직계자식이 될 수 있는 경우만 보는 것이 아니라 모든 경우를 다 본다) 하고 생각했지만...

아까 위에서 말했듯이, 내 방식대로 하면 트리가 만들어짐에도 그렇게 느린 이유는 바로 겹치는 사각형들이 있고 그 겹친 사각형들에 공통으로 포함된 사각형들이 존재해서 서로 다른 노드가 같은 노드를 자식으로 가질 수 있게되고 트리의 노드 개수가 k개가 아니라 훨씬 커질 수 있는 것이다... 결국 내 방식대로 하더라도 memoization을 이용하는 게 도움이 된다.

그래서 memoization을 적용해봤는데, 그래도 시간초과...
근데 시간복잡도를 계산해보면 난 직계자식인지 아닌지 판단하기 위해 isChild함수를 호출해서 O(n)이긴 하지만 좀 복잡하게 확인하는데 결국 O(n)이고 모든 노드에 대해 isChild함수를 호출하다 보니 d배열의 크기는 n이고.. 그러니까 결국 O(n세제곱)의 시간복잡도가 되는 것이었다...!!! 헉...

그렇다. memoization을 쓸것이므로 포함되는지만 살펴보는 enclose함수만 써주면 O(n제곱)만에 가능하다... 결국 어쩌다 보니 공유코드에 있는 분들의 코드와 똑같은 코드가 되어가고 있었다. 조금 다른 점이라면 난 매우 큰 네모를 만들어서 root로 놓고 거기서부터 시작해서 좀 편하게 한 것 정도...?..

그런데 또 시간초과.. 혹시나 해서 max를 없애고 그냥 < 비교를 통해 최대값을 갱신해봤는데, 아슬아슬하게 통과했다... 아 STL이 느리네... 음 혹시나 해서 enclose함수를 지우고 그냥 그 안의 내용을 직접 if문에 옮겼더니 0.1초 정도 더 빨라졌다.. 여유있게 통과.. 아...
enclose함수에 parameter가 복사되고 그러느라.. 시간이 좀 더 걸린건가..

어쨌든 공유코드를 보고 맞긴 맞았는데... 나름 깨달음을 얻게해준 문제였다.
이 문제는 종만북 처럼 트리의 지름을 구하는 문제가 아니기 때문에.. 굳이 트리를 쓸 필요도 없을 뿐더러, 특히 겹치는 부분이 나오기 때문에.. 트리를 만들더라도 노드의 수가 매우 늘어나서 시간초과가 난다!! 그래서 memoization을 이용해야 하고 O(n제곱)으로 구현할 수 있다.

그리고 좀 뒷통수 맞은 기분이기 한데 dp로 보면 별거 아닌 것이..
d[parent]= parent사각형부터 시작해서 겹치지 않고 포함되는 사각형의 개수 라고 하면,
d[parent]= MAX(d[child]+1) 이 될 것이다. child는 parent에 완전히 포함되는 사각형일 것이고... child사각형이 포함하는 사각형은 결국 parent사각형에도 포함될 것이므로...

아 생각도 못했었는데...여튼 공부가 많이 된 좋은 문제였다.

Baekjoon Online Judge Blog(백준 온라인 저지 블로그) 피보나치 수 특집

https://www.acmicpc.net/blog/view/28

위의 링크에 나와있는 Baekjoon Online Judge Blog의 피보나치 수를 구하는 여러가지 방법에 대해 공부해 보겠다.

BOJ 2749 피보나치 수 3 부터 좀 어렵다.
수가 매우 크지만 다행히 피보나치 수를 M으로 나눈 나머지를 구하는 것인데, 왜 다행이냐면 피보나치 수의 특성 상 피보나치 수를 M으로 나눈 나머지들은 주기를 가지게 된다. 일정 주기로 똑같은 나머지가 반복된다는 것이다. 이 것을 피사노 주기(Pisano Period)라고 한다.

BOJ Blog의 백준님 설명을 보면 피사노 주기를 구하는 공식도 소개 되어있는데, 나는 한 번 직접 주기를 구해서 풀어보고자 한다. 음 근데 직접 주기를 어떻게 구할지 모르겠다...
일단 피사노 주기를 구하는 공식으로 풀어야 겠다. 그리고 BOJ 9471 피사노 주기 문제도 있는데 이 문제도 어려운 것 같다... 일단 BOJ 9471 피사노 주기 문제부터 공부해야겠다.

BOJ 9471을 통해서 피사노 주기 구하는 방법을 알아내고 따로 정리해 놨다.
이제 BOJ 2749 피보나치 수 3 을 풀어야 겠다.
좀 헷갈리는 부분이 이 문제에서 피보나치 수가 0, 1, .. 이렇게 시작한다는 것이고 0번째 피보나치 수부터 시작한다. 그렇기 때문에 n번째 피보나치 수를 구할 때 n을 주기로 나눈 값을 pp라고 하면  0번째 수 부터 시작해서 pp번째 뒤에 있는 수로 생각하면 될 것 같다...

아 그리고 이 문제는 행렬을 이용해서도 풀 수 있다고 한다. 나중에 풀어 봐야겠다.

다음 문제는 BOJ 11444 피보나치 수 6 이다.
이 문제는 앞의 문제와 달리 무려 10억7로 나머지 연산을 해야하는데, 이 경우 피사노 주기가 매우 커지니까 피사노 주기로는 시간 내에 풀기 힘들어 보인다.(현재 내 역량으로 보기에는 그렇다..) 백준님의 설명에는 행렬을 이용한 방법으로 풀어야 한다고 나와있다.

1629번 곱셈문제를 풀었다면,


바로 위의 식을 정리해 아래의 식으로만 나타낼 수 있으면 행렬 제곱을 빠르게 계산해서 풀 수 있다. 무려 O(logN)만에... 곱셈을 빠르게 하는 것도 엄청나지만 이 피보나치 수열을 이렇게 행렬로 나타낼 생각을 했다는 것도 대단한 것 같다.
근데 첫번째 식은 이해가 되는데..(그냥 피보나치 수열 식을 옮겨 놓은 것이므로) 그 식을 정리해 아래와 같이 나타낼 수 있는지 이해를 못했었다. 그래서
이 블로그를 좀 참조 했다. 저 블로그에 나와있는 그대로 한 것은 아니고 좀 보면서 도움을 받았는데, 나는 피보나치 수를 행렬로 나타낸 식을 정리해 아래와 같이 나타내는 것에 집중해서 위의 식을 1번식, 그 아래의 식을 2번식이라고 하면 1번식의 양변에 (1 1 1 0)의 역행렬을 곱해보는 방식으로 그 블로그의 2번식 유도 과정을 따라가다보니 정말 역행렬을 이리저리 잘 곱해주면서 조작해 보면 2번식이 나옴을 알 수 있다.

그리고 이제 이 문제의 핵심중 하나는 행렬 곱셈을 구현하는 것인데, 내가 생각한 건 아니지만 백준님의 코드를 보고 이해했다. 

그리고 마지막으로 소개된 방법은 피보나치 수를 더 작은 피보나치 수의 합 또는 곱으로 구할 수 있음을 이용해서 memoization을 이용하는 방법이다.

 근데 n이 매우 큰데, memoization할 배열을 할당할 때 메모리 초과가 나지 않을까? 라는 걱정이 드는데, 백준님의 코드를 보면 dp처럼 배열을 미리 잡는 것이 아니라, map을 이용해서 memoization을 구현하고 있다. map으로 구현한 것과, 메모리 초과가 나지 않는다고 할 때, 아마 n번째 피보나치 수를 구할 때, d[1]부터 d[n]까지 모두 필요한 것이 아닌 것 같다. 위의 식을 보면 짝수든 홀수든 간에 대략 자기 자신의 2분의 1에 해당하는 값들의 합 또는 곱으로 구할 수 있으므로, 대충 짐작해보면 d[n]을 알기 위해 d[n/2]가 필요한 셈이므로 시간 복잡도 뿐 아니라 memoization에 쓰이는 배열 역시 O(logN)만큼만 필요할 것이다.
그래서 map으로 구현한 것이고, 메모리 초과가 나지 않을 것이다.

참 멋진 풀이다. 그리고 map을 사용해서 memoization을 이렇게 재귀로 구현하므로서 필요한 것만 쓰게 되고 결국 시간과 메모리에서 문제 없이 된다는 것이 매우 멋지다.
일단 위의 식이 맞는지 이해한 후에 memoization으로 구현해 봐야겠다. 음 근데 위의 식이 왜 저렇게 나오는지.. 아니 맞는지조차 증명을 못하겠다... 검색해봐도 잘 나오지 않는 것 같고... 그래서 일단 구현만 해보고 나중에 정수론 같은 것도 공부해 봐야겠다.

참고 및 출처 :
백준 온라인 저지 블로그 - 피보나치 수를 구하는 여러가지 방법
어떤 수학(정수론)관련 블로그

 











BOJ 1312 소수

a, b, n이 주어지면
a/b의 소수점 n번째 자리의 수를 구하는 문제인데, n이 매우 크기도 하고 또한 소수점 n번째 자리를 어떻게 알아내지? 라는 생각부터.. 나는 정말로 실수끼리 나눗셈을 할 생각부터 하고 있었다.
하지만 slack과 질문게시판을 통해서 놀라운(나는 생각도 못한..) 방법을 알게 되었다.
바로 a/b의 소수점 n번째 자리의 수는 a*(10의 n제곱) / b의 일의 자리수와 같다는 것!!!
그렇다 실제로 예를 들어 4를 7로 나눠서 나오는 소수점 n번째 자리의 수를 구해내는 과정이나, 4의 뒤에 0을 n개 붙여서 7로 나누는 과정이나 똑같다!! 아... 난 이런 것도 생각못하고...

자... 하지만 문제가 있다. 그래도 n이 너무 크다는 것이다. 어떻게 해야할까? 또 전혀 생각도 안나고 해서 질문게시판을 봤는데...





etaehyun4님의 이런 엄청난 답변이 있었다. 좀 생각해보니 아하..!!
4의 뒤에 0을 n개 붙인 수는 너무 커서 만들 수 없다. 하지만 4의 뒤에 0을 n개 붙인 수를 7로 나눠서 그 몫의 일의 자리수를 구하는 것은 꼭 4의 뒤에 0을 n개 붙인 수가 있지 않아도 된다. 위의 힌트대로 생각해보면 그 나눗셈 과정을 구현을 하면 되는 것이다. 4부터 시작해서 0을 하나씩 붙이면서 7로 나누고 그 나머지에 또 0을 붙여서(10을 곱해서) 7로 나눠주고... 이런 식으로 n번 반복하면 답을 구할 수 있을 것이다!

와... 멋있다. 그와 동시에 정말 내 실력의 부족함을 느꼈고.. 생각을 잘 못하면 생각하는 연습도 해보고 무엇보다 많은 문제를 끊임없이 풀어보면서 실력을 키워야겠다.