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

■ 24262번 알고리즘 수업 - 알고리즘의 수행 시간 1 문제

 

출처: 백준 24262번 알고리즘 수업

 

 

■ 코드 풀이

 

처음 문제를 접했을 때, 당황스러웠습니다. 아무리 읽어도 문제가 이해가 안 되더군요. 혹시 저와 같은 분이 계셨다면, 아래 글을 천천히 따라와 주시기 바랍니다.

먼저, 이 문제를 풀기 위해서는 시간 복잡도에 대해 알아야 합니다. 시간 복잡도에 대해 정말 잘 설명된 글이 있어서 아래 링크를 첨부합니다. 시간 복잡도에 대해 처음 들어보신 분들께서는 아래 링크를 꼭 정독해 주세요.

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

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

 

위의 글을 정리하면 시간 복잡도란 입력이 커질 경우, 소요되는 시간의 변화량을 의미합니다. 일반적으로 최악의 경우를 고려한 시간 복잡도를 사용하며 그 표기법을 Big-O라고 합니다. Big-O 표기법의 종류는 5가지가 있는데 그중 입력이 아무리 커져도 시간이 일정한 경우를 O(1)이라고 합니다.

여기까지 읽으셨다면, '도대체 이게 24262번 문제와 무슨 상관이 있는 거지?'라고 생각하실 수 있습니다. 다시 문제로 돌아가 보겠습니다. 문제에서 주어진 MenOfPassion를 해석하면 'n을 입력받아서 2로 나누고 버림 했을 때 나오는 정수를 Index로 한다. 이를 A[]라는 배열의 Indexing 값을 구하고 이를 Return하라'라는 의미입니다. 그리고 문제에서 이 함수의 '수행 횟수'를 출력하라고 했습니다. 수행 '횟수'.. 어디서 많이 본 표현 아닌가요?

맞습니다. 이는 '시간 복잡도'를 구하라는 문제입니다. 일종의 독해력 문제라고 할까요. 이것을 간파했다면 코드는 정말 간단합니다. MenOfPassion 함수는 반복문도 없고 단순히 입력값을 받아서 배열의 Indexing 값을 출력하는 함수이므로 입력이 아무리 커져도 '딱 1번'만 코드를 실행합니다. 그래서 첫 줄에는 무조건 1을 출력해야 합니다.

또한, 입력과 무관한 시간 복잡도 함수는 O(1)로 표현하고 상수항이므로 차수는 0이 됩니다. 따라서 두 번째 줄에는 무조건 0을 출력해야 합니다. 이를 코드로 정리하면 아래와 같습니다.

 

print(1)
print(0)

 

정말 허무하지 않나요? 오늘은 코드 공부보다는 시간 복잡도에 대한 개념 공부를 한 것에 의의를 두어야겠습니다.