BOJ 1799 비숍

이 문제는 예전에 시간초과나고 어떻게 고쳐야할지 몰라서 포기했던 문제인데, 약 3달이 지난 오늘 다시 코드를 보니, 일단은 (1, 1)칸부터 시작해서 각 칸에 비숍을 놓을지 아 놓을지 결정하는 백트래킹으로 풀었는데, 좀 이상한 점이 눈에 띄었다. 바로 각 재귀함수마다 비숍을 놓을지 말지 결정하는 칸부터 끝 칸(n, n)까지 다 본다는 것이다. 어차피 한 칸을 결정한 후 결정된 체스판의 상태에 맞게 뒤따르는 칸은 재귀함수로 호출해서 살펴보는데..뭐하러 각 함수내에서 for문으로 전체 칸을 다 보려고 하는거지? 완전 낭비이다.

한 번 고쳐서 제출해 봐야겠다.

그리고 다시 보니, 한 칸을 결정할 때, 비숍을 놓기로 결정하면 대각선 방향의 칸에는 비숍을 놓을 수 없게 되는데, 이 것을 어떻게 체크하냐면 만약 (r, c)에 놓는다 치면, x+y == r+c이거나 x-y==r-c인 곳은 놓을 수 없는 대각선을 의미하게 된다.

구현이 간단하지는 않다. 조금 까다롭지만 예제로 테스트 해보고 제출했는데 또 시간초과..
이렇게 하는 방법도 결국은 최대 2의 100제곱이라 그런 것인가...
문득 든 생각이 그렇다면 memoization을 활용해 보는 것... 음 근데 그렇다면 체스판의 상태에 따라 다르게 결정되므로 체스판의 상태에 따라 memoization을 해줘야 하는데, 상태dp를 하듯이 state를 배열로 판별하면 ...칸이 최대 100칸이라 너무 크다. 음...

--------------------------------------------------------------------------------

백트래킹을 어떻게 해야 시간을 단축시킬 수 있을까?
질문 검색을 보다가 힌트를 얻었다. nqueen문제는 한 행씩 한 열씩 제하면서 가면 되듯이, 이 비숍문제는 대각선 한 행이 아닌 한 번에 한 대각선이다!
오... 일단 대각선/을 차례로 보면서 대각선/에 있는 칸에 bishop을 놓을지 말지 결정하고, 그에 따라 반대 대각선\도 체크하면서 나간다. (그리고 전체 칸 n*n을 체크할 필요 없이 어떤 대각선에는 놓을 수 없다... 이런 식으로 대각선별로 체크하면 된다.)

대각선을 체크하기 위한 배열을 쓰려 하는데, 각 대각선에 해당하는 index를 어떻게 맞출까 고민이다. 각 칸은 행과 열로 나타낼 수 있는데, 어떤 대각선에 속하는지 판별하기가 쉽지 않다.
일단 반대 대각선\에 대해 보면, (0, n-1)부터 시작하는 대각선부터 (n-1, 0)부터 시작하는 대각선까지 2n-1개의 대각선이 존재한다.
특징을 보면
 (0, n-1)부터 시작하는 대각선상의 칸 (x, y)는 x-y값이 -(n-1) 이고,
쉬운 이해를 위해, (0, 3)부터 시작하는 대각선 상의 칸 (x, y)에 대해 x-y값은 0-3이다.
즉 반대 방향 대각선\의 경우 각 대각선에 존재하는칸의 행-열 값이 각 대각선마다 고유하다. 그런데 음수이면 배열의 index로 쓸 수 없으므로 n-1을 더해준다.
그럼 (0, n-1)부터 시작하는 대각선의 index는 0이 되고, (0, n-2) -> index1,....., (n-1, 0) 에서 시작하는 대각선의 index는 n-1이 된다. 이렇게 반대 방향 대각선\에 대해서 index를 0부터 n-1까지로 나타낼 수 있다.

그리고 대각선/단위로 볼 때, 비숍을 한 대각선/에 하나만 놓거나 아예 안 놓거나 둘 중 하나이다. 그래서 아예 그 대각선/에는 놓지 않는 경우를 처리해주고, 한 칸에만 놓는 경우들을 처리해주면 된다.

그리고 backtracking함수의 parameter로 r, c를 보내는데, 이 행, 열 정보는 각 대각선/의 시작점을 의미한다.

그런데도 시간초과를 받았다. 시간 복잡도에 대해 생각해보니 각 대각선 별로 한 칸씩 선택하는 경우와 선택하지 않는 경우에 대해 다 해보는 것이므로 O(2*3*....*(n-1)*n*(n-1)*...*2)... 이런 식이 되지 않을까? n이 10인 경우에는 O(10! * 9!) 정도..? 물론 여러 조건때문에 중간 중간 좀 더 시간이 줄긴 하겠지만 시간 초과가 날만도 해보인다.

---------------------------
결국 질문 게시판을 보고 어떻게 풀어야할지 알게 되었다.
어떤 분의 코드와 유카리코님의 답변 을 보면,

 내가 푼 방식과 비슷하다. 그런데 차이가 있다면 바로 마지막 줄, "위 코드는 인접한 대각선끼리는 독립적이라는 사실을 이용하여 반으로 쪼개어 더해준 것으로 최적화를 수행한 것 같습니다." 

처음에는 무슨 말인지 이해가 안 됐지만 다른 질문글의 답변을 떠올려보고, 게시글의 코드에서 f(0)+f(1)을 답으로 출력하는 것을 보고 깨달음을 얻었다!

참조가 된 답변


체스판을 그려놓고 보면, 비숍이 흰 칸에 놓이면 나머지 칸에 대해서 영향을 줄 때, 오직 나머지 흰 칸들에 대해서만 영향을 준다. 마찬가지로 검은 칸에 놓이면 나머지 검은 칸에 대해서만 영향을 준다! 즉, 인접한 대각선끼리 독립적이라는 말은 인접한 대각선끼리는 색깔이 다르고, 흰 대각선은 흰 대각선끼리만 영향을 주고, 검은 대각선은 검은 대각선끼리만 영향을 끼치므로 흰 대각선, 검은 대각선 부분을 나눠서 비숍을 놓을 수 있는 개수를 구해서 합치는 방법으로 구할 수 있다. 그리고 이렇게 하면 반으로 나눠서 하는 것이기 때문에 시간 복잡도는 n이 10인 경우에, 그냥 나누지 않고 다 볼때의 O(10! * 9!) 에서 O(10! + 9!)로... 엄청나게 감소하게 된다!!!

검은 칸으로만(검은 대각선으로만) 구성된 부분에는 비숍을 어디에 놓든지 간에 흰 칸으로 구성된 부분에 영향을 끼치지 않기 때문이다! (반대로 흰 칸도 마찬가지...)
참고할 만한 것으로 대각선/도 index로 나타낼 수 있다. 대각선/의 경우는 편하다. 그냥 r+c만 하면 된다. 그리고 대각선을 한 칸 건너뛰는 것을 구현하려면 대각선/도 index로 나타내서 하는 것이 더 편한 것 같다. 그리고 index로 나타낼 경우 최대 2*n-1개라는 것도 주의!!

그리고 또 하나, 나는 원래 대각선에 아무 것도 안 놓는 경우도 생각했는데, 놓을 수 있으면 꼭 놓아야 할 것 같다. 앞에 놓든, 뒤에 놓든 그 대각선에는 하나의 비숍만 놓을 수 있고, 각 대각선당 한 개씩 놓아져야 한다. 그리고 한 대각선에 놓는다고 해서 같은 방향의 다른 대각선에 놓을 수 없게 되는 것도 아니고, 또한 뒤에 나오는 대각선에서의 칸은 놓을 수 없는 칸일 수도 있으므로 앞에서 놓을 수 있는 대각선과 놓을 수 있는 칸이 나온다면 미리미리 놓아야 최대를 구할 수 있을 것이다. 그리고 놓을 수 있는데도 아예 안놓고 넘어가는 경우에서 놓고 넘어가는 경우보다 더 큰 값이 나올 수 없을 것 같다. 일단 제출은 아무것도 안 놓는 경우를 포함하는 것도 해보고 그냥 무조건 하나씩 놓는 경우도 해봐야겠다.
-> 예상외로 바로 예제에서부터 답이 안 나와서.. 왜인가 봤더니... 이 예제에서 보면 처음 입력으로 주어질 때, 한 대각선이 비숍을 아예 놓을 수 없는 칸들로만 이루어져 있다. 그렇기 때문에 만약 아무것도 놓지 않는 조건을 빼면 그 대각선에서 끝나버리고 탐색을 안하기 때문에 최대값이 안 나온다... 내가 생각한 것을 실행하려면 아무것도 놓지 않는 조건을 빼는 대신 한 칸씩 고르는 while문 안에서 아무 것도 골라지지 않은 경우에 다음 대각선을 탐색하도록 추가하면 될 것 같다. 결국 AC를 받았다!!
-> 그리고 그냥 안 놓고 넘어가는 경우를 넣어봤더니 시간이 더 오래 걸린다. 0ms에서 8ms로 증가했다. 역시 굳이 할 필요 없는 경우까지 탐색하기 때문인 것 같다.

좋은 문제같다. 그리고 내가 시간 복잡도를 맞게 계산했는지는 모르겠지만 체스판과 비숍의 성질을 이용해서 반으로 나눠 푸는 방식으로 시간복잡도를 확 줄일 수 있다는 것은 사실이다.


아 그리고, 질문 게시판의 답변에 의하면 이분매칭, 최대유량 알고리즘으로도 풀 수 있다고 한다. 이참에 네트워크 플로우를 복습해서 이 문제도 네트워크 플로우로 풀어 봐야겠다.

BOJ 1280 나무 심기

1번부터 N번까지의 나무가 있는데, 각 나무를 어디에 심을지가 주어진다.
1번 나무부터 시작해서 차례대로 N번 나무까지 심을 것이고 1번 나무를 제외한 모든 나무는 심는데 비용이 든다. 각 나무를 심는데 드는 비용은 각 나무에서 현재 심어져 있는 모든 나무까지의 거리의 합이다.
이 때, 2번 나무부터 N번 나무까지 각 나무를 심는데 드는 비용의 곱을 구하는 문제이다.
데이터가 최대 20만개가 들어오기 때문에, 각 나무를 심는데 드는 비용을 일일이 계산하면 O(n제곱)의 시간이 걸릴 것이다.

각 나무를 심는데 드는 비용을 그려보면, 그리 어렵지 않다.
d[n] : n번째 나무를 심는데 드는 비용 이라고 하자.
그리고 그림을 그려서 보면, d[n]은 d[n-1]를 구성하는 n-1번째 이전의 나무들과의 거리에 각각 pos[n]-pos[n-1]을 더한값과, pos[n]-pos[n-1]으로 구성돼있는 것을 볼 수 있다.

