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

시간복잡도

1) n*m 크기를 가진 맵을 탐색하는 bfs의 시간복잡도
: O(nm), bfs는 맵을 한 번 완전히 탐색하기 때문에

2) nm 크기를 가진 맵에서 2가지 지점을 뽑고 그 이후에 다시 BFS를 하는
시간복잡도
: O(nmC2 nm)
순서가 상관없으면 조합이 바로 생각나야하고, 순서가 상관있으면 바로 순열이 생각나야함

3) 10명의 선수 중 3명의 선수를 순서와 상관있게 뽑는 시간 복잡도
: O(10P3)

내가 짜는 코드의 시간복잡도가 얼마인지 알고 써야함
시간복잡도를 모두 외워야함

• map이나 set 같은 경우는 균형잡힌 트리로 구현되기 때문에 Red-Black Tree로 만들어져 있으므로 Red-Black Tree의 시간복잡도를 따른다, 즉 오드(log n)을 따른다? 즉, Access Search Insertion Deletion 모두 O(log(n))의 시간복잡도를 따른다

• sort() : nlogn (주로 Quick sort)

• lower_bound(), upper_bound() : nlogn

• find(), fill(), unique() : n

공간복잡도

프로그램을 실행시켰을 때 필요로 하는 자원공간의 양
정적/동적 공간 모두 포함함

알고리즘 문제를 풀 때는 배열의 경우 1000만짜리는 못 만든다
이분탐색과 펜윅트리를 배우면 이 문제를 펜윅트리로 풀 수 있어도
배열의 크기가 10억이 필요하다면 1000만 이상이라 불가능하다는걸 깨닫고
이분탐색으로 해야되겠구나 라는 사실을 알수 있어야 함 (판단척도)

• 재귀함수
  함수 정의 시, 자신을 재참조하는 함수
  무언가 인덱스를 변화시켜서 진행된다 ex) 피보나치

재귀함수는 "기저사례"와 "메인로직"으로 나뉘어진다
기저사례란, 탈출할 조건으로 종료조건을 말하고 가장 먼저!! 기저사례부터 작성해야함
메인로직은 피보나치 함수의 경우 fibo(idx-1) + fibo(idx-2)와 같은 부분임

• 누적합
  미리 요소들의 합을 저장해주는 누적된 수의 합을 의미함
  앞에서부터 더하는 것 : prefix sum (코테엔 이것만 나옴=psum)
  뒤에서부터 더하는 것 : postfix sum

예를 들어 1,2,3,4라는 배열의 누적합은 1,3,6,10이 됨
누적합 배열을 만들어놓으면 구간쿼리에 대응하기 쉬움
예를 들어 0번째 요소부터 3번째 요소까지 더하라고하면 누적합 배열의 3번째 요소를 추출하기만 하면 됨

예를 들어 A번째부터 B번째까지의 합을 구하라고 하면 누적합[B]-누적합[A]+A번째 요소값, 이렇게만 풀면 된다
이걸 무식하게 코드 짜서 풀면 시간복잡도가 엄청나게 올라가게 됨
그러니까 누적합을 미리 만들어놓는게 좋다 (배열 : 변함없는 정적요소)

구간쿼리는 2가지의 분류가 있는데, 정적배열 / 동적배열로 주어짐
정적배열로 주어지면 구간합을 쓰면 됨
동적배열로, 배열 자체가 어떤 순간에 변화된다고 하면 무조건 트리(세그먼트 트리, 패닉트리)를 사용해야 함

누적합을 만들때는 반드시 1번째 요소부터 만드는게 좋다.
0번째부터 시작하면 psum[i] = psum[i-1] + a[i]에서 i-1이 -1이 되어버리기 때문이다

• 구현
  reverse(str.begin(), str.end())로 str 문자열 전체를 뒤집어버림

• 문제를 푸는 방법
  문제를 해석하는게 가장 중요함
  1) 최대 최소 범위 파악
  2) 무식하게 for문이나 재귀를 통해 풀 수 있을까?
  3) 이걸 푸는 최적해가 있을까?
  4) 단순구현이라면 어떤 반례가 있을까?
  5) 단순구현이 아니고 다른 최단거리, 유니온파인드 등의 문제라면 어떻게 풀어야 하는가?