BOJ 3012 올바른 괄호 문자열에서 실수

주석 처리한 부분이 백준님의 소스코드 부분인데, 내가 짠 코드(주석 처리 안 되어있는 코드)와 무슨 차이가 있는지 아무리 생각해도 모르겠는데, 답은 다르게 나오고... 졸리고... 몇시간 버린 것 같다. 확실히 이 부분만 바꾸니 답이 제대로 나오는 걸로 봐서 이 부분이 차이가 있다는 것인데, 결국 시간을 허비하다가 내 코드가 어떤 경우에 solve를 호출하는지 보려고 출력을 해봤는데.... 헉...
보면 내 코드는 ?과 ( 같은 올바르지 않은 쌍까지 통과시킨다... 아... 이걸 몰랐다니... 백준님 코드는 ({[, )}]을 묶어서 사용하기 때문에 그럴 일이 없다.

dp어렵다 요즘은 dp를 보면 아예 생각을 하기 힘들다. 뭐랄까 차근 차근 하면되는데, 시간도 많지 않고, 사실 내가 시간을 효율적으로 못 쓴다. 앉아있기만 하지... 계속 졸고 있고... 일단 존경하는 셜록홈즈님의 말씀에 따라 dp문제들을 외워버릴까 생각중이다. 그 시작이 바로 이 문제였는데 벌써 몇시간이 날라간건지... 처음엔 완벽히 못하더라도 넘어가고 여러번 반복해서 보는 식으로 해봐야겠다.

BOJ 2820 자동차 공장 어렵다.

일단 풀이는...
Fenwick Tree를 이용하기 위해 각 사람의 부하직원들을 구간합을 구할 수 있도록 연속되게 표현해야 한다. 그렇기 때문에 preorder로(dfs가 preorder와 유사한 것을 오늘 깨달았다. 관련 링크 : http://programmers.stackexchange.com/questions/227779/is-pre-order-traversal-same-as-depth-first-search ) 트리를 순회하면 한 노드의 자식들이 연속된 구간으로 나오게 된다. 그래서 Fenwick Tree를 이용할 수 있다.


Baekjoon Online Judge Slack에서 캡쳐.

여기서 preorder로 순회하면서 각 노드의 자식들을 연속된 구간으로 표현하는 것도 어렵지만, 검색해보면 몇몇 블로그에 나와있다. 하지만 Fenwick Tree에서의 range update(구간 갱신)에 대해서는 코드는 있지만 자세한 설명이 없어서 이해하기 힘든 것 같다.
그래서 이것저것 찾아보다가 영어로 된 참조 사이트를 일단 첨부한다. 방법은 다르지만 설명은 좀 잘되어있어서 이해하기는 조금 더 낫다.

TopCoder Forums_FenwickTree_RangeUpdate
https://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/
petr-mitrichev Blog Fenwick Tree Range Updates
petr님의 사이트가 링크 되어있던 sisobus님 블로그
일단 외국사이트 방법대로 풀어보긴 해야겠다. AC는 받았는데, 어제 이해하기 힘들었던 방식을 이해하기 위해서 깔끔하고 이해하기 쉬울 것 같은 Acka님 코드를 계속 봤는데, 도저히 이해가 안되고 이게 과연 정답이 나올까 하는 의문에 결국 내가 직접 test case를 만들어서 실험을 해봤는데, 직접 test를 하면서 내가 여태 이해못했던 이유를 알 수 있었다.
내가 문제를 잘못 이해하고 있었던 것이다... 이 문제는 range update, point query문제였다!!  TopCoder Forum에도 댓글에 range update, point query에 대한 설명이 있었는데, 난 무조건 range update, range query로 생각하고 있었기 때문에 전혀 이해 못한 것이었다...

그렇다. 2820문제는 range update, point query문제이기 때문에 Fenwick Tree는 변경하지 않고 간단하게 풀 수 있다. 어찌됐든 이 문제를 풀려면 Fenwick Tree를 응용해야하고, 그에 대한 이해도 충분해야할 것이고... 정말 대단한 것 같다. preorder로 순회해서 자식들을 연속된 구간으로 표현하는 것부터, Fenwick Tree의 응용까지... 멋지다.

약 한달 반 후 다시 봤는데, 내 코드도 이해가 안되고, 링크된 사이트를 봐도 이해가 잘 안된다... 그래서 다시 공부해 보고 여기에 정리해 보려고 한다.

정리할 것은 2가지이다. 
1. Fenwick Tree Range Updates and Range Queries
2. Fenwick Tree Range Updates and Point Queries
이 문제를 2가지 방법으로 풀어볼 것이다.

1. Fenwick Tree Range Updates and Range Updates

정말로 range update를 다 해버리면 O(n)만큼 걸릴 것이다. O(n log n)만큼 걸릴 것이다. 여기서 소개하려는 방법은 O(log n)만에 update하고, O(log n)만에 query하는 방법이다. 즉 일반 fenwick tree를 이용할 때와 같은 시간복잡도로 range update와 range querie를 수행할 수 있다.
Topcoder Forum의 AnilKishore님의 설명과 Petr Mitrichev 님의 코드를 보고 생각해보자.

우리는 sum(0 ~ p)값을 구하려 하고, 그 값을 좀 다른 방식으로 표현해보려 한다.
sum(0 ~ p) = mul * p + add <- 이렇게 나타낼 것이다. 그리고 이렇게 나타내기 위해 mul과 add에 해당하는 Fenwick tree를 각각 만들어 놓아야 한다. 즉, Fenwick Tree가 2개 필요하다.
 0으로 초기화된 상태에서 범위 a ~ b에 v만큼 더해주는 것은 update(pos, mul, add) 함수를 이용해서 update(a, v, -v*(a-1)), update(b, -v, v*b) 를 해줘야 한다.
이렇게 a번째 위치와 b번째 위치에 해당하는 mul과 add를 업데이트하면 Fenwick tree 그림상에서 a를 끝으로 하는 막대와 그 위의 막대들이 모두 업데이트가 되고, 결국 a이상의 모든 위치에 대해서 query연산을 할 때, a를 업데이트 함으로 인해 업데이트 된 막대기들 중 하나를 이용하게 된다. 즉, a이상의 수들에 대해서 update(a, v, -v*(a-1))이 영향을 끼치게 된다. (단 한 번씩 영향을 끼치기 때문에 여러번 중복되지 않을까 하는 걱정할 필요 없다.)

1. 0 <= p < a 인 경우 mul=0, add=0 -> 아무 영향을 받지 않음. 즉, 0
2. a <= p < b 인 경우 mul=v, add=-v*(a-1) -> v*p - v*(a-1)
3. b <= p <= n 인 경우 mul= v-v = 0, add=v*b - v*(a-1) -> v*b - v*(a-1)

이렇게 모든 위치에 대해서 다 답을 구할 수 있다. 이제 이해는 잘되는데, 어떻게 이런 변형을 생각했는지는 모르겠다. 정말 대단하다.. 아 그리고 위의 예시는 맨 처음에 0으로 초기화 된 상태에서 a ~ b구간을 업데이트 한 것인데, 그 이후에 다른 구간들에 대해 더 업데이트를 해도 잘 생각해보면 적용이 된다.

2. Fenwick Tree Range Updates and Point Queries

point query이기 때문에 정말로 우리가 생각하는 range update를 할 필요가 없다.
일반적인 Fenwick Tree를 그대로 사용하고, 0으로 초기화되어 있는 Fenwick Tree에는 추가되는 값(변경되는 값의 크기)을 저장한다고 할 때,
예를 들어, 구간 [a ~ b]에 v만큼 더 해준다면, [1 ~ a-1]까지는 영향을 받지 않고,
[b+1 ~ n]까지도 영향을 받지 않는다. 그리고 point query이므로 [a ~ b]범위에서 point query를 할 때는 v값이 (b-a+1)번 더해져 있는 값이 아닌, 단 한 번만 더해진 값이면 된다.
그렇기 때문에, [a ~ b]에 v를 더해줄 때는 add(a, v) 와 add(b+1, -v) 만 해주면 된다.
이렇게 하면 [1 ~ a-1]은 영향을 받지 않고, [a ~ b]는 v만 더한 값이 나올 것이고,
[b+1 ~ n]은 v-v=0이 되어 영향을 받지 않을 것이다.

그리고 추가로 계속 변경되는 값이 들어와서 이런 식으로 업데이트를 해도 다 적용이 된다.
펜윅트리의 쿼리는 1~x까지의 부분합을 구하는 것이기 때문에 이런 방식이 좀 이해가 안될 수 있다. 일단 여기서는 쿼리의 의미를 x값의 변화된 값의 크기라고 볼 수 있다.

그리고 내가 이 것들을 이해하면서 알게 된 펜윅트리의 특성이 있다.
바로 어떤 x에 대해서 add(update)를 하면, 펜윅트리의 그림에서 x의 막대 위에 있는 막대들은 다 add(update)가 되고, x보다 큰 값에 대해서 query를 할 때는 그 query는 반드시 x를 update할 때, update된 막대들 중 하나만을(딱 하나만 이용하게 됨, 여러개 아님!) 계산에 이용하게 된다.

그리고 TopCoder Forum에서 VladBelous라는 분이 위의 range updates, point queries에 대해서 좀 더 쉽게 설명해놓은 것이 있다.
이 fenwick tree를 구성하는 배열을 d라고 하고 원래 배열을 a일 때, 
d[0] = a[0]
d[1] = a[1]-a[0]
d[2] = a[2]-a[1]... 이런 식으로 인접한 수의 차이로 d배열을 정의하면

a[k] = d[0]+d[1]+...+d[k]가 된다. 즉 d로 이루어진 fenwick tree에서 query를 할 경우, 구해지는 부분합은 우리가 구하고자 하는 a의 값이 되는 것이다.
그리고 d배열의 의미를 생각하면, 구간 x ~ y를 업데이트할 때, add(x, v), add(y+1, -v)를 하는 것이 쉽게 이해가 된다. 구간 x~y에서는 똑같이 v만큼 업데이트 되니까 d값또한 변경이 없다. 변경이 있는 곳은 d[x] = a[x]-a[x-1] 과 d[y+1]=a[y+1]-a[y] 이 부분이다.

확실히 이렇게 이해하면 매우 쉽게 이해할 수 있다. 이렇게 접근하는 것이 좋아보인다.

이것들을 다시 이해하고 정리하는데 일주일은 걸린 것 같고, 정말 이해가 잘 안되고 너무 귀찮은데 다른 걸 하기에는 이걸 먼저 끝내고 싶고... 찝찝해서.. 결국 이것도 일주일만에 끝내고 일주일동안 아무것도 안해버렸다. 평소에 정리를 잘 해놓고, 즐겁게 공부하자.
기본기를 쌓은 후에는 즐겨야 한다. 그러면 성과는 그 뒤에 저절로 따라온다.

출처 : Topcoder Forum과 petr-mitrichev님의 blog
추가 : 나중에 읽어볼 설명 잘 되어있는 사이트

BOJ 2315 가로등 끄기

점화식을 세울때 시간을 하나의 요소로 넣으려고 했더니... 배열의 크기가 너무 커져서 고민하다가 그냥 백준님의 강의자료를 봤는데,

d[i][j] = i~j까지의 가로등을 껐을 때 낭비되는 전력의 최소값

처음 봤을 때는 이게 어떻게 되지? 라는 생각이 들었다. 하지만 고민해보니... 일단 i~j사이에 켜져있는 가로등이 있을 수가 없다. 즉 마지막으로 꺼지는 가로등이 중간에 있을 수 없다. 마지막으로 꺼지는 가로등은 항상 양쪽 맨 끝 중 하나일 것이다. 왜냐하면, 문제를 읽어보면 가로등을 끈 동안의 시간은 무시한다고 되어있으므로 설령 다른 전력소비량이 높은 등을 목표로 잡고 끄러 간다고 해도 지나가면서 마주치는 다른 등들은 꺼버려도 전혀 손해볼 것 없고 오히려 그렇게 해야 전력의 낭비를 최소로 할 수 있기 때문이다.

그리고 실제로 풀 때는 마지막으로 등을 끈 위치도 중요하기 때문에 0과 1로 i에 있는지, j에 있는지 위치도 표시해주어야 한다. d[i][j][where] ->  where==0이면 i를 마지막으로 끈 것이고, where==1이면 j를 마지막으로 끈 것.

BOJ 1866 택배, 2141 우체국을 풀면서...

택배 문제를 보면 헬기로 여러개를 한 번에 운송할 때 어디로 운송하는 것이 가장 효율적인지를 고민해야 하는데, 이것을 식(그래프)으로 나타내면 다음과 같다.

y=|x-k1|+|x-k2|+|x-k3|+...+|x-kn|
y는 우리가 구하고자 하는 최소비용이고, x는 최소 비용을 만들기 위해 운송해야할 위치를 나타낸다. 즉 위치x로 운송했을 때 최소 비용이 나와야한다. k는 각 물건들의 목적지이고, 오름차순으로 배열된 상태이다.**

이 경우는 쉬운 편이다. 그래프를 그려보면 항상 k값들의 중간값에서 기울기가 음과 양으로 갈린다. k값들의 중간 값을 기준으로 왼쪽은 음의 기울기 오른쪽은 양의 기울기를 가지는 그래프가 된다.
생각해보면 당연하다. 이 절대값 기호로 둘러싸인 식을 일반식으로 풀어낸다고 생각해보자.
절대값 기호 안의 값이 양수이면 그냥 그대로, 음수이면 식에 -를 붙여준다. 지금 k값들이 크기순으로, 오름차순으로 배열되어있기 때문에, x가 가운데 값일 때, 그 가운데 값을 기준으로 왼쪽은 절대값 기호 안의 식이 양수가 되고, 오른쪽 식들은 음수가 되어버린다.

그래서 가운데 값을 기준으로 x가 가운데 값보다 작을 때는 -x값들이 더 많아지는 것이므로 기울기가 음수가 되고, 그 반대는 기울기가 양수가 되는 것이다.

그렇기 때문에 결국 x를 가운데 값으로 설정했을 때 최소값을 가지게 되는 것이다. 그리고 k값들의 개수가 짝수인 경우는 x가 될 수 있는 값이 가운데 2개가 같은 최소값을 갖게 될 것이고 아무거나 선택해도 된다.

2141번 우체국 문제 같은 경우는 약간 더 생각을 해봐야한다.
식(그래프)이 y=a1*|x-k1|+a2*|x-k2|...an*|x-kn| 이런식으로 절대값 기호 앞에 곱이 하나 붙는다. 이렇게 되면, 일반식으로 풀어썼을 때 x앞에 계수가 붙으므로 이 계수의 크기가 중요해진다. 그래서 결국 선택을 할 때 계수값들의 합의 중간값이 포함된 k를 선택해줘야 하는 것 같다.
center=(a1+a2+...+an)/2 라고 하면 center값이 포함되는 부분의 k값을 x의 값으로 해야 그래프에서 최소값이 나오는 부분이 되는 것 같다.
결국 2141을 AC받았는데, 틀렸던 이유는 sort를 안해준 것이었다.

2141 우체국 문제를 다시 풀었는데, 예전에 풀었던 것을 보니 누적합을 따로 구해놓고 비교했던데, 그럴 필요 없이 맨 처음에 전체 합(sum)을 구해놓고, sorting한 후, for문 돌면서 처음부터 누적합(psum)을 구하면서 psum>=sum-psum 이 되는 순간 그에 해당하는 x좌표가 답이된다. 처음으로 psum>=sum-psum 이 되는 순간이 바로 그래프에서 기울기가 0이 되기 시작하거나, 음의 기울기에서 양의 기울기로 바뀌는 순간이기 때문이다. 그래서 그 부분이 최소값!

BOJ 1648 격자판 채우기

백준님의 강의자료를 보고 풀었다.
다시 한 번 풀어보면서, g+1해줘도 되지만, 경우에 따라 g+2 , s>>2를 해줘도 되는 경우가 있어서 그렇게 풀어봤는데, 예제의 답이 매우 큰 수가 나왔다. 그래서 그것을 g+1, s>>1이런 식으로 고치면 정답이 나온다... 도대체 왜 그럴까 거의 1시간을 고민하다가 아까 백준님의 소스 코드에서 본 기저사례 처리 방법이 기억이 났다. 아까 처음에 봤을 때는 별 차이 못느꼈는데 계속 틀리게 되어 차이를 알게 되었고, 왜 그렇게 기저 사례 처리를 하셨는지 알 수 있었다.

난 기저 사례 처리를 if(g==n*m) return (s==0); 이렇게 한다.
그런데 백준님은 if(g>=n*m)이 들어가있다. 바로 g+2, s>>2 같은 방식 때문이다. g+1, s>>1식으로 한 칸씩 본다면 g==n*m이 될 때가 오겠지만, 2칸씩 간다면 저 기저 사례 조건에 걸리지 않을 수 있기 때문이다. 그래서 매우 큰 엉뚱한 값이 나온 것이었다. 지금 생각해보니 무사히 종료한 것도 신기하다.

BOJ 1328 고층 빌딩

모르겠어서 백준님의 강의 슬라이드 풀이를 봤는데, 일단 d[N][L][R]로 설정한 것은 같았지만 아예 접근 방식이 다르다...

나로써는 전혀 생각조차 못해서 그런지(어쩌면 생각을 안 한 것일 수도...) 감탄이 나오는 방식인데, 기본이 되는 아이디어는
1. 빌딩이 1~N까지의 빌딩이 있으면 2~N까지의 빌딩으로 만들 수 있는 모든 경우를 만들고, 2. 거기다 남아있는 높이 1의 빌딩을 넣어보면서 경우의 수를 세는 것이다!

높이 1의 빌딩은 높이가 가장 작기때문에, 1을 넣는 방법은 이미 2~N으로 만들어 놓은 어떤 경우에도 항상 동일한 규칙으로 적용되어 경우의 수를 구하기가 용이하다.

처음엔 왜 이렇게 하나 이해가 잘 안되었는데, 이렇게 하면 당연히 모든 경우의 수를 커버할 수 있을 뿐만 아니라 경우의 수를 세는 규칙(점화식)도 알 수 있어서 좋은 것 같다.

좀 더 생각해보고 정리해서 풀어봐야겠다.

일단 풀었는데, 처음에 틀리길래 int를 long long으로 바꾸었더 AC를 받았다. 분명 중간 중간에 일일이 1e9+7로 나누어주는데 왜 integer overflow가 나지? 이렇게 한참 고민하다가 깨달았다!

바로 ret+=building(n-1, l, r)*(n-2) 이 부분이다! n-2만큼 곱해주니 integer overflow가 날 수 있는 것이다. 그래서 이것을 for문으로 고쳐서 n-2번 더하면서 계속 나눠줬는데, 그러니 시간이 더 오래 걸린다. 내가 듣기로는 일부 연산의 경우 나누기였나? %였나 많이 하면 시간에 꽤 영향을 준다고 들었는데, 그래서 그런 것 같다. 컴퓨터 구조 열심히 공부했으면 왜 그런지 알았을 텐데 일단 나중에 공부 해봐야겠고, dp 열심히 해야겠다.

Algospot :: TRIPATHCNT 계속 오답이었던 이유.

정말 어이없는 실수를 하고 말았다.

더 큰 문제는 그런 실수를 하고도 한동안 그 실수를 깨닫지 못했다는 것이다.

이 문제에서 숫자의 합이 가장 큰 경로의 개수를 구하기 위해서 일단 각 점에서 출발하는 경로중 숫자의 합의 최대값을 dp로 구하고 그것을 이용해서 각 점에서 출발하는 숫자의 합이 최대가 되는 경로의 개수를 구하였다.

다음 점을 선택할 때, 선택할 점은 바로 아래 혹은 오른쪽 대각선 방향 아래로 2가지 점밖에 없다. 그 두 가지 점중에서 어느 점으로 가야 숫자의 합이 최대가 되는 경로인지 찾아서 만약 둘다 똑같다면 두 점에서 출발하는 (숫자의 합이 최대가 되는)경로의 개수를 더하고, 다르다면 그 숫자의 합이 최대가 되는 경로를 갖고 있는 점을 선택해서 그 점에서 출발하는 경로의 개수를 택하면 되는 것인데...

나는 다음 두 점이 다를 경우 숫자의 합이 최대가 되는 경로를 갖고 있는 점을 선택하지 않고, 그냥 경로의 개수가 더 큰 점을 선택하였다.
근데 이게 정말 알아차리기가 힘들었다. 아무리 봤지만 알아차리지 못했고, 정답 코드를 실행해보고 비교해보면서도 한동안 이해 못했다...

그래도 결국 이해해서 다행이다.

BOJ 2293 동전1

기본적인 dp문제들 중 하나이다.
하지만 어렵다...

2차원 dp 풀이 참고 : https://www.acmicpc.net/board/view/6217
2차원 dp로 푸는 방법이 가장 이해하기 쉽지만 이 문제에서는 메모리 제한이 4GB이기 때문에 2차원 dp를 쓸 경우, sliding window기법을 이용해야 한다.

혹은 2차원 dp의 식을 잘 살펴보고 표로 그려보면, 없어도 되는 부분이 있다. 그래서 그 식을 좀 수정하면 1차원 dp로 바꿀 수 있다. 

2차원 dp를 간단히 만든 1차원 dp랑 같긴하지만, 처음부터 1차원 dp로 생각해서 짠다고 해보자. 1차원 dp로 프는 방법이 좀 이해하기가 어려운데, 그리고 이해해도 시간이 지나면 다시 이해못하게 되는 그런... 그래서 여기서 내가 이해한 것을 기록해놓으려 한다.

d[k]=주어진 동전 n개를 적절히 사용해서 k원을 만들 수 있는 경우의 수.
d[k]=d[k-a[1]]+d[k-a[2]]+d[k-a[3]]+...+d[k-a[n]] (a[1]~a[n]은 n개의 동전들)
==>이렇게 k원을 만들 수 있는 경우를 사용할 수 있는 동전을 다 사용한 경우들의 합으로 할 경우, 중복이 발생한다. 1+2+1과 1+1+2 는 같은데, 다른 것으로 개수를 세는 것이다.

그렇다면 어떻게 해야할까?

바로 하나의 동전을 이용해서 모든 k에 대해 k를 만들 수 있는 경우의 수를 구하고, 이제 그 동전은 사용하지 않는다. 그리고 구해놓은 것을 이용해서 다음 동전을 이용해서 모든 k에 대해 k를 만들 수 있는 경우의 수를 모두 구한다... 이런식으로 동전을 하나씩 사용하면서, 동전 하나에 대해서 모든 k에 대한 경우의 수를 구하고, 그 동전은 더 이상 사용하지 않는식으로 하면 중복되지 않는 경우의 수를 구할 수 있다.

참고) 이해가 잘 안되면, 직접 써보는 것이 이해하기 수월하다.
추천 예제 : k=7, n=3, 동전 : 1원, 2원, 5원
0 : X
1 : 1*1
2 : 1*2
3 : 1*3
...

BOJ 2225를 풀면서 dp - sliding window를 쓸 때 주의할 점!

dp에서 memory를 줄이기 위해 sliding window기법을 썼지만, 틀렸습니다가 나와서 내가 직접 확인해보니 AC코드의 답보다 더 컸고, 입력이 커질수록 그 차이는 더 커졌다. 이 문제의 경우 바로 직전 행의 값들로 현재의 행의 값을 채우기 때문에 sliding window적용하기도 매우 쉽고 잘 적용했는데, 왜 그런걸까... 꽤 오래 고민하다가 직접 출력을 해서 봐야겠다는 생각이 들어 직접 출력해보고 나서야 이유를 깨달았다.

이 문제의 경우, 현재 칸의 값을 구하기 위해서는 직전 행의 값들의 합을 구해야되서, 직전 행의 값들을 현재 칸의 열 범위까지 하나씩 더해준다. 근데, sliding window를 쓰지 않고 했을 경우, d배열을 0으로 초기화한 상태에서 하기 때문에 괜찮은데, sliding window기법을 썼을 경우에는 맨 처음을 제외하고는, 즉 두 번째 부터는 d배열에 값이 들어가있다. 그래서 거기다가 더해주게 되는 것이고 AC코드보다 더 큰 값이 나왔던 것이다.

그래서그 합을 구하는 for문에 들어가기 전에 배열을 0으로 초기화해 주었고, AC를 받았다.

//그리고 이 문제는 2차원 배열에서 sliding window를 쓰는 방법 말고도, 그냥 1차원 배열로 써서 메모리를 줄일 수 있고, 또한 속도도 더 빠르게 하는 방법들이 존재한다.

잊어버릴 때쯤복습, 그리고 복습 또 복습! 결국은 일정 기간을 두고 꾸준한 복습뿐이다!

SPFA(Shortest Path Faster Algorithm), BOJ 11657 타임머신

spfa는 bellman-ford 알고리즘을 개선한 알고리즘이라고 볼 수 있다.
bellman-ford알고리즘은 E개의 모든 간선에 대해서 V번 업데이트 해보는데, spfa는 E개의 모든 간선을 업데이트 하는 대신 갱신된 노드에 연결된 간선들에 대해서만 업데이트 한다.

bellman-ford처럼 모든 간선에 대해서 업데이트를 하더라도, 결국은 직전에 갱신되었던 노드에 연결된 노드들만 업데이트될 것이기 때문에, spfa는 bellman-ford에서 불필요한 업데이트 과정을 빼서 성능의 향상을 노려볼 수 있다.

하지만 spfa역시 최악의 경우에는 bellman-ford와 같다고 하고, 평균적으로 O(E)의 시간복잡도를 갖는다고 한다.

그리고 또 하나 문제가 되는 것이... 바로 음수 사이클의 존재 여부를 판별하는 것인데, 일단 시작점에서 각 점들까지의 최단거리는 최대 V-1개의 edge로 연결되어 있고, 한 번 update할 때마다 최단 경로를 구성하는 적어도 하나의 edge는 찾게 되므로 최대 V-1번만 update하면 최단 경로가 찾아지고, 만약 negative cycle이 존재한다면 V번째도 update(relax)가 될 것이다.

(정점의 개수V를 n으로 놓고 써야겠다.)
spfa같은 경우는 조금 까다로워 보일 수 있는데, 일단 spfa방식은 queue를 사용하고, bfs와 유사하기 때문에 bfs에서의 한 단계를 수행할 때마다 (최단 경로를 구성하는) 적어도 하나의 edge는 찾게 될 것이다. 그러므로 bfs의 단계가 최대 n-1번만 실행되고 더이상 실행이 안되어야 정상인데, 만약 더 n번이상 실행된다면 negative cycle이 있는 것으로 볼 수 있겠다.

더 간단한 방법으로는 각 정점이 queue에 들어가는 횟수를 기록해놓고 그 중 하나라도 n번 이상이 되면 negative cycle이 있는 것으로 판별하는 것이다. negative cycle이 없다면 어떤 정점이 queue에 n번 들어가기전에 이미 최단거리는 구해졌을 것이다. 그래서 어떤 정점이 queue에 n번 들어갈리도 없을 것이다.

그리고 내가 잘못 생각했던 것이, 그냥 정점이 update될때마다 횟수를 세서 n번 이상 update되면 negative cycle로 판별하는 것이었는데, 통과할 때도 있겠지만... 안되는 것이... 일단 반례를 찾았다. 정점이 2개가 있고, 그 두 정점을 연결하는 edge가 여러개인 경우에 negative cycle이 있다고 잘못 판별하게 된다.
ex) A와 B사이에 A에서 B로 가는 각각 가중치가 5, 4, 3, 2, 1이렇게 있을 때 5번이나 갱신하게 된다.

 - 끊임없이 배우고 생각하고 깨닫자.