즉, d[n] = d[n-1] + (pos[n]-pos[n-1])*(n-1) 이 된다.
한 번 풀어봐야겠다. 계속 틀려서 이것 저것 해보다가 떠오른 것이, 나는 n번 나무가 n-1번나무보다 죄표상으로 앞에 온다고 가정하고 풀고 있었다... 문제에는 n번 나무가 무조건 n-1번 나무 보다 좌표상 뒤의 위치에 온다는 말이 없다. 아... 다시 처음부터 생각해 봐야겠다.

어렵다... 질문 게시판과, 구글 검색을 해보니 segment tree나 fenwick tree를 써서 풀 수 있는 것 같다. fenwick tree를 어떻게 이용할지, 무엇을 저장하면 좋을지 생각해 봐야겠다.
결국 kks227님의 블로그의 풀이를 읽어봤다. 감탄했고 동시에 난 접근도 못했다는 생각에 많이 반성했다. 정말 열심히 하자.

먼저 알게된 것은 문제에 한 위치에 나무가 한 그루만 세워진다는 말이 없으므로 한 위치에 나무가 여러 그루 세워질 수 있다.
펜윅 트리를 어떻게 활용하냐면, 일단, 펜윅트리를 처음에 업데이트 해줄 때, 0부터 x까지의 거리로 업데이트 해준다. 즉, 펜윅트리에서 쿼리x가 의미하는 것은 좌표 x이하의 좌표들에 대해서 좌표 0부터의 거리들의 합이된다. 간단히 말하면 그냥 좌표 x이하의 좌표들의 합이되는데, 좌표 0부터 각 좌표까지의 거리의 합으로 생각하는 것이 뒤에 나오는 것을 이해하기 좋다.
그리고 펜윅 트리가 하나 더 있어야 한다. 각 좌표에 대해 각 좌표까지의 존재하는 나무의 개수를 기록해야 한다. - cnt_query라고 하겠다.

자, 이제 어떻게 구할 것이냐, 일단 n번째 나무가 들어왔다고 치자. 그럼 n번째 나무 이전의 나무들은 왼쪽에 있을 수도, n번재 나무의 위치에 있을 수도, 오른쪽에 있을 수도 있다.

먼저 n번째 나무의 위치 이하에 해당하는 이전 나무들에 대해서 거리의 합을 구해보자.
결론부터 말하면 cnt_query(pos[n]) * pos[n] - query(pos[n]) 이 될 것이다.
일단 쉽게 이해하기 위해 pos[n]이하의 위치에 1부터 n번 나무까지 모두 있다고 가정해보자. 일단 n번나무에서 1, 2, 3..., n-1, n번째 나무까지의 거리들의 합은
(pos[n]-pos[1]) + (pos[n]-pos[2])+..+(pos[n]-pos[n-1])+(pos[n]-pos[n]) 으로 표현할 수 있고, 정리하면
pos[n] * n - (pos[1]+pos[2]+...+pos[n]) 이 된다.
query(pos[n])은 0부터 1, 2, ...n까지의 거리의 합으로서 (pos[1]+pos[2]+...+pos[n])에 해당하고, cnt_query(pos[n]) * pos[n]이 pos[n] * n에 해당한다.

알고보면 별거 아닌 것 같지만 난 조금이라도 비슷하게 생각조차.. 아니 접근조차 못했다.
갑자기 드는 생각인데, 처음부터 펜윅트리로 어떻게 하지가 아니라, 이렇게 식을 세워보고 펜윅트리를 써야겠구나...하면 나을 것 같은데... 음 그것도 쉬운 건 아니려나...정말 열심히 해야겠다. 문제를 많이 풀어보라는 말이 괜히 있는 게 아닌 것 같다.

