알고리즘 성능평가
•
시간복잡도
array = [3, 5, 1, 2, 4]
## 시간 복잡도: O(N^2)
for i in array:
for j in array:
temp = i * j
print(temp)
## 알고리즘 문제 해결 과정
## 1. 지문읽기 및 컴퓨터적 사고
## 2. 요구사항(복잡도) 분석
## 3. 문제 해결을 위한 아이디어 찾기
## 4. 소스코드 설계 및 코딩
## => 핵심 아이디어 캐치하면 간결하게 소스코드 작성하는 형태로 문제 출제
Python
복사
•
파이썬 시간 계산해주는 코드
import time
start_time = time.time() # 측정 시간
# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력
Python
복사
자료형
•
프로그래밍은 결국 데이터를 다루는 행위.
◦
정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 사전 등이 있음.
◦
파이썬의 자료형은 필수적으로 알아야 한다!
•
정수형: 정수를 다루는 자료형이다.
◦
양의 정수, 음의 정수, 0이 포함된다.
•
실수형: 소수점 아래의 데이터를 포함하는 수 자료형
◦
변수에 소수점을 붙인 수를 대입하면 실수형 변수로 처리된다.
◦
소수부가 0이거나, 정수부가 0인 소수는 0을 생략하고 작성할 수 있다.
•
지수 표현 방식
◦
파이썬에서는 e나 E를 이용한 지수 표현 방식을 이용할 수 있다.
◦
최단 경로 알고리즘에서는 도달할 수 없는 노드에 대하여 최단 거리를 무한(INF)로 설정한다.
◦
지수 표현 방식은 임의의 큰 수를 표현하기 위해 자주 사용된다.
◦
가능한 최댓값이 10억 미만이라면 무한(INF)의 값으로 1e9를 이용할 수 있다.
•
나누기, 나머지 연산자
◦
파이썬에서는 나누어진 결과를 실수형으로 반환한다.
◦
다양한 로직을 설계할 때 나머지 연산자(%) 를 이용해야 할 때가 많다
◦
파이썬에서는 몫을 얻기 위해 몫 연산자(//) 를 이용한다.
리스트 자료형
•
여러 개의 데이터를 연속적으로 담아 처리하기 위해 사용하는 자료형
◦
Array의 기능과 유사한 기능을 지원.
◦
리스트 대신에 배열 혹은 테이블이라고 부르기도 한다.
◦
비어 있는 리스트 선언 시 list() 혹은 간단히 [] 를 이용할 수 있다.
◦
리스트의 원소에 접근할 때는 인덱스(Index) 값을 괄호에 넣는다.
◦
리스트 컴프리핸션
▪
대괄호 안에 조건문과 반복문을 적용하여 리스트를 초기화 할 수 있다.
▪
2차원 리스트 초기화할 때 효과적으로 사용될 수 있다.
•
특히 N X M 크기의 2차원 리스트를 한 번에 초기화 해야 할 때 매우 유용하다.
◦
array = [[0] * m for _ in range(n)]
◦
참고 코드
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(a)
print(a[3])
n = 10
a = [0] * n
print(a)
print(a[7])
# 뒤쪽에서는 -1부터 시작
print(a[-1])
# 슬라이싱
print(a[1 : 4])
# 0부터 9까지의 수를 포함하는 리스트
# 리스트 컴프리핸션 - i for i in range(10)
array = [i for i in range(10)]
print(array)
# 0부터 19까지의 수 중에서 홀수만 포함하는 리스트
array = [i for i in range(20) if i % 2 == 1]
print(array)
# 1부터 9까지의 수들의 제곱 값을 포함하는 리스트
array = [i * i for i in range(1, 10)]
print(array)
Python
복사
•
언더바 언제 사용?
◦
반복을 수행하되 반복을 위한 변수의 값을 무시하고자 할 때 언더바(_)를 자주 사용
for _ in range(5):
print("Hello World")
Python
복사
•
기타 메소드
•
특정 값을 가지는 원소 모두 제거하기
문자열 자료형
•
문자열 변수 초기화 시 큰따옴표(”) 나 작은 따옴표(’)를 이용해야 한다.
•
문자열 안에 큰따옴표나 작은따옴표가 포함되어야 하는 경우도 있다.
•
백슬래시(\)를 사용하면, 큰따옴표나 작은따옴표를 원하는 만큼 포함시킬 수 있다.
•
문자열 변수에 덧셈(+)을 이용하면 문자열이 더해져서 연결된다.
•
문자열은 특정 인덱스의 값을 변경할 수는 없다 (Immutable).
튜플 자료형
•
튜플은 한 번 선언된 값을 변경할 수 없다.
•
리스트는 대괄호([])를 이용하지만, 튜플은 소괄호(())를 이용한다.
•
튜플은 리스트에 비해 상대적으로 공간 효율적이다.
•
튜플의 장점
◦
서로 다른 성질의 데이터를 묶어서 관리해야 할 때
◦
최단 경로 알고리즘에서는 (비용, 노드 번호)의 형태로 튜플 자료형을 자주 사용한다.
◦
데이터의 나열을 해싱(Hashing)의 키 값으로 사용해야 할 때
▪
튜플은 변경이 불가능하므로 리스트와 다르게 키 값으로 사용될 수 있다.
◦
리스트보다 메모리를 효율적으로 사용해야 할 때