알고리즘 성능 평가지표
코딩테스트를 볼 때 알고리즘 성능 평가 지표에서 '메모리 사용량'과 효율성 그 중에서도 '시간복잡도'를 신경써야한다. 메모리 사용량 같은 경우는 대부분 넉넉하게 주기 때문에 코딩테스트에서는 시간복잡도만 최우선으로 하면 된다,
시간복잡도란 입력크기의 값에 대해 단위 연산을 몇 번 수행하는지 계산하여, 알고리즘의 수행시간을 평가하는 방법이다. 여기에는 3가지 접근적 표현법이 있다.
- O(빅오) : 최악의 상황을 고려하여 성능측정결과를 표현한다. 주로 이것이 많이 사용된다.
- θ(세타) : 평균적인 경우에서의 성능측정결과를 표현한다.
- Ω(오메가) : 최선의 상황일 떄의 성능측정결과를 표현한다.
빅오의 표기법은 4가지로 나눌 수 있는데,
- 반복문 없이 일련의 단순한 코드만 있을 경우 O(1) 상수로만 표기한다. 이것은 엄청 빠르다는 것을 의미하기도 한다.
- 반복문이 1개가 있을 경우 O(N)으로 표기한다. 반복문에 들어가는 변수의 개수만큼 반복을 하기 때문에, n 즉 1차로 표현한 것이다.
- 반복분이 중첩으로 있는 경우 O(N^2)으로 표기한다. 반복문 한 개당 N의 차수가 하나씩 커진다고 생각하면 된다. 삼중으로 되있을 경우는 세제곱으로 표기될 수도 있지만, 이런 경우는 속도를 매우 저하시키기 때문에 지양되는 코드이다.
- 반복문에서도 증감문이 배수로 커지는 경우 O(logN)으로 표기한다. 배수로 커지는 경우 배수만큼 반복이 나누기가 되기 때문에 이렇게 표기된다.
경우의 수
코드를 짜다보면 경우의 수를 아는 것이 매우 중요하다고 느껴진다. 완전탐색의 경우는 경우의 수를 푸는 알고리즘이기 때문에 코딩테스트를 준비한다면 순열과 조합을 꼭 한 번 짚고 넘어가야 한다. 반복문과 재귀함수로 코드를 짤 수 있는데, 반복문의 경우 변수가 늘어나는 만큼 반복문의 중첩이 늘어나기 때문에 지양하는 방법이다.
순열
순열은 서로 다른 n개의 원소 중 r을 중복없이 골라 순서에 상관있게 나열하는 경우의 수를 말한다.공식은 nPr로 쓰기도 한다. 여기서 중요한건 순서가 상관있다는 점이다.
예: 서로 다른 카드를 순서있게 나열할 때
중복순열
중복순열은 서로 다른 n개의 원소중에서 r개를 중복으로 골라 순서에 상관있게 나열하는 경우의 수이다. (nH)
조합
조합은 서로 다른 n개의 원소중에서 r개를 중복없이 골라 순서에 상관없이 나열하는 경우의 수이다. (nCr)
예: 서로 다른 카드들 중에서 r개의 카드를 뽑을 때
재귀함수가 이해가 잘 안 간다. 더 찾아봐야겠다.
점화식(=재귀식)
점화식이란 수열에서 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식, 귀납적 추론을 이용해서 수식을 만들 수 있다. 경우의 수와 마찬가지로 반복문 또는 재귀함수로 코드를 짤 수 있다.
예: 등차수열[F(n) = F(n-1)+a], 등비수열[F(n) = F(n-1)*a], 팩토리얼[F(n) = F(n-1)*n], 피보나치수열[F(n) = F(n-1) + F(n-2)]
