[스파르타코딩클럽] 알고보면 알기쉬운 알고리즘 - 1주차

• 최댓값 찾기 문제 1

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


def find_max_num(array):
    # 배열 인덱스 만큼 반복
    for num in array:
        for compare_num in array:
            # 비교숫자보다 작으면 break
            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]))

• 최댓값 찾기 문제 2

def find_max_num(array):
    max_num = array[0]
    for num in array:
        if max_num < 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]))

 

• 최고 빈도값 찾기(배열 갯수)

def find_alphabet_occurrence_array(string):
	# 알파벳 a~z 배열 인덱스 0~25
    alphabet_occurrence_array = [0] * 26

    for char in string:
    	# 알파벳 아니면 아래 코드 패스
        if not char.isalpha():
            continue
        # 영어 알파벳 인덱스 부여하기위한 ord() 함수, ord('a')는 97, 예를들어 ord('b') 는 98로 (98-97) 인덱스 번호를 가진다.
        arr_index = ord(char) - ord('a')
        alphabet_occurrence_array[arr_index] += 1

    return alphabet_occurrence_array


result = find_alphabet_occurrence_array

print(find_alphabet_occurrence_array("hello my name is sparta"))

아스키코드

• 최고 빈도수 알파벳 출력하기(1)

input = "hello my name is sparta"


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(input)
print(result)

• 최고 빈도수 알파벳 출력하기(1)

input = "hello my name is sparta"


def find_max_occurred_alphabet(string):
    # 알파벳 26개 배열 생성
    alphabet_occurrence_array = [0] * 26


    # 배열의 index 만큼 반복
    for char in string:
        # 해당 문자가 알파벳이 아닌가? 아니면 continue
        if not char.isalpha():
            continue #(아래 코드를 건너뛴다)
        # 알파벳 26개 인덱스
        arr_index = ord(char) - ord('a')
        # 해당 인덱스 알파벳 1 증가
        alphabet_occurrence_array[arr_index] += 1

    # 최대 빈도수 알파벳
    max_occurrence = 0
    # 최대 빈도수 알파벳 인덱스
    max_alphabet_index = 0
    # range(len(alphabet_occurrence_array) == range(26)
    for index in range(len(alphabet_occurrence_array)):
        # index 0 -> alphabet_occurrence 3
        # 알파벳 별 빈도수
        alphabet_occurrence = alphabet_occurrence_array[index]

        # 알파벳 빈도수가 가장 큰 녀석이라고 판단되었기 때문에
        if alphabet_occurrence > max_occurrence:
            # 알파벳 인덱스 업데이트
            max_alphabet_index = index
            # 알파벳 빈도수 업데이트
            max_occurrence = alphabet_occurrence

    # max_alphabet_index + ord('a') == 0, 최대빈도수 알파벳은 0번째 인덱스, 즉 말파벳 a
    # 인덱스 0 dmf dnlgo ord('a') 즉 아스키코드 97 을 빼줬기 때문에 다시 더해줘서 아스키 코드 복귀
    # 결국 0 + 97 = 97 아스키코드인 a 출력
    result = chr(max_alphabet_index + ord('a'))

    return result


result = find_max_occurred_alphabet(input)
print(result)

 

• 시간 복잡도 : 입력값과 문제를 해결하는데 걸리는 시간과의 상관관계

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

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

    return False # N * 1 = N 만큼


result = is_number_exist(3, input)

print(result)

for 문으로 array 를 한바퀴 돌때 내부에 비교연산자가 1번 있다면 N x 1

 

for 문으로 array 가 한바퀴 돌 때 그 내부에 이중 포문으로 array 가 한번더 돌아가는 내부에 비교연산자가 2번 있다면

N x N x 2

 

대입 연산 1번 for 문 array 반복문 아래에 대입연산 1, 비교연산 1 일 경우 1 + N x 2 시간 복잡도가 되는것이다.

 

이때 N은 입력값으로, 이 입렵값이 커질수록 N x N 경우 길이가 엄청나게 길어질 수 있는 것이다. 

 