자 n번째 나무의 위치보다 이제 오른쪽에 있는 나무들에 대해서 거리의 합을 구해보자.
결론부터 말하면
query(pos[rightEnd]) - query(pos[n]) - (n - cnt_query(pos[n]) * pos[n]
오른쪽에 나무가 어디까지 있는지 모르지만 그냥 범위에서 제일 끝에 해당하는 pos[rightEnd]에 대해서 query를 해주면 0부터 모든 나무들까지의 합을 구할 수 있다. 이제 이 모든 나무들까지의 거리의 합에서 query(pos[n])을 빼주면 n보다 오른쪽에 있는 나무들의 거리의 합만 남는다 (그냥 n번째 나무의 위치보다 오른쪽에 있는 나무들의 거리의 합이라고 보면 된다). 여기서 오른쪽에 있는 나무들의 개수만큼 pos[n]을 빼주면 pos[n]에서 오른쪽에 있는 나무들까지의 거리의 합이 될 것이다.

자 이제 구현해보자.
시간 초과를 받는다. 전혀 시간 복잡도 상으로 문제가 없는데...
그래서 랜덤으로 데이터를 생성해서 돌려보는데... 바로 시간 초과다.. 분석해보니 데이터 중에 위치값이 0이 들어오는 곳에서 멈춘다. 각각의 좌표는 0이상 200000이하... 아...
펜윅트리는 인덱스를 1부터 사용하는데, 0이 들어올 경우 업데이트 해줄 때 무한루프에 빠진다. 이 부분은 전혀 생각 못했었다....그래도 정말 감사하게도 바로 원인을 찾을 수 있었다. 그렇다면 펜윅트리의 크기를 1늘리고 들어오는 위치값에 1씩 더해서 사용해야겠다.
결국 AC를 받았다.
열심히, 간절하게, 몰두해서 하자.

참고 및 출처 : kks227님 블로그

BOJ 2758 로또

1부터 m까지의 숫자 중에서 n개의 숫자를 고를 때, 이전에 고른 수의 2배 이상인 수만 고를 수 있다. 이 때, 고를 수 있는 n개의 숫자의 경우의 수를 구하는 문제이다.

n=10, m=2000의 제한이 주어진다.

예제를 보면서 생각해보니 일단 떠오르는 것은
d[x][y] : x번째 수를 y로 결정했을 때, 만들 수 있는 경우의 수
d[x][y] = sum(ny=2y ~ m,  d[x+1][ny]) 가 될 것이고,
답은 sum(y=1~m, d[1][y]) ... 대략적으로 이렇게 잡으면 O(N*M*M*M) 의 시간복잡도를 가지게 될 것이다. 이렇게 하면 시간초과가 날 것 같다.

한 번 d[x][y]에 관한 식을 조금 변형해보자.
d[x][y] : x번째 수를 y로 결정했을 때, x번째까지 만들 수 있는 경우의 수
d[x][y] = sum(ny=1 ~ y/2, d[x-1][ny]) 으로 변형하고 for loop dp로 구현해보자.
답은 sum(y=1~m, d[n][y])...가 될 것 같은데, 어라?  O(N*M*M)만에 해결될 것 같다.
답을 구할 때의 m번은 따로 처리되기 때문이다...음 그렇게 치면 memoization이 있기 때문에 위의 top-down방식에서도 O(N*M*M)만에 해결될 것 같아 보인다.

먼저 bottom-up방식으로 구현해보고, top-down으로도 구현해 봐야겠다.
일단 bottom-up방식으로 구현했는데 시간 초과를 받았다... O(N*M*M)이라도, T값, 즉 테스트 케이스의 개수가 많으면 시간초과가 날 것이다. 음 근데 문득 떠오른 것이... d배열은 다른 테스트 케이스에도 사용가능 하지 않을까?
그렇다. x번째 수를 y로 결정했을 때, x번째까지 만들 수 있는 경우의 수이기 때문에... 일단 d배열을 다 구해놓고, 각 테스트케이스에 대해서 sum(y=1 ~ m, d[n][y])만 구하면 되는 것이다.

그렇게 제출해보니, 시간초과는 사라지고 WA를 받았다. 예제로 10, 2000을 넣어보니 음수가 나온다. integer overflow일 것이다. long long형으로 수정해서 제출해 봐야겠다.
AC를 받았다. 12ms로 통과했는데, 0ms인 사람들도 꽤 보인다.

bottom up 구현에서 d[x][y]를 구할 때, ny=1 ~ y/2까지의 d[x-1][ny]의 합을 구하는데, 이 부분에서 시간 단축을 할 수 있어 보인다. 바로 부분합(누적합)을 이용하는 것이다. d[x-1][y]값들을 구할때, d[x-1][~]의 부분합(누적합)을 미리 구해놓고, d[x][~]를 구할 때, 이용하면 O(m)의 시간을 O(1)로 단축시킬 수 있다. 즉 전체 수행시간을 O(N*M)으로 단축시킬 수 있는 것이다.
결국 0ms로 AC를 받았다!

다른 분들의 코드를 보고 있는데, 음 정말 대단하신 것 같다. 다들... 내가 정말 허접해보인다. 인상깊은 구현을 여기 써보고 그렇게도 풀어봐야겠다.

d[x][y] : x번째 수를 y로 결정했을 때, 만들 수 있는 경우의 수 <- 내가 한 방법.
d[x][y]는 같은데, 고수분들의 d[x][y]는 의미가 좀 다르고 그렇기에 식도 다르게 나온다.
나처럼 시간을 단축시키기 위해 누적합을 쓸 필요도 없다.

d[x][y] = 1부터 y까지의 수 중에서 x개의 수를 고르는 경우의 수 <- 바로 답 그 자체이다.
점화식이 중요한데... 알고보면 이미 다른 문제들에서도 몇 번 봤던 방식으로 생각하는 것인데, 난 전혀 생각하지 못했다.
d[x][y] = d[x][y-1] + d[x-1][y/2] 이다!
바로 1부터 y까지의 수 중에서 y를 고를지 말지 결정하는 것이다.
y를 고르지 않는다면 1부터 y-1까지의 수 중에서 x개를 고르는 경우가 될 것이고
y를 고른다면 1부터 y/2까지의 수 중에서 x-1개를 고르는 경우가 될 것이다!
이렇게 하면 모든 경우도 커버할 뿐 아니라, O(N*M)만에 가능하다. 정말 아름다운데... 난 생각을 못했다. 좋은 문제다. 
한 번 이 방식을 이용해서 top-down으로 풀어봐야겠다. 기저 사례의 경우 dp(n, m)에서
n < m인 경우는 0을 return하고, n==1인 경우는 m을 return했다. 확실히 이 방식이 top-down으로 하든 bottom-up으로 하든 쉬울 것이다.

BOJ 9177 단어 섞기

단어 3개가 주어지는데, 첫번째 단어와 두번째 단어를 섞되 원래의 각 단어내에서 알파벳의 순서는 변하지 않도록 해서 세번째 단어를 만들 수 있는지 판단하는 문제이다.

단어들을 각각 str1, str2, str3라고 하면
나는 str3의 뒤에서 부터 한 글자씩 str1, str2의 뒤의 글자와 비교하면서 모든 경우를 다 해보는 식으로 접근했다.
str3[idx3]와 str1[idx1], str2[idx2]을 비교해보고 같다면 각각의 경우를 다 보는 식으로 해서 재귀를 이용해서 구현했는데 이렇게 할 경우 O( 2의 400(str3의 길이)제곱 )의 시간 복잡도를 갖게 된다. 그래서 memoization을 이용해야 한다.

근데 문제의 데이터가 약해서인지 O(2의 N제곱) 구현이 통과됐다. 그것도 0ms만에... (참고로 memoization을 이용한 다른 분들의 코드는 대부분 4ms이상) 처음에는 통과되서 좋아했는데, 생각해보니 절대 시간내에 들어올 수가 없는 시간복잡도라... 내가 직접 예제를 넣어봤다.
최악의 경우를 테스트하기 위해 aaaa... aaaa... aaaaaaaa... 이런식의 예제를 넣어봤다.
str3의 길이가 30만 되어도 10억을 넘기때문에 대충 30 - 40을 길이로 하면 몇초가 걸려야 하는데, 1초도 안걸려서 바로 나왔다. 그래서 처음엔 나도 모르게 엄청 효율적인 알고리즘을 짠 것인가...라는 생각을 잠시 했지만 아무리 생각해봐도 그럴리 없는 코드이다. 그래서 재귀함수 안에 printf를 넣어서 어떻게 돌아가는지 살펴보기로 했다. 하지만 그리 쉽지 않았다. 엄청 헷갈리고.. 그래서 예제를 줄여서 해보고 printf를 이곳 저곳 다 찍어보고 ...예제도 바꿔보고 하면서 알게 된 사실 하나가 답이 yes가 나와야하는 예제에 대해서는 생각과 달리 엄청 빨리 나오는데, no가 나와야하는 예제에 대해서는 생각한대로 정말 느리게 나온다는 것이다.
printf로 출력하는 것도, no가 나와야하는 예제는 끝날 기미를 안보인다. 정말 2의 N제곱만큼 보는 것 같아보인다. 하지만 yes가 나와야하는 예제는 입력이 아무리 길어도 조금만 출력되고 끝난다.
아마 Baekjoon Online Judge의 데이터는 최악의 경우를 가정한 데이터도 yes가 나오는 경우만 넣어놓은 것이 아닐까... 그건 그렇고 왜 저런 처이가 발생할까?
여기저기 printf를 해보면서 과정을 따라가다보니 함수가 호출되지 않는 경우가 발생했다는 것을 알 수 있었고, 정말 감사하게도 순간적으로 short circuit evaluation이 떠올랐다!!!

short circuit evaluation! || 연산이나 && 연산에서 왼쪽 부분에 따라 오른쪽 부분이 뭐가 오든간에 결과는 같을 경우, 오른쪽 부분 계산을 하지 않고 넘어가는 것인데, 바로 이 것 때문에 yes가 나와야하는 경우에 왼쪽이 true가 되어 || 오른쪽은 살펴보지 않고 넘어갔고 그래서 매우 빠르게 나왔던 것이다. 반면에 no가 나와야하는 경우는 false가 왼쪽에 있어서 오른쪽까지 다 보게된 것이다...

그래서 하나 또 실험을 해봤는데,true, false를 판별하는 경우에는 |나 ||나 똑같기 때문에 |를 써봤다. 참고로 |(bitwise | operator)는 short circuit evaluation이 적용되지 않는다. 역시 ||를 썼을 때 매우 빠르게 나오던 예제에 대해서도 매우 느리게 나온다.
그리고 궁금해서 찾아봤는데 참고 : bitwise operator는 short circuit evaluation이 적용되지 않는 이유
다양한 답변들이 있는데, 내가 이해한 답변을 하나 소개하면, 0*x에 대해서도 0*를 하는 경우가 거의 없고 다른 경우가 많기 때문에 short circuit evaluation이 적용되지 않듯이 bitwise &이나 bitwise |의 경우 대부분의 경우 short circuit evaluation을 쓸 경우가 많지 않기 때문에(대부분 그냥 bitwise 연산) 그런 것 같다.

그리고 또한, short circuit evaluation의 side effect(부작용)에 관한 것들도 눈에 띄었는데, 제대로 찾아보지는 않았지만 나중에 찾아보면 좋을 것 같고, 조금 찾아본 바로는 나의 경우에서 처럼 디버깅을 해볼 때, 매우 헷갈린다든지, 시스템 프로그래밍 같은데서 command에 해당하는 코드가 실행되지 않을 수 있다든지 하는 문제가 있어서 주의해서 코딩해야 한다고 한다.

이제 dp로 어떻게 구현할 것인지에 대해 생각해보자.
내가 처음에 이렇게 완전탐색으로 구현하기 전에도 dp로 구현하려고 했었는데,
d[idx1][idx2] = 단어1을 idx1까지, 단어2를 idx2까지 사용했을 때, 단어3에대해 가능한지 아닌지.
하지만 이렇게 하면, memoization해놓은 것이 주어진 단어3에만 적용되는 것이라 새로운 단어3이 들어오면 안되지 않나...는 고민을 했는데, 내가 예제만 보고, 단어1, 단어2는 똑같은 것이 들어오고 단어3만 바뀐다고 착각해서 잘못 생각한 것 같기도 하고, 또한 완전탐색으로 해보고 디버깅하면서 엄청나게 많은 경우를 보기 전에는 memoizaion을 해도 다시 또 쓰일까? 라는 의문이 있었다. 즉 완전 잘못 생각하고 있었다. 처음에는 완전탐색도 O(N)으로 착각하고 있었다...실제로, 완전탐색을 자세히 들여다보면 먼저 재귀로 한 가지 경우를 끝까지 보고, dfs처럼 탐색하는데, 모든 경우를 다 보면서 처음에 봤던 경우를 또 봐야되는 경우가 생긴다.

아 그리고, 원래 코드에서는 배열의 인덱스가 -1까지 가버리는 경우도 있었다. idx3==-1인 경우만 기저사례로 처리하기 때문에, idx1이나 idx2가 음수가 되는 경우가 있었는데, 이 부분도 if문에 처리를 해줘야 한다.
그래서 이번에는 memoization을 이용해서 풀어보려고 한다.
구현하려 하면서 든 생각이, d[idx1][idx2]만으로는 부족해보인다. idx3의 정보도 알아야할 것 같다. 하지만 잘 생각해보면, idx3정보는 필요없다. idx1, idx2가 뭐냐에 따라 결정되기 때문이다. 그리고 d[idx1][idx2]에 해당하는 경우가 여러가지 있지 않나? 라는 생각이 들 수 있다. 하지만 어차피 하나의 단어3에 대한 memoizaion이기 때문에, d[idx1][idx2]가 참이라는 것은 단어3에대해 참이라는 것. 즉 d[idx1][idx2]는 단어3에 대해만 성립하는 것으로 생각하면 납득이 된다.

테스트케이스가 이상한건지... 내가 이상한건지... 실수로 메모이제이션을 빼먹었는데..정확히는 bool& ret= 에 받지 않고, bool ret=d[idx1][idx2]로 해버렸는데... 이러면 d[idx1][idx2]에 기록이 안될텐데... AC를 받았다. 다시 제대로 짜보려고 한다...

이번에는 제대로 했다고 생각한다..(확실치는 않다.) 일단 짜면서 idx1이나 idx2가 -1이 되는 경우를 처리하는데 애먹었다. 결국 d[200][200]에서 d[201][201]로 늘리고 d[len1][len2]로 놓고(idx대신 길이로..) 해결했다.
그리고 idx1이나 idx2가 -1이 되는 경우를 처리할 일이 없도록 index를 0부터 늘려나가는 식으로 구현해보려고 한다. 이렇게 구현해도 결국 idx1이나 idx2가 끝에 도달하는 경우를 신경써야하지만 -1이되는 경우를 처리하는 것보다는 좀 더 쉬운 것 같다. 그리고 이 방법 역시 끝부분을 처리하기 위해 d[201][201]로 늘렸는데, d[idx1][idx2]의 의미는 그대로 사용하면 된다.

BOJ 1701 Cubeditor(Editor)

구하는 것은 간단하다.
입력으로 주어진 문자열에서 어떤 부분 문자열을 검색해서 두 번 이상 나오는(일부가 겹쳐도 된다.) 부분 문자열 중에서 가장 긴 길이를 구하는 문제이다. 

두 번 이상 나오는 문자열 중에서 가장 긴 길이를 구하는 것이므로, 두 번 나오는지만 파악하면 된다. 그러면 생각나는 것이 있다. prefix와 suffix가 같은 부분 문자열 중 최대의 길이를 저장하는 pi배열을 생각했는데, 더 생각해보니 아니다. 모든 prefix에 대해 pi를 구한 것으로는 중간에 두 번 등장하는 부분 문자열을 커버할 수 없다. 그렇다면 모든 부분 문자열에 대해 pi배열을 구하면 가능하겠지만 경우의 수가 너무 많을 것이다.

다시 생각해보자.
결국 백준님의 풀이를 봤다. 좀 충격이었다. 내가 위에서 생각했던 것처럼 정말 모든 부분 문자열에 대해 pi배열의 값을 구해서 그 중 최대값을 구한다. 나는 막연히 경우의 수가 많아 안될 것이라 생각했고 모든 부분 문자열을 어떻게 구해야할지도 몰랐는데, 모든 부분 문자열을 구하는 것은 생각보다 간단하다.

핵심 아이디어는 이것이다. (출처 : 백준님 강의 자료)
모든 부분 문자열은 어딘가에서 시작해서 어딘가에서 끝난다.
즉 어떤 suffix의 prefix가 된다.
pi배열을 구하되, 문자열의 모든 suffix에 대해서 pi배열을 구하면 모든 부분 문자열에 대한 pi배열의 값을 얻을 수 있는 것이다!!
그리고 문자열의 길이는 최대 5000이므로 O(N제곱)의 시간복잡도로도 충분하다.

추가) suffix array와 lcp(longest common prefix)를 이용해서도 가능하다. (더 빠름)

BOJ 1305 광고

광고는 전광판의 크기만큼 보여지고, 길이가 N인 광고를 무한히 붙여서 한 칸씩 움직이며 나타나게 한다.
전광판의 크기와 현재 보여지는 문자열(길이가 N인 광고를 무한히 붙였을 때, 전광판의 크기만큼 보여지는 부분)이 주어질 때, 가능한 광고의 길이 중 가장 짧은 길이N을 구하는 문제이다.

어떻게 풀어야할까? 예전에 백준님의 풀이를 보고 풀었는데 기억이 안난다. 힌트로는 알고리즘 분류는 kmp알고리즘으로 되어있다.

kmp로 생각해보자. 문제에서 주어진 예제 aabaaa와 aaaaa로 생각을 해보면, 각 문자열에 해당하는 pi값을 구하고 그 값을 문자열의 길이에서 빼준 것이 답이되는 것 같아보인다.
 일단 aabaaa에서 보면 pi=2, prefix suffix가 같은 최대의 부분 문자열이 aa이다. 길이가 N인 광고가 계속 이어져 있는 것을 생각하면 prefix aa는 앞 광고의 suffix aa로 볼 수도 있을 것이다. 즉 baaa가 원래 광고이고, baaa앞의 aa는 baaa의 suffix aa가 채우고 있는 것으로 볼 수 있는 것이다.

최대를 찾는다면 당연히 aabaaa이렇게 전체가 되겠지만 최소를 찾는다면 aa를 뺀 길이가 된다.

BOJ 1939 중량제한