추가+) 11657 타임머신 문제를 spfa로 풀어보았다. 위의 방법중에, bfs의 단계를 세주는 방식으로 구현해봤는데, bfs의 단계의 수를 cnt에 기록하고, cnt가 n이상이 되면 negative cycle인 것으로 판단하였다. 근데 cnt가 n 이상인지 판단하는 위치가 중요하다.

1) WA를 받는 코드(cnt가 n이상인지 판단하는 위치 잘 보기)

이렇게 할 경우, n-1번째 단계에서서 최단 경로에 속한 마지막 edge를 찾은 후 queue에 마지막 vertex가 들어가 있을것이다. 그리고 cnt=n-1일 것이다. 그리고 다시 while loop로 올라가서 내려오면서 보는데, 이미 최단 경로를 찾았기 때문에, 마지막 vertex에 연결된 점들은 더이상 갱신되지 않을 것이다. 그래서 queue는 비게되고, 여기서 while문을 탈출하면 되는데, 문제는 저 cnt>=n인지를 보는 코드가 아래에 위치해 있기 때문에, cnt++을 한 후 cnt는 n이되어 negative cycle로 판별하고 종료해버린다.

그렇기 때문에 이 것을 해결하기 위해서 저 부분만 위로 올려주면 된다.

2) AC를 받는 코드(cnt가 n이상인지 판단하는 위치 잘 보기)

