BOJ 11658 구간 합 구하기3

백준님의 풀이 슬라이드를 보고 풀었다.

처음에 고민할 때는 2차원배열의 각 칸에 번호를 매겨서 segment tree혹은 fenwick tree로 풀려고 했는데, 그러면 조금 복잡해질 것 같기도하고 해서 고민하다가 그냥 풀이 슬라이드를 보니... 2D Fenwick tree란 것이 있었다.

막 와닿지는 않는데, 대충(?) 살짝 억지로 이해하고 넘어가는 중이다...
문제도 그 풀이대로 풀었다.

탑코더 페이지에 보면 좋은 그림이 하나 있긴한데, 그 그림을 봐도 이해가 되고, 와닿는 것은 아니지만 일단 참고하면 좋을 것 같다.
Fenwick Tree(in topcoder community)

그리고 문제를 푼 후 dotorya님의 코드를 봤는데, 넓이를 구할 좌표 2개를 입력 받고
좌표의 크기를 비교한 후 swap시키는 코드가 있었다. 생각해보니 문제 조건에
x1, y1, x2, y2가 주어졌을 때, (x1 <= x2 && y1<= y2) 라는 조건이 없다! 그렇다면 dotorya님의 방식대로 해주어야 한다!

난 별 생각 없이 ....당연히 저 조건을 만족하는 입력만 들어올 것이라고 막연하게 생각하고 있었던 것 같다.
항상 조건을 잘 보고, 그에 맞는 코드를 짜도록 하자!

2016년 9월 22일 추가+
오늘 BOJ Slack에서 이 문제에 대한 appa님의 풀이를 보게 되어서 그렇게 풀어보고 여기 간단히 정리해보려고 한다.


 

appa님의 설명이 정말 잘 돼있어서 굳이 내가 뭘 쓸 필요가 없을 것 같다. 그리고 이 풀이로 AC를 받기 전까지 몇 번 틀렸는데 그 이유는 누적합을 update해준 후, 배열의 값을 update해주지 않아서 였다. 주의하도록 해야겠고, 확실히 이렇게 푸는 것이 훨씬 쉬운 것 같다. 물론 속도는 좀 더 느리게 나왔다. 아마 2D FenwickTree로 풀면 FenwickTree안에 2중 for loop가 있기 때문에 O(M*logN*logN)이 나오지 않을까 생각한다...

BOJ 2042 구간 합 구하기를 풀던 중 실수

2042번 구간 합 구하기 문제를 Fenwick Tree로 풀어보고 있었다.

long long을 이용해야 했는데,

int a, b, c;
scanf("%d %d %lld", &a, &b, &c);

이렇게 코드를 작성해버리니 런타임 에러가 나서, 살펴보니, b에 0이 들어가있었다...

int a, b;
long long c; 로 고쳐주니 해결되었다. 왜 b에 0이 들어갔는지는 자세히는 모르지만, 일단 내가 변수 type을 잘못 선언했던 것이 1차 원인이었던 것 같다. 변수 선언 잘하자!
실전에서 이런 실수를 하면 찾기 힘들다!

12969 ABC 백준님 코드 분석...

백준님의 코드를 봤는데,
d[i][a][b][p] 의 의미가
"i번째까지 A가 a개, B가 b개 이고, s[l]<s[m] 쌍이 p개인 경우를 검사(방문)했었는가?"
같아 보인다...

그래서 d[i][a][b][p]가 true이면, 검사(방문)를 했다는 뜻이고, 이 경우에는 false를 return 한다. 이미 검사(방문) 했으면, 해당하는 문자열이 존재하지 않는 경우는 당연히 false이고, 존재한다면 이미 return true해서 그것이 답이 되었을 것이다....

일단 여기까지가 내 생각인데,
백준님한테 여쭤봐야겠다.

12969번 ABC - memoization을 이용한 문자열 구하기에서...

처음엔 백준님의 정답 코드를 이용해서 모든 가능한 입력값에 대한 답을 구한 후 비교를 하려고 했는데, 일단 -1이 나오는 경우는 비교를 했는데 똑같았다. 그 외에는 답이 다르기 때문에...(special judge) 그래서 결국 내가 직접 내 코드의 출력 값이 맞게 나왔는지 검증하는 코드를 짜서 비교해본 결과 나온 반례가

13 40 -> ACBBACCCCCCCC 였다.
확실히 틀렸다.

음... 그래서 분석을 하는데 정말 힘들었다. 내 생각에 따르면 절대 저렇게 답이 나오면 안되는데... 직접 출력도 해보고 그려보기도 하고 했는데도, 점점 범위를 좁혀나가면서 알듯 말듯 했는데, 결국 알아냈다!

