알고리즘 성능 평가와 python 수 자료형

알고리즘 성능 평가

 
<복잡도 개념>
복잡도 : 알고리즘의 성능을 나타내는 척도
- 시간 복잡도 : 입력 N에 대한 수행 시간 분석
- 공간 복잡도 : 입력 N에 대한 메모리 사용량 분석
 
<복잡도 표기 방법 - Big-O Notation>

 
<알고리즘 설계 시 복잡도를 고려해야 하는 이유>
코딩 테스트 문제에서 시간 제한이 통상 1~5초 가량이기 때문이다 !
채점용 서버에서 연산 횟수가 5억이 넘어가는 경우, python 기준으로 통상 5~15초 가량의 시간이 소요된다.
채점용 서버에서 약 1초의 2000만번 연산이 가능하다고 가정하고, 몇 초 걸릴지 예상해보기
 
<시간 제한 요구 사항에 따라 적절한 알고리즘 계산하는 사고 예시>
시간제한(수행시간 요구사항)을 문제에서 파악하기(option. 미언급시 보통은 5초)
e.g., 시간 제한이 1초인 문제일 때,

 
<알고리즘 문제 해결 과정>
1. 지문을 꼼꼼히 읽고 -> 컴퓨터적 사고로 문제를 잘게 쪼개서 정리하기
2. 요구사항(복잡도) 분석하 
3. 문제 해결을 위한 아이디어 찾기 : (핵심 아이디어를 캐치 한다면, 최대한 간결하게 작성할 수 있게 문제가 설계된다)
4. 소스코드 설계하기
5. 코딩하기
 
<수행 시간 측정할 수 있는 소스코드 예제>

import time
start_time = time.time() #측정 시작

#프로그램 소스 코드

end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력

 

파이썬 문법 - 수 자료형

 
<자료형>
- python은 기본 자료형이 가지고 있는 기능이 매우 다양해서 잘 알아두는 것이 중요하다.
list : 표준 라이브러리를 불러와 사용하지 않아도, 다른 언어에서 라이브러리 단에서 제공하는 것들을 쉽게 사용 가능
- 모든 프로그래밍은 '데이터'를 다루는 행위라고 정의할 수 있다. 따라서 '데이터'를 담는 자료형에 대한 이해가 중요 !
 
<수 - 정수형>
- 코딩테스트에서 출제되는 문제는 정수형을 주로 다룬다.

a = 1000
print(a) # 1000

a = -1
print(a) # -1

a = 0
print(a) # 0

a = int(10000.0) # 10000

 
<수 - 실수형>
- 파이썬에서는 변수에 소수점을 붙인 수를 대입하면 실수형 변수로 처리된다.
- 소수부가 0이거나, 정수부가 0일 때는 0을 생략 가능

a = .5
print(a) # 0.5

a = 7.
print(a) # 7.0

- 오늘날 가장 보편적으로 쓰이는 IEEE754 표준에서는 실수형을 저장하기 위해 4바이트 or 8바이트의 고정된 메모리 크기를 할당한다. => 컴퓨터 시스템은 실수 정보를 표현하는 정확도에 한계를 가진다.

a = 0.3 + 0.9
print(a) # 0.89999999999999

if a == 0.9
    print(True)
else
    print(False)
    
# False

- 실수 값을 제대로 비교하지 못해서 원하는 결과를 얻지 못할 수 있기 때문에 반올림 함수인 round() 함수를 사용한다.
e.g., round(0.8765,2) # 0.88 

a = 0.3 + 0.9
print(round(a,4))

if round(a,4) == 0.9:
    print(True)
else:
    print(False)
    
# True

 
<지수 표현 방식>
- e나 E를 이용한다. (e.g., 1e9 = 10의 9제곱)
- 유효숫자e지수 = 유효숫자 * 10지수
   1e8 = 1 * 10의 8제곱
- 지수 표현 방식은 실수로 인지된다.
- 임의의 큰 수를 표현하기 위해 자주 사용된다.
e.g., 도달할 수 없는 노드에 대하여 최단 거리를 무한(INF)로 설정하는 경우가 있다.
e.g., 최댓값이 10억 미만이라면, 무한의 값으로 1e9를 이용 가능하다.
 
<수 자료형의 연산>

• 파이썬에서 나누기 연산자(/) 사용시, 결과는 실수형으로 반환된다.
• 다양한 로직 설계시, 나머지 연산자(%)를 주로 이용한다.
• 몫을 얻기 위해 몫 연산자(//)를 사용
• 거듭 제곱 연산자(**)도 있다.
  => 제곱근을 구할 때에 사용할 수 있다. e.g., print(5 ** 0.5) # 2.23606797749979