이렇게 바꿔주면, 위에서 말한 경우는 while(!q.empty()) 이 부분에서 while loop를 탈출하게 될 것이다.

음 이렇게 쓰고 보니 좋은 방식인지는 모르겠다.
아니면 그냥 중간에 q가 비어버리면 break를 시킨다든지 하는 방법도 있을 것이다.

플로이드 문제를 풀다가...

내가 여태 플로이드 문제를 풀 때, 처음 초기화를 할 때, i와 j사이에 길이 없으면 INF로 초기화해주는데, INF의 값을 2e9;로 했다가 계산 중에 정수 범위를 넘어가는 문제가 발생해서 그냥 입력 비용 제한의 최댓값+1으로 설정했었는데 그러면 안된다. 왜냐하면, 비용의 제한의 최대가 10000이라고 치면 9000씩 여러개의 경로를 통해서 i에서 j로 가는 경로는 10000을 넘는데, INF가 10000이므로 경로가 없다고 할 것이기 때문이다...

그러니까 INF는 나올 수 있는 최대 경로의 길이로 설정해야 한다...

BOJ 1507을 풀다가 vector와 boolean...

vector로 2차원 boolean배열을 true로 초기화하면서 할당하려고 했는데, 값을 출력해봐도 이상한 값으로 차있고, 대입 연산을 통한 값의 변경도 안된다...뭐지, 그래서 구글링을 해보니 C++98(?)에서는 1byte가 아닌 1bit를 bool에 쓴다나.. 여하튼 제대로 갖춰져 있지 않은 것 같긴하다. 나중에 시간 있을 때 자세히 찾아봐야 겠다.