이 문제는 나도 모르게... 습관적으로 문제 분류를 보게 되었다.

이분 탐색 + bfs 로 푸는 문제인데, 일단은 이렇게 안 푼다고 한 번 생각해보자.

모든 경로를 다 보고 각 경로를 구성하는 간선의 가중치 중 최소의 가중치를 찾으면 그 값이 그 경로의 중량 제한인데, 중량 제한의 최대값이므로 모든 경로에서 구해낸 그 값들 중 최대값을 구해야 한다. 하지만 모든 경로를 다 가보는 것도 못 구현하겠고, 설령 한다해도 시간이 엄청 걸릴 것이다. 근데 이 문제를 이렇게 생각하다보니 얼마 전에 봤던 코드 몬스터 2번 문제와 똑같다는 느낌이 든다. 하지만 코드 몬스터 2번 문제는 입력 데이터 제한이 더 커서 단순히 이분 탐색과 bfs로 풀어서는 시간 초과이다. BOJ slack에 검색해서 고수님들이 말씀하신 걸 보니 그 문제는 maximum spanning tree와 lca를 이용해서 풀거나 maximum spanning tree와 (다익스트라 or bfs)로 풀면 된다는 것 같다. 비슷한 문제로는 이 1939 중량제한 문제와 3176 도로 네트워크 문제가 있다.

일단 이 문제를 이분 탐색과 bfs로 풀어보고, 할 수 있다면 mst를 이용해서도 풀어봐야겠다.

1. 이분 탐색과 bfs(혹은 dfs)
이분 탐색으로 중량 제한의 최대값 MAX를 정하고 bfs로 출발지에서 목적지까지의 경로를 탐색하면서 MAX 이상의 가중치를 가지는 경로로만 이동해서 목적지에 도착하는 경로가 존재하면 다시 이분 탐색으로 범위를 좀 줄여서 해보고.. 이런 식으로 중량 제한의 최대값을 찾아나갈 수 있다. 좋은 문제같다. dfs, bfs로 각각 구현해 봐야겠다.

그리고 이분 탐색을 할 때, ans라는 변수를 써서 답을 저장해도 되지만, l이나 r값만으로 답을 구할 수 있다. 이 문제에서는 이분 탐색에서 mid값이 성립이 되면, (최대값을 찾아야 하므로) l = mid+1, 성립이 안되면 r=mid-1을 한다. 잘 생각해보면 실제 정답이 되는 mid값을 찾은 후에는 그 다음부터 구하는 mid값은 성립이 안될 것이므로 계속 r=mid-1을 하게 되고, l은 계속 성립된 mid값(정답)+1 인 상태일 것이다. 그리고 while(l<=r)인 동안 돌게 되므로 결국 r이 mid+1보다 왼쪽으로 한 칸 더 간... 바로 mid값(정답) 값이 되면서 끝난다. 이 것도 여태 엄청 헷갈렸는데, 요즘 스터디에서도 많이 배우고 다양한 방면의 문제를 접하면서 깨닫게 된 것 같다.

일단 AC를 받았는데, 다른 분들의 풀이도 보고 검색도 하다 보니 꼭 이분탐색 + bfs만 있는 것은 아니었다. 그 중 나에게 영감을 준 블로그 글이 두 개 있다. : onjo0127님의 블로그, http://kthng.tistory.com/15

2. dijkstra(...bfs)
onjo0127님의 글에서 onjo0127님이 자신의 풀이가 다익스트라와 비슷하다고 말씀하시는데, 순간 왠지 위에서 말했던 코드 몬스터 2번을 풀 때, 다익스트라로 풀 수 있다는 것과 관련이 있어보인다는 생각이 들었다. 그래서 잠깐 저녁먹으러 갔다오면서 다익스트라로 어떻게 풀지 생각해 봤다.
그리고 생각해보니 정말 다익스트라로 가능하다. 다익스트라는 원래 한 점에서 나머지 각 점까지의 최단거리를 찾는 알고리즘이지만, 조금 변형해서 최장거리, 아니 어떤 점까의 최대 중량 제한을 찾는 것으로 하면 가능하다. priority_queue에 후보를 넣고, 그 중 가장 중량이 큰 후보를 뽑으면 그 점까지의 최대 중량은 확정되는 것이고, 그럼 그 점에서 또 후보들을 찾아보고, 후보의 최대 중량 값은 이전 정점의 최대 중량값과 이전 정점과 자신이 연결된 간선의 가중치(중량) 중 더 작은 값을 택하면 된다. 그리고 후보의 최대 중량 값이 더 큰 값으로 갱신될 때 큐에 넣어주면 된다. 즉, 이것도 다익스트라 처럼 출발점에서 시작해서 다른 정점까지의 최대 중량을 하나씩 확정해 나가는 것이다.
pq의 후보값중에 최대값을 뽑게 되면 나머지 어떤 정점은 그 정점보다는 값이 작거나 같다는 것이므로 어떤 정점을 거쳐가든 반드시 그 최대값보다는 작거나 같은 중량을 가질 수 밖에 없다. 이런 원리로 결정해 나가는... 다익스트라의 원리와 같다.
일단 구현해 봐야겠다. 시간은 좀 더 걸렸지만 거의 비슷하면서 AC를 받았다.

3. MST(이 문제에서는 Maximum) + dijkstra
Maximum Spanning Tree에 대해 생각해 봤는데, 일단 스패닝 트리는 그래프에서 일부 간선을 선택해 만든 트리이다. 즉 n-1개의 간선으로 n개의 정점들을 연결하고 있다. 여기서 볼 Maximum Spanning Tree 최대 스패닝 트리는 간선의 (가중치)합이 최대가 되도록 그래프에서 간선을 선택해서 만든 트리이다. 그렇다면 왜 이게 이 문제와 코드몬스터 2번문제에 유용(필요)한지 차근차근 설명하려고 한다.
각 경로의 중량 제한은 각 경로에서 가장 작은 간선의 가중치가 된다. 그렇기 때문에 직관적으로 답이되는 최대 중량 제한을 이루고 있는 경로는 분명 최대 스패닝 트리(MST) 위에 있을 것이다. 스패닝 트리로 모든 정점들이 이어져 있으므로 경로가 없지 않을까 하는 걱정은 안 해도 된다. 그리고 스패닝 트리는 n-1개의 간선으로 이루어져 있기 때문에 다익스트라를 돌릴 때, 시간복잡도가 확 줄어들게 된다.
이제야 왜 코드 몬스터 2번 문제에서 최대 스패닝 트리가 필요한지 깨달았다. 일단 이 중량 제한 문제도 최대 스패닝 트리를 이용해서 풀어봐야겠다.
AC를 받았다. 시간이 좀 더 걸린다. 하지만 코드 몬스터 2번처럼 쿼리가 많이 들어오는 경우에는 시간을 훨씬 줄일 수 있을 것이다. 이 문제는 쿼리가 하나밖에 없는 것이므로 MST로 그래프를 만드는 전처리 과정이 O(ElogE)로 시간복잡도를 대부분 차지할 것이다.

4. MST + LCA
내가 아직 LCA를 모르기 때문에 공부해 봐야한다.
드디어 알아냈다. BOJ 3176 도로 네트워크 MST를 만들면 이 문제와 푸는 방법이 똑같다.
일단 MST를 만들면 트리가 된다. LCA는 최소 공통 조상을 찾는 알고리즘인데, 여기서는 배열에 저장하는 값을 조상과 최소값까지 같이 저장해놓는데, 이렇게 하면 최소 공통 조상을 찾으면서(O(logn)) 최소값을 비교해서 그 중 최소값을 찾으면 그것이 정답이다. 왜나하면 트리에서 한 정점에서 다른 한 정점까지의 경로는 그 두 정점의 최소 공통 조상을 지나게 되고, 최소 공통 조상을 구하는 과정에서 그 경로를 다 보게 되기 때문이다.
dp배열을 전처리하는데 O(nlogn)이 걸리고, 답을 구하는데는 한 쿼리당(logn)이 걸린다.
이 문제는 쿼리가 한 개인 셈이므로 O(nlogn + logn)이 걸릴 것이다.
풀어봐야겠다. AC를 받았는데, 시간은 꽤 빠르게 나왔다. 음 시간은 서버의 영향도 좀 받기 때문에 완전 신뢰할 수는 없겠지만...

일단은 많은 공부를 하게 되었고, LCA에 대해서도 알게 되었다.
힘들게 익힌거 잊지않도록...복습을 꾸준히 하자!

이 글을 다시 보는데, 3. MST+dijkstra에서 MST를 만들었으면 트리이므로 한 점에서 다른 한 점까지의 경로는 하나밖에 없다. 그냥 간단하게 dfs를 돌려도 될 것 같다. - 13905 세부 문제를 풀면서 dfs로 해봤는데 내 부족한 실력때문인지... 좀 까다로웠다.

BOJ 3176 도로 네트워크

코드 몬스터 2번이랑 유사한 문제라고 한다.

문제 분류는 LCA로 되어 있는데 LCA를 이용해서 어떻게 풀어야할지 감이 오지 않는다.

문제 설명
N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다.
모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다. -> 트리를 의미한다.

그리고 이제 k개의 도시 쌍이 주어지면, 두 도시를 연결하는 경로 상에서 가장 짧은 도로 길이와 가장 긴 도로의 길이를 구해야 한다.

일단 트리이기 때문에, 두 도시를 연결하는 경로는 유일하게 결정되고 그 경로는 반드시 두 도시의 LCA(최소 공통 조상)을 지날 것이다. 음... 저번에 슬랙에서 고수님들이 말씀하셨던 것을 다시 생각해 봤다.

 LCA에서 dp를 이용하는 O(logn)짜리 방식이 있는데,
그 방식의 경우 d[node][k] = node의 2의 k제곱번째 부모
였는데, 여기에 부모만 저장하는 게 아니라, 최소값(구하고자 하는게 최대값이면 최대값) 도 같이 저장하라고 하셨던 것 같다.

생각해보니 d[node][k]에 그 node부터 2의 k제곱번째 부모까지의 최소값을 저장한다면, 이 dp배열의 식을 조금만 수정하면 된다.
원래 식은 d[node][k] = d[d[node][k-1]][k-1] 이었는데,
node에서 2의 k제곱 번째 부모까지의 최소값
= MIN (node에서 2의 k-1제곱번째 부모 노드P 까지의 최소값, 노드P에서 2의 k-1제곱번째 부모까지의 최소값) 으로 하면 될 것 같다.

2의 k제곱 번째 부모를 구하는 것과 2의 k제곱 번째 부모까지의 최소값을 구하는 것은 따로 처리를 해줘야 한다.

두 정점사이의 경로는 결국 LCA를 기준으로 나뉘기 때문에, 즉, 각 정점의 부모를 거쳐 LCA를 찾는 과정이 곧 그 경로위에서 이루어지기 때문에 이렇게 LCA를 이용하면 (O(nlogn)의 dp배열 전처리만 해두면) O(logn)만에 두 정점 사이의 최소값을 구할 수 있을 것 같다.
 직접 구현해 봐야겠다.

