자료구조, 알고리즘 생소하고 생소하다.
음 처음 시작부터 알고리즘과 친해지기 목차가있네 ㅋㅋ
친해지러 가볼까나
가볼까...
음?
선생님 무슨말하시는지 모르겠는데요..?
아니 선생님..
모르겠다구요...그래도 가보자고...
[목차]
01. 알고리즘과 친해지기 (1)
02. 알고리즘과 친해지기 (2)
03. 시간 복잡도 판단하기
04. 공간 복잡도 판단하기
05. 점근 표기법
06. 알고리즘 더풀어보기 (1)
07. 알고리즘 더풀어보기 (2)
01. 알고리즘과 친해지기 (1)
- 최댓값 찾기
Q. 문제 설명
다음과 같이 숫자로 이루어진 배열이 있을때, 이 배열 내에서 가장 큰 수를 반환하시오.
[3, 5, 6, 1, 2, 4]
def find_max_num(array):
# 이 부분을 채워보세요!
return 1
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]))
# 이 부분을 채워보세요! -> 채워보자!
1) 셀프 풀이
# 1. 셀프 체크
def find_max_num(array): # 함수 생성
max_num = 0 # 최댓값을 넣을 변수 지정
for i in array: # array 의 길이만큼 아래 연산 실행
if i > max_num: # 비교 연산 (i가 max_num보다 큰수인지 비교) 실행
max_num = i # 크다면 i를 최댓값 변수에 저장
return max_num # 최종 반복문 실행 후 최댓값 return
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]))
# 셀프 풀이)
# 정답 = 6 / 현재 풀이 값 = 6
# 정답 = 6 / 현재 풀이 값 = 6
# 정답 = 1888 / 현재 풀이 값 = 1888
2) 1차 풀이
# 2. 풀이1)
def find_max_num(array):
for num in array: # array 의 길이만큼 아래 연산이 실행
for compare_num in array: # array 의 길이만큼 아래 연산이 실행
if num < compare_num: # 비교 연산 (array[0]부터 요소 하나씩 비교) 실행
break # compare_num이 num보다 크다면 현재 반복문 종료
else:
return num # 반복문 종료시 num return
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]))
# 풀이 1)
# 정답 = 6 / 현재 풀이 값 = 6
# 정답 = 6 / 현재 풀이 값 = 6
# 정답 = 1888 / 현재 풀이 값 = 1888
3) 2차 풀이
# 3. 풀이2)
def find_max_num(array):
max_num = array[0] # 최댓값에 받아온 첫번째 요소를 지정
for num in array: # array 의 길이만큼 아래 연산이 실행
if num > max_num: # 비교 (num이 max_num보다 큰지 비교) 연산 실행
max_num = num # 크다면 최댓값을 num으로 지정
return max_num # 최종 최댓값 return
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)
# 정답 = 6 / 현재 풀이 값 = 6
# 정답 = 6 / 현재 풀이 값 = 6
# 정답 = 1888 / 현재 풀이 값 = 1888
02. 알고리즘과 친해지기 (2)
- 최빈값 찾기
Q. 문제 설명
다음과 같은 문자열을 입력받았을 때, 어떤 알파벳이 가장 많이 포함되어 있는지 반환하시오
"hello my name is sparta"
def find_max_occurred_alphabet(string):
# 이 부분을 채워보세요!
return "a"
result = find_max_occurred_alphabet(input)
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))
# 이 부분을 채워보세요! -> 채워보자!
tip 시작하기전에 힌트 드립니다.
문자인지 확인하는 방법 (str.isalpha())
print("a".isalpha()) # True
print("1".isalpha()) # False
s = "abcdefg"
print(s[0].isalpha()) # True
알파벳 별 빈도수를 저장하기 위한 초기 배열 생성
alphabet_occurrence_array = [0] * 26
# 출력 : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
아스키 코드 (ASCII)
코드 적용시
# 내장 함수 ord() 이용해서 아스키 값 받기
print(ord('a')) # 97
print(ord('a') - ord('a')) # 97-97 -> 0
print(ord('b') - ord('a')) # 98-97 -> 1
예제) 알파벳 빈도수 세기
def find_alphabet_occurrence_array(string):
alphabet_occurrence_array = [0] * 26
# 이 부분을 채워보세요!
return alphabet_occurrence_array
print("정답 = [3, 1, 0, 0, 2, 0, 0, 0, 1, 0, 0, 2, 2, 1, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 1, 0] \n현재 풀이 값 =", find_alphabet_occurrence_array("Hello my name is sparta"))
print("정답 = [2, 1, 2, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0] \n현재 풀이 값 =", find_alphabet_occurrence_array("Sparta coding club"))
print("정답 = [2, 2, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 3, 3, 0, 0, 0, 0, 0, 0] \n현재 풀이 값 =", find_alphabet_occurrence_array("best of best sparta"))
예제 풀이)
# 1. 알파벳 빈도수 세기
print("\n 1. 알파벳 빈도수 세기)")
def find_alphabet_occurrence_array(string):
alphabet_occurrence_array = [0] * 26
# 이 부분을 채워보세요! -> 추가한 내용
for s in string:
if not s.isalpha():
continue
arr_index = ord(s.lower()) - ord("a")
alphabet_occurrence_array[arr_index] += 1
return alphabet_occurrence_array
print("정답 = [3, 1, 0, 0, 2, 0, 0, 1, 1, 0, 0, 2, 2, 1, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 1, 0] \n현재 풀이 값 =",
find_alphabet_occurrence_array("Hello my name is sparta"))
print("정답 = [2, 1, 2, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0] \n현재 풀이 값 =",
find_alphabet_occurrence_array("Sparta coding club"))
print("정답 = [2, 2, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 3, 3, 0, 0, 0, 0, 0, 0] \n현재 풀이 값 =",
find_alphabet_occurrence_array("best of best sparta"))
# tip 알파벳 리스트 만들기
print("\n tip 알파벳 리스트 만들기")
alphabet = "abcdefghijklmnopqrstuvwxyz"
alphabet_arr = []
for alp in alphabet:
alphabet_arr.append(alp)
print(alphabet_arr)
# 1. 알파벳 빈도수 세기)
# 정답 = [3, 1, 0, 0, 2, 0, 0, 1, 1, 0, 0, 2, 2, 1, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 1, 0]
# 현재 풀이 값 = [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]
# 정답 = [2, 1, 2, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0]
# 현재 풀이 값 = [2, 1, 2, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0]
# 정답 = [2, 2, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 3, 3, 0, 0, 0, 0, 0, 0]
# 현재 풀이 값 = [2, 2, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 3, 3, 0, 0, 0, 0, 0, 0]
# tip 알파벳 리스트 만들기
# ['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']
1) 셀프 풀이
# 2-1. 셀프풀이
def find_max_occurred_alphabet(string):
# 이 부분을 채워보세요!
alphabet_occurrence_array = [0] * 26 # 빈도수를 저장할 초기 배열 생성
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'] # 각 요소들을 비교할 알파벳 배열
alp_index = 0 # 알파벳 인덱스를 확인할 변수 지정
max_alp_count = 0 # 최대 빈도수 카운트 변수 지정
for s in string: # 받아온 string 의 길이만큼 아래 연산 실행
if not s.isalpha(): # 문자인지 확인하기 위한 비교 연산 실행
continue
arr_index = ord(s.lower()) - ord("a") # 빈도수 저장할 초기 배열에 아스키코드 활용하여 인덱스 값 찾기
alphabet_occurrence_array[arr_index] += 1 # 빈도수 저장
for i, alp_count in enumerate(alphabet_occurrence_array): # i: 인덱스값, alp_count: 저장한 빈도수
if alp_count > max_alp_count: # 저장한 빈도수로 각각 비교하여 최빈값 찾기
max_alp_count = alp_count # 위 비교 연산에서 큰 값을 찾아서 최빈값 변수에 저장
alp_index = i # 최빈값이 저장된 인덱스값 저장
return alphabet_array[alp_index] # 알파벳 배열[최빈값이 저장된 인덱스값]
result = find_max_occurred_alphabet
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))
# 2-1. 셀프 풀이)
# 정답 = a 현재 풀이 값 = a
# 정답 = a 현재 풀이 값 = a
# 정답 = s 현재 풀이 값 = s
2) 1차 풀이
# 2-2. 풀이1)
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
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))
# 2-2. 풀이1)
# 정답 = a 현재 풀이 값 = a
# 정답 = a 현재 풀이 값 = a
# 정답 = s 현재 풀이 값 = s
3) 2차 풀이
# 2-3. 풀이2)
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)):
alphabet_occurrence = alphabet_occurrence_array[index]
if alphabet_occurrence > max_occurrence:
max_occurrence = alphabet_occurrence
max_alphabet_index = index
return chr(max_alphabet_index + ord('a'))
result = find_max_occurred_alphabet
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))
# 2-3. 풀이2)
# 정답 = a 현재 풀이 값 = a
# 정답 = a 현재 풀이 값 = a
# 정답 = s 현재 풀이 값 = s
03. 시간 복잡도 판단하기
시간 복잡도란?
- 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계
- 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것
# 알고리즘 친해지기 (1) 최댓값 풀이1)
def find_max_num(array): ########################################################################################################
for num in array: # array 의 길이만큼 아래 연산이 실행
for compare_num in array: # array 의 길이만큼 아래 연산이 실행
if num < compare_num: # 비교 연산이 1회 실행
break ########################################################################################################
else:
return num
###########################################################################################################################################
# 시간 복잡도 판단하기
# 1. array의 길이 X array의 길이 X 비교 연산 1번
# 2. 위 내용 종합하여 나온 표현 ( N * N )
###########################################################################################################################################
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]))
# 알고리즘 친해지기 (1) 최댓값 풀이2)
def find_max_num(array): ###############################################################################################################
max_num = array[0] # 연산 1회 실행 (1회)
for num in array: # array 의 길이만큼 아래 연산이 실행 (N회)
if num > max_num: # 비교 연산 1회 실행 (1회)
max_num = num # 대입 연산 1회 실행 (1회)
return max_num ###############################################################################################################
###########################################################################################################################################
# 시간 복잡도 판단하기
# 1. max_num 대입 연산 1번
# 2. array의 길이 X (비교 연산 1번 + 대입 연산 1번)
# 3. 위 내용 종합하여 나온 표현 ( 1 + 2 * N )
###########################################################################################################################################
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]))
자세한 내용은 추가로 공부하기로!
04. 공간 복잡도 판단하기
공간 복잡도란?
- 입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계
- 입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 공간은 몇 배로 늘어나는지를 보는 것
# 알고리즘 친해지기 (2) 최빈값 풀이1)
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"] # 26개의 공간을 사용합니다.
max_occurrence = 0 # 1개의 공간을 사용합니다.
max_alphabet = alphabet_array[0] # 1개의 공간을 사용합니다.
for alphabet in alphabet_array:
occurrence = 0 # 1개의 공간을 사용합니다.
for char in string: ##############################################################################
if char == alphabet:
occurrence += 1
if occurrence > max_occurrence:
max_alphabet = alphabet
max_occurrence = occurrence
return max_alphabet
####################################################################################################################################
# 공간 복잡도 판단하기
# 1. alphabet_array 의 길이 = 26
# 2. max_occurrence, max_alphabet, occurrence 변수 = 3
# 3. 위 내용을 종합하면 총 29개의 공간을 사용합니다.
####################################################################################################################################
result = find_max_occurred_alphabet
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))
####################################################################################################################################
# 알고리즘 친해지기 (2) 최빈값 풀이2)
def find_max_occurred_alphabet(string): ###################################################################
alphabet_occurrence_array = [0] * 26 # 26개의 공간을 사용합니다.
for char in string:
if not char.isalpha():
continue
arr_index = ord(char) - ord('a') # 1개의 공간을 사용합니다.
alphabet_occurrence_array[arr_index] += 1
max_occurrence = 0 # 1개의 공간을 사용합니다.
max_alphabet_index = 0 # 1개의 공간을 사용합니다.
for index in range(len(alphabet_occurrence_array)):
alphabet_occurrence = alphabet_occurrence_array[index] # 1개의 공간을 사용합니다.
if alphabet_occurrence > max_occurrence: ###################################################################
max_occurrence = alphabet_occurrence
max_alphabet_index = index
return chr(max_alphabet_index + ord('a'))
####################################################################################################################################
# 공간 복잡도 판단하기
# 1. alphabet_array 의 길이 = 26
# 2. arr_index, max_occurrence, max_alphabet_index, alphabet_occurrence 변수 = 4
# 3. 위 내용을 종합하면 총 30개의 공간을 사용합니다.
####################################################################################################################################
result = find_max_occurred_alphabet
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))
05. 점근 표기법
점근 표기법이란?
- 알고리즘의 성능을 수학적으로 표기하는 방법입니다. 알고리즘의 “효율성”을 평가하는 방법
- 점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법
- 지금까지 이 함수는 N 정도의 시간과 공간이 걸리겠구나 하면서 분석했던 게 점근 표기법의 일종이라고 말할 수 있습니다.
점근 표기법의 종류
- 점근 표기법의 종류에는 빅오(Big-O)표기법, 빅 오메가(Big-Ω) 표기법이 있습니다.
- 예를 들어 빅오 표기법으로 표시하면 $O(N)$, 빅 오메가 표기법으로 표시하면 $Ω(1)$ 의 시간복잡도를 가진 알고리즘이다.
tip 알고리즘에서는 거의 모든 알고리즘을 빅오 표기법으로 분석합니다. 왜냐면 대부분의 입력값이 최선의 경우일 가능성은 굉장히 적을 뿐더러, 우리는 최악의 경우를 대비해야 하기 때문입니다.
06. 알고리즘 더 풀어보기 (1)
Q. 곱하기 or 더하기
다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오. 단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.
[0, 3, 5, 6, 1, 2, 4]
def find_max_plus_or_multiply(array):
# 이 부분을 채워보세요!
return 1
result = find_max_plus_or_multiply
print("정답 = 728 현재 풀이 값 =", result([0,3,5,6,1,2,4]))
print("정답 = 8820 현재 풀이 값 =", result([3,2,1,5,9,7,4]))
print("정답 = 270 현재 풀이 값 =", result([1,1,1,3,3,2,5]))
풀이)
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
print("정답 = 728 현재 풀이 값 =", result([0,3,5,6,1,2,4]))
print("정답 = 8820 현재 풀이 값 =", result([3,2,1,5,9,7,4]))
print("정답 = 270 현재 풀이 값 =", result([1,1,1,3,3,2,5]))
07. 알고리즘 더 풀어보기 (2)
Q. 반복되지 않는 문자
다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오.
"abadabac" # 반복되지 않는 문자는 d, c 가 있지만 "첫번째" 문자니까 d를 반환해주면 됩니다!
input = "abadabac"
def find_not_repeating_first_character(string):
# 이 부분을 채워보세요!
return "_"
result = find_not_repeating_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))
풀이)
def find_not_repeating_first_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_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))
이게 1주차라니.. 빨리하고 쟝고해야하는데 이해가 너무 느리다..
그래도 화이팅하고 스겜해봐야지
'Sparta Coding Club > Today I Learned [TIL]' 카테고리의 다른 글
[TIL] #DAY - 017 - 파이썬 장고 실무 기초 (1) (내일배움캠프AI 3기) (0) | 2022.09.22 |
---|---|
[TIL] #DAY - 016 - 자료구조, 알고리즘 (2) (내일배움캠프AI 3기) (1) | 2022.09.21 |
[TIL] #DAY - 014 - 파이썬 기초 복습하기!(2) (내일배움캠프AI 3기) (1) | 2022.09.20 |
[TIL] #DAY - 013 - 파이썬 기초 복습하기! (내일배움캠프AI 3기) (1) | 2022.09.16 |