BOJ 11780 플로이드 2 문제 이해...

내가 문제가 잘 이해가 안 되었던 것이, 문제에선 i에서 j로 갈 수 없으면 비용과 경로를 그냥 0으로 출력하라고 하는 것인데,
다시 생각해본 결과는 다음과 같다.
1->1로 가는 것은 경로가 1->5->1 이런식으로 존재한다.
하지만 0이 출력 되어있는 것은 자기자신으로 가는 것은 최소비용이 0이므로 그냥 0을 비용으로 보면 될 것 같다. 문제는 경로 부분인데, 경로에도 0이 출력되는 것은 자기자신에서 움직이지 않으니 경로가 없다고 봐도 될 것 같고, 물론 문제에선 i에서 j로 갈 수 없으면 경로를 0으로 출력하라고 되어있어 좀 석연찮은 부분이 있긴 하지만, 일단 i에서 j로 갈 수 없는 경우를 두가지로 나눠보면 좀 해소가 된다.

i에서 j로 갈 수 없는 경우
1. i==j인 경우
2. 그 외의 경우들

그리고 비용 값으로 들어오는 입력은 100000 이하의 자연수! 이므로 0이 들어올리는 없기 때문에, adj[i][j]가 0이거나 INF인 경우 i에서 j로 갈 수 없는 경우로 보면 될 것 같다!

