프로그램의 성능은 가장 중요한 요소입니다. 그러면 프로그램의 성능은 어떻게 측정할까요? 이 책에서는 시간 복잡도라는 개념을 기준으로 프로그램의 성능을 분석합니다.
시간 복잡도를 코딩 테스트에 활용하는 방법
이제 시간 복잡도를 표현하는 방법이 빅오 표기법이라는 건 알았습니다. 그럼 빅오 표기법을 어떻게 활용하면 좋을까요? 코딩 테스트 문제에는 제한 시간이 있으므로 문제를 분석한 후에 빅오 표기법을 활용해서 해당 알고리즘을 적용했을 때 제한 시간 내에 출력값이 나올 수 있을지 확인해볼 수 있습니다. 그러면 문제 조건에 맞지 않는 알고리즘을 적용하느라 낭비하는 시간을 줄일 수 있습니다. 보통은 다음을 기준으로 알고리즘을 선택합니다.
“컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억 번이다.”
코딩 테스트의 문제는 출제자가 의도한 로직을 구현했다면 대부분의 코드를 정답 처리할 수 있도록 채점 시간을 충분히 여유있게 지정합니다. 따라서 연산 횟수는 1,000~3,000만 정도로 고려해서 시간 복잡도를 생각하면 됩니다. 예를 들어 제한 시간이 1초인 문제는 연산 횟수가 3,000만이 넘는 알고리즘은 사용하면 안 됩니다. 제한 시간이 1초인 문제에 각 시간 복잡도별로 허용할 수 있는 최대 연산 횟수는 다음과 같이 생각하면 됩니다.
※ 언어별로 성능은 다를 수 있으나 특정 언어가 유리하거나 불리하면 안 되겠죠? 그래서 언어에 따른 성능 차이는 고려하지 않아도 됩니다.
맨 처음 우리가 살펴본 배열에서 검색하기로 돌아가보면…
이렇게 하나하나 짚어가며 찾는 방식은 시간 복잡도가 O(N)입니다. O(N)이 허용하는 연산 횟수는 1,000만이므로 데이터의 개수가 1,000만 개 이하면 이 알고리즘은 사용해도 됩니다. 바로 이렇게 시간 복잡도를 활용하여 불필요한 알고리즘을 제외하면 됩니다.
시간 복잡도 계산해보기
이제 실전으로 넘어와 시간 복잡도를 계산해봅시다. 몇 가지 상황을 보면서 시간 복잡도를 계산하는 방법을 익혀두면 다른 문제를 풀 때도 시간 복잡도를 수월하게 계산해볼 수 있을 겁니다. 여기서는 ❶ 문제 정의부터 시작해서 ❷ 연산 횟수를 측정한 후 ❸ 시간 복잡도를 분석하는 순서로 공부를 진행하겠습니다.
별 찍기 문제
별 찍기 문제는 언어를 공부한 여러분에게는 매우 익숙할 겁니다. 문제는 숫자 N를 입력받으면 N번째 줄까지 별을 1개부터 N개까지 늘려가며 출력하라는 것입니다. 다음 입출력 예를 확인하면 어떤 문제인지 쉽게 이해할 수 있을 것입니다.
푸는 과정
우선 연산 횟수를 구합니다. 지금은 출력 자체가 연산입니다. 1번째 줄은 1번 연산, 2번째 줄은 2번 연산, … N번째 줄은 N번 연산합니다. 그림으로 보면 다음과 같습니다.
결국 연산 횟수 f(N)는 다음과 같습니다. 빅오 표기법으로는 O(N2)이라고 할 수 있겠네요.
박테리아 수명 문제
초기 박테리아 세포 개수가 N일 때 해마다 세포 개수가 이전 세포 개수의 반으로 준다면 언제 모든 박테리아가 죽을지 계산해야 합니다. 입출력의 예는 아래 표와 같습니다.
푸는 과정
예를 들어 N이 16인 경우, 모든 박테리아는 5년이면 소멸합니다.
현재 박테리아의 수가 N이라면 1년 뒤의 박테리아 수는 ½*N이라고 할 수 있습니다. Y년 후의 박테리아의 수는 (½)Y*N입니다. 이를 그림으로 나타내면 다음과 같습니다.
그러면 박테리아의 소멸 시기는 (½)YN의 값이 최초로 1보다 작아질 때입니다. 수식으로는 (½)YN <= 1인 Y를 찾으면 됩니다. 이 수식은 다음과 같이 정리할 수 있습니다.
- (½)Y은 ½Y로 생각해 (½)Y*N는 Y <=1이다.
- 양변에 2Y를 곱해 식을 정리하면 2Y >= N이고
- 양변에 로그를 취하면 Y >= log2N이다.
이를 통해 이 알고리즘은 O(logN)의 시간 복잡도를 가진다는 것을 알 수 있습니다.
지금까지 빅오 표기법으로 알고리즘의 효율을 분석하는 방법을 공부했습니다. 코딩 테스트에서 시간 복잡도를 이해하고 분석하는 것은 매우 중요합니다. 시간 복잡도를 이해하면 알고리즘의 성능을 정확하게 측정할 수 있으므로 문제를 풀 수 있는 적절한 알고리즘을 선택하고 설계할 수 있죠. 내가 적용한 알고리즘이 문제를 해결할 수 있는지, 왜 시간 초과가 발생하는지 원인을 명확히 인지하고 공부하기 바랍니다. 무슨 일을 하더라도 현재 여러분의 상태를 분명히 파악해야 개선할 수 있는 것처럼요.
자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(파이썬 편)
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
