어려운 문제란?

👉 컴퓨터조차 오래 걸리는 문제
얼마나 오래 걸리는지는 시간 복잡도를 통해 파악

1~N까지의 합

해법 1 <for문 반복>

N이 커질수록 연산 횟수 증가

해법 2 <공식 이용> N(N+1)/2

N이 크던 작던 연산은 딱 1번만 수행

문제를 푸는 솔루션이 꼭 하나만 있으란 법은 없다
알고리즘에 따라 답을 구하는 시간(효율)이 다르다

시간 복잡도

Time Complexity

입력량 N에 비례해서 얼만큼 연산을 많이 하는지 빅오 표기법 (Big-O notation)으로 나타냄

• 알고리즘 효율성의 척도

Big-O natation

• 가장 큰 항을 살리고 그보다 작은 항들은 다 뗀다
• 계수, 상수도 뗀다

시간 계산법

정확한 연산 시간이 아니므로 대강 시간 조건을 만족하는지 계산할때 사용하자!

• 1초에 총 연산 1억 번이 넘어가면 위험하다. "1초 = 1억"이라고 생각
• k중 for문 = O(N^k)

공간 복잡도

Space Complexity

N에 비례해서 메모리를 얼마나 쓰는지를 나타냄

• 일반적으로 메모리(공간)과 시간은 반비례 관계
• 기업 코딩테스트에서는 시간, 공간 복잡도까지는 잘 계산하지 않음 (대회나 백준에서는 필요할 때가 있음)

꿀팁

int 범위 (-2^31 ~ 2^31-1 -> 21억) 초과하는 값을 다룰 때는 long long 사용

• 이것 또한 대회, 백준이 아닌 기업 코테에서는 잘 나오지 않는 이슈