1. 최댓값 찾기
숫자들로 이루어진 배열이 있을 때, 이 배열에서 가장 큰 수를 반환해라.
방법1. 가장 큰 수를 저장할 변수를 만들고 for문으로 배열을 돌아가며 변수와 비교한다. if 값이 더 크다면 큰수변수에 대입
def find_max_num(array):
max_num = array[0]
for num in array:
if num > max_num:
max_num = num
return max_num
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. 최빈값 찾기
입력받은 문자열에서 가장 많이 들어간 알파벳 출력하기
input = "hello my name is sparta"
def find_max_occurred_alphabet(string):
alphabet_occurrence_array = [0] * 26
for char in string:
if char.isalpha():
numberth = (ord(char) - ord('a'))
alphabet_occurrence_array[numberth] += 1
else:
pass
# 가장 많이 발생했던 빈도수를 저장하는 변수
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
max_alphabet = chr(max_alphabet_index + ord('a'))
return max_alphabet
result = find_max_occurred_alphabet(input)
print(result)1) 리스트에 초기값 0으로 알파벳 갯수만큼 생성
2) 입력 받은 문자열을 for문 돌려서 알파벳 하나씩 뽑아낸다.
3) .isalpha() 를 사용해서 띄어쓰기와 알파벳 구분
4) ord() 를 사용하면 ASCII 코드대로 문자를 숫자로 바꿔준다.
5) (for문의 현재 알파벳 아스키값) - (a의 아스키값) = (배열안에서 현재 알파벳 인덱스 번호)
6) 해당 인덱스 +1
7) alphabet_occurrence_array 안에는 입력 받은 문자열의 알파벳마다 해당하는 인덱스에 중복되는 수 만큼 값이 들어가있게된다.
8) alphabet_occurrence_array 를 for문으로 인덱스 하나씩 비교해서 더 큰 값을 저장
가장 많이 발생했던 빈도수를 저장하는 변수 , 그때의 인덱스 값을 저장하는 변수 정의
9) max_alphabet_index 에 가장많이나온 알파벳의 인덱스가 들어가고 a의 아스키값을 더해서 해당 알파벳의 아스키 값으로 만든다.
10) chr() 을 사용해서 다시 문자로 바꾸어서 출력
시간 복잡도
입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계
입력값이 늘어났을때 걸리는 시간은 몇 배로 늘어나는가
for num in array: # array 의 길이만큼 아래 연산이 실행
for compare_num in array: # array 의 길이만큼 아래 연산이 실행
if num < compare_num: # 비교 연산 1번 실행
break
else:
return numarray의 길이 X array의 길이 X 비교 연산 1번
= N x N = N^2
for num in array: # array 의 길이만큼 아래 연산이 실행
if num > max_num: # 비교 연산 1번 실행
max_num = num # 대입 연산 1번 실행- max_num 대입 연산 1번
- array의 길이 X (비교 연산 1번 + 대입 연산 1번)
- 2N+1
- N 과 N^2은 N 이 커질수록 더 큰 차이가 나게된다.
- N의 지수를 먼저 비교하면 되겠구나.
매번 코드를 매 실행 단위로 이렇게 몇 번의 연산이 발생하는지 확인하는 건 불가능하다. 따라서 상수는 신경쓰지말고, 입력값에 비례해서 어느 정도로 증가하는지만 파악하면 된다.
즉, 2N+1의 연산량이 나온 첫번째 풀이 방법은 N 만큼의 연산량이 필요하다. N^2 의 연산량이 나온 두번째 풀이 방법은 N^2 만큼의 연산량이 필요하다. 참고로, 만약 상수의 연산량이 필요하다면, 1 만큼의 연산량이 필요하다고 말하면 됩니다.
공간 복잡도
입력값과 문제를 해결하는 데 걸리는 공간과의 상관관계를 말한다.
저장하는 데이터의 양이 1개의 공간을 사용한다고 계산한다.
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개의 공간을 사용합니다공간복잡도는
- alphabet_array 의 길이 = 26
- max_occurrence, max_alphabet, occurrence 변수 = 3
29 가 된다.
대부분의 문제에서는 알고리즘의 성능이 공간에 의해서 결정되지 않는다. 따라서 공간 복잡도보다는 시간 복잡도를 더 신경 써야 한다.
점근 표기법
알고리즘의 효율성을 평가하여 수학적으로 표기하는 방법.
위에서 이 함수는 N 정도의 시간과 공간이 걸리겠구나 하면서 분석했던 게 점근 표기법의 일종이라고 말할 수 있다.
빅오(Big-O)표기법 : 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기
빅 오메가(Big-Ω) 표기법 : 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기
def is_number_exist(number, array):
for find_num in array:
if number == find_num:
return True
return False
result = is_number_exist
print("정답 = True 현재 풀이 값 =", result(3,[3,5,6,1,2,4]))
print("정답 = Flase 현재 풀이 값 =", result(7,[6,6,6]))
print("정답 = True 현재 풀이 값 =", result(2,[6,9,2,7,1888]))위 코드에서 시간복잡도는 N*1 시간 인것을 알 수 있다.
하지만 입력값을 다르게 비교해보면,
input = [3, 5, 6, 1, 2, 4] 이라는 입력값에 대해서 3을 찾는다면 1번의 연산이 걸리고
input = [4, 5, 6, 1, 2, 3] 이라는 입력값에 대해서 3을 찾으면 가장 마지막 연산에서(input의 길이(N) 만큼) 찾게된다.
따라서
빅오 표기법으로 표시하면 O(N), 빅 오메가 표기법으로 표시하면 Ω(1) 의 시간복잡도를 가진 알고리즘이다.
알고리즘에서는 최악의 경우를 대비해야 하기때문에 빅오 표기법으로 분석한다.
곱하기 or 더하기
Q. 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오.
단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.
input = [0,3,5,6,1,2,4]
def find_max_plus_or_multiply(array):
cal = 0
for num in array:
if (cal <= 1) or (num <= 1):
cal += num
else:
cal *= num
return cal
result = find_max_plus_or_multiply(input)
print(result)계산해야할 숫자에 0 또는 1 이 있다면 더해주고 그 외에 상황은 곱해준다.
시간복잡도 : O(N)
숙제 1. 소수 찾기
Q. 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오.
20이 입력된다면, [2, 3, 5, 7, 11, 13, 17, 19] 같이 반환해야 한다.
A.
input = 20
def find_prime_list_under_number(number):
result_list = []
for num in range(2, number+1):
for i in range(2, num):
if num % i == 0:
break
else:
result_list.append(num)
return result_list
result = find_prime_list_under_number(input)
print(result)
풀이.
입력받은 숫자까지 반복문을 돌며, 해당 숫자 이하의 수로 나누어떨어지는가 판별하여 리스트에 추가해준다.
소수의 조건 (코드 개선)
1. 자기 자신과 1 외에는 아무것도 나눌 수 없다.
if num % i == 0:
break
나눈 나머지가 0이면 리스트에 추가하지않고 다음 for문 진행
2. 2 부터 num 까지 모든수로 나누어 떨어지지 않는지 확인할 필요 없다. => 모든 소수로 나누어 떨어지지않으면 된다.
for i in range(2, num): => for i in range(2, result_list):
3. 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 N의 제곱근 이하이기 때문에 N이 N의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다.
if num % i == 0: => if num % i == 0 and i * i <= num:
숙제 2. 문자열 뒤집기
Q. 0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자를 모두 0, 혹은 모두 1로 같게 만들어야 한다. 할 수 있는 행동은 연속된 하나의 숫자를 잡고 모두 뒤집는 것 이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.
A.
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
if string[0] == '0':
count_to_all_one += 1
elif string[0] == '1':
count_to_all_zero += 1
for i in range(len(string) - 1):
if string[i] != string[i + 1]:
if string[i + 1] == '0':
count_to_all_one += 1
if string[i + 1] == '1':
count_to_all_zero += 1
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로 만들때 뒤집는 횟수를 저장하는 변수
첫 문자가 0 인지 1인지 부터 판단
문자열 for문으로 0번째부터 반복하면서
0에서 1로 변하는 순간 혹은 1에서 0으로 변하는 순간 상황에 맞게 카운트를 올린다.
min() : 가장 작은 수를 반환한다.
'AI 웹 개발 과정 > 알고리즘' 카테고리의 다른 글
| 알고리즘 - 3주차 [스택, 큐, 해쉬] (0) | 2022.08.06 |
|---|---|
| 알고리즘 - 3주차 [버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬] (0) | 2022.07.25 |
| 알고리즘 - 2주차 이진탐색 / 재귀함수(팩토리얼, 회문검사) (0) | 2022.07.22 |
| 알고리즘 - 2주차 Array / LinkedList (0) | 2022.07.21 |