바로 단순히 재귀가 아닌, dp를 이용하기 때문이다.
정확히는 memoization을 이용해서 한 번 살펴본 것은 더이상 살펴보지 않기 때문에, 문자열이 잘못 나오는 경우가 발생한다...

더 자세히 기록하자면... 일단 memoization때문에 한 번 살펴본 것은 다시 안 보는데, 예를 들어 처음에 dp(3, 2, 1, 2)에 대하여 'ABB'가 저장되었다고 하자.
그럼 이제 더이상 dp(3, 2, 1, 2) 인 부분은 의심하지 않고 넘어가게되는데, 문제는 'ABB'이 것이 유지가 안된 다는 것이다. 배열을 전역변수로 놓고 계속 업데이트 되기 때문에 중간에 다른 과정을 거쳐 'ABB'가 'BCA'로 바뀌었더라도, memoization때문에 그 부분은 살펴보지 않게 되는 것이다. 물론 그냥 재귀라면 다시 살펴보기 때문에 옳은 값이 나온다.

근데 이렇게 원인은 알았는데, 이제 이 것을 어떻게 수정해야할지도 문제다...

일단 아까도 중간에 잠깐 해보았지만, 다시 수정한 것이

이 부분에서, if, if, if를 if, else if, else if로 바꿔서 되는 경우 하나만 보게 하는 것인데, 이렇게 실행해보니 일단 내가 만든 검증 코드에서는 맞는 것으로 나온다.

그래서 생각해보니 ...지금 문제가 전역변수인 어레이가 수정되어도 안보게 되는 것인데,
위와 같이 수정할 경우, 어레이가 수정될리가 없다. 왜냐하면 true이면 그걸 쓰기 때문이다.

다시 설명하자면, 처음 코드에서는 세 번 dp를 호출하면서, 만약 첫 번째 dp에서 true인 것을 memoization하고 그 부분은 array를 더 이상 안 보게 되는데, 세번 째 dp에서 만약 그 memoization인 부분을 만나면 당연히 true이므로 array는 당연히 맞겠지 하고 넘어가지만, array는 전역변수라 중간에 다른 dp들에 의해 바뀌었을 수 있다!!!

하지만, 위와 같이 수정할 경우, 되는 것 하나만 보기 때문에, 되는 것을 다보는 처음 코드처럼 array의 수정이 일어나지 않을 것이다!

한 번 제출해봐야겠다!
맞았습니다! 가 떴다...
시간을 많이 소비하긴 했지만 그래도 이렇게 문제점을 완전히 파악하고 고쳐서 제출해서 다행이다.

BOJ 1505 두 번 뒤집기

처음에는 오름차순 구간, 내림차순 구간을 구해서 각 구간을 구성하는 요소들의 모든 조합으로 다 해보고 일치하는지 찾아보려고 했는데... 많은 경우에 맞지만, 안 되는 경우도 있다는 것을 예제들을 만들어보면서 알게 되었다.

일단 2504문제에서 시간도 많이 뺐겼고, 공부할 것과 날 기다리고 있는 문제들이 매우 많기 때문에 이 문제의 해법을 검색해봤다.

해법은 다음과 같다.

  1, ..., n까지의 수열이 있다면 맨 앞의 수(1) 혹은 맨 뒤의 수(n)를 기준으로 차례대로 원래 위치와 비교해가면서 찾는 방식인데, 이게 어떻게 성립이 되느냐 곰곰히 생각해보니 두 번 다 뒤집어서 숫자들의 위치가 변했을 때, 맨 앞의 수(1)과 맨 뒤의 수(n) 둘 중 하나는 한 번 뒤집힐 수 밖에 없다. 반드시 둘 중 하나는 원래 위치에서 한 번 뒤집혀 바뀐 위치에 위치하므로 맨 앞 수나 맨 뒤의 수를 기준으로 뒤집은 구간을 찾아나가면 되는 것이다.

또한 맨 앞의 수나 맨 뒤의 수가 한 번 뒤집혀서 위치가 바뀌었을 경우, 그 뒤집은 구간의 경우의 수는 하나 밖에 존재하지 않는다.

그리고 맨 앞의 수나 맨 뒤의 수를 기준으로 해서 뒤집은 구간을 구한 후에는, 바로 그 다음 수로 하나씩 늘려나가면서(줄여나가면서) 확인해봐야 하는데, 이것 역시 이렇게 해야 경우의 수가 하나 밖에 존재하지 않기 때문인 것 같다.

일단 코드 짜봐야겠다.

열심히 하자!
복습하자!
준비된 자에게 기회가 온다.