겨우 AC를 받았다. 코드가 매우 복잡하다... parent[node][k]배열을
pair<int, pari<int, int> >로 해서 부모와, 최소값, 최대값을 다 저장하다보니...
그리고 계속 제대로 답이 안 나왔던 원인은... 바로 u, v의 최소 공통 조상을 찾으러 올라가면서 u와 v를 갱신해주는데, 일단 갱신전에 최소값, 최대값을 갱신해야 한다!! 최소, 최대를 갱신하기 전에 u, v를 갱신해버리니, 최소, 최대가 엉뚱한 값이 들어가게 되는 것이다.

다른 분들 코드도 좀 보고 공부해야겠다. 대충 봤는데, 나처럼 pair<int, pair<int, int> > 를 쓰지않고, struct를 쓰거나 배열을써서 0, 1, 2로 구분하거나 혹은 부모, 최소값, 최댁값을 각각 다른 3개의 배열로 하거나 하는게 더 가독성이 좋은 것 같다. 그리고 어떤 분은 parent[i][j-1]을 따로 변수로 받아서 쓰시는데 이것도 정말 좋은 것 같다.
나는 여태 이 생각도 못하고 parent[parent[i][j-1]][j-1]이러고 있었는데, 한 번만 쓰이면 상관없지만 이 문제에서는 최소값, 최대값까지 무려 3번이 쓰이므로 따로 변수로 받아쓰는 것이 깔끔하고 알아보기도 좋을 것 같다.
  그리고 주의해야할 점이 parent[i][j-1]값이 -1일 수도 있으니 -1이 아닌 경우만 보게 해야한다.
 좀 더 보기 좋게 고쳐서 다시 짜봐야겠다. 하면서 알게된 것인데, struct의 constructor를 이용하면 struct member를 처음부터 초기화 할 수 있다. (방법이나 종류가 여러가지가 있다.)
  난 이렇게 했다.

시간은 좀 느려졌지만 코드도 짧아지고, 실수도 많이 줄었다.

BOJ 11437 LCA ( Least / Lowest Common Ancestor )

LCA(Least/Lowest Common Ancestor, 최소/최저 공통 조상)를 공부해 보려고 한다.

LCA, 최소 공통 조상은 두 노드를 모두 자손으로 갖는 노드 중 가장 아래에 있는 노드를 말한다. 두 노드에서 조상을 찾아 올라가면서 발견되는 공통된 조상중 가장 먼저 발견되는 조상...

LCA를 구하는 방법은 O(n)방법과 O(logn)방법이 있는데,

1. O(n) 방법
 일단 각 노드까지의 depth와 각 노드의 parent를 dfs를 돌면서 구한다.
그리고 노드 u, v가 주어지면, u, v의 depth가 같게 맞춰야 한다. depth가 큰 노드가 작은 노드의 depth까지 부모를 타고 올라간다. 이제 두 노드의 depth가 같아졌으면 두 노드 모두 함께 하나씩 위로 올라가면서 두 노드가 같아질 때까지 올라간다. 같아지면 그것이 최소 공통 조상이 된다. 최소 공통 조상은 두 노드의 공통 조상중에 가장 먼저 발견되는 조상이므로 이렇게 구할 수 있는데 이 방법의 시간 복잡도는 트리의 모양에 따라 O(logn)이 될 수도 있지만, 최악의 경우 일렬로 쭉 펴진 트리(skewed tree)에서는 O(n)이 걸린다.

2. O(logn) 방법 - DP 이용
 위의 O(n)방법과 큰 틀은 같은데, 좀 더 빠르게 하는 방법이다.
원래는 parent배열에 자신의 바로 위 부모만 저장했다면, 이제 parent[node][k]배열에 node의 2의 k제곱 번째 조상(부모)을 저장한다.
2의 k제곱 = 2의 k-1제곱 + 2의 k-1제곱 이므로 node의 2의 k제곱번째 조상은 node의 2의 k-1제곱 번째 조상의 2의 k-1제곱번째 조상이 될 것이다. 즉,
 parent[node][k]=parent[ parent[node][k-1] ][k-1] 로 나타낼 수 있고, parent[node][k]는 parent[x][k-1]을 이용해서 구할 수 있으므로 dp로 parent배열을 n log n만에 구해놓을 수 있다.
이렇게 O(nlogn)에 전처리를 해놓고, 위에서 했던 과정을 좀 더 빠르게 해보겠다.

노드 u, v가 주어지면, 먼저 u, v의 depth가 같게 맞춰야 하는데, 두 노드의 depth차이를 구한다음에 그 depth차이를 이진수로 변환한다. 예를 들어 그 차이가 13이라고 하면 13은 이진수로 1101이므로 13 = 1101(2) = 2의 3제곱 + 2의 2제곱 + 2의 0제곱  이므로 O(logn)만에 두 노드의 depth를 맞출 수 있다.
이제 depth를 맞췄다면, 두 노드가 같이 올라가면서 최소 공통 조상을 찾아야 하는데, 이 과정도 하나씩 올라가지 않고 좀 더 빠르게 할 수 있다. 일단 u, v의 최소 공통 조상 위의 조상들은 모두 같을 수 밖에 없다. 그리고 우리가 찾아야 하는 것은 그 중 최소 공통 조상인데, 문제는 최소 공통 조상이 u와 v에서 정확히 2의 k제곱 만큼 떨어져 있지 않을 수가 있다. 그렇기 때문에 먼저 가장 큰 k부터 시작해서 k를 줄여나가면서 parent[u][k]와 parent[v][k]가 서로 다르면서 (즉 서로 조상이 다른) 가장 k가 큰 경우를 찾고 그 경우에 u, v를 2의 k제곱 만큼 올려준다. 

여기서 쓰이는 원리는 parent[u][k]와 parent[v][k]가 서로 다른데, parent[u][k+1]과 parent[v][k+1]이 서로 같다면 parent[u][k]와 parent[u][k+1]사이에 최소 공통 조상이 있다는 원리이다. 그래서 일단 parent[u][k] != parent[v][k]이면서 k가 최대인 경우를 찾아야 한다. 그리고 k+1까지 올라가면서 parent[u][k] == parent[v][k]가 되는 최소 공통 조상을 찾는 것이다.

여기서 의문이 생기는 것이, 예를 들어 2의 3제곱 과 2의 4제곱 위 조상들 사이에 최소 공통 조상이 있다면 그 사이를 다 볼 수 있을까?
다 볼 수 있다. 일단 2의 3제곱에서 다르기 때문에 멈추고(k는 3) k는 계속 줄어들면서 k=2일 때 parent[u][2] != parent[v][2]이면 u와 v를 2의 2제곱씩 올려주고, 
만약 parent[u][2]==parent[v][2] 라면 k=1이 되어 또 확인하는 작업을 하고.. 이러다보면
8에서 16사이의 모든 수를 조건에 따라 다 갈 수 있게 된다. 예를 들어 15까지 가는 과정을 보면 8-> 8+4=12 -> 8+4+2=14 -> 8+4+2+1 =>15 => 16번째 위의 조상이 LCA가 된다.
하나 더 9까지 가는 과정을 보면
8 -> 8+1=9 => 10번째 위의 조상이 LCA가 된다.
==> 사실 생각해보면 어떤 수든 간에 2의 x제곱의 합으로 나타낼 수 있다. 바로 2진법을 생각해보면 쉽다. 어떤 수든 이진법으로 나타내고 보면 위의 방식이 쉽게 이해가 될 것이다.

이렇게 k는 가장 큰 수 부터 시작해서 1씩 줄여가면서 parent[u][k] != parent[v][k]일 때마다 계속 u, v를 2의 k제곱씩 올리고, parent[u][k]==parent[v][k]이면 올리지 않고 하다보면 결국에 u, v가 u != v인 최대값까지 가게 될 것이고 최종적으로 구하는 최소 공통 조상은 u, v의 부모가 된다. 뭐랄까... 약간 이분탐색 느낌이랑 비슷하다. 
어쨌든 이 방법으로 O(logn)만에 조상을 찾을 수 있다. 

직접 구현해 보고 있는데, 내 실력이 부족해서인지 구현이 쉽지는 않다. 예를 들어 depth를 맞추는 과정에서 이진수로 변환한다든지.. 하는 부분이 아직 나에겐 까다롭다. 연습을 열심히 해야겠다.

계속 에러가 나고 문제가 좀 많았다. 주의해야할 점을 적어보겠다.
 parent[node][k] = parent[parent[node][k-1]][k-1]에서 parent[node][k-1]이 값이 -1이 아닌 경우에만 이 대입연산을 해줘야 한다. 그리고 node는 (노드가 1번부터 있다면) 2번 부터 for문을 돌려줘야하고... k는 1부터 해줘야 한다(k가 0인 경우는 dfs로 구했음)
 그리고 만약 u와 v중에서 u가 v의 조상이라든가, v가 u의 조상인 경우는 두 노드중 조상인 노드가 최소 공통 조상이 되기 때문에, 두 노드의 깊이를 같게 맞춰줬는데 두 노드가 같다면 바로 최소 공통 조상을 return하면 된다. 2의 k제곱씩 같이 올라가는 것을 하면 안된다.


3. O(logn) 방법 - Segment Tree(RMQ) 이용
 Segment tree를 사용하기 위해서 트리의 정점들을 일렬로 나열해야 하는데, 트리를 preorder로 순회하면서 방문하는 정점들을 나열한다. 그런데 preorder로 순회하면서 이미 방문했더라도 자식을 방문하고 다시 부모로 돌아오면서 방문하는 정점(부모들)도 나열해준다.
이렇게 나열한 수열에서 어떤 두 정점을 골랐을 때, 그 두 정점 사이에 있는 수들 중 depth가 가장 낮은 것(이 중 최상위 노드)이 최소 공통 조상이 된다.

preorder로 방문하면서 돌아오면서 다시 방문하는 점들까지 기록해서 놓으면, u에서 v사이으 정점들은 모두 u를 방문하고 v를 방문하기 까지의 중간에 거친 정점들이라 볼 수 있는데, u와 v의 최소 공통 조상이 있다면 u와 v는 최소 공통 조상에서 갈라지는 서로 다른 서브트리에 포함되어 있을 것이다.(물론 u, v중 하나가 최소 공통 조상인 경우는 예외) 그렇기 때문에, u를 방문하고 v를 방문하려면 최소 공통 조상을 지날 수 밖에 없고, 그 최소공통 조상보다 더 상위 노드를 방문하려면, 최소 공통 조상의 자손들을 다 방문한 후에나 가능하기 때문에, u를 방문하고 v를 방문하러 가는 도중에는 최소 공통 조상이 방문하는 최상위 노드가 될 것이다.

자 이제 u, v가 있으면 u와 v사이의 점들 중에서 depth가 제일 작은 점을 고르면 되는데, 이 것을 RMQ(segment tree)로 하면 O(logn)만에 가능하다. depth를 비교하지 않고도 할 수 있는 방법이 있다. 바로 preorder로 순회하면서 각 정점에 순번을 매기면 항상 부모부터 먼저 방문하기 때문에 부모 노드의 순번이 자식노드의 순번보다 작을 수 밖에 없다. 즉 최소 공통 조상은 u, v사이의 구간에서 가장 작은 순번을 가진 정점이 되는 것이다.

