시간복잡도

알고리즘이란?

유한한 수의 규칙에 따라 구별 가능한 기호들을 조작하여 입력 정수에서 출력 정수를 생성하기 위한 일반화된 작업을 정의

정밀성: 변하지 않는 명확한 작업 단계를 가져야 한다.
유일성: 각 단계마다 명확한 다음 단계를 가져야 한다.
타당성: 구현할 수 있고 실용적이어야 한다. → 알고리즘의 성능
입력: 정의된 입결을 받아들일 수 있어야 한다.
출력: 답으로 출력을 내보낼 수 있어야 한다.
유한성: 특정 수의 작업 이후에 정지해야 한다.
일반성: 정의된 입력들에 일반적으로 적용할 수 있어야 한다.

알고리즘의 성능은 어떻게 측정할 것인가?(절대 시간 측정)

PC에서 코드가 수행된 시간이 짧을수록 좋은 성능이다라고 정의한다면 동일한 코드를 수행할 때, 두 개의 PC에서 결과가 같게 나올까?

알고리즘 성능 측정을 위해서는 환경에 제약을 받지 않는 기준이 있어야 한다.

연산 횟수 측정

환경 영향을 받지 않지만 입력값에 따라 달라질 수 있으므로 기준 필요

입력값에 따른 연산횟수가 일정하지 않는 경우 → 코테에서는 최악의 경우를 기준으로 연산횟수를 정하는 것이 좋음.

입력값에 따른 연산횟수를 측정해서 알고리즘의 성능을 지표로 나타내는 것을 시간복잡도라고 함.

생각해볼 점

코딩테스트에서 이렇게 정밀한 연산 횟수를 매번 측정해야하는가?
- 점근적 표기법으로 표기. 연산 횟수 추이로 통과 여부만 파악하면 됨
시간복잡도 활용법
- 입력값을 기준으로 가용한 자료구조 및 알고리즘 고려 가능

점근적 표기법

N^2 + 3N + 5를 봤을 때

N을 무한으로 보내면 가장 큰 차수만 남겨도 무방.

N^2 + 3N + 5 → N^2

점근적 표기법: 정확한 연산 횟수가 아닌, 연산 횟수의 추이 활용해 시간 복잡도 표기.

이 때 최악의 경우 고려하여 점근적 표기법으로 나타내는 것이 빅오표기법.

자주 보이는 복잡도의 점근적 표기법

1차원 배열 탐색: O(N)
2차원 배열 탐색: O(N*M)
이진탐색트리 원소 탐색: O(log N)
동전 N개를 던졌을 때 경우의 수: O(2^N)

점근적 표기법 코테에 활용하기

입력값의 크기를 통해 어느 정도 시간복잡도까지 허용되는지 추측 가능→ 본인이 구현한 코드가 시간 초과가 발생할지 미리 파악 가능
→ 대략 초당 1,000 ~ 2,000만 정도 연산한다 가정하면 된다.
→ 구현 시 알고리즘/자료구조 선택 명확히 할 수 있음

메서드의 시간 복잡도 파악

동일한 동작을 하는 것처럼 보이나 시간 복잡도가 다른 경우 존재

기본 컨테이너 - unordered 컨테이너
vector와 dictionary/set에서 특정 key 존재 유무 확인
vector와 list에서 특정 위치 원소 가져오기

실전 예시

문제 1 짝지어 제거하기

알파벳 소문자로 구성된 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 짝을 찾은 다음에는 그 둘을 제거한 뒤 앞뒤로 문자열을 이어붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성하세요. 성공적으로 수행할 수 있으면 1, 아니면 0을 반환해주면 됩니다. 예를 들어 문자열 S가 baabaa라면

baabaa→ bbaa → aa

순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

제약 조건

문자열의 길이: 1,000,000 이하의 자연수

문자열은 모두 소문자로 이루어져 있음.