21.12.06 TIL

알고리즘 문제 풀기 with Python

외부 입력 받기

a,b = input().split() 
a=int(a) 
b=int(b) 
print(a+b)

문제 풀어보기

입력 조건과 문제, 출력 조건을 확인하기

최대 빈도수의 알파벳 찾기

def find_max_occurred_alphabet(string):
    array = [0] * 26
    for s in string:
        if s.isalpha() :
            index = ord(s)-ord('a')
            array[index] += 1

    max_num = 0
    for num in array:
        if num > max_num :
            max_num = num
    return chr(array.index(max_num)+ord('a'))


s = "hello my name is sparta"
result = find_max_occurred_alphabet(s)
print(result)

• 공간 복잡도 보다는 시간 복잡도를 더 신경쓰고 줄이려고 노력하자
• 최악의 경우 시간이 얼마나 소요될 지에 대해 고민하자

점근 표기법

점근 표기법은 알고리즘의 "효율성"을 평가하는 방법이다.

빅 오 표기법 : 최악의 성능 기준의 연상량 (ex 배열의 제일 마지막이 찾는 값)
빅 오메가 표기법 : 최선의 성능 기준의 연산량 (ex 배열의 제일 처음이 찾는 값)

알고리즘에서는 최악의 경우를 대비해야 하므로 거의 모든 알고리즘을 빅오 표기법으로 분석한다!

연습문제

소수 나열하기

def find_ord_num_under(num):
    result = []
    for target in range(num):
        if is_ord(target):
            result.append(target)
    return result


def is_ord(target):
    if target <= 1:
        return False
    for num in range(target):
        if num > 1:
            for sub in range(num+1):
                if sub > 1 and sub * num == target:
                    return False
    return True


print(find_ord_num_under(20))

시간 복잡도 : O(N^3)
공간 복잡도 : O(N)

실제로 돌려봐도 입력값이 커질 경우 엄청 느려짐..

문자열 뒤집기

input = "011110"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
    first = 0
    seconds = 0
    for i in range(len(string)):
        if string[i] == '1':
            if i == 0:
                first += 1
            if i > 0 and string[i-1] == '0':
                first += 1
            else:
                continue

    for i in range(len(string)):
        if string[i] == '0':
            if i == 0:
                seconds += 1
            if i > 0 and string[i-1] == '1':
                seconds += 1
            else:
                continue

    return min(first, seconds)


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

시간 복잡도 : O(N)
공간 복잡도 : O(1)