그래서 상수는 제거하고 시간 복잡도를 명시한다.

 

• 공간 복잡도 : 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말한다. (상수)

상대적으로 시간 복잡도보다 입력값에대한  중요도가 낮기 때문에 공간 복잡도를 희생해서라도 시간 복잡도를 좋게 만들어야 한다.

 

• 점근 표기법 : 알고리즘의 성능을 수학적으로 표기하는 방법이다.

표기법으로는 빅오(Big-O)표기법, 빅오메가(Big-Ω)표기법이 있다.

 

빅오표기법은 최악의 상황을 표기하고, 빅오메가표기법은 최선의 상황을 표기하는데, 

 

개발할때는 빅오표기법 즉 최악의 상황을 대비하고 개발해야한다.

 

 기억할 것!
 1. 입력값에 비례해서 얼마나 늘어날지 파악해보자 1 ? N ? N^2 ?
 2. 공간복잡도 보다는 시간 복잡도를 더 줄이기 위해 고민하자.
 3. 최악의 경우에 시간이 얼마나 소요될지(빅오 표기법)에 대해 고민하자.

 

• 곱하기 or 더하기

- 양의 정수로 이루어진 배열이 있을때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자사이에 X 혹은 + 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램 작성

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


def find_max_plus_or_multiply(array):
    max_sum = 0
    for num in array:
    	# 제일 왼쪽에있는 숫자가 1 보다작을때 즉 1이거나 0 일때 곱하게되면 숫자가 최대로 커지지 못한다.
        if num <= 1 or max_sum <= 1:
            max_sum += num
        # 숫자가 1보다 클 경우는 곱하는경우가 최대로 커질 수 있다.
        else:
            max_sum *= num

    return max_sum


result = find_max_plus_or_multiply(input)
print(result)


# 이 코드의 시간복잡도는 N 이다

• 영어로 되어있는 문자열이 있을 때, 문자열에서 반복되지 않는 첫 번째 문자를 반환

(어렵다 공부좀 더하자)

input = "abadabac"


def find_not_repeating_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

    print(not_repeating_character_array)
    return alphabet_occurrence_array

    return "_"


result = find_not_repeating_character(input)
print(result)

 

• 소수 나열하기

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

input = 20

# 주어진 자연수 N이 소수이기 위한 필요충분 조건은 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다. 
# 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문입니다.

def find_prime_list_under_number(number):
    prime_list = []
    # 2부터 number + 1 정수까지, 즉 number 가 20 일 경우 2 부터 20 사이의 연속적인 숫자들을 리턴 
    for num in range(2, number + 1):
        for i in prime_list:
        	# 나머지가 0 이고 제곱근 보다 크지 않은 수
            if num % i == 0 and i * i <= num:
                break
        else:
            prime_list.append(num)

    return prime_list


result = find_prime_list_under_number(input)
print(result)

• 문자열 뒤집기 (어렵...)

- 0과 1로만 이루어진 문자열, 문자 모두 0 혹은 1로 같게 만드는 최소 횟수 반환

input = "011110"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
    cnt_to_all_zero = 0
    cnt_to_all_one = 0

    if string[0] == '0':
        cnt_to_all_one += 1
    elif string[0] == '1':
        cnt_to_all_zero += 1

    for i in range(len(string) - 1):
        if string[i] != string[i + 1]:
            if string[i + 1] == '0':
                cnt_to_all_one += 1
            if string[i + 1] == '1':
                cnt_to_all_zero += 1

    return min(cnt_to_all_one, cnt_to_all_zero)


result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

1) 뒤집어 질 경우

2) 첫 번째 원소가 0 인지 1 인지에 대해서 계산하면, 모두 0으로 만드는 횟수와 모두 1로 만드는 횟수를 만들 수 있음

그리고 0 으로 만드는 횟수가 모두 1로 만드는 횟수 둘 중 최솟값을 반환해주면 된다.

==========================================================================================

 

출처 : [스파르타코딩클럽] 알고보면 알기쉬운 알고리즘 - 1주차

 

============================================================================================