백준 24262 - 파이썬

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

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

문제 풀이

오늘은 단계별 풀어보기에서 시간 복잡도 관련 문제를 풀어보았다. 처음에 이 문제를 읽었을 때 이해를 하지 못했다. 난독증이 온거처럼 문제가 이해되지 않아 구글링을 해 보니 이 문제는 시간 복잡도를 평소에 생각하지 않고 문제를 풀었던 사람들에게 시간 복잡도라는 개념을 각인시켜주기 위한 문제라는 것을 알았다.

 

MenOfPassion(A[], n) {
    i = ⌊n / 2⌋;
    return A[i]; # 코드1
}

 

이 코드를 보면 n에 값이 들어오고, n을 2로 나눈 값을 인덱스로 하여 배열 값을 리턴한다. 즉, n에 어떤 값이 들어와도 1번만 수행하는 수행횟수가 한 번인 함수인 것이다. 이런 함수를 보고 시간 복잡도가 O(1)이라 한다.

 

이렇기 때문에 출력문에서 첫번째 줄 출력에 1이 출력된 것이다. 두번째 줄 출력은 최고차항을 나타내는 것인데 위 코드는 다항식이 아니기 때문에 0이 출력된 것이다.

 

그럼 두번째 출력에서 1이나 2가 나오는 경우인가? 아래 코드를 보면 이해하기 쉬울 것이다.

for i in range(n): # n은 0이 아니다.
	print(i)

 

위 코드처럼 반복문이 하나일 때 시간복잡도는 O(n)이다. 이런 경우가 수행횟수가 다항식인 것이고, 1차 함수이기 때문에 두번째 줄출력은 1이 된다.

for i in range(n):
    for j in range(n):
    	print(n)

 

이 경우는 이중 반복문이기 때문에 시간 복잡도는 O(n^2)이다. 따라서 두번째 줄 출력은 2가 되는 것이다.

 

느낀점

이 글의 첫 문단에서 말했다시피 문제를 처음 읽고는 이해를 하지 못했다. 기존에 풀어오던 문제들과는 달라 보였기 때문이다, 하지만 문제의 의도를 알고 나니 시간 복잡도라는 것을 상기할 수 있었다. 평소에 알고 있던 개념인데도 막상 문제를 풀 때는 생각하지 않았던 개념이기 때문이다. 다음 문제를 풀 때는 시간 복잡도도 생각해 보면서 풀어 봐야 되겠다.