leehanjun   7년 전

문제는 최적화를 통해서 해결했습니다. 

그런데 문제를 풀면서 시간 복잡도에 대해서 질문이 있어서 질문을 남깁니다.

이전의 결과 값을 이용하여서 비교 값을 찾는 알고리즘을 실행했는데, 

이럴 경우에는 어떻게 시간 복잡도를 계산해야 하는 것일까요?  

때때로 입력 값: 9, 8, 7, 6, 5 에서 10이 들어가서 worst case가 되는 경우가 있는데, 어떻게 계산해야 하는지 모르겠습니다.

많은 분들이 O(N) 라고 계산하시는 이유가 무엇인가요?

tddhot2   7년 전

제 생각엔 문제를 푸는 원리가 삽입정렬과 비슷한 형태로 이뤄집니다.

삽입정렬의 최악 시간복잡도가 O(n^2)입니다.

아마도 최악의 경우 시간복잡도는 O(n^2)이지만

삽입정렬의 경우 데이터 실제 값에 따라 O(n)까지 효율을 낼 수 있는 것처럼

최악의 경우가 없는 대부분의 테스트 케이스가 문제의 테스트 케이스로 주어진거 아닐까 조심스럽게 생각합니다.

starjrm00   7년 전

이 문제는 stack을 사용하면 쓸모없는 연산의 횟수를 줄여 최대 3n이 안되는 연산횟수로 해결할 수 있습니다.

문제에서 우리가 봐야할 점이 a,b,c,높이의 탑이 연속해서 있고, a>b, b<c일때는 c 뒤에있는 탑에서는 b에 절대로 정보를 보낼수가 없다는 것입니다.

우리는 여기서 b의 값을 아예 버려버리면 연산 앞의값과의 연산을 더 빠르게 할 수 있다는 점을 알 수 있습니다.

모든 n에 대해서 stack에 넣는 연산을 총 n번, 각자의 n이 수신하는 건물을 찾았다는 연산을 총 n번, 쓸모 없는 건물을 빼는 연산 (최대)n번으로 총 3n 이하의 연산을 사용하여 최악의 경우 시간복잡도가 O(n)이 되게 됩니다.

정해라고 할 수 있는 개념을 여기에 쓰기는 뭣한거 같아 약간 추상적으로 썼습니다만 도움이 되었으면 좋겠습니다.

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