[Algorithm] 백준 특강

자료형 문제

자료형 선택이 핵심인 문제

• 파이썬은 자료형을 신경 쓰지 않아도 되지만, C++ · 자바는 자료형을 신경 써야 한다.

카운트 배열 초기화와 입력 조건

cnt 배열 초기화 예시

• cnt → 256으로 초기화한다.
• 입력은 대소문자만 있고, 대소문자를 구분하지 않는다고 가정한다.
• 파이썬을 쓰는 경우 (이런 상황이) 상당히 자주 발생한다.
• 매번 길이를 구해야 하므로 O(N²)과 같아진다.

파이썬과 시간복잡도

파이썬으로 문제를 해결할 때는 시간복잡도를 반드시 알아야 한다.

6번 문제 시간복잡도

• 6번의 정답은? → O(M)
• 파이썬으로 풀면 시간초과를 많이 받는데, 실제로는 한 줄만 썼더라도 그 한 줄의 시간복잡도가 1이 아니라 N이나 M인 경우가 많기 때문이다.
• 그 아래 if문의 시간복잡도는? → O(N)

문자열 누적 연산의 시간복잡도

s += A와 s = s + A의 시간복잡도는 같을까?

언어	시간복잡도
C++	O(N)
Python	O(N²)
Java	O(N²)