알고리즘과 친해지기 (1) - 최대값 찾기
- Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 이 배열 내에서 가장 큰 수를 반환하시오.
input = [3, 5, 6, 1, 2, 4]
def find_max_num(array):
# array의 인덱스의 값을 max_num에 할당
max_num = array[0]
# num에 array만큼 for문 실행
for num in array:
# 할당된 num의 값이 max_num이 된다면 max_num에 num을 할당
if num > max_num:
max_num = num
return max_num
result = find_max_num(input)
print(result)
알고리즘과 친해지기 (2) - 최빈값 찾기
- Q. 다음과 같은 문자열을 입력받았을 때, 어떤 알파벳이 가장 많이 포함되어 있는지 반환하시오
- TIP
# str.isalpha() 를 이용하면 해당 문자열이 알파벳인지 확인할 수 있습니다.
print("a".isalpha()) # True
print("1".isalpha()) # False
s = "abcdefg"
print(s[0].isalpha()) # True- Answer
def find_alphabet_occurrence_array(string):
# 알파벳 숫자의 개수
alphabet_occurrence_array = [0] * 26
# char에 string의 값을 할당해서 for문 실행
for char in string:
# char가 영어라면 다음 코드를 계속 실행한다
if not char.isalpha():
continue
# arr_index에 아니스코드로 변환된 char를 아니스코드로 변환된 'a'를 뺀다
arr_index = ord(char) - ord('a')
# char에서 a만큼 뺀 값을 알파벳 오큐리언스 어레이에 더한다
alphabet_occurrence_array[arr_index] += 1
return alphabet_occurrence_array
print(find_alphabet_occurrence_array("hello my name is sparta"))
시간 복잡도
시간복잡도의 가장 간단한 정의는 알고리즘의 성능을 설명하는 것이다.
다른의미로는 알고리즘을 수행하기 위해 프로세스가 수행해야하는 연산을 수치화 한것이다.
왜 실행시간이 아닌 연산수치로 판별할까? 위에도 설명했지만 명령어의 실행시간은 컴퓨터의 하드웨어 또는 프로그래밍 언어에 따라 편차가 크게 달라지기 때문에 명령어의 실행 횟수만을 고려하는 것이다.
시간복잡도에서 중요하게 보는것은 가장큰 영향을 미치는 n의 단위이다.
1 O(1) --> 상수
2n + 20 O(n) --> n이 가장 큰영향을 미친다.
3n^2 O(n^2) --> n^2이 가장 큰영향을 미친다.시간복잡도의 문제해결 단계를 나열 하면 아래와같다.
O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.
- O(1) : 상수
아래 예제 처럼 입력에 관계없이 복잡도는 동일하게 유지된다.
def hello_world():
print("hello, world!")- O(N) : 선형
입력이 증가하면 처리 시간또는 메모리 사용이 선형적으로 증가한다.
def print_each(li):
for item in li:
print(item)- O(N^2) : Square
반복문이 두번 있는 케이스
def print_each_n_times(li):
for n in li:
for m in li:
print(n,m)- O(log n) O(n log n)
주로 입력 크기에 따라 처리 시간이 증가하는 정렬알고리즘에서 많이 사용된다.
다음은 이진검색의 예이다.
def binary_search(li, item, first=0, last=None):
if not last:
last = len(li)
midpoint = (last - first) / 2 + first
if li[midpoint] == item:
return midpoint
elif li[midpoint] > item:
return binary_search(li, item, first, midpoint)
else:
return binary_search(li, item, midpoint, last)시간복잡도를 구하는 요령
각 문제의 시간복잡도 유형을 빨리 파악할 수 있도록 아래 예를 통해 빠르게 알아 볼수 있다.
- 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
- 컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
- 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
- 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
- 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n * m) -> O (n²)
- 컬렉션 정렬을 사용하는 경우 : O(n*log(n))
점근 표기법
시간복잡도를 근사치로 표현한 것이다.
아래에서 빅 오를 예시로 들어 어떤 식으로 시간복잡도를 계산하는지에 대해 알아볼건데,
컴퓨터의 성능과는 관계없이 두 알고리즘을 비교해서 어떤 알고리즘이 더 나은 알고리즘인지,
더 빠른 알고리즘인지를 가늠할 때 사용한다.
- 점근 표기법의 종류
- 빅 오 (Big O : Ο) : 알고리즘이 최악으로 실행될 경우(아무리 늦더라도 이 정도의 성능을 보장한다는 것을 의미)의 성능을 표현할 때 사용. 알고리즘의 성능을 표현하는데 가장 많이 사용. = 최악의 경우의 수에 어떤 성능을 내는지 궁금해하기 때문.
- 빅 오메가 (Big Omega : Ω) : 알고리즘이 가장 최선으로 실행될 경우의 성능을 표시.
빅오 표기법으로 표시하면 O(N)
빅 오메가 표기법으로 표시하면 Ω(1)
배열에서 특정 요소 찾기
- Q. 다음과 같은 숫자로 이루어진 배열이 있을 때, 이 배열 내에 특정 숫자가 존재한다면 True, 존재하지 않다면 False 를 반환하시오.
input = [3, 5, 6, 1, 2, 4]
def is_number_exist(number, array):
# 엘리먼트에 어레이를 할당하고 for문을 실행한다.
for element in array:
# 만약에 입력된 넘버가 엘리먼트와 같다면 True를 반환한다.
if number == element:
return True
# 그게 아니라면 False를 반환한다.
return False
result = is_number_exist(3, input)
print(result)알고리즘 더 풀어보기 (1) - 곱하기 or 더하기
- Q. 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오.
- 단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.
input = [0, 3, 5, 6, 1, 2, 4]
def find_max_plus_or_multiply(array):
# multiply_sum에 0을 할당한다.
multiply_sum = 0
# number에 array를 할당하고 그만큼 for문을 실행한다
for number in array:
# 만약에 number가 1이하거나 multiply_sum이 1이하라면
if number <= 1 or multiply_sum <= 1:
# multiply_sum 에 number를 더한다 (1 이하의 숫자는 더하는게 곱하는 것보다 숫자가 더 커지기 때문에)
multiply_sum += number
else:
# 그게 아니라면 multiply_sum에 number를 곱한다
multiply_sum *= number
return multiply_sum
result = find_max_plus_or_multiply(input)
print(result)
알고리즘 더 풀어보기 (2) - 반복되지 않는 문자
- Q. 다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오.
def find_not_repeating_first_character(string):
# alphabet occurr array에 알파벳 숫자 만큼 배열 할당
alphabet_occurrence_array = [0] * 26
# char에 string만큼 for문 실행
for char in string:
# 만약 char가 알파벳이라면 다음 코드들을 계속 실행한다
if not char.isalpha():
continue
# arr_index에 아스키코드로 변환된 char에서 a만큼의 숫자를 뺀다.
arr_index = ord(char) - ord("a")
# alphabet occurr array[arr_index]에 1을 더한다.
alphabet_occurrence_array[arr_index] += 1
# not repeating char array 에 빈 배열 할당
not_repeating_character_array = []
# alphabet occurr array의 길이만큼 index 에 할당하고 for문 실행한다
for index in range(len(alphabet_occurrence_array)):
# alphabet occurr 에 alphabet occurr araay[index]를 할당한다
alphabet_occurrence = alphabet_occurrence_array[index]
# alphabet occurr가 1이라면 index-97(a의 유니스코드)를 하고 char로 변환한 후 not repeating char array에 추가한다
if alphabet_occurrence == 1:
not_repeating_character_array.append(chr(index + ord("a")))
# string 를 char에 할당시키고 for문을 실행한다
for char in string:
# char가 not repeating char array에 있다면 char를 리턴한다
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"))
1주차 숙제
소수 나열하기
- Q. 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오.
- 소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.
input = 20
def find_prime_list_under_number(number):
list = []
# 2부터 number + 1까지 하나씩 num에 할당해서 for문 실행한다
for num in range(2, number + 1):
# list에 있는 변수 하나하나 i 에 할당해서 for문 실행한다
for i in list:
# num 을 i 로 나눈 나머지 값이 0이되면 브레이크
# ex) 3 % 2 = 1 로 통과 4 % 2 = 0 으로 브레이크
if num % i == 0:
break
else:
# 그게 아니라면 list에 num을 추가한다
list.append(num)
return list
result = find_prime_list_under_number(input)
print(result)
문자열 뒤집기
- Q. 0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자를 모두 0, 혹은 모두 1로 같게 만들어야 한다. 할 수 있는 행동은 연속된 하나의 숫자를 잡고 모두 뒤집는 것 이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.
input = "011110"
def find_count_to_turn_out_to_all_zero_or_all_one(string):
zero = 0
one = 0
# string[0]의 숫자가 0이면 one 을 더하고 1이면 zero 를 더한다
if string[0] == '0':
one += 1
elif string[0] == '1':
zero += 1
# string[i]가 그 뒷 숫자랑 같지 않고, 그 뒷 숫자가 0이라면 one을 더하고 1이라면 zero를 더한다.
for i in range(len(string) - 1):
if string[i] != string[i + 1]:
if string[i + 1] == '0':
one += 1
if string[i + 1] == '1':
zero += 1
# one 과 zero 중 작은 값을 반환
# string[0] 이 0이었고 그 뒤로 쭉 1이 반복되기 때문에 zero 는 1이다
return min(one, zero)
result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)