뭔가 막히고 모르겠고 이해 안되는 것이 있으면, 혼자 생각하지말고 그냥 누군가한테 모르는 걸 설명해보는 것 자체도 물어보는 것 자체도 나의 생각을 정리하고 실마리와 깨달음을 얻는 데 도움이 되는 것 같다. 테디베어 효과인가...

추가+) 플로이드 문제를 풀 때 내가 경로가 없는 경우는 0을 출력해주는 부분을 깜박했는데도 맞은 것 같다. 빼머지 말고 꼭 쓰자! 중요!

BOJ 1600 말이 되고픈 원숭이

yukariko(유카리코)님의 코드와 방식을 거의 그대로 사용하여 풀었다.

이 문제를 풀면서 다시금 내가 bfs에 대한 이해가 부족하다는 것을 느꼈다.
유카리코님의 코드를 보면 정말 bfs를 꿰뚫고 있어야 저런 코드를 짤 수 있구나 하는 것을 느낀다. 정말 멋있는 방법이었다.

그리고 같이 공부하는 wonsik의 아이디어도 시간 단축에 큰 몫을 했다. 바로 왼쪽 위 부분의 2방향은 볼 필요가 없다는 것이다. 왼쪽 위에서 오른쪽 아래로 가는 것이므로 또한 최소 횟수를 구하는 것이므로...(물론 확실히 증명하거나 한 건 아니지만...음) 일단, 목표지점이 맨 오른쪽 맨 아래 이기도 하고, 어떤 위치에서 저 두가지 방향을 써서 돌아갔다가 목표지점 까지 가는 것보다 그 위치에서 바로 목표지점까지 가는 것이 나을 것이고...음 생각을 해봐야겠지만... 일단은 그래보인다.

