스파르타코딩클럽 내일배움캠프 Node.js반 알고리즘 강의 1주차 및 특강
알고리즘?
- 어떤 문제의 해결을 위해, 입력된 자료를 토대로 하여 원하는 출력을 유도해내는 규칙의 집합 [표준 대국어 사전]
좋은 프로그램?
- 프로그램을 수행하기 위해 꼭 필요한 자료구조 + 알고리즘
최댓값 찾기
Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 이 배열 내에서 가장 큰 수를 반환.
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)입력받은 리스트의 맨 처음 숫자를 최댓값으로 초기화를 한 후, 리스트를 돌면서 현재 최댓값과 비교를 하고,
더 큰 수를 최댓값으로 설정해주는 기본적인 방법이다.
최빈값 찾기
Q. 다음과 같은 문자열을 입력받았을 때, 어떤 알파벳이 가장 많이 포함되어 있는지 반환.
# 내가 작성한 코드
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','w','x','y','z']
alphabet_count_list = [0] * 26
for char in string :
if not char.isalpha():
continue
idx = ord(char) - ord('a')
alphabet_count_list[idx] += 1
for num in alphabet_count_list :
for compare_num in alphabet_count_list :
if num < compare_num:
break
else:
max = num
alphabet_array_index = alphabet_count_list.index(max)
return alphabet_array[alphabet_array_index]
result = find_max_occurred_alphabet(input)
print(result)나는 입력받은 문자열의 알파벳의 빈도수를 저장하는 배열을 만들고, 빈도수를 다 저장한 다음,
빈도수를 저장한 배열을 중첩으로 돌면서 최댓값을 찾아,
그 최댓값의 해당하는 알파벳을 알파벳을 반환하는 방법을 생각하여 작성하였다.
하지만, 해설을 들으니
내가 작성한 코드는 불필요한 부분이 좀 많이 들어가있다는 것을 알았다.
최댓값을 찾을 때에도 반복문을 한번만 쓸수도 있고,
내장함수 chr()을 사용하여 다시 문자로 변환할 수도 있어서 알파벳 배열을 선언하지 않아도 되었었다.
시간 복잡도
- 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계
- 크기가 변경될 수 있는 입력값을 N , N의 크기에 따른 상관관계로 수식으로 표현
공간 복잡도
- 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계
- 저장하는 데이터의 양이 1개의 공간을 사용한다고 계산
상수는 큰 상관이 없다.
대부분의 알고리즘의 성능은 공간에 의해서 결정되지 않는다.
따라서, 공간 복잡도 보다는 시간 복잡도를 신경 써야 한다.
점근 표기법
- 빅 오 표기법 (Big-O)
최악의 성능이 나올 때 어느정도의 연산량이 걸릴것인지 - 빅 오메가 표기법 (Big-Ω)
최선의 성능이 나올 때 어느정도의 연산량이 걸릴것인지
알고리즘에서는 거의 모든 알고리즘이 빅 오 표기법으로 분석.
대부분의 입력값이 최선의 경우일 때가 잘 없기 때문.
숙제
소수 나열하기
Q. 정수를 입력 했을 때, 그 정수 이하의 소수 모두 반환
input = 20
def find_prime_list_under_number(number):
list = []
# 2 ~ number까지 반복
for num in range(2, number):
isPrime = True # 소수인지 확인하는 트리거
# 2는 무조건 소수
if num == 2 :
list.append(num)
continue
for i in range(2, num):
# 2부터 자신까지 중에 자신이외의 수로 나누어지면 소수가 아니다
if num % i == 0:
isPrime = False # 소수가 아니면 판별하는 반복문을 빠져나가고 isPrime 을 False로 만든다
break
# 위의 판별하는 반복문을 돌고 나와서도 isPrime 이 true이면 리스트에 소수를 넣는다
if isPrime == True:
list.append(num);
return list
result = find_prime_list_under_number(input)
print(result)오늘 특강을 듣고 python 에서는 카멜케이스 말고 스네이크 형식을 쓴다고 한다.
isPrime 을 is_prime 으로 쓰도록 하자.
문자열 뒤집기
Q. 0혹은 1로만 이루어진 문자열이 주어졌을 때, 문자를 모두 0, 혹은 모두 1로 같게 만들자. 이때 모두 0 혹은 1로 만드는 최소 횟수를 구하라
input = "011110"
def find_count_to_turn_out_to_all_zero_or_all_one(string):
count_to_all_zero = 0
count_to_all_one = 0
current_char = string[0]
if current_char == '0':
count_to_all_one += 1
elif current_char == '1':
count_to_all_zero += 1
# 하나씩 돌아가면서 판별
for char in string :
if current_char != char:
if char == '0':
count_to_all_one += 1
current_char = char
if char == '1':
count_to_all_zero += 1
current_char = char
return min(count_to_all_one, count_to_all_zero)
result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)솔직히 문제 자체가 이해가 잘 되지않았다.
- 첫 번째 원소가 0인지 1인지 생각
- 다음문자가 바뀌는 구간을 생각
아직 많이 어렵다..