이게 구현을 하려고 하면 쉽지 않은데, 구현 방법은 JM book에 코드와 같이 자세히 나와있다.

- JM book(알고리즘 문제 해결 전략- 구종만 저)을 읽고 정리해 봤는데, JM book 설명이 훨씬 낫다. JM book을 꼭 읽어볼 것.


참조 : 알고리즘 문제 해결 전략 - 구종만 저,  kks227님 블로그,  https://www.acmicpc.net/board/view/332

BOJ 12846 무서운 아르바이트

BOJ 6549 히스토그램에서 가장 큰 직사각형 문제와 똑같은 문제라고 보면 된다.

문제를 설명하자면, 
아르바이트가 있는데, 날마다 급여가 정해져있고, 한 번 일하기 시작하면 중간에 빠질 수 없고(즉 연속으로 며칠을 일해야 한다), (그 연속으로 일한 날들마다의 급여 중에서 가장 작은 값)* (근무 일수)가 받을 수 있는 급여가 된다.

각 날마다의 급여가 주어지면, 언제부터 언제까지 일을하는 것이 급여를 최대로 받을 수 있는지를 구하는 문제이다. 받을 수 있는 최대 급여를 구해서 출력하는 문제이다.

분할 정복(+세그먼트 트리)의 방법과, stack을 이용하는 방법이 있다.
참고하면 좋은 문제는 히스토그램 문제이고, 풀이는 -> baekjoon online judge blog

BOJ 1981 배열에서 이동

0이상 200이하의 숫자로 이루어져 있는 n*n짜리 배열이 주어지는데,  (1, 1) (맨 왼쪽 위)에서 (n, n) (맨 오른쪽 아래)로 이동하는 경로에 있는 숫자중에서 최대값과 최소값의 차이가 최소가 되도록 하는 문제이다. 각 경로의 최대값과 최소값의 차이 중 최소를 구하면 된다.

상, 하, 좌, 우로만 이동할 수 있다.
그리고 생각해보면 한 번 방문했던 곳을 또 방문하는 것은 무의미하다.

bfs로 해볼까 생각을 했지만... 그러면 모든 칸을 다 방문하기는 하지만 최대값과 최소값이 최소가 되는 경로를 방문하지는 못할 수 있다. 혹은 체크를 하지 않고(한 번 방문했던 곳도 또 방문하면서) 하면서 각 칸을 최소값으로 갱신해주면...음 그러면 너무 오래 걸리거나 메모리 초과가 날 것 같다.

dp로 접근해보려 한다.
d[r][c] = (1, 1)에서 (r, c)까지의 최대값과 최소값의 차이들 중 최소값...으로 하면 음...

문제 분류를 봤다.
bfs, 이분 탐색이라고 되어있다... 그래도 감이 안와서 질문게시판을 좀 참조했다.

아... 배열에 주어지는 숫자는 0이상 200이하이다. 즉 최대값과 최소값의 차이도 최소 0에서 최대 200까지이다. 구하는 값을 이분 탐색으로 정한 후, bfs를 통해 (1,1)에서 출발해서 (n, n)까지 도달할 수 있는지 탐색해보면 되는 것이다.

음 근데 질문게시판의 질문글, 답변글이 없었으면 나는 생각하지 못했을 거다... 음 정말 내 능력이 부족하다는 것을 다시금 느끼면서도 참 이렇게 풀 수 있다는 것을 알고나니 멋있고 재미있는 문제같다.

일단 구현해 봐야겠다.
막상 구현하려니 거대한 벽이 존재하는 느낌이다. 그냥 bfs를 해서는 안된다. check배열을 쓰지 않고 방문했던 곳을 또 방문한다면 무한 루프에 빠질 수 있다. 그렇지만 check배열을 써서 방문한 곳은 방문하지 않는다면, 정답인 경로를 찾지 못할 수 있다....
그래서 고민하다가 생각한 것이 check배열에 인자를 더 넣는 것이다.
바로 check[r][c][(1, 1)에서 (r,c)까지의 최소값][(1, 1)에서 (r,c)까지의 최대값] ... 이것이다. 처음에는 check[r][c][(1,1)에서 (r,c)까지의 최대값과 최소값의 차이]로 하려고 했지만, 최소값과, 최대값이 다르더라도 최대값과 최소값의 차이는 같을 수 있고, 그 경우 다음에 어떤 정점을 방문하느냐에 따라 결과가 달라질 수 있기 때문에 안된다.

하지만 그 경로까지의 최소값, 최대값이 같다면 뒤에 어떤 경로를 방문하든 당연히 똑같은 값이 나올 것이므로 이미 같은 최소값, 최대값으로 방문했었다면 또 방문할 필요가 없는 것이다. 근데 이렇게 해도 시간은 꽤 걸릴 것 같아 보인다.

그래서 한가지 더, 일단 답을 정하고 탐색하기 때문에, 최대값과 최소값의 차이가 그 답을 넘어가면 더이상 그 경로로는 탐색하지 않으면 bfs탐색을 더 줄여줄 수 있을 것이다.

다시 구현해 봐야겠다. 음 정말 만만치 않은 아름다운 문제같다.
음... 근데, 저 check배열을 선언하려고 하면 check[100][100][200][200]... 메모리 초과가 날 것이다. 음.... 좀 더 고민해 봐야한다.

결국... 어떤 분이 써놓으신 풀이와 코드를 보고 이해했다.
음 이분 탐색으로 답을 정하고 bfs로 그 답을 만족하면서 갈 수 있는지 탐색하는 것이 맞는데, 문제는 그 답을 만족하면서 갈 수 있는지 탐색하는 부분이었다. 한 번 방문한 곳을 또 방문하지 않게되면, 답을 만족하는 경로를 찾지 못할 수 있고, 최대값과 최소값의 차이로만 구별을 하게 되면 최소값과 최대값의 차이는 같아도 최소값, 최대값이 다른 경우에는 다음에 어떤 정점을 방문하냐에 따라 결과가 달라질 수 있기 때문에 결국은 최소값, 최대값을 다 체크하면서 bfs를 해야했다. 하지만 그러면 메모리 초과... 여기에서 막혔었는데, 풀이를 보고 정말 감탄했다.

이분 탐색으로 최소값과 최대값의 차이값 diff를 정하고... 그 diff를 최대값과 최소값의 차이로 가지는 경로에서의 최소값(혹은 최대값도 가능)이 뭔지도 정해놓고 탐색하는 것이다!
diff도 정해져있고, 최소값도 정해진다면 방문할 수 있는 칸이 제한이 될 것이다. 그래서 조금 전처리를 하고 bfs를 돌리든지 아니면 bfs를 돌리면서 최소값이상이고 최소값+diff이하인 칸 만 방문하게 bfs를 돌려서 (1,1)에서 (n, n)으로 갈 수 있는지 보면된다.
최소값은 최소0부터 200인데, 일단은 그 배열에서 최소값a와 최대값b를 구해서 a부터 시작해서 최대 b까지(좀 더 정확히는 b-diff까지) 해보면된다.

그러면 시간 복잡도는 이분탐색 log(2N) * (a~b까지 최소값 설정) 2*N * bfs N^2
대충 N^3 * log N 이 될 것 같다.
실제로 계산하면 대략 최대 log(200) * 200 * (10000+40000) = 대략 8천만?
10000+40000은 bfs시간 복잡도인 (V+E)를 나타낸 것인데, 정점은 10000개, 간선의 개수는 40000보다 적겠지만 계산 편의상 한 정점당 간선 4개라고 하고 40000으로 계산했다...
시간제한이 2초라 충분히 들어올 것이다.

일단 AC를 받았는데, 최소값을 정할 때, 내가 위에다가 좀 더 정확히는 b-diff까지 라고 적었는데, 이러면 틀릴 수 있다. diff값이 너무 커서 b-diff가 a값보다 클 경우, for문에서 조건을 체크할 때, 아예 최소값을 정하지 못하고 for문이 실행되지 않아버린다. 그러면 이분 탐색을 할 때, diff를 최대 b-a까지만 정하도록 하면 될 것 같다. left=0, right=b-a로 놓고 해보면 될 것 같다. AC를 받았다. 그리고 다른 분들의 코드를 보니 dfs를 쓴 코드도 꽤 보인다.
이 방식대로 하면 bfs대신 dfs를 써도 될 것 이다. 한 번 해봐야겠다.

dfs로 구현하다보니 떠올랐는데, 아까 bfs로 구현할 때, (1, 1)시작부분은 체크를 안해서 또 방문하는 일이 생길 것 같아 보인다. 한 번 체크하고 다시 제출해 봐야겠다. 음 똑같다...다시 생각해보니 또 방문해서 그 때 체크하는 것도 시간상으로는 별 차이 없을 것 같다.
그럼 계속해서 dfs로 수정해 봐야겠다. dfs로 구현할 때는 조금 까다로운 것이, 방문한 경로 중에 하나라도 diff이하를 만족시키면 true를 반환하게 하는 것이 살짝 까다로웠다.
그냥 간단하게 if(dfs(r, c)) return true 이런식으로 하나라도 true이면 true를 return하고, 모두 true가 아닌 경우에 false를 return하는 식으로 구현해야 한다.

dfs로 하니까 메모리와 시간이 아주 조금씩이나마 줄었다.
 참 좋은 문제였고, 내가 내 혼자 힘으로 푼 것이 아닌만큼 다음에 꼭 복습하고 다시 풀어봐야겠다.


참조 및 출처 : KSJ14님의 블로그

BOJ 2228 구간 나누기

n개의 수가 주어지면 m개의 구간으로 나눠서 구간에 속한 수들의 총합이 최대가 되게 하려고 한다. 구간은 하나 이상의 연속된 수들로 이루어지고, 두 개의 구간이 붙어 있거나 겹치면 안된다. 그리고 m개 이하가 아닌 m개의 구간이 모두 있어야 한다.

이 때, 구간에 속한 수들의 총합을 구하는 문제이다.

dp다. 분명 약 두 달전에 푼 것으로 돼있는데... 딱 떠오르지가 않는다.
한 번 생각을 해보자.
d[n][m] = n번째 수부터 구간으로 선택할지 말지 결정해야 하고 만들어야 하는 구간은 m개일 때, n번째 수부터 시작해서 m개의 구간에 속한 수의 총합의 최대값

d[n][m]= MAX( d[n+1][m], a[n]+d[n+1][m], a[n]+d[n+2][m-1]) 인 것 같다.

1. d[n+1][m]은 a[n]을 선택하지 않았을 때이다.
2. a[n]+d[n+1][m]은 a[n]을 선택했지만 아직 하나의 구간이 끝나지 않은 경우이다.
3. a[n]+d[n+2][m-1]은 a[n]을 선택했고, a[n]에서 하나의 구간이 끝난 경우이다. 주의해야할 점은 구간끼리 붙어있으면 안되기 때문에 n+2번째부터 봐야한다.