(2년 뒤에 보니... 재채점이 되어있었고, 내가 제출한 상당수의 코드가 AC에서 WA로 바뀌어 있었다... 아마도 왼쪽 위의 2방향을 볼 필요가 없다고 처리해서 그런 것 같다. 사실 생각해보면 왼쪽 위의 2방향도 봐야하는 경우가 있을 수도 있을 것 같다. 돌로 막혀 있어서, 왼쪽 위로 갔다가 나와야 하는 그런... 앞으로 증명하지 않고 추측으로만 코드를 짜는건 자제해야겠다. 실제로 그 부분만 고쳐서 내보니 )

이제 유카리코님의 아이디어를 보면, 여기서 구하는 답인 원숭이가 움직인 횟수는 결국, bfs를 쓰기 때문에 처음으로 방문한 곳이 최소의 동작횟수를 써서 방문한 것이 되는 것이고, 그 동작횟수라 함은 bfs의 단계의 개수로 볼 수 있다.

그래서 목적지가 처음 나오기 전까지, bfs의 단계가 몇단계인지 세주는 것이다...!

유카리코님의 아름다운 코드 였다.

BOJ 1504 특정한 최단 경로 - 계속 WA를 받은 이유

오랜만에 복습도 할겸 다시 풀어봤는데, 계속 틀렸습니다가 나왔다.

