자료구조 1주차_시간복잡도 & 공간복잡도

자료구조 1주차_시간복잡도 & 공간복잡도

 

editor : Pycharm

파이썬 : Python 3.8 

---

📌 시간복잡도란?

연산하는데 걸리는 시간

 

array의 길이만큼 도는 이중 for문 : array의 길이 × array의 길이 × 비교연산(if) 1번 = N^2

for문 2번과 if문 1번 = array길이 + array길이 + 비교연산(if) 1번 = 2N + 1

 

N의 값이 커질 수록 N^2과 2N+1의 격차는 커짐!!

---

📌 공간복잡도란?

입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘!

하지만 공간복잡도가 차이 난다고해서 성능이 크게 차이 나지 않음

---

결론, 공간복잡도보다는 시간복잡도에 더 비중을 두고 알고리즘을 짜야 한다!

 

점근표기법

알고리즘의 성능을 수학적으로 표기하는 방법

 

📌 빅오 표기법(Big-O notation)

O(N)

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

 

📌 빅 오메가(BIG-Ω)

Ω(1)

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

---

📌 배열 내의 특정 요소 찾기

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


def is_number_exist(number, array):
    for num in array: #array의 길이만큼 아래 연산 실행
        if number == num: #비교 연산
            return True


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

시간 복잡도 : N × 1 = N

운이 좋으면 한번만 연산해도 값을 찾을 수 있음!

운이 나쁘면, for문을 다 돌아야(N만큼의 연산을 해야) 값을 찾을 수 있음

 

따라서, 입력값에 따라서 성능이 달라질 수 있음

즉 최악의 경우에 시간이 얼마나 소요될지(빅오 표기법)에 대해 고민해 봐야 합니다.

 

거의 모든 알고리즘은 빅오 표기법으로 분석합니다.

---

+또는 × (곱하기 또는 더하기)

 

일반적인 수학 방식과 달리, 모든 연산은 왼쪽부터 순서대로 이루어진다.

 

📄 나의 풀이

input = [0, 3, 5, 6, 1, 2, 4] #length 7, 0123456


def find_max_plus_or_multiply(array):
    plus = array[0] + array[1]
    multiply = array[0] + array[1]

    max_find = max(plus,multiply)

    for i in range(len(array)):
        if i > 1:
            plus = max_find + array[i]
            multiply = max_find * array[i]
            max_find = max(plus, multiply)
    return max_find


result = find_max_plus_or_multiply(input)
print(result)

 

 

처음 배열의 두값을 더한값과 곱한값을 비교해 더 큰 값을 max_find 변수에 넣어주는 식으로 진행!

처음 두값을 계산해 줬으니 그 다음 값들은 if문을 이용해서 익덱스 2부터 6까지~

 

for문 × if문 = N × 1 = N 

 

 

📄 강의 풀이

input = [0, 3, 5, 6, 1, 2, 4] #length 7, 0123456


def find_max_plus_or_multiply(array):
    multiply_sum = 0
    for number in array:
        if number <=1 or multiply_sum <=1:
            multiply_sum += number
        else:
            multiply_sum *= number
    return multiply_sum


result = find_max_plus_or_multiply(input)
print(result)

 

모든 경우의 수를 고려해 배열 인덱스가 0이거나 1이면 더해주고 그렇지 않으면, 곱한 수가 무조건 크므로 분기문을 이용해 구하셨다.

또한 초반에 0이 연속해서 나올 수 있으므로 multiply_sum이 1이하일 때도 더하기를 해줘야 더 크다!

테스트케이스를 여러번 생각해 문제를 풀면(일종의 수학적 공식? 적용하면) 코드 길이도 줄어들고 이해하기 편한 것 같다.

 

quiz.  함수의 시간 복잡도는?

for문 × if문 = N × 1 = N 

따라서 O(N)

---

반복되지 않는 문자

 

📄 나의 풀이

input = "aabbcddd" # 8 01234567
# aabb 0123
# cddd 4567

def find_not_repeating_character(string):
    n = int(len(string) / 2)
    value = ''

    i = 0
    while True:
        if string[i] != string[n + i]:
            value += string[i]
            break
        else:
            value += '_'
        i += 1
    return value


