[자료구조와 알고리즘] #2

1-1 오늘 배울 것

알고리즘

왜배우나? 알고리즘 푸는데 통로가 되도록 하고 싶음.

1.알고리즘 공부 필요 이유

2.알고리즘 학습을 위한 기본 코드 구현력

3.시간복잡도, 공간복잡도 배우기

 

-알고리즘이란?

문제를 해결하기위한 방법들의 집합

-공부하는 이유

좋은 개발자가 되기 위해. (적은 공간으로 ᄈᆞ른 속도로 수행되는 프로그램 만들기)

프로그램을 잘 만들기 위해서 여러 자료구조와 방법을 배우고 익혀야함.

 

1-6 시간 복잡도 판단하기

6)시간 복잡도란?

입력값과 문제를 해결하는데 걸리는 시간과의 상관관계.

입력값이 늘어나도 걸리는 시간이 덜늘어나는 알고리즘이 좋은 알고리즘

7)최대값 찾기 알고리즘 시간 복잡도 판단하기

ㅇ첫 번째 방법 시간 복잡도

input = [3,5,6,1,2,4]

 

def find_max_num(array):

for num in array:

for compare_num in array :

if num < compare_num :

break

else :

return num

 

result = find_max_num(input)

print(result)

각 줄이 실행되는 것을 1번의 연산이 된다고 생각.

for num in array: #array 의 길이만큼 아래 연산이 실행

for compare_num in array : #array 의 길이만큼 아래 연산이 실행

if num < compare_num : #비교연산 1번 실행

break

else :

return num

위에서 연산된 것들을 더해보면

array길이 * array길이 * 비교연산 1번

만큼의 시간이 필요, 여기서 array의 길이는 보통 N이라고 표현. 그러면 시간을 다음과 같이 표현 가능 > N*N > n**2만큼 시간이 걸림

질문)길이가 변할 수 있는 값을 입력값이라고 함.

ㅇ두번째 방법의 시간 복잡도

input = [3,5,6,1,2,4]

 

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

 

result = find_max_num(input)

print(result)

>max_num 대입연산 1번 + array 길이 *(비교연산 1번, 대입연산 1번)

1 + 1*2N

상수의 연산량은 1만큼의 연산량이 필요하다고 하면 됨.

 

1-7 공간 복잡도 판단하기

입력값과 문제를 해결하는데 걸리는 공간과의 상관관계를 말함. 입력값이 2배로 늘어났을 때 문제 해결하는데 걸리는 공간은 몇배로 늘어나는지 보는 것

최빈값 찾기로 확인하기

저장하는 데이터의 양이 1개의 공간

ㅇ첫번째 방법

alphabet_array=[‘a’~‘z’] > 26개의 공간 사용

max_occurance = 0 >1개의 공간 사용

max_alphabet = alphabet_array[0] > 1개의 공간 사용

for alphabet in alphabet_array:

occurrence = 0 > 1개의 공간 사용

그럼 총 29개의 공간을 사용

ㅇ두번째 방법

alphabet_array=[‘a’~‘z’] > 26개의 공간 사용

arr_index = ord(char) - ord(‘a’) > 1개의 공간 사용

max_occurance = 0 >1개의 공간 사용

max_alphabet_index > 1개의 공간 사용

alphabet_occurrence = alphabet_occurrence_list[index] > 1개의 공간 사용

그럼 총 30개의 공간을 사용

 

그럼 첫 번째가 더 효율적인가? 사실 29랑 30은 둘다 상수여서 상관이 없음. 알고리즘의 성능에 큰 영향이 없음. 시간복잡도로 비교하면 알고리즘의 효율성을 비교할 수 있고, 공간복잡도는 성능에 큰 차이가 없다고 할 수 있다. 그래서 시간 복잡도를 더 신경써야함.

-시간복잡도

알고리즘 개선시 공간을 희생하더라도 시간 복잡도를 최소화 하기위해 노력해야함.

 

1-8 점근 표기법

점근 표기법 : 알고리즘의 성능을 수학적으로 표기(효율성을 평가)

종류는 빅오표기법, 빅오메가 표기법 있음

빅오표기법은 최악의 성능이 나올 때 어느정도의 연산량 > O(N)

빅오메가는 최선의 성능이 나올 때 어느정도의 연산량 오메가(1)

문제)배열에서 특정 요소 찾기

input = [3,5,6,1,2,4]

 

def is_number_exist(number, array):

#이부분을 채워보세요

return True

 

result = is_number_exist(3, input)

print(result)

 

>풀이

우선 배열 돌면서 찾고자하는 숫자가 발견되면 True반환, 없으면 False 반환

for문 돌면서 배열 원소 뽑기

def is_number_exist(number, array):

for element in array:

if number == elemnt:

return True

 

return Flase

return True

그럼 끝. 여기서 시간복잡도 계산

우선 for문이 돔.

def is_number_exist(number, array):

for element in array: > array의 길이만큼 아래 연산 실행

if number == elemnt: >비교연산 1번 실행

return True >N*1 만큼의 시간 복잡도

 

return Flase

return True

알고리즘은 입력값의 분포에 따라 성능이 달라질 수 있음. 그러나 우리는 항상 최악에 대비하기 때문에 거의 모든 알고리즘을 빅오표기법으로 분석.

 

기억해야할 것

1)입력값에 비례해서 얼마나 늘어날지 파악

2)공간복잡도 보다는 시간 복잡도를 줄이기 위해 고민

3)최악의 경우 얼마나 시간이 소요될지(빅오표기법)에대한 고민

 

1-9 알고리즘 더 풀어보기(1)

문제 1) 곱하기 or 더하기

배열의 숫자에 더하기 곱하기해서 가장 큰 수가 나오도록 하기.(단 일반 계산과는 달리 왼쪽에서 오른쪽으로 계산해줌)

input=[0,3,5,6,1,2,4]

def find_max_plus_or_multiply(array):

#이부분을 채워보세요!

return 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:

multipy_sum *=number

return multiply sum

 

1-10 알고리즘 더 풀어보기(2)

문제 1)영어로된 문자열에서 반복되지 않은 첫 번째 문자를 반환(문자가 없을시 ‘_’를 반환

abadabac >반복되지 않는 문자는 d,c가있는데, 첫 번째 문자니까 d를 반환.

 

input = "abadabac"

 

def find_not_repeating_character(string):

# 이 부분을 채워보세요!

return "_"

 

 

result = find_not_repeating_character(input)

print(result)

우선 반복되지 않는 것을 어떻게 찾을까에 대한 고민을 해야함.

 

1-11 끝&숙제 설명

1)소수 나열하기

소수나열하기 : 정수를 입력했을 때 그 정수이하의 소수를 모두 반환

input = 20

 

 

def find_prime_list_under_number(number):

# 이 부분을 채워보세요!

return []

 

 

result = find_prime_list_under_number(input)

print(result)

 

2)문자열 뒤집기

0과 1로만 이루어진 문자열의 모든 숫자를 뒤집는 것 (1을 0으로, 0을 1로 바꾸기)

 

알고리즘 풀다보면 문제 자체를 이해하기 힘들 때

그럴때는

1)문제의 다른 예시들을 떠올리면서 규칙성 생각

2)배웠던 자료구조를 활용하면 어떨지 생각

3)문제의 특징을 하나하나 글로 쓰기