Machineboy空
문제로 연습하는 시간복잡도, 공간복잡도,누적합,구현 본문
https://machineboy0.tistory.com/57
https://blog.naver.com/jhc9639/222283814653
# 시간복잡도 예제
# 시간복잡도 1 n^2
몇 번이나 반복될까?
cnt가 얼마나 증가하는지 손으로 쓰며 체화할 필요가 있다
# 시간복잡도 2
수행 횟수 : N+M
# 시간복잡도 3 - 다항식이 든 재귀함수O(n)
시간복잡도는 단순하다. 몇 번 반복되는지를 카운트하면 된다.
얼마 반복되었는지를 점화식으로 표현해서 빅오로 나타내는 것.
go라는 재귀함수가 몇번 호출되었는지 cnt돌려봐.
10일 때 19, 5일때 9인 걸 보니
혹시 2n-1아닐까?
+는 상수시간 복잡도를 가진다.
# 시간복잡도 계산 실전
- cnt 디버깅 후 어림잡아 시간복잡도를 계산하라
- 정석은 점화식을 구하는 것
# 점화식
# 시간복잡도 4
# 시간복잡도 5
함수 하나 당 몇번 호출되는지에 따라 x^n의 시간복잡도
# 공간복잡도 (space complexity)
- 입력 크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양
- 변수든 뭐든 컴퓨터 메모리에 올라가니까 여기에 쓰이는 메모리 공간의 양
- 정적변수로 선언된 것 외에도
- 동적으로 재귀함수로 인해 공간을 계속해서 필요로 할 경우도 포함하며
- 배열이든 맵이든 셋이든 요소들을 담을 공간이면 다 적용
int a[100000000]; // 전역변수
void f(){
int b[1004]; // 지역변수
}
int main(){
}
입력이 N이 들어왔다면 N개짜리의 int형 요소를 담아야 할 공간이 필요하므로 4N바이트 공간이 필요
이를 빅오 표기법으로 나타내면 O(N)
하지만, 이런 공간 복잡도의 개념은 문제 푸는데 잘 사용되지 않는다
보통 문제 풀 때 배열의 범위등을 잡을 때는 2가지 방법을 기반으로 잡는다.
- 최대범위
- 대부분의 문제는 최대범위를 기반으로 배열을 미리 만든다.
- int a[1000000]
- 메모리 제한
- 메모리 제한: 512MB (=512,000,000)byte
- 즉 int a[128000000] 선언 가능
메모리 제한을 매번 보기는 힘들다.
"1000만까지는 어느 정도는 된다"고 잡고 들어가는 것이 좋다.
ex) 펜윅트리, 이분탐색 중 어떤 알고리즘을 택하는 것이 맞을까?
유동적 배열에서 한 요소를 logN만에 찾을 수 있음
그런데 펜 윅트리는 새로이 배열을 만들어야 하고, 이분탐색은 그러지 않을 수 있다.
메모리 제한이 1000만이라 생각하고 이분탐색을 사용해야한다고 감을 잡아야 함.
# 누적합(prefix sum, 앞에서부터 더하는 것)
* 뒤에서 더하는 거 suffix sum이라고 함
- 요소들의 누적된 합의 의미로
- 어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것
N,M이 둘 다 최댓값인 N = 100,000이고 M = 100,000이라면,
코드의 시간복잡도는 10만 * 10만 = 100억
누적합을 미리 만들어두고 구간쿼리 즉, 빼는식으로 하면
코드의 시간 복잡도 10만 * 1
구간 쿼리라고 하면
구간 합 또는 펜윅트리 생각하기
동적 배열이라면 펜윅트리, 정적배열이라면 구간합 사용가능
# 구현
구현은 아주 쉬운 알고리즘이다. 숙달이 안되면 어려움
- 구현 예시
- 앞에서부터 3개의 문자열을 출력하라
- 해당 문자열을 거꾸로 해서 출력하라
- 해당 문자열 끝에 "umzunsik"이란 문자열을 추가하라.
# 문제를 푸는 방법의 기초
- 문제를 본다
- 문제를 해석한다 (코드를 작성하지 말고 해석에 좀 더 시간을 쓰기- 최대 최소 범위 이런 거 보고, 단계적 로직 등)
- 코드를 작성한다
예시
- 최대,최소 범위를 파악한다
- 단순 구현이라면 구현하자
- 무식하게 풀 수 있다면 무식하게 풀자 (brute-force : 완전탐색 무식하게 풀기)
- 아니라면 다른 알고리즘을 생각하자
- 제출하기 전에 반례를 항상 생각하자 (test case가 다 맞다고 해도, 반례 생각!)
'Computer > 알고리즘' 카테고리의 다른 글
그래프 이론 기초 (Graph, Vertex, Edge, Indegree, Outdegree, Weight) (1) | 2024.02.05 |
---|---|
순열(Permutation)과 조합(Combination) (1) | 2024.01.30 |
정수론 - 에라토스테네스의 체 / 오일러 피 / 유클리드 호제법 (0) | 2023.12.19 |
백준 11004번: K번째 수 - 퀵 정렬 (Quick Sort) (0) | 2023.10.31 |
Sorting(정렬) - bubble, selection, insertion, quick, merge, radix (0) | 2023.10.14 |