이유는 Integer Overflow!!!
int형 변수를 사용하고 있는데, 내가 INF값을 2e9, 즉 20억으로 잡아놓았기 때문에,
경로가 존재하지 않는 경우, INF값이 더해지면서 결과값이 int형 범위를 초과할 수 있다...

게시판 질문에도 나와 같은 케이스가 좀 있어서 그것을 보고 알 수 있었다.
예전에 제출한 코드를 보니 INF를 240만으로 설정해놓았는데, 그 이유는 주어진 간선의 개수가 800개이고, 간선의 가중치(거리)가 최대 1000이라 최단 경로는 최대 (800-1)*1000 가 나오겠지만 여유있게 800*1000=800000(80만)으로 해놓고, 그리고 문제에서 구하는 경로는 3가지 최단 경로로 구성되어 있으므로 80만 * 3 = 240만... 이러면 오버플로우도 일어나지 않는다.

BOJ 11779 최소비용 구하기2 - 메모리 초과가 난 이유

간단히 적자면,
내가 dist[src]=0으로 초기화를 안해주었는데, 우선 순위 큐에는 0, src를 넣어줘서 최단거리는 구해졌다. 하지만, dist[src]와, parent[src]가 갱신이 되면서 마지막에 경로를 stack에 넣는 과정에서, parent[src]에 넣어놓았던 값이 바뀌었기 때문에, 계속 stack에 push하게 되어 메모리 초과가 나는 것이다...! 실수 하지 말자. 연습하자! practice makes perfect!