알고리즘에 대해서 공부해봐야지만 생각하고 딱히 어떻게 공부해야 할지 고민하면서 공부를 하지 않았었다.
하지만, 이번에 스파르타 코딩클럽에 알고리즘 강의가 있는 것을 발견하고, 이번 기회에 알고리즘을 확실하게 공부해 봐야겠다는 생각이 들어 수강하게 되었다!
학습목표
- 개발자들에게 알고리즘 공부가 필요한 이유를 이해한다.
- 알고리즘을 학습하기 위한 기본 코드 구현력을 높인다.
- 시간 복잡도, 공간 복잡도에 대해 배운다.
알고리즘이란?
어떤 문제의 해결을 위하여, 입력된 자료르 토대로 하여 원하는 출력을 유도하여 내는 규칙의 집합
-> 어떤 문제가 있을때, 그것을 해결하기 위한 여러 동작들의 모임이다.
좋은 개발자가 되려면 알고리즘을 공부해야 한다.
좋은 프로그램이란? 작은 공간을 이요해 빠른 속도로 수행되는 프로그램이다. 이런 프로그램을 만들기 위해서는 특정 자료구조나 접근방법을 사용해야 한다.
또한, 좋은 회사에 취업하고 싶다면 알고리즘을 공부해야 한다!
컴퓨터 언어를 배우면서 가장 기본적인 알고리즘으로 최대값, 최빈값 찾기를 해보았다.
기본적인 언어인 C나 JAVA 같은 컴파일러 언어들만 알고 있던 나에게 인터프리터 언어인 python은 조금 생소했다. 그래서 첫번째 연습 문제였던 최대값을 구하는 코드에서부터 막히기 시작했다. 프로젝트를 하면서 파이썬을 살짝 다룬적이 있어서 최대값 문제를 금방 풀 수 있을 줄 알았다.
그런데,,, for문 안에서 tab 키를 누르지 않아 코드가 이상하게 작동되었다. 최대값을 찾아야 하는데, 가장 처음 수만 출력 되는 것이었다.
def find_max_num(array):
for num in array:
for compare_num in array:
if num < compare_num:
break
else:
return num
if문과 같은 열로 else를 작성하였는데, if에서 당연히 3보다 3이 작을 테니 3이 return 되는 것이었다. 그런데, else를 2번째 for문 열로 맞춰주니, 2번째 for문 안에서 최대값을 찾고 나온 값을 얻을 수가 있었다.
tab키의 사용의 중요성을 알 수 있었다.
파이썬의 내장 함수 str.isalpha() :
해당 문자열이 알파벳인지 알 수 있다.
파이썬의 배열 초기화 : array = [0] * 26
--> 배열을 0으로 26개를 초기화시킨다는 의미
파이썬에서 문자를 아스키코드로 변환시켜주는 함수 : print(ord('a')) # 97
반대로, 아스키코드를 문자로 변환하는 코드 : chr()
Q. 다음과 같은 문자열을 입력받았을 때, 어떤 알파벳이 가장 많이 포함되어 있는지 반환하시오
A. 정답은 ~
-> 내가 직접 작성한 코드(강사님의 코드x)
input = "hello my name is sparta"
def find_max_occurred_alphabet(string):
array = [0] * 26
for char in string:
if not char.isalpha():
continue
num = ord(char) - 97
array[num] += 1
max_index = 0
for index in range(len(array)):
max_num = array[0]
if max_num < array[index]:
max_num = array[index]
max_index = index
return chr(max_index + ord("a"))
result = find_max_occurred_alphabet(input)
print(result)시간복잡도
입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계이다. 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것이다.
입력값이 늘어도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘일 것이다!
각 줄이 실행되는 걸 1번의 연산이 된다고 생각하고 계산한다. 배열의 계산은 배열의 길이 만큼의 연산된다고 생각하여, N 만큼의 시간이 걸린다고 표현한다.
N과 은 N이 커질수록 그 차이가 심하게 난다.
그래서 N의 지수를 비교하면서 시간복잡도를 분석할 수 있다.
상수는 신경쓰지말고, 입력값에 비례해서 어느 정도로 증가하는지만 파악하면 된다.
공간복잡도
입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말한다.
입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것이다.
입력값이 늘어나도 공간은 덜 차지하는 알고리즘이 좋은 알고리즘일 것이다!
저장하는 데이터의 양이 1개의 공간을 사용한다고 계산한다.
공간복잡도로 계산되는 수들은 상수이기 때문에 (변하지 않기 때문에) 적은 차이의 공간 사용량은 크게 상관이 없다. 따라서 공간 복잡도보다는 시간 복잡도를 더 신경 써야 한다.
시간복잡도 계산하는 방법
for alphabet in alphabet_array: # alphabet_array 의 길이(26)만큼 아래 연산이 실행
occurrence = 0 # 대입 연산 1번 실행
for char in string: # string 의 길이만큼 아래 연산이 실행
if char == alphabet: # 비교 연산 1번 실행
occurrence += 1 # 대입 연산 1번 실행
if occurrence > max_occurrence: # 비교 연산 1번 실행
max_alphabet = alphabet # 대입 연산 1번 실행
max_occurrence = number # 대입 연산 1번 실행이 코드의 시간 복잡도는
1. alphabet_array 의 길이 X 대입 연산 1번
2. alphabet_array 의 길이 X string의 길이 X (비교 연산 1번 + 대입 연산 1번)
3. alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 2번)
즉, 52N + 104라는 시간이 걸린다.
for char in string: # string 의 길이만큼 아래 연산이 실행
if not char.isalpha(): # 비교 연산 1번 실행
continue
arr_index = ord(char) - ord('a') # 대입 연산 1번 실행
alphabet_occurrence_list[arr_index] += 1 # 대입 연산 1번 실행
max_occurrence = 0 # 대입 연산 1번 실행
max_alphabet_index = 0 # 대입 연산 1번 실행
for index in range(len(alphabet_occurrence_list)): # alphabet_array 의 길이(26)만큼 아래 연산이 실행
alphabet_occurrence = alphabet_occurrence_list[index] # 대입 연산 1번 실행
if alphabet_occurrence > max_occurrence: # 비교 연산 1번 실행
max_occurrence = alphabet_occurrence # 대입 연산 1번 실행
max_alphabet_index = index # 대입 연산 1번 실행이 코드의 시간 복잡도는
1. string의 길이 X (비교 연산 1번 + 대입 연산 2번)
2. 대입 연산 2번
3. alphabet_array 의 길이 X (비교 연산 1번 + 대입 연산 3번)
으로 3N + 106의 시간이 걸린다.
점근 표기법
알고리즘의 성능을 수학적으로 표기하는 방법이다. 알고리즘의 "효율성"을 평가하는 방법이다.
- 표기법의 종류
- 빅오(Big-O) : 최악의 성능이 나올 때 오느 정도의 연산량이 걸릴 것인지- 빅 오메가(Big-Ω) : 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴 것인지
=> 알고리즘은 입력값에 따라서 성능이 달라질 수 있다. 입력값의 분포에 따라서 성능이 변화할 수 있다.
input = [3, 5, 6, 1, 2, 4]
def is_number_exist(number, array):
for num in array: # array 의 길이만큼 아래 연산이 실행
if num == number: # 비교 연산 1번 실행
return True # N *1 = N 만큼
return False
result = is_number_exist(8, input)
print(result)위 코드의 시간복잡도는 만큼 이다. 그런데 만약 input 배열에 3이 가장 마지막에 들어가 있으면, for문이 배열 끝까지 돌아야 하기 때문에, 3이 배열의 첫번째에 있을 때보다 효율이 떨어질 수 밖에 없다. 그래서 앞에서 말했듯이 입력값의 분포에 따라 알고리즘의 성능에는 변화가 있다.
- 빅오 표기법으로 표시하면 O(N)(최악)
- 빅 오메가 표기법(최상)으로 표시하면 Ω(1)의 시간 복잡도를 가진 알고리즘이다.
✅ 알고리즘에서는 거의 모든 알고리즘을 빅오(최악) 표기법으로 분석한다.
-> 대부분의 입력값이 최선의 경우일 가능성은 굉장히 적기도 하고, 최악의 경우를 항상 대비해야 하기 때문이다!!
1차 반복문이 나오고, array의 길이만큼 그 반복문이 돈다면, 다른 상수 상관 없이 N만큼의 시간복잡도가 걸린다고 생각하면 된다.
Q. 다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오.
주어진 문자열 : "abadabac"
- 힌트 : 반복되지 않는 문자는 d, c 가 있지만 "첫번째" 문자니까 d를 반환해주면 된다.
Q1. 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오.
소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.
이 문제를 작성할 때 수학적인 지식이 부족해서 조금 애를 먹었다. 주어진 수에서 소수를 구분해 내는 것이 어려웠다.
처음에는 for문을 2차로 구성해서 문제를 푸는 방법밖에 생각이 안나서 앞에서 2차원이 되면 알고리즘 효율성에서 비효율적이라는 것은 알고 있었지만, 이 방법 밖에는 생각이 안났었다..
prime_list = []
for n in range(2, number + 1):
for i in range(2, n):
if n % i == 0:
break
else:
prime_list.append(n)위 방법으로 for문을 2개 사용해서 작성하였지만, 이건 효율적인 방법이 아님을 알기에 다른 방법이 있는지 공부해보기 위해 찾아보았다.
일단, 수가 2~ n-1까지의 수로 나눠지면 그 수는 소수가 아니기에 for문의 range를 수정하였다.
그런데, 2 ~ n-1까지의 소수로 나누어 떨어지지 않는다면 더 빠르게 소수를 찾을 수 있을 것이다.
또한, 주어진 자연수 n이 소수이기 위해서 필요한 조건은 n이 n의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다는 것이다. 수가 수를 나누면 몫이 발생하게 되는데, 몫과 나누는 수, 둘 중 하나는 반드시 n의 제곱근 이하이기 때문이다.
=> 그래서 i * i <= n 일때까지 비교하면 된다.
prime_array = []
if number < 2:
return 0 #소수는 없다.
for num in range(2, number+1):
for n in prime_array:
if num % n == 0 and n * n <= num:
break
else:
prime_array.append(num)나는 2보다 작은 수가 들어왔을 때를 다루기 위해 if문을 추가했고, 2차 for문에서 지금까지 구해진 소수들의 배열의 내용들로 수를 나누고, 그 수가 n의 제곱근 이하인지 확인하는 if문을 두어 소수를 구하는 배열을 만들어 내었다.
이 문제는 구현하는데 좀 많이 힘이 들었었다. 어떻게 접근해야 할지 몰라서 많이 헤맸던 문제였다. 이런 문제들이 코딩 시험에 나온다니 나는 못할 것 같다는 생각도 들었다...
Q2. 0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자를 모두 0, 혹은 모두 1로 같게 만들어야 한다.
할 수 있는 행동은 연속된 하나의 숫자를 잡고 모두 뒤집는 것 이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.
주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.
0을 1로, 1을 영으로 몇 번 바꾸는게 최소한으로 바꾸는 것인지 구하는 알고리즘 문제였다.
전 문제와는 다르게 이 문제는 빠르게 풀 수 있었다.
input = "011110"
def find_count_to_turn_out_to_all_zero_or_all_one(string):
count_0_to_1 = 0
count_1_to_0 = 0
for index in string:
if index == '0':
count_0_to_1 += 1
else:
count_1_to_0 += 1
if len(string) > 0 and (count_1_to_0 == 0 or count_0_to_1 == 0):
return len(string)
return min(count_1_to_0, count_0_to_1)
result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)강사님의 해설과는 흐름은 같지만 약간 다른 접근을 해보았다. 현재 주어진 string에서 0과 1이 몇 개인지 각각 세고, 그 수가 적은 숫자를 바꾸는 것이 최소한으로 바꾸는 것이기에 그 수를 반환해 주면 되는 것이었다.
그런데, 내 코드의 문제점은 만약 전체가 다 0이거나, 1이면 한 쪽은 무조건 0이 되기 때문에 string의 길이만큼 변하는 것이 아닌 0으로 반환되는 것이다.
그래서 전체가 0이거나 1일때를 처리해주는 if문 코드를 넣어주었다.
그랬더니 어떤 string을 넣어도 최소 변환 횟수를 잘 출력해주었다.
⠀⠀⠀⠀
⠀
⠀
⠀
이번주 학습 소감
알고리즘은 어렵다....
