[코딩 테스트 합격자 되기 - 1주차]
03 - 알고리즘의 효율 분석
시간 복잡도 : 알고리즘 성능을 나타내는 지표
시간 복잡도는 대체로 낮으면 낮을수록 좋음.
빅오 표기법 : 해당 알고리즘에 대한 최악의 시간 복잡도를 표현하는 방법.
| 수식 | 빅오 표기 | 설명 |
| 3x^2 + 5x + 6 | O(x^2) | 다항 함수로 구성되어 있으므로 최고 차항 x^2 만 남습니다 |
| x + logx | O(x) | 다항함수 + 로그함수의 경우, 증가폭이 더 낮은 로그함수를 제거하고 다항함수만 남깁니다. |
| 2^x + 10x^5 + 5x^2 | O(2^x) | 지수함수는 다항함수보다 빠르게 증가하므로 지수함수만 남습니다. |
| 시간 복잡도 | 최대 연산 횟수 |
| O(N!) | 10 |
| O(2^N) | 20 ~ 25 |
| O(N^3) | 200 ~ 300 |
| O(N^2) | 3,000 ~ 5,000 |
| O(NlogN) | 100만 |
| O(N) | 1,000 ~ 2,000만 |
| O(logN) | 10억 |
시간 복잡도를 활용하여 불필요한 알고리즘을 제외하면 됩니다.
예시1) 별 찍기
N = 3, *, **, ***
N = 5, *, **, ***, ****, *****
f(N) = 1 + 2 + ... + N = N(N + 1) / 2
따라서, O(N^2)의 시간 복잡도를 가진다.
04 - 코딩 테스트 필수 문법
뮤터블 객체 : 객체 생성 후 객체를 수정할 수 있다. 예) 리스트, 딕셔너리, 셋
list = [1, 2, 3, 4, 5]
list[4] = 6
print(list)
>>> [1, 2, 3, 6, 5]이뮤터블 객체 : 객체 생성 후 수정이 불가능한 객체. 대표적으로 정수, 부동 소수점, 문자열, 튜플
리스트
lst1 = [1, 2, 3, 4, 5]
lst2 = [1, 3, 5] + [7, 9]
lst3 = list(lst1)
print(lst1)
print(lst2)
print(lst3)
>>> [1, 2, 3, 4, 5]
>>> [1, 3, 5, 7, 9]
>>> [1, 2, 3, 4, 5]
리스트 인덱싱
lst1 = [1, 2, 3, 4, 5]
lst1.append(6)
print(lst1)
>>> [1, 2, 3, 4, 5, 6]
del lst1[2]
print(lst1)
>>> [1, 2, 4, 5, 6]리스트 슬라이싱
lst1 = [1, 2, 3, 4, 5]
print(lst1[:2])
print(lst1[0:2])
print(lst1[1:])
print(lst1[3:-1])
print(lst1[-4:-2])
>>>
[1, 2]
[1, 2]
[2, 3, 4, 5]
[4]
[2, 3]
양수 슬라이싱은 왼쪽에서부터 인덱스 0 ~ n - 1
음수 슬라이싱은 오른쪽에서부터 인덱스 -1 ~ -n
딕셔너리
딕셔너리 초기화
dct = {}
딕셔너리 삽입과 출력
dct = {}
dct['aapl'] = 1
dct['msft'] = 2
dct['goog'] = 3
print(dct)
>>> {'aapl': 1, 'msft': 2, 'goog': 3}
딕셔너리 검색
key = 'apple'
if key in dct :
value = dct[key]
print(f'{key} : {value}')
else :
print(f'{key}는 딕셔너리에 존재하지 않습니다.')
>>> apple는 딕셔너리에 존재하지 않습니다.
딕셔너리 수정
dct['msft'] = 4
print(dct)
>>> {'aapl': 1, 'msft': 4, 'goog': 3}
딕셔너리 삭제
del dct['goog']
print(dct)
>>> {'aapl': 1, 'msft': 4}
튜플
튜플은 이뮤터블 객체입니다. 한 번 생성되면 삽입하거나 삭제할 수 없습니다.
튜플 초기화
my_tuple = (1, 2, 3)
print(my_tuple)
>>> (1, 2, 3)
튜플 인덱싱, 슬라이싱
my_tuple = (1, 2, 3)
# 인덱싱
print(my_tuple[0]) # 1
print(my_tuple[1]) # 2
print(my_tuple[2]) # 3
# 슬라이싱
print(my_tuple[1:]) # (2, 3)
print(my_tuple[:2]) # (1, 2)
print(my_tuple[-1:])# (3, )
문자열
string = "Hello, World!"
string2 = 'Hello, World!'
print(string) # Hello, World!
print(string2) # Hello, World!
문자열 추가, 삭제
string = 'He'
string += 'llo'
print(string) # Hello
문자열 수정
string = 'Hello'
string = string.replace('l', '')
print(string) # Heo
함수
함수 정의
def add(num1, num2) :
result = num1 + num2
return result
answer = add(10, 50)
print(answer) # 60
람다식
파이썬은 람다식을 활용하여 함수를 더 간단하게 표현할 수 있습니다. 또한 익명 함수를 만드는 데 활용되며, 말 그대로 이름이 없는 함수를 말하며 코드에서 딱 한 번 실행할 목적으로 사용되거나, 다른 함수의 인수로 사용하는 데 사용합니다.
람다식 정의
lambda x, y : x + y
람다식 사용
add = lambda x, y : x + y
print(add(5, 4)) # 9lst = [1, 2, 3, 4, 5]
cubic = list(map(lambda x: x ** 3, lst))
print(cubic) # [1, 8, 27, 64, 125]
코딩 테스트 코드 구현 노하우
조기 반환
def fib3(n):
arr1 = 1
arr2 = 0
now = 0
if n <= 1:
return n # 1
for i in range(2, n + 1):
arr2 = now
now = arr1
arr1 = now + arr2
return arr1 # 2
print(fib3(10)) # 551. n <= 1이 성립하면 # 1을 조기 반환함.
2. 성립하지 않으면, (n > 1) 이라면, # 1을 건너 뛰고 for 이하로 루프를 돌다가 # 2를 리턴함.
보호 구문
def calc_average(num) :
if num is None :
return None
if not isinstance(num, list) :
return None
if len(num) == 0 :
return None
total = sum(num)
average = total / len(num)
return average
합성 함수
def add_five(x) :
return x + 5
def cubic(x) :
return x * x * x
composed_function = lambda x : cubic(add_five(x))
print(composed_function(3)) # (3 + 5) ^ 3 = 512