알고리즘
어떠한 문제를 풀기 위한 절차나 방법으로 알기 쉽게 설명하는 것이다.
알고리즘을 통해 어떤 문제든 가장 합리적인 방법을 쉽게 찾기가 가능하다.
공간 복잡도
프로그램 실행을 할 경우 메모리의 사용량이 중요하다.
10을 투자 했는데 1이 돌아온다면 얼마나 억울 한가
이 처럼 공간 복잡도는 내가 투자한 공간의 량이며 적으면 적을수록 좋다.
시간 복잡도
특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간으로 영향을 많이 준다.
big-o는 걸리는 시간으로 종류에 따라 사용하는 반복문에 따라 걸리는 시간이 천차만별이다.
10시간 일 했는데 1시간 일한 것만 받는 다면 얼마나 억울한가!!
big-o 종류들을 암기해서 효율적으로 알고리즘 문제를 풀어보자!!
1. O(1) 상수 복잡도
문제를 해결하는데 오직 한 단계만 처리하는 방식
인덱스 번호 list [n]를
2. O(log n) 로그 복잡도
문제를 해결하는 데 반으로 쪼개가며 탑색 하는 방식
3. O(n) 선형 복잡도
문제를 해결하는데 데이터양이 증가하면 연산량도 같이 증가하는 방식으로
n의 범위가 10.000.000 - O(n) 일 때 사용한다.
4. O(n log n) 선형 로그 복잡도
문제를 해결하는데 n*log n 번 만큼 수행하는 방식
n의 범위가 100.000인 경우 - O(n log n)
5. O(n^2) 2차 복잡도
문제를 해결하는데 데이터의 제곱만큼 증가하는 방식
n의 범위가 2000인 경우 - O(N^2)
2의 거듭제곱과 규칙을 꼭 암기해 두자(log)
2 4 8 16 32 64 128 256 1024
더 큰 2의 거듭제곱을 보면 많인 정보들이 나오지만 규칙이 있다.
2^11과 2^21은 앞에 자리는 숫자는 언제나 똑같고
2^n과 2^n+1은 뒷자리가 3개씩 증가한다.