백준 24262번 풀이

문제

https://www.acmicpc.net/problem/24262

24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1

주어진 알고리즘의 실행 시간을 출력한다.

 

Reference

https://develop247.tistory.com/195

[파이썬/Python] 백준 24262번 알고리즘 수업 - 알고리즘의 수행 시간 1

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

[알고리즘] Time Complexity (시간 복잡도) - 하나몬

 

풀이

일단 이 문제를 본 본인의 심정:

이짤 너무 우려먹는 것 같다면 기분탓입니다. 아무튼 솔직히 이 글 보러 온 여러분들도 그렇잖아요?

 

일단 이 문제의 답은 개 심플하다. 근데 배경 설명을 듣고 가시는게 다음 문제, 다다음 문제를 풀 때도 그렇고 아무튼 정신건강에 이롭다. 답은 여기다가 올리면 답만 보고 갈 것 같으니 밑에 공개해드리겠음.

 

시간 복잡도가 이 카테고리의 주제인데 이건 쉽게 말하자면 '이 코드를 실행하는데 시간이 얼마나 걸리느냐'이다. 당장 3초만 로딩 걸려도 새로고침 연타하는 한국인 특...인 건 아니지만 모든 코드는 효율적으로 짜는 편이 좋잖음? 솔직히 코드 하나 돌리는데 10분 돌리는거랑 1분 돌리는거랑 여러분은 후자 고를거잖아요.

 

일단 시간 복잡도는 보통 빅 오 표기법을 쓰는데, O(n) 이런 식으로 쓰는 게 빅 오 표기법이다. 다른 표기법으로는 빅 오메가, 빅 세타가 있지만 아무튼 여기서는 빅 오에 대해서만 서술하겠음. 나머지 두개는 나도 뭔지 몰라요. 아무튼 빅 오 표기법은 실행 시간의 '상한선'을 나타낸다. 이게 머선소리9?

 

무슨 그래프인지는 모르겠는데 아무튼 점근선이라는 개념을 갖는 그래프가 있다. 일단 쌍곡선은 아닌게 내 중고딩때 배웠던거임. 로그함수는 아닌것같고 아마 y = 1 / x였나 그랬을텐데 이 점근선이 뭐냐면 어떤 그래프가 특정 직선에 대한 거리가 0으로 수렴할때 그 직선을 점근선이라고 부른다. 빅 오 표기법의 다른 이름도 점근 표기법인데... 생각해봅시다. 점근선이라는 건 어느 점에 가까워진다는거잖아요? 그래프의 형태에 따라서는 암만 지하실로 가봐야 여기까지가 바닥이다! 이런 개념일 수도 있지만 암만 올라가봐야 여기까지가 천장임! 이런 개념이라고 보면 된다. 빅 오 표기법도 점근선이랑 비슷하게, 얘가 암만 실행 시간이 오래 걸려봐야 여기가 천장임! 이라는 얘기.

 

이 빅오는 내가 다른 포스트로 따로 다루겠고, 일단 시간 복잡도가 왜 중요한지는 아시겠죠? 그럼 이제 답 공개함.

print(1)
print(0)

이거 진짜냐고요? 예. 나도 그 반응이었으...