시간 복잡도
이후 알고리즘들을 소개하기 전에 가장 기본이 되는 시간 복잡도에 대해 설명해보려한다.
이틀 전에 처음 접했기 때문에 굉장히 쉬운 단어들만 골라서 사용할 것이다.
빅오 표기법 (BigO)
흔히 시간 복잡도를 빅오 표기법을 사용해 표현한다.
빅오는 그냥 대문자 O를 얘기하는 거 같고,
그래서 표기법을 보면
O(1) = 상수 시간
O(logN) = 로그
O(N) = 직선(선형)
O(NlogN) = 선형 로그
O(N^2) = 제곱
O(2^N) = 지수의 N 제곱
대충 눈치챘을지 모르겠지만 위에서 밑으로 갈수록 시간복잡도가 커지는 것이다.
그럼 밑으로 커지는 건 알겠는데 어느정도 차이인지 실감나게 하기 위해
N을 9로 가정해보겠다.
O(1)
O(1) = 상수 시간은 시간 복잡도 자체가 그냥 1이다.
N을 몇이라고 가정한들 한방에 그 작업이 끝나는 것이다.
예를 들면, console.log(100000) 을 찍는다고 해서
여러번에 걸쳐 작업하는게 아닌 것과 같다.
O(logN)
O(logN) = 침착하자 로그가 뭔지 나도 모른다.
N이 9라고 했으니까 log9 가 될 것이다.
log9는 뭘 제곱했을 때 9가 되는지를 묻는 것과 같다.
즉 log9는 3이다. 그럼 log16은 ? 4이고 log25는 5가 될 것이다.
여기서 알아야할건 log9가 뭔지가 중요한게 아니고
기존 N의 값이 줄어들었다는 걸 알아야한다.
O(N)
O(N) : 직선(선형) : O(9) 받은 값 그대로 어떤 소스도 들어가지 않는다.
이쯤 되면 앞에 O(빅오)는 지금 수준에서 딱히 왜 쓰는지,
왜 날 헷갈리게 하는지 화만 날 뿐이다.
O(NlogN)
O(NlogN) : 선형로그 : O(9log9)
log9 = 3이니까 자연스레 O(9x3 = 27)이 된다.
O(9x3 = 27) 이렇게 표기하는거 아닐탠데 이해를 돕기 위해 쓴거다.
O(N^2)
O(N^2) : 제곱 : 9의 2제곱이다. = 81이 된다.
O(2^N)
O(2^N) : 지수 N의 제곱 : 정신 차리자 마지막이다.
그대로만 읽으면 2의9제곱이 된다.
이게 몇인지를 알아보려는게 아니고 대충 엄청 크다 는 걸 인지하면 된다.
이렇게 시간 복잡도에 대해 알아봤다.
어떠한 식을 적을 때 무조건 시간 복잡도가 낮을수록 좋은 코드일 수 있지만,
구현 자체가 안된다면 의미가 없다.
제 기능을 하면서 시간 복잡도를 최소한으로 잡을 수 있다면 또 그렇게 사용할 수 있다면
알고리즘 + 코테의 신이 될 수 있다
투 포인터 알고리즘
흔히 두개 이상의 변수가 배열을 순회할 때 사용했던 방법은
이중 포문을 돌려 각각 전부를 탐색해서 원하는 비교를 하고 그에 맞는 출력을 했다.
하지만 언제까지고 그렇게 문제를 푼다면 서울에서 부산까지 가는 방법 중
걸어가는 방법만 매번 채택하고 있는 것과 다름 없다고 생각한다.
이중 포문을 돌려 해결하는 것도 하나의 알고리즘 이라면 ,
시간 복잡도를 고려하여 기존의 O(n^2) 시간 복잡도에서,
O(n)의 시간 복잡도가 되는 투 포인터 알고리즘을 사용한다면 코딩 테스트 시간 측면에서
좀 더 알맞는 문제 해결이 가능하다.
예를 들어 하는 설명은 다음을 기약하겠다.
