문제로 연습하는 시간복잡도, 공간복잡도,누적합,구현

https://machineboy0.tistory.com/57 

시간복잡도(Time-Complexity), 빅오표기법(Big-O)

https://blog.naver.com/jhc9639/222283814653

[알고리즘 강의] 1주차. 시간복잡도, 빅오표기법, 공간복잡도, 누적합, 구현

---

# 시간복잡도 예제

# 시간복잡도 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가지 방법을 기반으로 잡는다.

1. 최대범위
   • 대부분의 문제는 최대범위를 기반으로 배열을 미리 만든다.
   • int a[1000000]
2. 메모리 제한
   • 메모리 제한: 512MB (=512,000,000)byte
   • 즉 int a[128000000] 선언 가능

메모리 제한을 매번 보기는 힘들다.

"1000만까지는 어느 정도는 된다"고 잡고 들어가는 것이 좋다.

 

ex) 펜윅트리, 이분탐색 중 어떤 알고리즘을 택하는 것이 맞을까?

유동적 배열에서 한 요소를 logN만에 찾을 수 있음

그런데 펜 윅트리는 새로이 배열을 만들어야 하고, 이분탐색은 그러지 않을 수 있다.

메모리 제한이 1000만이라 생각하고 이분탐색을 사용해야한다고 감을 잡아야 함.

---

# 누적합(prefix sum, 앞에서부터 더하는 것)

* 뒤에서 더하는 거 suffix sum이라고 함

• 요소들의 누적된 합의 의미로
• 어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것

풀이 1

 

N,M이 둘 다 최댓값인 N = 100,000이고 M = 100,000이라면,

코드의 시간복잡도는 10만 * 10만 = 100억

누적합을 미리 만들어두고 구간쿼리 즉, 빼는식으로 하면

코드의 시간 복잡도 10만 * 1

 

구간 쿼리라고 하면

구간 합 또는 펜윅트리 생각하기

동적 배열이라면 펜윅트리, 정적배열이라면 구간합 사용가능

---

# 구현

 

구현은 아주 쉬운 알고리즘이다. 숙달이 안되면 어려움

• 구현 예시
  • 앞에서부터 3개의 문자열을 출력하라
  • 해당 문자열을 거꾸로 해서 출력하라
  • 해당 문자열 끝에 "umzunsik"이란 문자열을 추가하라.

---

# 문제를 푸는 방법의 기초

• 문제를 본다
• 문제를 해석한다 (코드를 작성하지 말고 해석에 좀 더 시간을 쓰기- 최대 최소 범위 이런 거 보고, 단계적 로직 등)
• 코드를 작성한다

예시

• 최대,최소 범위를 파악한다
• 단순 구현이라면 구현하자
• 무식하게 풀 수 있다면 무식하게 풀자 (brute-force : 완전탐색 무식하게 풀기)
• 아니라면 다른 알고리즘을 생각하자
• 제출하기 전에 반례를 항상 생각하자 (test case가 다 맞다고 해도, 반례 생각!)