24262번 /알고리즘의 수행시간1 (시간 복잡도 개념)

시간 복잡도 개념

● 시간복잡도 ( Time Complexity)

- 효율적 알고리즘 구현 방법에 대한 고민

- Big-O 표기법

 

❗️효율적인 알고리즘 고민

- 알고리즘의 문제풀이도 중요하지만 효율적 방법의 해결도 그만큼 중요

- 효율적 방법 고민 == 시간 복잡도 고민

 

❗️시간 복잡도

- 알고리즘의 로직을 코드로 구현시, 시간 복잡도 고려

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?

따라서 , 효율적인 알고리즘 구현은

입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성

- 주로 Big-O 표기법 사용

 

❗️Big-O 표기법

👉 시간 복잡도를 표기하는 방법

• Big-O(빅-오) ⇒ 상한 점근
• Big-Ω(빅-오메가) ⇒ 하한 점근
• Big-θ(빅-세타) ⇒ 그 둘의 평균
• 위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법

 

👉 가장 자주 사용되는 표기법?

• 빅오 표기법은 최악의 경우를 고려
• 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려
• “최소한 특정 시간 이상이 걸린다” 혹은 “이 정도 시간이 걸린다”를 고려하는 것보다 
• “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능

👉 시간 복잡도 최선의 경우를 고려한 경우

• 결과를 반환하는 데 최선의 경우 1초, 평균적으로 1분, 최악의 경우 1시간이 걸리는 알고리즘을 구현했고, 최선의 경우를 고려한다고 가정
• 이 알고리즘을 100번 실행한다면, 최선의 경우 100초가 걸린다.
• 만약 실제로 걸린 시간이 1시간을 훌쩍 넘겼다면, ‘어디에서 문제가 발생한 거지?’란 의문이 생긴다.
• 최선의 경우만 고려하였으니, 어디에서 문제가 발생했는지 알아내기 위해서는 로직의 많은 부분을 파악해야 하므로 문제를 파악하는 데 많은 시간이 필요하다.

👉 시간 복잡도 중간의 경우를 고려한 경우

• 평균값을 기대하는 시간 복잡도를 고려한다면 어떨까?
• 알고리즘을 100번 실행할 때 100분의 시간이 소요된다고 생각했는데, 최악의 경우가 몇 개 발생하여 300분이 넘게 걸렸다면 최선의 경우를 고려한 것과 같은 고민을 하게 된다.

👉 시간 복잡도 최악의 경우를 고려한 경우

• 극단적인 예이지만, 위와 같이 최악의 경우가 발생하지 않기를 바라며 시간을 계산하는 것보다는 ‘최악의 경우도 고려하여 대비’하는 것이 바람직하다.
• 따라서 다른 표기법보다 Big-O 표기법을 많이 사용한다.
• Big-O 표기법은 ‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’를 표기하는 방법이다.

👉 Big-O 표기법의 종류

1. O(1)
2. O(n)
3. O(log n)
4. O(n2)
5. O(2n)

출처 : https://hanamon.kr/wp-content/uploads/2021/07/Big-O-Complexity-Chart.png

 

❗️각 Big-O 표기법에 대한 자세한 설명은 하기 링크 참조(상기 내용도 동일한 링크 참조)

https://hanamon.kr/wp-content/uploads/2021/07/Big-O-Complexity-Chart.png

 

📚문제

 

출처 : 백준 / 24262번 (https://www.acmicpc.net/problem/24262)

 

📝풀이

print(1) # 어떤 입력값이 들어오든 수행횟수는 1이므로
print(0)

 

시간 복잡도란 입력값의 값이 커질 경우, 소요되는 시간의 변화량을 말한다.

일반적으로 최악의 경우(시간이 제일 오래걸리는경우)를 고려한 시간 복잡도 사용 => Big-O 표기법

👉 Big-O 표기법의 종류 5가지

1. O(1)
2. O(n)
3. O(log n)
4. O(n2)
5. O(2n)

이 때, 어떤 입력값이 들어오든 시간이 일정한 경우는 O(1)이다

 

24262번 문제가 이 O(1)경우에 해당한다

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

해당 코드의 내용은 우선

배열 A와 n을 입력받는데, n을 2로 나누고 정수 값만 취한 다음(i)

A배열에서 i의 인덱스에 해당하는 값을 반환하는 코드이다

 

이 때 n이 10이 들어오든10000이 들어오든

i의 값을 구한 다음에 A[i]의 값을 1회만 return하기 때문이다

 

문제에서 주어진

"첫째 줄에 코드1의 수행 횟수" => 1회로 고정 => print(1)

"둘째 줄에 코드1의 수행횟수를 다항식으로 나타낼 때, 최고차항의 차수 출력" 

=> 수행횟수 1이 상수항이므로 차수는 0으로 고정 => print(0)

 

시간 복잡도 개념을 알고 있다면 진짜 간단하게 풀 수 있는 독해문제...

시간 복잡도 개념을 찍먹한 것에 의의를 두자