이 글은 블로그주인장이 여태 공부했던 알고리즘 독학 및 강의들의 내용을 정리하는 포스팅입니다.
최댓값 찾기
- Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 이 배열 내에서 가장 큰 수를 반환하시오.
[3, 5, 6, 1, 2, 4]Sol. 간단하게 생각하면 저 배열원소를 하나씩 완전탐색을 하면 된다.for compare in arr: #먼저 배열 원소 중 기준 원소를 잡는다. for num in array: #비교 원소를 for문을 이용if num > compare: #기준이 작으면 멈추고 break else: #제일 크면 return num #그대로 반환
def find_max_num(array):
for num in array:
for compare_num in array: #비교대상을 잡기 위한 for문
if num < compare_num:
break
else:
return num최빈값 찾기
- Q. 다음과 같은 문자열을 입력받았을 때, 어떤 알파벳이 가장 많이 포함되어 있는지 반환하시오
"hello my name is sparta"
sol
1.알파벳 별 빈도수를 저장하기 위한 길이가 26인 0으로 초기화된 배열을 만듭니다.
alphabet_occurrence_array = [0] * 26
2.아스키코드 변환
print(ord('a') - ord('a')) # 97-97 -> 0
3. 문자열을 하나씩 확인하여 문자를 카운트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
시간복잡도
한줄요약: "차수만 봐라"
상수는 신경쓰지말고, 입력값에 비례해서 어느 정도로 증가하는지만 파악해야함 즉, N의 차수를 봐야함
#각 줄이 실행되는 걸 1번의 연산
for num in array: # array 의 길이만큼 아래 연산이 실행
for compare_num in array: # array 의 길이만큼 아래 연산이 실행
if num < compare_num: # 비교 연산 1번 실행
break
else:
return max_num
#각 줄이 실행되는 연산 ==> N * N ==> N^2
#즉 위 비교연산의 시간복잡도는 N^2max_num = array[0] # 연산 1번 실행
for num in array: # array 의 길이만큼 아래 연산이 실행
if num > max_num: # 비교 연산 1번 실행
max_num = num # 대입 연산 1번 실행
# 각 줄이 실행되는 연산 ==> 1 + 2 * N공간 복잡도
한줄요약: "공간을 희생해서라도 시간을 줄여라"
저장하는 데이터의 양이 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점근 표기법
빅오(Big-O)표기법, 빅 오메가(Big-Ω) 등으로 표기
빅오 표기법은 최악의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지, 빅오메가 표기법은 최선의 성능이 나올 때 어느 정도의 연산량이 걸릴것인지에 대해 표기
#알고리즘은 항상 최악의 경우의 수를 생각해야함
for element in array: # array 의 길이 N
if number == element: # 비교 연산 1번 실행
return True
return False
# 각 줄이 실행되는 연산 ==> O(N)알고리즘 문제
- Q. 곱하기 or 더하기
[0, 3, 5, 6, 1, 2, 4]
다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오. (단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다.)
#곱하기 or 더하기
#무턱대고 각 원소를 곱할수는 없음
#만약 원소가 1 or 0이면 더하는 게 더 큰 수이기 때문
#그러므로 각 원소와 합 변수가 0,1인 경우에 더해주고 나머진 곱해준다.
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- Q.반복되지 않는 문자
"abadabac"
다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오.
#반복되지 않는 첫 문자를 반환하는 문제
#반복되지 않는다는 것은 그 문자의 갯수가 1이라는 것
#알파벳 갯수의 카운트를 의마하는 리스트를 선언하고
#각 문자열의 문자를 카운트하면 해결가능
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: #그게 1이라면
not_repeating_character_array.append(chr(index + ord("a")))
for char in string:
if char in not_repeating_character_array:
return char #한 번 나온 첫 문자 반환
return "_" #그게 아닐 시소수 나열하기
- 문제
정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오. (소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.)
# 20이 입력된다면, 아래와 같이 반환
[2, 3, 5, 7, 11, 13, 17, 19]- 내 풀이
#먼저 소수인지 판별해야한다 생각했다.
def is_prime_number(n):
for i in range(2,int(math.sqrt(n))+1): #제곱근이용
if n % i ==0: #나누어 떨어지면 소수가 아니므로
return False
return True
def find_prime_list_under_number(number):
answer=[]
for i in range(number+1):
if 1<i<=3: #위 범위의 값들은 소수 이므로
answer.append(i)
elif is_prime_number(i): #소수이면
answer.append(i)
return answer- 강의해설
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문자열 뒤집기
-
문제
0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자열에 있는 모든 숫자를 전부 같게 만들려고 한다. 할 수 있는 행동은 문자열에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.예를 들어 S=0001100 일 때,
전체를 뒤집으면 1110011이 된다.
4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.
하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.
-
내 풀이
#모두 1으로 만드는 방범 최소로 뒤집는다
def find_count_to_turn_out_to_all_zero_or_all_one(string):
cnt_1_trans=0 #0->1
cnt_0_trans=0 #1->0
#연속된 것을 한번에 뒤집어야 하므로 문자열 첫번째를 잡는다.
if string[0]=='1':
cnt_0_trans += 1
else:
cnt_1_trans += 1
for i in range(1,len(string)):
if string[i-1] !=string[i]: #앞 뒤 문자열이 다른 경우
if string[i]=='1': #뒤 문자열이 1인 경우
cnt_0_trans+=1
else: #뒤 문자열이 0인 경우
cnt_1_trans+=1
return min(cnt_0_trans,cnt_1_trans)- 강의해설
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)개선할점
기존에 알고 있던 내용도 괜히 어렵게 생각하면서 접근 하는 것을 알게 되었다. 문제를 읽고 떠올리는 생각들을 천천히 정리하며 코드를 작성하는 연습이 필요한 것 같다.
참고
- 자료구조(열혈강의) -학부생때 강의
- 컴퓨터공학 전공 올인원 패키지 (SW기본) -패스트 캠퍼스
- 알고보면 알기 쉬운 알기쉬운 알고리즘 -스파르타 코딩클럽
소스코드
(Python)
https://github.com/BOLTB0X/Sparta-Algorithm/tree/main/week_1
발버둥