[CS] APS, 시간 복잡도 정리

🔍 APS란 무엇인가

APS : Algorithm Problem Solving

 

나도 강의에서 처음 듣게 된 APS,, 한번 정리해보려 한다.

 

우선 APS는 알고리즘 문제 풀이 방법을 말한다.

알고리즘 문제 풀이법에는 많은 것들이 있고, 그중에서 주어진 문제에 따라 원하는 결과를 낼 수 있도록 프로그램을 작성하는 것이 목표이다. 

 

그렇다면 APS 공부는 왜 해야 할까 ??

 

1. 알고리즘 풀이법을 공부하면서 문제 구현력을 기를 수 있다.

2. 다양한 문제가 발생하는 경우의 디버깅 경험을 쌓을 수 있을 것이다.

• 알고리즘 문제 풀이를 하며 발생하는 오류들을 접해보고, 이러한 오류를 해결해 나가는 과정 자체에서 우리는 많은 것을 배우고 성장할 수 있다.

3. 논리적으로 사고하는 법을 배우게 된다.

• 여러 알고리즘을 적용하며 문제를 풀면서 논리적으로 문제를 풀어가는 방법에 대해 배울 수 있다.

 

이러한 APS의 목표는 실행시간을 줄이는 것에 있다. 적은 실행시간으로 정확하게 문제를 푸는 것이 가장 중요하다.

나도 알고리즘 문제를 본격적으로 풀기 시작하면서 실행시간을 줄이기 위한 고민을 하게 되었다. 나중에 더 공부하고 많은 문제들을 풀어보면서, 같은 풀이에서도 실행 시간을 줄일 수 있는 방법을 고민해 보고 정리해 올릴 계획이다.

 

⏱ 시간 복잡도

작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타낸다. - by. 위키백과

 

다시 설명하자면 시간 복잡도는 실행되는 명령문의 개수와 로직을 통해 프로그램 실행 시 걸리는 시간을 나타낸 함수이다.

 

실행시간을 줄이기 위해서, 즉 효율적으로 알고리즘을 짜기 위해서는 입력값이 커지더라도 적은 연산을 통해 결과를 찾을 수 있는 시간을 단축시키는 것이 중요하다.

 

이러한 시간 복잡도를 나타내는 것이 바로 Big-O 표기법이다.

 

작년에 독학으로 빅오 표기법에 대해 공부를 하려다가 무슨 말인지 모르겠고, 예제를 접하기 어려워 포기했었는데 싸피에서 배우니까 생각보다 어려운 내용이 아니라 당황했다 ..

 

📃 Big-O 표기법

Big-O 표기법의 경우 연산이 가장 많이 일어나는 경우(최악의 경우)를 가정한다.

 

예를 들어, 배열의 앞에서부터 하나씩 비교를 찾을 때 {1, 44, 8, 34, 59, 90, 50}이라는 배열이 있을 경우 50이라는 값을 찾기 위해서는 7번의 비교 끝에 50을 찾을 수 있을 것이다. 이와 같은 경우를 시간복잡도에서 최악의 경우라고 하고, 1을 찾는 경우 한 번에 바로 찾을 수 있기 때문에 최선의 경우라고 한다.

 

지금의 예시는 원소가 7개에 불과하지만 원소의 개수가 10000개를 넘어간다면 어떨까 ? 아마 최선의 경우와 최악의 경우 차이가 꽤 커질 것이다. 

 

이렇게 다양한 경우의 수 중에서 가장 연산이 오래 걸리는 경우를 대비해야 하기 때문에, Big-O 표기법을 자주 사용하게 된다.

 

Big-O 표기법의 종류

 

 

위의 그래프는 Big O 시간 복잡도에서 요소 수에 따른 연산 수를 나타낸 그래프이다.

 

O(log n), O(n)의 경우 요소수가 많이 늘어나더라도 연산 수가 크게 차이 나지 않는데, O(n!)이나 O(2^n)과 같은 경우에는 요소수가 10만 되더라도 연산의 수가 기하급수적으로 늘어나는 것을 볼 수 있다.

 

이러한 시간 복잡도를 알고 나면, 문제를 풀 때에 어떤 알고리즘을 적용해야 시간초과가 일어나지 않을 수 있을지 예상하며 풀 수 있게 된다.

 

그럼 다음에는 몇 가지 정렬을 보면서 시간 복잡도를 구해보도록 하자.