이제 구현에 들어간다.
m개 이하가 아닌 m개의 구간이 모두 있어야 한다는 조건 처리해주는 것도 주의해야할 점이다.
제출했는데 WA를 받아서 여러 테스트 케이스도 해보고 고민하던 차에... 코드를 보는데...아... 감사합니다... 생각이 떠올랐다.
보통 dp를 할 때, 배열을 -1로 초기화하는데, 이 문제는 dp배열이 총합의 최대값을 나타내는데, 총합의 최대값은 음수가 될 수도 있다. 즉 -1이 될 수도 있다... 이것은 따로 check배열을 놓고 해야한다. 고쳐서 다시 제출해야겠다.

근데 또 WA를 받아서 내가 원래 풀었던 AC코드랑 비교하는 중이다. 예전에는 내가 미리 부분합을 구해놓고 부분합을 이용해서 풀었던 것으로 보인다. 일단 랜덤으로 데이터를 생성해서 비교해보겠다.

비교해 봤는데... 1. d[n+1][m]은 a[n]을 선택하지 않았을 때의 경우라 생각했는데...잘못됐다... d[n-1][m]에서 a[n-1]을 선택하고, d[n][m]을 호출했고, d[n+1][m]을 하려고 한다면 a[n]은 선택하지 않은 것이므로 그룹이 끊긴게 되는데, d[n+1][m]으로.. m이 그대로이다. 중간에 선택을 안하는 경우는 그룹이 끊겨서 결국 하나의 그룹을 쓴 것으로 되므로 m을 1줄여야 되는데 그 것이 안되서 틀린 것으로 보인다. 이것을 보완하려면 그룹이 이어지는 것인지 아닌지를 체크해줄 것이 필요하다. parameter를 하나 더 써서 해봐야겠다.

처음에는 parameter만 추가하려고 했는데, 이어지는지 아닌지에 따라 뒤의 값이 바뀔 수 밖에 없으므로 memoization이 제대로 되려면 d[n][m][con]이렇게 이어지는지 아닌지도 추가해줘야 한다. 결국 AC를 받았다.

위의 틀린 이유를 찾아낼 수 있게 해준 test case
n = 12, m = 1
27, 4, -17, -4, -3, 13, 10, 7, 7, 4, -6, -14

이제 예전에 풀었던 방법으로도 풀어보고 다시 정리해 봐야겠다.
배열의 부분합을 입력받으면서 구해놓고,
d[n][m] = n번째 수부터 보는데, 만들어야 하는 구간은 m개일 경우 m개의 구간에 속한 수들의 총합의 최대값

d[idx][cnt] = d[idx+1][cnt] // a[idx]를 선택하지 않는 경우
d[idx][cnt] = MAX(d[idx][cnt], d[idx+k+1][cnt-1]+psum[idx-1+k]-psum[idx-1]) (k는 1에서 idx+k-1 <= n-(cnt-1)*2 일 때까지) //a[idx]를 포함해서 k개 연속으로 선택하는 경우

->위의 두 가지 방법으로 다시 풀어봤는데 아래 방법에서
선택하지 않는 경우와 k개 연속으로 한 그룹으로 선택하는 경우에서.. k개 연속으로 선택하는 것으로 구현하려고 하면 구현이 좀 까다롭다... 복잡해진다. 실수할 확률이 높아진다.
오늘 다시해보니 이렇게 하는게 훨씬 구현하기 편하다.

xth부터 i까지 선택하는 것으로 하는 것이 훨씬 구현이 편하다! 결국은 똑같은 뜻이지만 굳이 k개를 선택한다는 것을 곧이곧대로 구현하기보다 ~까지 선택하는 식으로 구현하는 것이 훨씬 낫다!

BOJ 6549 히스토그램에서 가장 큰 직사각형

문제 유형을 보면
세그먼트 트리, 스택, 분할 정복 이렇게 3가지로 분류된다.
풀 수 있는 방법이 다양한 것 같다.
히스토그램은 너비는 같고, 높이가 다른 직사각형 여러개가 아래 부분을 맞춰서 옆으로 붙어 있는 모양인데 이 붙어있는 모양에 포함되는 가장 큰 직사각형 모양의 넓이를 찾는 것이다.

직사각형의 너비는 1로 같고, 입력으로는 높이가 차례로 주어지는데... 모르겠다. 그냥 바로 풀이를 봐야겠다.

baekjoon online judge blog에 백준님이 풀이를 잘 써놓으셔서 이해는 어느정도 됐는데, 내가 다시 써보려니 그리 쉽지는 않다. 백준님이 소개하는 방법으로는 두 가지가 있는데, 바로 분할 정복(+세그먼트 트리)을 이용하는 방법과 스택을 이용하는 방법 이렇게 두 가지이다.

먼저 분할 정복(+세그먼트 트리)으로 풀어보자.
히스토그램을 구성하는 각 직사각형을 하나씩 봤을 때, 그 직사각형의 높이를 가지는 가장 큰 직사각형은 그 직사각형을 기준으로 양쪽으로 직사각형을 확장하면서, 그 직사각형의 높이보다 작은 직사각형이 나오기 직전까지 확장하면 만들 수 있다.
그런데 이 과정을 모든 직사각형에 대해 일일이 해보려고 하면 O(n제곱)의 시간이 걸릴 것이다. 하지만 이것을 하나의 아이디어와 분할 정복을 이용한다면 좀 더 쉽게 할 수 있다.
각 직사각형의 높이를 가지는 가장 큰 직사각형을 찾을 때, 일단 가장 높이가 작은 직사각형부터 찾기 시작한다. 가장 높이가 작은 직사각형의 경우 양쪽으로 보면서 그 직사각형의 높이보다 작은 직사각형을 찾을 필요가 없다. 높이가 가장 작기 때문에 히스토그램의 왼쪽 끝과 오른쪽 끝까지의 직사각형이 그 높이를 가지는 가장 큰 직사각형이 될 것이다.

근데 여기서 의문이 들 것이다. 높이가 가장 작은 직사각형은 그렇다 치고 그럼 다른 높이를 가지는 것은 어떻게 할 것인가? 바로 여기서부터 분할 정복이다. 높이가 가장 작은 직사각형을 기준으로 분할할 수 있다. 분할을 한 후에 분할된 각 히스토그램에서 가장 높이가 작은 직사각형을 찾아서 그 높이를 자기는 가장 큰 직사각형은 역시 그 분할된 히스토그램의 양쪽 끝까지이다. 그리고 또 그 직사각형을 기준으로 분할하는 작업을 해 나간다. 바로 이렇게 분할함으로서 양쪽으로 확장해서 찾을 필요 없이 바로바로 해당 높이를 가지는 가장 큰 직사각형을 찾을 수 있다.
그리고 당연한 것이지만 설명하자면 히스토그램을 분할하면서 가장 작은 높이를 가진 직사각형 기준으로 분할하는 것은 어차피 그 높이보다 큰 높이를 가지는 직사각형을 만들 때는 더 작은 높이는 필요가 없기 때문이다.

자 그런데 문제가 하나 있다. 이렇게 분할을 해도 결국 그 분할된 히스토그램에서 최소값을 찾아야 한다. 생각해보면 분할 정복은 이분 탐색이랑은 좀 달라서 최악의 경우에는 최대 O(n)의 분할을 할 수도 있으므로 최소값을 직접 찾는다면 O(n제곱)의 시간복잡도를 가질 수 있다. 여기서 이 문제를 해결해줄 것이 바로 segment tree이다. segment tree를 이용하면 구간의 최소값을 O(log n)만에 찾을 수 있으므로 O(nlog n)에 해결할 수 있다.

한 번 구현해 봐야겠다.
주의할 점으로는 segment tree에 저장해야할 값은 구간의 최소값이 아닌 구간의 최소값의 index이다. (분할할 때 필요한 것은 index이고, 또한 index만 알아도 최소값은 바로 알 수 있기 때문에)
막상 구현해보니 segment tree를 구현할 때 구간의 최소값이 아닌 index를 넣다보니 조금 헷갈리기도 하고 실제로 실수도 해서 런타임에러도 났다. 결국 AC를 받았다.

이제 stack을 이용해 푸는 법을 알아보겠다.
각 직사각형 마다 그 높이를 가지는 가장 큰 직사각형은 그 직사각형을 기준으로 양쪽으로 살펴보면서 처음으로 높이가 작은 직사각형 직전까지가 되는데, 이 것을 stack을 이용해서 O(n)만에 구할 수 있는 것 같다.

일단 맨 앞에서부터 직사각형x를 stack에 넣는데, 현재 stack의 top값보다 작다면 stack의 top값을 높이로 하는 가장 큰 정사각형의 오른쪽 끝이 x-1까지라는 것을 알 수 있다. 그렇다면 왼쪽끝은 어떻게 알까? stack에는 top값보다 큰 경우에만 push하기 때문에, top값 바로 직전에 들어가있는 값이 y이면 y+1이 왼쪽끝을 나타내는게 된다.
그리고 히스토그램의 맨 끝에 도달할 경우에는 오른쪽 끝은 히스토그램의 맨 끝으로 놓고, top값의 직전에 들어간 값을 보면서 왼쪽 끝을 정할 수 있다.


출처 : 백준님 풀이, 강의 자료, https://www.acmicpc.net/blog/view/12

BOJ 9466 Term Project

그래프가 주어지면 그래프에서 사이클을 찾고, 사이클에 포함되지 않은 노드의 개수를 출력하는 문제라고 보면된다.

주어지는 그래프가 양방향 그래프가 아닌 단방향 그래프이고, 모든 정점이 서로 연결되어 있지 않을 수도 있다. (그래프 덩어리가 여러개 일 수 있다.)

일단 주어지는 그래프를 자료구조에 저장하는데, 그냥 일차원 배열에 저장 가능하다. 왜냐하면 한 정점은 한 정점만 가르킬 수 있기 때문이다. 그리고 dfs탐색을 하는데, 그러다가 이미 방문했던 정점을 또 방문하려할 때, 사이클이 있다는 것을 알 수 있다. 근데 사이클을 구성하는 정점이 몇 개인지 알아야 한다. 정점을 하나 하나 탐색하면서, 번호를 매긴다. 예를 들어 처음 방문 시작하는 정점은 1, 그 정점에 이어진 정점은 2, 3, 4...이렇게 번호를 매기다가 n번째 정점에서 3번째 정점을 만났다고 하면 n-3+1이 사이클을 구성하는 정점의 개수가 될 것이다.(더 편하게, 사이클에 포함되지 않는 정점의 개수는 n-1개일 것이다) 근데 문제는 방문하지 않은 다른 정점에서 시작해서 이미 방문한 정점과 만났을 때, 사이클이 아닌데 사이클로 판단한다는 것이 문제가 된다. 그래서 배열을 하나 더 만들어서 몇 번 정점에서 시작한 건지를 기록하고 이것을 참고해서 사이클이 아닌 경우를 구별해 보려고 한다.

AC를 받았다. 예전에 푼 코드를 보니 이렇게 비슷하게 푼 것도 있다.

