문제
주어진 알고리즘의 실행 시간을 출력한다.
Reference
https://develop247.tistory.com/195
풀이
일단 이 문제를 본 본인의 심정:
이짤 너무 우려먹는 것 같다면 기분탓입니다. 아무튼 솔직히 이 글 보러 온 여러분들도 그렇잖아요?
일단 이 문제의 답은 개 심플하다. 근데 배경 설명을 듣고 가시는게 다음 문제, 다다음 문제를 풀 때도 그렇고 아무튼 정신건강에 이롭다. 답은 여기다가 올리면 답만 보고 갈 것 같으니 밑에 공개해드리겠음.
시간 복잡도가 이 카테고리의 주제인데 이건 쉽게 말하자면 ‘이 코드를 실행하는데 시간이 얼마나 걸리느냐’이다. 당장 3초만 로딩 걸려도 새로고침 연타하는 한국인 특…인 건 아니지만 모든 코드는 효율적으로 짜는 편이 좋잖음? 솔직히 코드 하나 돌리는데 10분 돌리는거랑 1분 돌리는거랑 여러분은 후자 고를거잖아요.
일단 시간 복잡도는 보통 빅 오 표기법을 쓰는데, O(n) 이런 식으로 쓰는 게 빅 오 표기법이다. 다른 표기법으로는 빅 오메가, 빅 세타가 있지만 아무튼 여기서는 빅 오에 대해서만 서술하겠음. 나머지 두개는 나도 뭔지 몰라요. 아무튼 빅 오 표기법은 실행 시간의 ‘상한선’을 나타낸다. 이게 머선소리9?
무슨 그래프인지는 모르겠는데 아무튼 점근선이라는 개념을 갖는 그래프가 있다. 일단 쌍곡선은 아닌게 내 중고딩때 배웠던거임. 로그함수는 아닌것같고 아마 y = 1 / x였나 그랬을텐데 이 점근선이 뭐냐면 어떤 그래프가 특정 직선에 대한 거리가 0으로 수렴할때 그 직선을 점근선이라고 부른다. 빅 오 표기법의 다른 이름도 점근 표기법인데… 생각해봅시다. 점근선이라는 건 어느 점에 가까워진다는거잖아요? 그래프의 형태에 따라서는 암만 지하실로 가봐야 여기까지가 바닥이다! 이런 개념일 수도 있지만 암만 올라가봐야 여기까지가 천장임! 이런 개념이라고 보면 된다. 빅 오 표기법도 점근선이랑 비슷하게, 얘가 암만 실행 시간이 오래 걸려봐야 여기가 천장임! 이라는 얘기.
이 빅오는 내가 다른 포스트로 따로 다루겠고, 일단 시간 복잡도가 왜 중요한지는 아시겠죠? 그럼 이제 답 공개함.
print(1)
print(0)이게 진짜 정답이냐고요? 예.
Reply