리처드 파인만 공부법
- 무언가를 간단하게 설명할 수 없다면, 그것을 제대로 이해하고 있는 것이 아니다
- 어린이도 이해할 수 있을 만큼 쉽고 평이한 언어로 설명할 수 있도록 공부해야 함
-> 어려운 단어, 문장을 그대로 외우는 게 아닌, 원리를 이해하여 간단히 설명할 수 있도록 연습
알고리즘 평가는 수행 시간/메모리 사용량에 기준을 둔다.
시간 복잡도(Time Complexity)
- 수행 시간에 해당함
- 특정 크기의 입력을 기준으로, “필요한 연산의 횟수”
공간 복잡도(Space Complexity)
- 메모리 사용량
- 프로그램 실행/완료에 “필요한 메모리 공간”
시간 복잡도와 공간 복잡도는 “반비례”하는 경향이 있다.
ex) 실행시간을 줄이면 메모리를 많이 쓰고, 메모리를 적게 쓰면 실행시간이 늘어나고...
실제 개발 시엔 시간/공간 복잡도를 적절하게 효율적으로 설계해야 할 것으로 보인다.
-> 일반적으로 알고리즘 성능을 판단할 땐 “시간 복잡도”를 기준으로 판단한다.
시간 복잡도(Time Complexity) 표기법
Big-O(빅 오) 표기법 : 알고리즘 최악의 실행 시간을 표기한다. 가장 많이 사용하는 표기법이다. 최소한 보장되는 성능을 표기하기 때문에 가장 일반적으로 사용한다.
Big-Ω(빅 오메가) : 표기법 알고리즘 최상의 실행 시간을 표기한다.
Big-θ(빅 세타) : 표기법 알고리즘 평균 실행 시간을 표기한다.
=> 주의!! 빅 세타는 일반적으로 평균 실행 시간을 표기하도록 사용되지만, 정확히는 최악, 최상 실행 시간의 같거나 거 의 비슷할 때 빅 세타로 표기할 수 있게 되는 것이다.
빅오 표기법(Big-O notation)의 특징
시간복잡도에 미미한 영향을 주는 것들은 “배제”하고 표기됨
- 상수항을 무시한다
O(N+5)의 복잡도를 가졌다고 하면 상수를 생략하고 O(N)으로 표기한다
- 계수를 무시한다
O(3N)의 복잡도를 가졌다고 하면 계수를 생략하고 O(N)으로 표기한다
- 최고차항만 표기한다
O(3N**3+2N**2+N+5) 복잡도를 가졌다고 하면 O(N**3)으로 표기한다
빅오 표기법의 종류
실행 속도 (N은 입력값)
O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N)
O(1)이 가장 빠르고 O(2^N)이 가장 느리다.
세로는 시간 복잡도, 가로는 입력값이다.
높이 있을 수록 느리고, 오른쪽에 있을 수록 입력값이 많다.
1. O(1)
입력값(N)이 증가해도 실행시간이 동일하다.
index로 접근하여 바로 처리할 수 있는 연산 과정의 시간 복잡도이다. (기본 연산 수와 같다)
2. O(log N)
연산이 한 번 실행될 때 마다 데이터 크기가 절반 감소한다 (log의 지수는 항상 2)
데이터가 많을 때 효율적이다
ex) binary search, tree형태 자료구조 검색
3. O(N)
입력값(N)이 증가함에 따라 실행시간도 선형적으로 증가한다(비례하여 증가한다)
ex) 1중 for문
4. O(N log N)
O(N)의 알고리즘과 O(log N)의 알고리즘이 중첩된 형태
ex) 퀵/병합/힙 정렬
5. O(N^2)
입력값(N)의 제곱만큼 실행 시간이 증가한다
ex) 2중 For문, 삽입/버블/선택 정렬
6. O(2^N)
빅오 표기법 중 가장 느린 시간 복잡도, 주로 재귀적으로 수행하는 알고리즘이 이에 해당함
ex) fibonacci 수열
번외 - O(N!)
O(2^N) 보다도 훨씬 느림. 팩토리얼 함수의 엄청난 성장 속도와 비례한다.
알고리즘
제곱근 구하는 법
- 0.5승을 하면 됨
ex) 50의 제곱근 : 50 ** 0.5
소수인지 판단하는 법
- 2부터 해당 숫자의 제곱근까지 나누어 보고 나누어 떨어지는 수가 없으면 소수. ( 소수 판별 함수 만들어서 푸는게 편하다 )
골드바흐 추측
- 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다. 이 짝수를 “골드바흐 수”라고 한다.
- 모든 짝수에 대해 적용된다는 점은 현재 아주 큰 수까지 증명되었지만, 모든 수에 대해서 적용되는지는 증명되지 않은 상태다.
- 짝수를 이루는 2개의 소수를 “골드바흐 파티션”이라고 한다. 골드바흐 파티션은 여러개일 수 있다.
이분 탐색(Binary Search)
- 정렬되어 있는 리스트에서, 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
- 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있음
- 변수 3개(start, end, mid)를 사용하여 탐색하며, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다.
(오늘 문제를 풀면서, if num in list : 형식의 코드로는 메모리 초과가 떴는데, 이분 탐색으로 바꾸니 통과되었다.)
재귀함수(recursive)
- 함수 자신과 똑같은 함수를 호출하는 함수, “직접 재귀”
- 함수 a가 b를 호출하고 b가 a를 호출하는 식이면 “간접 재귀” -> a가 “b를 이용”해서 자기 자신과 같은 함수를 호출한 것