*해당 스터디는 <코딩테스트 합격자 되기> 책 저자분과 함께 하는 스터디입니다.
3장 알고리즘의 효율 분석
시간 복잡도
알고리즘의 성능을 나타내는 지표. 입력 크기에 대한 연산 횟수의 상한
시간 복잡도 측정법
: 알고리즘 시작부터 결괏값이 나올 때 까지의 연간 횟수 측정
코딩테스트 활용법
: 문제 분석 후 빅오 표기법 활용해 해당 알고리즘을 적용했을 때 제한 시간 내 출력값이 나올 수 있을지 확인
| 시간 복잡도 | 최대 연산 횟수 |
|---|---|
| O(N!) | 10 |
| O(2^N) | 20~25 |
| O(N^3) | 200~300 |
| O(N^2) | 3000~5000 |
| O(NlogN) | 100만 |
| O(N) | 1000~2000만 |
| O(logN) | 10억 |
4장 필수 문법
4-1. 빌트인 데이터 타입
built-in data type : 언어 자체에서 제공하는 데이터 타입 및 컬렉션 데이터 타입이 존재함
기본 데이터 타입: 정수형, 부동소수형, 문자열 타입
컬렉션 데이터 타입: 리스트, 튜플, 셋, 딕셔너리
- 부동소수형(float) 일 경우, epsilon 에 주의
: 파이썬은 부동소수형 데이터를 이진법으로 표현하기 때문에 오차 발생.
! 부동소수형 데이터 활용 문제는 오차 허용 범위를 언급하는 경우가 많으니 주의할 것
4-2. 컬렉션 데이터 타입
collection: 여러 값을 담는 데이터 타입 (리스트, 튜플, 딕셔너리, 셋, 문자열)
*데이터 수정 가능 여부에 따라서 mutable/immutable 로 나뉨
뮤터블 객체: 리스트, 딕셔너리, 셋
객체 생성 후 객체 수정 가능
my_list = [1, 2, 3, 4, 5]
my_list[4] = 6
print(my_list) # [1, 2, 3, 4, 6]
# my_list 가 참조하고 있는 [1, 2, 3, 4, 5] 에서 5번째 위치를 6으로 수정리스트(뮤터블 객체)
my_list = [1, 2, 3, 4, 5]
my_list2 = [1, 3, 5] + [7, 9]
my_list3 = list(my_list) #
print(my_list) # [1, 2, 3, 4, 5]
print(my_list2) # [1, 3, 5, 7, 9]
print(my_list3) # [1, 2, 3, 4, 5]- my_list3 = list(my_list)
: 파이썬은 리스트를 다른 변수에 할당할 때 해당 리스트의 복사본이 생성되는 것이 아니라 원본 리스트에 대한 참조가 새 변수에 할당되기 때문에 복사 개념과 같다.
리스트 인덱싱
인덱스를 활용해 특정 위치의 원소에 접근하는 것을 말함. '인덱싱으로 원소에 접근한다'고 표현한다.
my_list = [1, 2, 4]
my_list.append(6) # [1, 2, 4, 6]
del my_list[2] # [1, 2, 6]딕셔너리(뮤터블 객체)
key, value 쌍을 저장하는 해시테이블로 구성, 키를 사용해 값을 검색하는 자료형
# 딕셔너리 초기화
my_dict = {}# 딕셔너리 값 삽입
my_dict['apple'] = 1
my_dict['banana'] = 2
my_dict['orange'] = 3
print(my_dict) # {'apple': 1, 'banana': 2, 'orange' : 3}
# 딕셔너리 검색
key = "apple"
if key in my_dict:
value = my_dict[key]
print(f{"key}: {value}") # apple: 1
else:
print(f"{key}는 딕셔너리에 존재하지 않습니다.")
# 딕셔너리 수정
my_dict["banana"] = 4 # {'apple': 1, 'banana': 4, 'orange' : 3}
# 딕셔너리 삭제
del my_dict['orange']
print(my_dict) # {'apple':1, 'banana': 4}이뮤터블 객체: 정수, 부동소수점, 문자열, 튜플
객체 생성 후 객체 수정 불가능
a = 4
b = a # a = 4, b = 4 / b는 a가 아닌 a가 참조한 4를 참조
b += 2 # b = 6 / 정수는 이뮤터블 객체이므로 4를 수정하는 것이 아니라 6을 새로 참조함
print(a, b) # 4 6튜플(이뮤터블 객체)
한 번 생성하면 삽입하거나 삭제할 수 없음
# 튜플 초기화, () 를 활용
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:2]) # (2, )문자열(이뮤터블 객체)
문자들을 집합 형태로 구성한 이뮤터블 객체로, 문자열 추가 삭제 시 기존 객체 수정이 아닌 새로운 객체를 반환함
이뮤터블 객체: 정수, 부동소수점, 문자열, 튜플
객체 생성 후 객체 수정 불가능
string = "Hello"
string = string.replace("l", "") # "l" 을 모두 삭제
print(string) # Heo4-3. 함수
람다식
람다식은 함수를 더 간단히 표현하는 방법이며, 익명 함수를 만드는 데 사용한다. 익명 함수란 말 그대로 이름 없는 함수를 말하며 코드에서 딱 한 번 실행할 목적으로 사용하거나, 다른 함수의 인수로 사용하는데 활용한다.
람다식 정의
lambda x, y : x + y # x, y 를 받아서 더한 값을 반환하는 람다식람다식 사용
람다식은 변수로 참조할 수 있다.
변수에 람다식을 할당하고 람다식 실행이 필요한 경우 변수(a, b) 와 같이 호출할 수 있다.
add = lambda x, y : x + y # add 변수에 람다식 할당
print(add(5, 4)) # 9인수로 람다식을 넘길 수도 있다.
num = [1, 2, 3, 4, 5] # 리스트 선언
squares = list(map(lambda x: x**2, num)) # 람다식 넘기기
print(squares) # [1, 4, 9, 16, 26]먼저 정수형 리스트를 선언하고, map() 함수에 람다식을 넘긴다. 이렇게 하면 map() 함수는 2번째 인수로 넘어온 리스트 num 에 1번째 인수로 받은 람다식 x**2 를 적용하여 num의 원소를 각각 제곱한 새 리스트를 반환한다.
+map 함수란?
map(function, iterable)
= map(적용시킬 함수, 적용할 값들)
첫 번째 매개변수로는 함수가 오고,
두 번째 매개변수로는 반복 가능한 자료형(리스트, 튜플 등) 이 온다.
map 함수의 반환 값은 map 객체이기 때문에 해당 자료형을 list 혹은 tuple로 형 변환 시켜주어야 한다.
함수의 동작은 두 번째 인자로 들어온 반복 가능한 자료형 (리스트나 튜플) 을 첫 번째 인자로 들어온 함수에 하나씩 집어넣어서 함수를 수행한다.
# 예제1
result1 = list(map(int, [1.1, 2.2])) # [1, 2]
# 예제2
import math
def func_pow(x):
return pow(x, 5)
result2 = list(map(func_fow, [1, 2, 3])) # [1, 32, 243]4-4. 코딩테스트 코드 구현 노하우
조기반환
조기 반환, early return은
