sourish92   4년 전

안녕하세요! 이제 막 알고리즘 공부를 시작한 초보입니다.ㅠㅠ

DP로 문제를 풀어보려고 해서 처음에 O(n^2)로 풀었었는데 시간 초과가 나더라구요..

그래서 루프를 한번만 돌도록 코드를 수정하였는데도 시간 초과가 나네요..

이유를 모르겠습니다..ㅠㅠ 아래의 코드가 O(n) 아닌가요..? K값이 최대 십만이라 절대 시간초과가 안 날거라고 생각했었는데

코드를 고쳐도 계속 시간초과가 나서 질문 드립니다.ㅠㅠ

dp[i]를 i번째 건물을 모두 지을 때 까지의 시간이라고 정의하고,

dp[table[i][1]] = max(dp[table[i][1]], arr[table[i][1]] + dp[table[i][0]]);

를 통해서 값을 구했는데요, max()를 사용해서 i번째 건물들을 짓기위해서 미리 지어야 하는 건물 들의

완료 시간들중 가장 큰 값을 넣어주었습니다. 부족한 코드지만 보시고 문제점 지적해주시면 감사하겠습니다!

algoshipda   4년 전

시간초과는 table이 크기가 작게 잡혀서 밖에 있는 곳을 참조하면서 메모리 값을 이상하게 바꿔서 생긴 것 같구요.
이 문제는 반복문으로 푸시려면 위상정렬을 하고 그 순서대로 테이블을 채워주셔야 해요.
왜냐면 arr[table[i][1]] + dp[table[i][0]]을 계산할 때 dp[table[i][0]]에 있는 값이 완성된 값이라는게 보장이 안되거든요.

sourish92   4년 전

먼저 답변 정말 감사합니다 ㅠㅠ..

저도 테이블 크기가 작다는 걸 깨닫고 코드를 바꾼 후에, 정렬이 필요할 것같아서 정렬을 해주긴 했는데..

제가 알고리즘을 공부한지 얼마 되지 않아서 위상정렬이 뭔지 모르겠는데 ㅠㅠ

제가 생각한 대로 라면 table을 정렬할 때 table[i][0]이 작은 순서가 먼저 오도록, 만약 table[i][0]값이 같으면 table[i][1]값이 작은 순서가 앞에 오도록

코드를 수정했었는데 틀렸습니다가 뜨더라구요.. ㅠㅠ 제가 정렬한 방식으로 정렬하면 dp[table[i][0]]값이 완성된 상태가 보장 되는게 아닌가요..?

algoshipda   4년 전

table[i][0] < table[i][1] 이 보장 되지 않아서, 반례가 있을 것 같아요.

sourish92   4년 전

아..감사합니다.. 생각해보니 그렇네요.. ㅜㅜ 수정을 해야 될 것 같아요

table[i][0]이 table[i][1]보다 먼저 지어지는건 맞지만 무조건 작은 숫자의 건물이 먼저 지어진다는 보장이 없네요..

그런데 말씀하신 위상정렬이 제가 정렬한 것과 비슷한건가요? 검색을 해보니 선수과목 같은 느낌으로 순서에 맞게끔 나열하는 것이라고 나와있던데..

algoshipda   4년 전

위상정렬이 저렇게 단순한 방식으로 되지는 않구요. DFS나 BFS로 할 수 있어요.
이쪽에 소스가 있네요

sourish92   4년 전

정말 감사합니다 ㅠㅠ 공부해볼게요!! 


댓글을 작성하려면 로그인해야 합니다.