알고보면 알기쉬운 알고리즘 - 1주차
1주차 공부 목표
- 개발자들이 알고리즘 공부가 필요한 이유
- 알고리즘 학습을 위한 기본 코드 구현력 높이기
- 시간, 공간 복잡도 학습
[목차]
1. 알고리즘이란?
2. 알고리즘 맛보기 (최댓값, 최빈값 찾기)
3. 시간복잡도
4. 공간복잡도
5. 점근 표기법
6. 알고리즘 문제 풀어보기
7. 1주차 숙제
01. 알고리즘이란?
알고리즘(algorithm)은 주어진 문제를 논리적으로 해결하기 위해 필요한 절차, 방법, 명령어들을 모아놓은 것입니다. 넓게는 사람 손으로 해결하는 것, 컴퓨터로 해결하는 것, 수학적인 것, 비수학적인 것을 모두 포함한답니다.
[네이버 지식백과] 알고리즘 [algorithm] (천재학습백과 초등 소프트웨어 용어사전)
즉, 어떤 문제가 있을 때 그것을 해결하기 위한 여러 동작을 모아놓은 것이다.
그렇다면 알고리즘은 왜 필요할까?
먼저 개발자는 좋은 프로그램을 구현할 줄 알아야 한다.
즉 좋은 프로그램을 위해서 작은 공간을 이용해 빠른 속도로 수행이 되는 프로그램을 구현을 해야한다.
이때 특정 자료구조나 접근방법을 사용해야 하기위해서는 알고리즘을 공부해야 한다.
02. 알고리즘 맛보기
최댓값 찾기
문제1)
다음과 같이 숫자로 이루어진 배열이 있을 때, 이 배열 내에서 가장 큰 수를 반환하시오.
[3, 5, 6, 1, 2, 4]
<첫번째 방법>
input = [3, 5, 6, 1, 2, 4]
def find_max_num(array):
for num in array:
for compare_num in array:
if num < compare_num:
break
else:
return num
result = find_max_num(input)
print(result)<두번째 방법>
input = [3, 5, 6, 1, 2, 4]
def find_max_num(array):
max_num = array[0]
for num in array:
if num > max_num:
max_num = num
return max_num
result = find_max_num(input)
print(result)
최빈값 찾기
문제2)
다음과 같은 문자열을 입력받았을 때, 어떤 알파벳이 가장 많이 포함되어 있는지 반환하시오
"hello my name is sparta"
첫번째 방법
def find_alphabet_occurrence_array(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
return alphabet_occurrence_array
print(find_alphabet_occurrence_array("hello my name is sparta"))실행값 : [3, 0, 0, 0, 2, 0, 0, 1, 1, 0, 0, 2, 2, 1, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 1, 0]
두번째 방법
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", "p", "q", "r", "s"
"t", "u", "v", "w", "x", "y", "z"]
max_occurence = 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_occurence:
max_occurence = occurrence
max_alphabet = alphabet
return max_alphabet
result = find_max_occurred_alphabet(input)
print(result)실행값 : a
여기까지 빈도수의 인데스를 알아냈으므로,
이것을 아스키 코드 번호를 실제 문자로 변환하여 나타내면
* chr() 함수를 사용
input = "hello my name is sparta"
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)):
# index 0 -> alphabet_occurence 3
alphabet_occurrence = alphabet_occurrence_array[index]
if alphabet_occurrence > max_occurrence:
max_alphabet_index = index
max_occurrence = alphabet_occurrence
print(max_alphabet_index)
return chr(max_alphabet_index + ord("a"))
result = find_max_occurred_alphabet(input)
print(result)실행값 : 0
a
03. 시간 복잡도
먼저 시간복잡도란?
입력값과 문제를 해결하는데 걸리는 시간과의 상관관계를 말함.
입력값이 2배로 늘었났을 때 문제를 해결하는데 걸리는 시간은 몇 배로 늘어나는지를 보는 것
우리는 시간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이
좋은 알고리즘임.
예시를 알아볼까요?
for num in array: # array 의 길이만큼 아래 연산이 실행
for compare_num in array: # array 의 길이만큼 아래 연산이 실행
if num < compare_num: # 비교 연산 1번 실행
break
else:
return num1. array의 길이 X array의 길이 X 비교 연산 1번
여기서 array(입력값)의 길이는 보통 N이라고 표현함.
즉 표현식으로 다시 정리하면
N x N = N^2
즉 N^2 만큼의 시간이 걸렸구나라는 것 을 알 수 있음
두번째 예시를 보면
def find_max_num(array):
max_num = array[0] # 연산 1번 실행
for num in array: # array 의 길이만큼 아래 연산이 실행
if num > max_num: # 비교 연산 1번 실행
max_num = num # 대입 연산 1번 실행
return max_num
result = find_max_num(input)1. max_num 대입 연산 1번
2. array의 길이 X( 비교연산 1번 + 대입 연산 1번)
다시 수식으로 나타내면
1+2 x N
즉 2N+1 만큼의 시간이 걸렸음을 알 수 있습니다.
결국 두 번째 방식이 더 효율적임을 알 수 있었습니다.
04. 공간 복잡도
공간복잡도에 대해서 알아보면
입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 의미함.
즉 입력값이 2배로 늘어났을 때 문제를 해결하는데 걸리는 공간은 몇 배로 늘어나는지를 보는 것.
우리는 공간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 공간이 덜 늘어나는 알고리즘이 좋은 알고리즘이다.
아까 우리가 구했던 최빈값 코딩에서 살펴보면
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"]
# -> 26 개의 공간을 사용합니다
max_occurrence = 0 # 1개의 공간을 사용합니다
max_alphabet = alphabet_array[0] # 1개의 공간을 사용합니다.
for alphabet in alphabet_array:
occurrence = 0 # 1개의 공간을 사용합니다1. alpahbet_array의 길이 = 26
2. max_occurrence, max_alphabet, ocurrence 변수 = 3
총 29 만큼의 공간이 필요함을 알 수 있습니다.
또 다른 예시로 알파벳 빈도수를 저장한 다음, 빈도 수 중 가장 많은 알파벳의 인덱스 값을 아스키 코드로 변환하여 문자로 나타내었던 코드를 살펴보면
alphabet_occurrence_list = [0] * 26 # -> 26 개의 공간을 사용합니다
for char in string:
if not char.isalpha():
continue
arr_index = ord(char) - ord('a') # 1개의 공간을 사용합니다
alphabet_occurrence_list[arr_index] += 1
max_occurrence = 0 # 1개의 공간을 사용합니다
max_alphabet_index = 0 # 1개의 공간을 사용합니다
for index in range(26):
alphabet_occurrence = alphabet_occurrence_list[index] # 1개의 공간을 사용합니다
if alphabet_occurrence > max_occurrence:
max_occurrence = alphabet_occurrence
max_alphabet_index = index1. alphabet_array 길이 = 26
2. arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
즉 30의 공간이 필요합니다.
그렇다면 공간을 적게 쓴다고 효율적일까?
또 그렇지는 않다고 합니다.
알고리즘의 성능은 공간에 의해서 결정되는게 아닌 시간 복잡도를 더 신경을 써야 합니다.
05. 점근 표기법
점근 표기법이란?
알고리즘의 성능을 수학적으로 표기하는 방법입니다. 알고리즘의 “효율성”을 평가하는 방법입니다. 점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 저희가 지금까지 이 함수는 N 정도의 시간과 공간이 걸리겠구나 하면서 분석했던 게 점근 표기법의 일종이라고 말할 수 있습니다.
종류
빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법이 있습니다.
빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지,
빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기합니다.
예를 들어 빅오 표기법으로 표시하면 O(N),
빅 오메가 표기법으로 표시하면 Ω(1) 의 시간복잡도를 가진 알고리즘이다! 라고 표현할 수 있습니다.
한 번 문제를 풀면서 알아보도록 하겠습니다!
문제1)
다음과 같은 숫자로 이루어진 배열이 있을 때, 이 배열 내에 특정 숫자가 존재한다면 True,
존재하지 않다면 False 를 반환하시오.
[3, 5, 6, 1, 2, 4]
input = [4, 5, 6, 1, 2, 3]
def is_number_exist(number, array):
for element in array: # array 의 길이만큼 아래 연산이 실행
if number == element: # 비교연산이 1번 실행
return True # N * 1 = N만큼
return False
result = is_number_exist(3, input)
print(result)실행값 : True
이 함수의 시간복잡도를 구해보면
1. array의 길이만큼 연산
2. 비교연산 1번 실행
N x 1 = N
여기서 주의할 점!
모든 경우에 N 만큼 시간이 걸릴까??
만약
input = [3, 5, 6, 1, 2, 4] 이라는 입력값에 대해서 3을 찾으면,
첫 번째 원소를 비교하는 순간!! 바로 결괏값을 반환하게 됩니다.
즉, 운이 좋으면 1번의 연산 이후에 답을 찾을 수 있다는 의미입니다.
그렇지만,
input = [4, 5, 6, 1, 2, 3] 이라는 입력값에 대해서 3을 찾으면 어떻게 될까요?
마지막 원소 끝까지 찾다가 겨우 마지막에 3을 찾아 결괏값을 반환하게 됩니다.
즉, 운이 좋지 않으면 input의 길이(N) 만큼 연산 이후에 답을 찾을 수 있습니다.
즉, 이처럼, 알고리즘의 성능은 항상 동일한 게 아니라 입력값에 따라서 달라질 수 있습니다.
어떤 값을 가지고 있는지, 어떤 패턴을 이루는 데이터인지에 따라서 뭐가 좋은 알고리즘인지 달라질 수 있다는 의미입니다.
| 입력값 | 소요되는 연산량 |
| 좋을 때 | 1 |
| 안 좋을 때 | N |
즉 이 같은 경우에
빅오 표기법으로 표시하면 O(N)
빅오메가 표기법 Ω(1) 의 시간복잡도를 가진 알고리즘이다.
여기서 의문점 >
지금까지 우리는 왜 항상 모든 반복문이 돌 것이라고 생각하고 계산했을까요?
항상 최악의 경우, 빅오 표기법으로만 구한 거 아닌가요?
알고리즘에서는 거의 모든 알고리즘을 빅오 표기법으로 분석합니다.
왜냐면 대부분의 입력값이 최선의 경우일 가능성은 굉장히 적을 뿐더러,
우리는 최악의 경우를 대비해야 하기 때문입니다.
우리가 기억해야 할 것 3가지
1. 입력값에 비례해서 얼마나 늘어날지 파악해보자. 1 ? N ? N^2 ?
2. 공간복잡도 보다는 시간 복잡도를 더 줄이기 위해 고민하자.
3. 최악의 경우에 시간이 얼마나 소요될지(빅오 표기법)에 대해 고민하자
06. 알고리즘 문제 풀어보기
문제1)
Q. 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오. 단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.
[0, 3, 5, 6, 1, 2, 4]
input = [0, 3, 5, 6, 1, 2, 4]
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)실행값 : 728
시간복잡도 :
O(N) 만큼 걸립니다. 함수 구문 하나하나를 보지 않더라도, 1차 반복문이 나왔고, array 의 길이 만큼 반복한다? 그러면 O(N) 이겠구나! 생각해주시면 됩니다.
문제2)
다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오.
"abadabac"
# 반복되지 않는 문자는 d, c 가 있지만 "첫번째" 문자니까 d를 반환해주면 됩니다!
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
return "_"
result = find_not_repeating_character(input)
print(result)실행값: d
시간복잡도 :
바로 O(N) 만큼 걸립니다. 함수 구문 하나하나를 보지 않더라도, 1차 반복문이 나왔고, array 의 길이 만큼 반복한다? 그러면 O(N) 이겠구나! 생각해주시면 됩니다.
07. 1주차 과제
문제1) 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오.
소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.
[2, 3, 5, 7, 11, 13, 17, 19]
# 20이 입력된다면, 아래와 같이 반환해야 합니다!
input = 20
def find_prime_list_under_number(number):
prime_list = []
for n in range(2, number + 1):
for i in prime_list:
if n % i == 0 and i * i <= n:
break
else:
prime_list.append(n)
return prime_list
result = find_prime_list_under_number(input)
print(result)실행값 : [2, 3, 5, 7, 11, 13, 17, 19]
★ 문제2) ★(다음에 다시 풀어보기)
1. 입력으로 소문자의 알파벳 순으로 정렬된 문자열이 입력됩니다.
2. 각 알파벳은 중복이 가능합니다.
3. 중간에 없는 알파벳이 있을 수도 있습니다. 입,출력 예시와 같이 입력 문자열에 나타나는 각 알파벳의 종류,갯수를 요약하여 나타내시오.
# 문제의 번호별 조건에 대한 입력 예시와 출력
Ex 1)
abc # a1/b1/c1
Ex 2-1)
aaabbbc # a3/b3/c1
Ex 2-2)
abbbc # a1/b3/c1
Ex 3-1)
ahhhhz # a1/h4/z1
Ex 3-2)
acccdeee # a1/c3/d1/e3