알고리즘 1주차 - 점근표기법, 연습문제

점근표기법

알고리즘의 성능을 수학적으로 표기하는 방법 즉 알고리즘의 '효율성'을 평가하는 방법.

어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법.

이전에서 공부했던 시간복잡도와 공간복잡도도 점근 표기법의 일종.

빅오(Big-O) 표기법

최악의 성능이 나올때 어느 정도의 연산량이 걸릴 것인지 표기

빅 오메가(Big-Ω) 표기법

최선의 성능이 나올때 어느 정도의 연산량이 걸릴 것인지 표기

배열에서 특정 요소 찾기

다음과 같은 숫자로 이루어진 배열이 있을 때, 이 배열 내에 특정한 숫자가 존재하면 True, 존재하지 않는다면 False를 반환하기

input = [3, 5, 6, 1, 2, 4]


def is_number_exist(number, array):
    # 이 부분을 채워보세요!
    return True


result = is_number_exist(3, input)
print(result)

# 내 코드
def is_number_exist(number, array):
    if number in array:
        return True
		return False

# 튜터 코드
def is_number_exist(number, array): 
    for element in array: # array의 길이 만큼 아래 연산 실행
        if number == element: # 비교 연산 1번 실행
            return True # N*1 = N

N이 시간복잡도 이지만 무조건 N인 것은 아니다.

3이 첫번째 인덱스에 있으므로 바로 True를 반환하게 된다.

운이 좋으면 한번만 연산해도 찾을 수 있다.

반대로 운이 좋지 않으면 N만큼의 연산을 다해야 한다.

즉 입력값에 따라서 입력값의 분포에 따라서 성능이 변화할 수 있다.

O(N),$\Omega (1)$ 만큼의 시간복잡도를 가진 것이다.

대부분의 경우는 최선의 방법이 나오지 않기 때문에 모든 알고리즘을 빅오 표기법으로 분석하는 것이다.

 

알고리즘 더 풀어보기

곱하기 or 더하기

Q. 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오. 단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.

input = [0, 3, 5, 6, 1, 2, 4]


def find_max_plus_or_multiply(array):
    # 이 부분을 채워보세요!
    return 1


result = find_max_plus_or_multiply(input)
print(result)

# 내 코드
def find_max_plus_or_multiply(array):
    result = 0
    for i in range(0, len(array)):
        try: # outofrange 방지
            if array[i] == 0 or array[i+1] == 0 or array[i] == 1 or array[i+1] == 1:
                result += array[i] + array[i+1]
            else:
                result += array[i] * array[i+1]
        except:
            return result

# 튜터 코드
def find_max_plus_or_multiply(array):
    result = 0
    for i in range(0, len(array)):
        try:
            if array[i] == 0 or array[i+1] == 0 or array[i] == 1 or array[i+1] == 1:
                result += array[i] + array[i+1]
            else:
                result += array[i] * array[i+1]
        except:
            return result

튜터의 코드의 시간 복잡도는 어떻게 될까? O(N)일 것이다.

1차 반복문이 있으니 O(N)인 것이다.

 

반복되지 않는 문자

Q. 다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오.

input = "abadabac"


def find_not_repeating_first_character(string):
    # 이 부분을 채워보세요!
    return "_"


result = find_not_repeating_first_character(input)
print(result)

# 내 코드
def find_not_repeating_first_character(string):
    dict = {}
    for char in string:
        if dict.get(char):
            dict[char]=dict.get(char) + 1
        else:
            dict[char] = 1
    result = [i for i, x in dict.items() if x ==1]
    return result[0]

# 튜터 코드
def find_not_repeating_first_character(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord("a")
        alphabet_occurrence_array[arr_index] += 1
    not_repeating_character_array = []
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurence = alphabet_occurrence_array[index]
        if alphabet_occurence == 1:
            not_repeating_character_array.append(chr(index + ord("a")))

    for char in string:
        if char in not_repeating_character_array:
            return char

튜터의 코드는 for이 3개 이므로 3N이려나 N^3 이려나..........정확하게 모르겠어서 튜터분에게 여쭤본 상황이다.

(3N이 정답이다! 내 생각이 맞았다)