시간 복잡도
cost - 시간자원(CPU), 공간자원(Memory)
점근적 복잡도 f(n) : 입력크기 n에 대한 알고리즘의 시간 복잡도(성능).
상수시간 복잡도 O(1) - 입력값이 아무리 커도 실행시간이 일정한 최고의 알고리즘. 단, 상수시간이 매우 큰 경우에는 의미가 없다..
로그시간 복잡도 O(log) - 매우 큰 값에도 영향을 받지 않는다.
선형시간 복잡도 O(n) - 입력값에 비례한다. 정렬되지 않은 리스트에서 최대, 최소 등을 찾는 경우가 이에 해당한다.
O(nlogn) - 병합정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘.
O(n^2) - 버블 정렬 같은 비효율적인 정렬 알고리즘.(nested loop에 해당)
O(2^n) - n^2이랑 비교할 수 없을만큼.. 느리다.
O(n!) - 답은 나와도 사용할 수 없음.
ALGORITHM CODE KATA
Ⅰ. 문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 합니다. 먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다. 이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다. 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리합니다. s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다. 남은 부분이 없다면 종료합니다. 만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료합니다.문자열 s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고, 분해한 문자열의 개수를 return 하는 함수 solution을 완성하세요. (school.programmers.co.kr)
def solution(s):
x = "" # 첫 글자
s_cnt = 0
other_cnt = 0
answer = 0
for alp in s:
if x == "":
x = alp
s_cnt = 1
continue
if x == alp:
s_cnt += 1
else:
other_cnt += 1
if s_cnt == other_cnt:
x = ""
s_cnt = 0
other_cnt = 0
answer += 1
if x != "":
answer += 1
return answer