프로그래밍 공부를 시작하기 전부터 알고리즘, 코딩 테스트 이런 이야기들을 듣다가 처음으로 수업을 들었는데, 결론은 어려웠다. 1주차 강의 개념을 이해하고 아 이런 거구나~ 하고 이제 문제를 풀어보려면 시작을 어떻게 해야 할지 감도 안 잡혔다. 강의는 짧은 호흡으로 초보자를 위해 간단하게 진행되지만, 내가 기초 지식이 너무 없어서 그런지 도중에 강의를 멈추고 꽤 오랫동안 생각한 다음에 넘기게 된다. 수학 문제처럼 답이 나올 때까지 붙잡고 있어야 하는 건지, 아니면 넘어가서 정답을 보고 풀이를 이해해야 하는지 공부방법도 잘 모르겠다.
풀이할 때 어떻게 접근해야 될까? 특히 알고리즘 문제를 풀 때 나는 너무 복잡하고 길게 쓰게 되는데 막상 정답을 보면 엄청 간단해서 공부를 많이 해야겠다고 생각했다. 심지어 풀이를 봐도 한참 붙잡고 있어야 이해하는 경우도 있었다. 강의시간은 1시간 반 정도이지만, 내용 정리하고, 복습, 직접 실습해보고 하는 시간 다 합쳐보니 총 수강시간은 거의 7시간정도 걸린 것 같다. 이렇게 또 하루가 갔다. 앞으로 알고리즘 수업은 이전 수업을 토대로 진행된다고 하는데 조금 걱정된다. 일단 이해는 어떻게 한 것 같은데, 손가락 사이로 흩어지는 모래처럼 지금 내 지식들도 빠르게 흩날리는 중이다.
그래도 한참 들여다보다가 궁금해하던 걸 해소하고 나면 뭔가 후련해진다. 혼자서 아무리 생각해도 이해를 못 해서 결국에는 해설이 잘못됐나?라는 생각도 했던 문제가 있었는데, 팀원들한테 물어보니 빠른 시간 내에 친절하게 해결해줬다. 아직 내가 제일 왕초보라서 어리바리한 것 같다. 어쨌든 어찌어찌 왕초보로서 1주차 강의는 완강했으니, 어서 기초 강의들을 끝내고 다양한 문제들을 접해봐야겠다. 일지가 아니라 푸념 글이 된 것 같은데 여전히 아직도 공부할 건 많다. 아자 파이팅~
# 중복 반복문 사용
# python의 for ~ else문은 for문에서 break가 발생하지 않았을 때의 동작을 else문에 제시
def find_max_num(array):
for num in array:
for compare_num in array:
if num < compare_num:
break
else
return num
# 가장 큰 수 저장한 변수와 비교
def find_max_num(array):
max_num = array[0]
for num in array:
if max_num < num:
max_num = num
return max_num
## 첫 번째 방법
def find_max_num(array):
for num in array: # array 의 길이만큼 아래 연산이 실행
for compare_num in array: # array 의 길이만큼 아래 연산이 실행
if num < compare_num: # 비교 연산 1번 실행
break
else:
return max_num
각 줄이 실행되는 것을 1번의 연산이 된다고 생각하고 계산함.
위에서 연산된 것: array 길이 X array 길이 X 비교연산 1번
array(입력값) 길이는 보통 N으로 표현하므로, 위의 식은 N X N = N^2 로 표현.
위의 함수는 N^2만큼의 시간이 걸렸다고 표현.
입력값: 함수의 크기가 변경될 수 있는 값. ex) 위에서의 배열
N에 숫자를 대입하는 것이 아니라, 수식으로 표현해야 함.
이유: (시간 복잡도: N의 크기에 따른 시간의 상관관계), N=40 이면 1600 보다 40 X 40이 적합.
def find_max_num(array):
max_num = array[0] # 대입 연산 1번 실행
for num in array: # array 의 길이만큼 아래 연산이 실행
if num > max_num: # 비교 연산 1번 실행
max_num = num # 대입 연산 1번 실행
return max_num
array의 길이를 N이라고 하면, 이 함수는 1 + 2 X (1 + 1) = 2N + 1 만큼의 시간이 걸림.
## 첫 번째 방법 (공간복잡도: 29)
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
## 두 번째 방법 (공간복잡도: 30)
def find_max_occurred_alphabet(string):
alphabet_occurrence_list = [0] * 26 # 26개, 인덱스의 요소 하나하나도 1개로 취급
for char in string:
if not char.isalpha():
continue
arr_index = ord(char) - ord('a') # 1개
alphabet_occurrence_list[arr_index] += 1
max_occurrence = 0 # 1개
max_alphabet_index = 0 # 1개
for index in range(len(alphabet_occurrence_list)):
alphabet_occurrence = alphabet_occurrence_list[index] # 1개
if alphabet_occurrence > max_occurrence:
max_occurrence = alphabet_occurrence
max_alphabet_index = index
return chr(max_alphabet_index + ord('a'))
29, 30 둘 다 상수라 큰 상관 X. 시간 복잡도로 비교해야 함.
대부분 문제에서는 알고리즘 성능이 공간에 의해 결정되지 않음. 공간복잡도 희생해라.
## 첫 번째 방법 (시간복잡도: 52N + 104)
# 26 * (1 + 2*N + 3) = 52N + 104
for alphabet in alphabet_array: # alphabet_array의 길이(26)만큼 실행
occurrence = 0 # 대입 연산 1번 실행
for char in string: # string(입력값: N)의 길이만큼 실행
if char == alphabet: # 비교 연산 1번 실행
occurrence += 1 # 대입 연산 1번 실행
if occurrence > max_occurrence: # 비교 연산 1번 실행
max_alphabet = alphabet # 대입 연산 1번 실행
max_occurrence = number # 대입 연산 1번 실행
## 두 번째 방법 (시간복잡도: 3N +106)
# N*(1+2) + 2 + 26*(1+3) = 3N + 106
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번 실행
점근 표기법 (asymptotic notation): 알고리즘의 성능을 수학적으로 표기하는 방법
알고리즘 '효율성'을 평가하는 방법임.
사전적 정의: 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법
어떤 함수는 N 정도의 시간, 공간이 걸리겠구나 하고 분석하는 것도 점근 표기법의 일종. (위에서 한 것)
점근 표기법 종류:
1. 빅오(Big-O)표기법: 최악의 성능이 나올 때의 연산량 표기. ex) O(N)
2. 빅 오메가(Big-Ω)표기법: 최선의 성능이 나올 때의 연산량 표기. ex) Ω(1)
ex) a 입력값은 10분 걸리는 반면, b 입력값은 300분이 걸림
02. [실습] 배열에서 특정 요소 찾기
## 시간복잡도: N * 1 = N
def is_number_exist(number, array):
for element in array: # array 길이(입력값: N)만큼 실행
if number == element: # 비교 연산 1번 실행
return True
return False
운 좋으면 한 번에 찾을 수 있지만, 그렇지 않다면 N번의 연산 후에 찾을 수 있음.
알고리즘 성능은 항상 동일하지 않고, 입력값 및 입력값 분포에 따라 변화.
빅오 표기법: O(N), 빅 오메가 표기법: Ω(1) 시간복잡도를 가진 알고리즘임.
대부분의 알고리즘은 거의 빅오 표기법으로 분석.
이유: 최선의 입력값일 가능성은 낮고, 항상 최악의 경우(빅오 표기법)를 대비해야 하기 때문.
최종 정리:
1. 입력값에 비례해서 연산량이 얼마나 늘어날지 파악. (N의 지수가 중요)
2. 중요도: 공간복잡도 << 시간복잡도
3. 빅오 표기법(최악의 경우)에 대해 고민하라. (앞으로 알고리즘은 빅오 표기법의 시간복잡도 분석)
시간복잡도: O(N)만큼 걸린다. 그냥 1차 반복문 나왔는데, array 길이만큼 반복되니 N으로 생각.
def find_max_plus_or_multiply(array):
multiply_sum = 0
for number in array:
if number <= 1 or multiply_sum <= 1:
# 초기 합계가 0이므로, 요소가 0, 1뿐만 아니라 합계가 0, 1일 때도 더하기 해줘야 함.
# 합계 0: 완전 초기 상태이므로 더하기
# 합계 1: 초기에서 1을 더한 것이므로 다음 요소와 더하기
multiply_sum += number
else:
multiply_sum *= number
return multiply_sum
def find_not_repeating_first_character(string):
alphabet_occurrence_array = [0] * 26
# 앞에서 초기화 리스트에 알파벳 빈도수 찾은 것을 이용. 빈도수 1이면 반복 X. 이거 찾기.
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]
# 빈도수가 1인 알파벳 찾기
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
# 입력값과 빈도수가 1인 알파벳 일치하는지 확인하고 출력
return "_"
result = find_not_repeating_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))
시간복잡도: 이중 반복문이 없고 1차 반복문만 있는데, array(입력값) 길이만큼 반복하므로 O(N).
## 소수 나열하기 답안
# 2, 3으로 나머지 0이 아니면 합성수(6)로도 나눠떨어지지 않음. 아래에 개선된 버전.
input = 20
# 소수는 약수가 자기 자신과 1뿐.
def find_prime_list_under_number(number):
prime_list = []
for n in range(2, number + 1): # n: 2 ~ 20(number), 얘네들 소수인지 판별
for i in range(2, n): # 2 ~ 19(number-1)
if n % i == 0:
break # 1과 자기 자신이 없는데 나머지가 0? 그러면 소수가 아니야
else: # break문이 한번도 발생하지 않았다면
prime_list.append(n) # 리스트에 추가
return prime_list
result = find_prime_list_under_number(input)
print(result)
## 소수나열하기 1차 개선
input = 20
def find_prime_list_under_number(number):
prime_list = []
for n in range(2, number + 1): # n: 2 ~ 20
for i in prime_list: # i: 2 ~ 19(n: 2 ~ 19(number-1)) 사이의 소수
if n % i == 0:
break
else: # n = 2 일때, 바로 이쪽으로 온다
prime_list.append(n)
return prime_list
result = find_prime_list_under_number(input)
print(result)
## 소수 나열하기 2차 개선
# 주어진 자연수 N이 소수이기 위한 필요 충분 조건은 N이 N 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않음.
# 나눗셈에서 몫과 나누는 수 둘 중 하나는 반드시 N의 제곱근 이하임.
# prime_list에서도 N = 20일때 소수인 19로 나눠줄 필요가 없음.
input = 20
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: # 여기 조건이 추가됨, i는 2 3 5만 있으면 됨
break
else:
prime_list.append(n)
return prime_list
result = find_prime_list_under_number(input)
print(result)
02. [실습] 문자열 뒤집기
알고리즘 문제풀이 팁:
1. 바로 코드 작성하지 말고, 문제의 다른 예시들로 규칙성 파악하기. ex) 00000의 최소횟수는?
2. 배웠던 자료구조 활용하기 ex) 스택, 큐
3. 문제의 특징을 하나씩 글로 써보기 ex) 문자열 뒤집는데 0, 1 중 고민됨. 초기 0, 1도 횟수와 연관.
## 답안 코드
# 고려해야 할 것: 1) 뒤집어 질 경우, 2) 첫 번째 원소가 0인지 1인지
# 위의 두 개를 계산하면 모두 0으로 만드는 횟수, 모두 1로 만드는 횟수 구함.
# 이 중 최솟값을 반환해주면 해결.
input = "011110"
def find_count_to_turn_out_to_all_zero_or_all_one(string):
count_to_all_zero = 0 # 0 -> 1 전환되는 순간에 += 1
count_to_all_one = 0 # 1 -> 0 전환되는 순간에 += 1
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]: # 1 -> 0, 0 -> 1
if string[i + 1] == '0': # 1 -> 0: 앞의 수를 전부 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)
