내일배움캠프

TIL 8일차 정리

Leo(상원) 2022. 11. 9. 18:01
반응형

오늘은 알고리즘을 공부하는 날입니다.

 

특히나 어려운 알고리즘과 자료구조.. 하지만 이해 해보려 노력하고, 정리를 해봤습니다.

 

코드정리

 

첫 번째는 최댓값을 찾아보는 문제입니다. 최댓값을 찾을 때에는 어떠한 알고리즘이 효율이 좋은지 알아봅시다.

 

1번 풀이

def find_max_num(array):
    for num in array:
        for compare_num in array:
            if num < compare_num:
                break
        else:
            return num


print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

첫 번째 풀이는 이중 for문을 돌면서 값을 찾는 방법입니다.

첫 for문에서 array [3, 5, 6, 1, 2, 4] 라는 값이 있다면 첫 인덱스 3을 가지고 두번 째 for문에서 나머지 5 6 1 2 4를 돌며 비교하는데 그 다음 숫자가 바로 더 큰 값인 숫자라 break문이 걸리며 첫 for문에서 다시 5라는 숫자를 가지고 두번 째 for문에서 다시 3 6 1 2 4를 돌며 비교를 반복해서 가장 큰 값을 return 하는 알고리즘 입니다.

 

 

2번 풀이

def find_max_num(array):
    max_num = array[0]
    for num in array:
        if num > max_num:
            max_num = num
    return max_num


print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

두 번째 풀이는 Array [3, 5, 6, 1, 2, 4] 에서 가장 첫 번째인 [0]번째 인덱스를 max_num이라는 변수에 초기값으로 할당하고, 반복문을 돌며 옆 숫자가 더 작으면 넘어가고 더 큰 숫자가 있다면 max_num에 재할당 해주는 알고리즘 입니다.

 

이 두개의 풀이 방법중 어떤것이 더 효율적이냐 하냐면 당연히 두 번째 풀이방법이 더 효율적입니다. 일단 알고리즘은 Big(O) 라는 시간복잡도로 비교를 합니다. for문을 한번 돌면 N(O) 라는 시간 복잡도가 나오고 두번 돌면 N^2(O)라는 시간 복잡도가 나옵니다. 그렇기 때문에 두 번째 방법이 더 빠르고 효율적이라고 할 수 있습니다. (시간 복잡도와 공간 복잡도에 관련된 것은 따로 포스팅을 하도록 하겠습니다.)

 

다음은 최빈값 찾기라는 문제입니다. 최빈값 찾기는 어떤 알고리즘을 활용하는지 알아봅시다.

이 알고리즘 또한 두 방법중 어떤 것이 더 효율이 좋을지 찾아봅시다.

 

첫 번째 방법입니다.

def find_max_occurred_alphabet(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

    max_occurrence = 0
    max_alphabet_index = 0
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index]
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index

첫 번째 방법은 alphabet_occurrence_array 라는 변수에 0이 26개 할당 되어있는 어레이를 저장 합니다. 그 후에 for문을 돌며 input값으로 들어온 string에 알파벳이 아닌 다른 값이 있는지 isalpha() 라는 함수를 통해 검사를 하고 알파벳이 맞다면 계속해서 로직을 이어 나갑니다. 그 다음은 아스키코드라는 것을 활용해 각각 자리에 맞는 인덱스에 값을 더해 줍니다.

아스키란 미국정보교환표준부호의 줄임말 입니다. 아스키코드 이 링크에 들어가서 자세한 정보를 확인 해보시길 바랍니다.

ord() 라는 함수는 해당하는 알파벳에 아스키코드값을 쉽게 가져 올 수 있는 라이브러리 입니다. ord('a')의 아스키 코드는 97이기때문에 예를 들면 ord('a') - ord('a') 는 0이라는 값이 나옵니다. 따라서 arr[0] 번째 인덱스는 a라는 알파벳의 자리라는 소립니다.

그렇기에 ord('b) - ord('a') 라는 값은 곧 98 - 97 = 1 이므로 arr[1] 번째 인덱스는 b라는 알파벳의 자리입니다. 때문에 반복문을 돌면서 ord(char) 라는 값에 계속해서 ord('a')를 빼주어서 해당 알파벳에 인덱스 자리를 찾습니다. 그리곤 어레이에 해당 인덱스에 +1 을 계속 해주면서 해당 알파벳 인덱스에 값을 정확히 가져옵니다.

이제 해당 자리에 인덱스값에 정확한 값이 들어갔으면 위에 최댓값 찾는 방법으로 어떤 알파벳 자리에 가장 높은 숫자가 있는지 찾으면 됩니다.

 

두 번째 방법

def find_max_occurred_alphabet(string):
    alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s",
                      "t", "u", "v", "x", "y", "z"]
    max_occurrence = 0
    max_alphabet = alphabet_array[0]

    for alphabet in alphabet_array:
        occurrence = 0
        for char in string:
            if char == alphabet:
                occurrence += 1

        if occurrence > max_occurrence:
            max_alphabet = alphabet
            max_occurrence = occurrence

    return max_alphabet


result = find_max_occurred_alphabet
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))

두 번째 방법은 alphabet_array에 a - z 까지 어레이안에 총 25개의 값을 직접 할당 합니다. 그리고 a - z 까지 값을 돌면서 input에서 받아온 string 값도 이중 for문으로 한번 더 돌립니다. 그리고 input에 받아온 string과 직접 할당한 알파벳값과 같다면 occurrence에 계속 +1 해줍니다. 그리고 if문을 통해서 계속 더해준 occurrence 값과 초반에 0이라는 초기값을 할당해준 max_occurence 값과 비교하면서 occurrence 값이 max_occurrence 값 보다 크다면 max_occurrence 값안에 할당 해주기를 반복하면서 가장 값이 높았던 값을 리턴하는 알고리즘 입니다.

 

이 또한 누가 더 효율적이냐 하냐면 for문을 한번만 돈 첫 번째 방법이 더 효율적이라고 할 수 있습니다.

 

이렇게 제가 오늘 알고리즘을 공부한 내용을 정리해 봤습니다. 그럼 20000..

 

 

반응형