result = find_not_repeating_character(input)
print(result)

반복되는 문장이라면 절반씩 똑 잘라서 비교하면 편하겠다는 생각이 들어서 위 처럼 구했다.

만약 절반씩 비교해서 같지 않으면 반환. 그 값이 제일 처음으로 반복되지 않는 문자가 나오는 순간일 것이다.

 

하지만, 이 방법은 강의 두번째 예제 

print("정답 = c 현재 풀이 값 =", result("aabbcddd"))

여기서 a로 출력되면서 답이 나오지 않는다.

아무래도 문자 하나하나 값을 살펴봐야 하는 문제인 듯 하다.

 

📄 강의 풀이

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_occurrence = alphabet_occurrence_array[index]

        if alphabet_occurrence == 1:
            not_repeating_character_array.append(chr(index + ord("a")))

	# 기존 문자열의 순서를 고려해주지 않는다.
	# 그래서 기존 문자열의 순서를 고려하기 위해 반복문을 한번 더 돌려줘야 함
    for char in string:
        if char in not_repeating_character_array:
            return char

    return "_"


result = find_not_repeating_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))

반복되지 않는 알파벳을 빈 배열에 집어 넣어준다. 즉, 한번 출현한 문자를 not_repeating_character_array에 넣어준다.

 

(문자, 그 문자 출현횟수) 이 두가지 객체를 담는 class를 생성해 이 문제를 풀면 어떨까? 싶다.

문자 출현 순서에 맞게 출력하려니 반복문을 많이 써야하는 느낌...

다시 풀어봐야 겠다!!!

---

1주차 숙제

 

소수 나열하기

정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오.

 

📄 나의 풀이

input = 20

def find_prime_list_under_number(number):
    nums = []
    for i in range(number):
        nums.append(i+1)

    # 1은 소수가 될 수 없으므로 제거
    nums.remove(1)

    for a in range(1000000):
        if a > 1:
            for b in nums:
                if a*b in nums:
                    nums.remove(a*b)


    return nums


result = find_prime_list_under_number(input)
print(result)

값을 삭제하기 편하게 리스트 타입 선택!

최종 반환하는 리스트에 1을 삭제한다. 원래 2는 아니면서 2의 배수인 것들을 모두 삭제하는 식으로 하려니 리스트에 들어있지 않아 삭제 되지 않는다는 오류가 났다. 그러다가 생각난게 2는 아니면서란 조건 없이 그냥 2의 배수(곱해주는 값을 2부터 시작하면 된다.) 이면 삭제하는 것! 그러면 2는 삭제되지 않고 4,6,8,10,12... 만 삭제된다.

마찬가지로 3도 삭제되지 않고 6,9,12,15 .... 값들만 삭제된다.

 

그래서 삭제하기 전에 리스트에 그 값이 있는지 확인하는 if문을 사용해야 했다.

만약, 리스트안에 그 값이 있다면 삭제!

a의 범위는 임의로 크게 뒀다.

 

---

문자열 뒤집기

0과 1로만 이루어진 문자열이 주어졌을때, 문자에서 연속된 하나 이상의 숫자를 찾고 뒤집는 것이다.

모두 같은 숫자로 만드는 최소 횟수를 반환하시오.

 

📄 나의 풀이

input = "0001100"

# 값이 바뀔 때 count하고 그 값에서 1 뺀게 최소 횟수임

def find_count_to_turn_out_to_all_zero_or_all_one(string):
    n = len(string)-1
    cnt = 0

    for i in range(n):
        if string[i] != string[i+1]:
            cnt += 1

    return cnt - 1


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

0으로 시작하든 1로 시작하든, 무조건 값이 달라질 때 카운트 해주고 카운트 값에서 1을 빼주면 최소값이 나오게 된다.

 

---

숙제 둘다 답안코드를 보면서 복습해야 될 것 같다.

소수 문제은 임의의 값(1000000)을 줘버려서 입력이 1000,000을 초과하면 원하는 소수값이 안나오기 때문에 문제가 있는 코드이다 ㅠ

 

모두 0이나 1로 뒤집는 문제 역시 나의 풀이가 예외인 예제가 있을 수도 있다.

그래서 답안 코드를 분석해봐 비교해 봐야 한다.