풀기 전 항상 질문할 리스트

1. 최종으로 구하자 하는 건 뭐지? -> 최종으로 보는 메시지

2. 입력값 중 수정되지 않는 건 뭐지? -> 유저 아이디

3. 입력값 중 수정되는 건 뭐지? -> 닉네임

   1. 입력값이 수정될 때 어디가 영향받지? -> 오픈 채팅방의 내용 변경

   2. 입력값은 어느 조건에서 수정되지? Enter와 Change인 경우

컴퓨터 1초 기준 -> 1000만~ 3000만, 으로 생각

시간 복잡도

시간 복잡도	N의 가용 범위
O(N!)	10
O(2^n)	20~25
O(N^3)	200~300
O(N^2)	3000~5000
O(NlogN)	100만
O(N)	1000~2000만
O(logN)	10억 이상

1. BUD를 찾자

두 단계로 이루어진 알고리즘이 있다고 가정해보자. 먼저 배열을 정렬한 뒤 특정 속성을 가진 원소를 찾는 알고리즘이라고 가정해보자. 첫 번째 단계에선 O(NlogN)이 소요되고 두 번째 단계에선 O(N)이 소요된다. 두번째 단계를 O(logN)이나 O(1)으로 줄일 수 있다고 해서 의미가 있을까? 별 의미가 없다. 왜냐하면 O(NlogN)이 알고리즘의 병목점이기 때문이다.