BOJ 2011 Alphacode

알파벳 대문자('A' ~ 'Z')로 이루어진 단어 'A'는 1로, 'B'는 2로, ... , 'Z'는 26으로 변환한 암호 코드는 여러가지 알파벳의 조합으로 해석될 수 있다.

숫자 1 ~ 26으로 변환한 암호 코드가 주어질 때, 암호의 해석이 몇 가지 나올 수 있는지 구하는 문제이다.

dp이다. d[n] = n번째 숫자까지 봤을 때, 해석될 수 있는 경우의 수
1에서 26까지의 숫자만 알파벳으로 변환될 수 있으므로, n-1, n번째 숫자 2개를 보고 경우의 수가 어떻게 구성될지 판단할 수 있다.

n-1, n번째 숫자 2개가 1보다 크고 26이하인 경우 두 자리 숫자인 경우 두 자리 숫자를 하나의 알파벳으로 바꾸거나, 그냥 맨 끝 하나의 숫자만 알파벳으로 바꾸는 두 가지 경우가 있어서 d[n]=d[n-2]+d[n-1]이 될 것인데, 10이나, 20, 01, 02 같은 경우를 조심해야 한다. 10, 20인 경우는 무조건 10, 20 이렇게 한 가지로 밖에 해석이 안되므로 d[n]=d[n-2], 01, 02같은 경우도 앞의 0(n-1번째 자리)은 무조건 n-2번째 자리의 수와 함께 쓰여야 하므로(10, 20 이런식으로) 1, 2, 이렇게 한 가지 경우로만 해석된다. 즉 d[n]=d[n-1] 이 될 것이다.

그리고 n-1, n번째 숫자 2개가 26보다 클 경우에는 맨 뒤 한 자리만 알파벳으로 변환 가능하므로 d[n]=d[n-1]이 될 것이다.

그리고 경우의 수가 커질 수 있으므로 중간 중간 modulo를 해줘야하는 것도 잊지 말아야 한다.

---------------------------------------------------------------------------
재채점 후 WA를 받아서, 다시 풀어보는 중이다. 예전에 풀었던 방식이랑 같지만 다시 해보니 코드가 좀 더 깔끔해지는 것 같다.
d[n] = n번째 숫자를 끝으로 하는 나올 수 있는 해석의 가짓수
n-1번째, n번째 숫자 2개를 보고 결정하는데, 이번에 좀 다르게 한 것은 d[0]은 무조건 1일 테고, d[1]값은 경우에 따라 1일 수도, 2일 수도 있는데.. 물론 저번에 풀었던 방식은 d[len]을 구하고, 이번에 푸는 방식은 d[len-1]을 구하는 방식이라... 저번에 풀었던 방식도 틀린 것은 아닌 것 같은데... 여튼 d[len-1]을 구하는 방식으로 하니까 더 쉬운 것 같다.

그리고 제출했는데, 90퍼센트를 넘어서 WA를 받았다. 내가 알기로 BOJ 데이터가 보통 큰 데이터부터 작은 데이터 순으로 채점을 하기 때문에, 아마 내가 틀린 것은 작은 케이스에 대해서 인 듯한데, 생각해보니 문제에 꼭 올바른 케이스, 즉 반드시 해석 가능한 케이스가 들어온다는 말이 없다.
그래서 d[0]에는 무조건 1을 넣으면 안될 것이라는 생각이 들었다. 만약 맨 처음에 0이 들어오면 0으로 초기화 해줘야 한다... 아니 그냥 맨 처음이 0이면 무조건 경우의 수는 0이므로 예외처리 해서 0을 출력해주면 될 것 같다. 역시 불가능한 경우가 들어오는 것이 문제였다. AC를 받았다.

오늘 스터디_좋은 문제

n개의 정수가 주어지고, 주어진 순서를 유지하면서 왼쪽, 오른쪽 두 부분으로 나눠서 왼쪽편의 최대값과 오른쪽 편의 최대값의 차이가 최대가 되도록 하는 문제. 시간, 공간 복잡도를 O(n)만에 풀어야 한다.

최대값MAX를 먼저 구한다. 그리고 왼쪽 끝의 수A, 오른쪽 끝의 수B와 비교해본다.
즉, |MAX-A| 와 |MAX-B| 중 더 큰 값이 구하는 차이의 최대이다.
왜냐하면, 일단 MAX가 n개 중에서 최대값이므로 MAX가 포함된 쪽에서는 당연히 MAX가 최대값일 것이고, MAX가 포함되지 않은 쪽에서 최대값을 고르되, 그 최대값이 가장 작아야한다. MAX가 있는 쪽의 범위를 늘려서 다른 쪽의 큰 값들을 MAX가 있는 쪽에 포함되게 만들 수 있지만 수열 양 끝에 있는 값 두 개 중 하나는 포함할 수 없다.
그렇기 때문에, 수열 끝에 있는 값이 한쪽 그룹에서 가장 큰 값이면 어쩔 수 없이 그 값을 한쪽 그룹의 최대값으로 뽑을 수 밖에 없고, 만약 그 그룹에서 끝에 있는 값보다 더 큰 값이 있다면 그 큰 값을 MAX가 있는 쪽의 범위를 늘려서 포함시키면 이제 그 그룹의 최대값은 수열의 끝에 있는 값이 된다.

그러니까... 양 쪽 끝에 있는 값중 하나는 수열을 두 개 그룹으로 나눴을 때 적어도 하나의 그룹에서는 최대값이 될 수 밖에 없거나, 최대값이 되어야 왼쪽 편의 최대값과 오른쪽 편의 최대값의 차이가 최대가 되도록 할 수 있다.

정말 좋은 아이디어인데, 더 중요한 것은 이 아이디어의 정당성을 설명할 수 있는 것이 중요하다. 그리고 위와 같이 풀 경우 시간복잡도 O(n), 공간복잡도 O(1)만에 푸는 것이 된다.

BOJ 13164 행복 유치원

greedy문제(?)이다. 정답률도 높고, 실제로 어렵지는 않지만 생각 좀 해야하는 문제이다.
그리고 나는 sksdong1님께 풀이 힌트를 받은 상태에서 풀었기 때문에 빨리 풀 수 있었다.

오름차순으로 주어진 수들을 k개의 그룹으로 나눠 묶었을 때(한 그룹에 1명 이상), 각 그룹에서 최대값과 최소값의 차이를 계산하고, 그 계산한 값들의 합을 최소가 되게 하라는 문제인데, 각 그룹에서 최대값과 최소값의 차이는 (오름차순으로 정렬돼있으므로) 각 그룹의 맨 오른쪽 값과 맨 왼쪽 값의 차이가 된다.

얼핏 보면 k개의 그룹으로 나눌 수 있는 경우를 다 해봐야하나 라는 생각이 들 수 있지만, 잘 생각해보면 간단하다. 위에서 말했듯이, 각 그룹의 맨 오른쪽 값과, 맨 왼쪽 값의 차이가 각 그룹의 비용인데, 이 것은 맨 오른쪽 값과 맨 왼쪽 값의 차이이기도 하지만, 그 그룹에 포함된 수들 중 인접한 수들의 차이의 합이기도 하다.
인접한 수들의 차이의 합을 최소로 해야하고, 또한 그룹으로 묶으므로써 그룹과 그룹의 경계에 있는 수들의 차이는 계산에 넣지 않게 된다. 즉 그룹을 지을 때, 인접한 수들의 차이가 큰 곳을 그룹의 경계로 만들어야 구하는 값이 최소가 될 수 있다.

결국 구하는 최소값은 인접한 수들의 차이들을 구하고 내림차순으로 정렬해서 가장 큰 k-1개의 값(인접한 수들의 차이)을 제외한 나머지의 합이 된다.

Codeground - 대피소 [SCPC 2016 - 1차 예선]

간선에 가중치가 있는 연결된 무방향 그래프가 주어지는데, 이 그래프의 정점들 중 일부는 대피소로 지정이 되어있다. 그리고 각각의 정점에서 가장 가까운 대피소를 찾고, 그 대피소까지의 거리를 구하는 문제인데,  정점의 개수는 최대 10만 개, 간선의 개수는 최대 50만 개, 그리고 대피소의 개수는 최대 10만 개(항상 대피소의 개수<=정점의 개수)이다. 시간 제한은 1초이다.

그냥 딱 떠오르는 것을 적자면, 각각의 정점에서 다익스트라 알고리즘을 이용해 대피소까지의 최단거리를 구한 후 그 중 최소를 구하면 될 것 같다. 하지만 다익스트라의 시간 복잡도는 O(ElogE) (E : 간선의 개수)... 이므로 V*ElogE...가 되어 시간 내에 불가능하다.

그렇다면 어떻게 해야할까... 아이디어가 필요하다.
일단, 무방향 그래프이기 때문에 각 정점에서 각 대피소까지의 최단 거리는 각 대피소에서 각 정점까지의 최단 거리와 같다. 음... 하지만 대피소 역시 최대 10만 개 이다. 그럼 dijkstra를 최대 10만 번 돌려야 하나...결국 각 정점에서 dijkstra를 실행하는 것이나 다를 바가 없다.
하지만 dijkstra를 한 번만 사용할 방법이 있다. 새로운 정점 src를 하나 더 만들자. 그리고 그 정점과 대피소들을 연결하는 간선을 만들고 그 간선의 가중치는 0으로 둔다.
그러면 새로운 정점src에서 dijkstra를 이용하면, src에서 각 정점까지의 최단 거리를 구할 수 있는데, src에서 각 대피소까지의 거리는 0이므로 결국 각 정점에서 가장 가까운 대피소까지의 거리를 구한 것이 된다.
<프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 - 구종만 / (종만북, JM Book) > 이 책에 이와 비슷한 문제와 풀이가 나와있다.

자 그런데, 이 문제에서는 가장 가까운 대피소가 여러개일 경우 번호가 작은 대피소를 선택해야하는 문제가 또 있다. 이 것은 어떻게 해결할까? 여러 방법이 있겠지만, 나는 대피소의 번호를 담는 shelter라는 배열을 만들어서, dijkstra를 이용해 최단 거리를 구하는 과정에서 here->there로 가는 더 작은 경로를 찾을 때마다 shelter[there]를 처음부터 here까지 전해져 온 대피소의 위치(shelter[here])로 갱신해준다. 그리고, here->there로 가는 같은 크기의 또 다른 경로가 발견될 경우, 이미 존재하는 shelter[there]와 같은 크기의 또 다른 경로로 전해져 오는 대피소의 번호shelter[here]와 비교해서 더 작은 번호를 shelter[there]에 넣는다.
그리고 여기서 주의해야할 점이 here->there로 가는 같은 크기의 또 다른 경로가 발견될 때는 shelter만 업데이트 해주고, 그 경로를 pq에 넣지 않아도 된다. 왜냐하면 이미 그 값(dist[there])은 dist[here]보다 크서 pq안에 있기 때문이다.

자세한 구현은 조금 더 신경써야할 것이 있지만 일단은 크게 보면 이런 식으로 구현을 해서
만점을 받았다.