[알고리즘 개념] 파이썬 문법

복잡도란?

알고리즘의 성능을 나타내는 척도

 

- 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

- 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

 

알고리즘 문제 해결 과정 

1. 지문 읽기 및 컴퓨터적 사고

2. 요구사항(복잡도) 분석

3. 문제 해결을 위한 아이디어 찾기

4. 소스코드 설계 및 코딩

 

수행시간 측정하기

import time
startTime = time.time() # 시간측정시작

# 프로그램 소스코드
endTime = time.time() # 시간측정종료
print("time", endTime - startTime) # 수행시간

 

 

파이썬 문법

 

○ 실수형

- 지수 표현 방식(실수)

유효숫자e지수 = 유효숫자 * 10지수 ex)1e9 = 10의 9제곱(1,000,000,000)

최단 경로 알고리즘에서는 도달할 수 없는 노드에 대하여 최단거리를 무한(INF)로 설정하기도 한다.

 

- 개발과정에서 실수 값을 제대로 비교하지 못하는 경우

반올림 round() 함수를 이용한다. ex) round(123.456, 2) => 123.46

 

- 사칙연산

나누기 연산자(/), 몫 연산자(//), 나머지 연산자(%), 거듭 제곱 연산자(**)

 

○ 리스트

1. 리스트 초기화

- ([]) : 대괄호 안에 원소를 넣어 초기화

- list() 혹은 []를 이요하여 비어있는 리스트 선언

 

2. 리스트의 슬라이싱

- 리스트에서 연속적인 위치를 갖는 원소들을 가져워야 할때 대괄호 안에 (:)을 넣어서 시작 인덱스와 끝인덱스를 설정할 수 있다.

- 끝 인덱스는 실제 인덱스보다 1을 더 크게 설정한다.

ex) a= [1,2,3,4,5,6,7] => print(a[1:3]) = [2,3,4]

 

3. 리스트 컴프리헨션

- 대괄호 안에 조건문과 반복문을 적용하여 리스트를 초기화한다.

ex) array = [i for i in range(3)] => print(array) = [0,1,2]

      array = [i i for i in range(10) if i %2 == 1] => print(array) = [1,3,5,7,9]

      array = [i*i for i in range(1,10)] => print(array) = [1,4,9,16,25,36,49,64,81]

- 2차원 리스트 초기화시 효과적으로 사용할 수 있다.

- N × N 크기의 2차원 리스트를 한 번에 초기화 해야 할 때 매우 유용합니다.

ex) array= [[0]*m for _in range(n)]

함수명
append()	변수명.append()	리스트에 원소를 하나 삽입
sort()	변수명.sort()	기본 정렬기능
reverse()	변수명.reverse()	리스트의 원소 순서를 뒤집음
insert()	변수명.insert(삽입위치, 삽입값)	특정 인덱스 위치에 원소 삽입
count()	변수명.count(특정값)	특정값을 가지는 데이터 개수 셈
remove()	변수명.remove(특정값)	특정값을 닺는 원소 제거(값이 여러개면 하나만 제거)

- 특정값을 가지는 원소 모두 제거하기

ex) remove_set = {3,5} result = [i for i in a if not in romve_set] 

 

○ 튜플 자료형

1. 튜플의 특성

- 리스트와 유사하지만 한번 선언된 값을 변경할 수 없다.

- 리스트는 대괄호[]를 이용하지만, 튜플은 소괄호 ()를 이용한다.

- 튜플은 리스트에 비해 상대적으로 공간 효율적이다.

2. 튜플을 사용하면 좋은 경우

- 서로 다른 성질의 데이터를 묶어서 관리해야 할 때

ex)  최단 경로 알고리즘에서는(비용, 노드 번호)의 형태로 튜플 자료형을 자주 사용한다.

 

- 데이터의 나열을 해싱(Hashing)의 키 값으로 사용해야 할 때

ex) 튜플은 변경이 불가능하므로 리스트와 다르게 키 값으로 사용될 수 있다.

 

- 리스트보다 메모리를 효율적으로 사용해야 할 때

 

○ 사전 자료형

1. 사전 자료형의 특성

- 키(Key)와 값(Value)의 싸을 데이터로 가지는 자료형

- '변경 불가능한(Immutable) 자료형'을 키로 사용할 수 있다.

- 파이썬의 사전 자료형은 해시 테이블을 이용하므로 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리할 수 있다.

 

2. 사전 자료형 관련 메서드

- 키 데이터만 뽑아서 리스트로 이용할 때는 keys() 함수를 이용

- 값 데이터만 뽑아서 리스트로 이용할 때는 values() 함수를 이용

 

○ 집합 자료형

1. 집합 자료형의 특징

-  중복을 허용하지 않고 순서가 없음

- 집합은 리스트 혹은 문자열을 이용해서 초기화 할 수 있는데 이 때 set()함수를 이용

- 중괄호 {}안에 각 원소를 콤마,를 기준으로 구분하여 삽입함으로써 초기

- 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리

- 합집합(A|B), 교집합(A&B), 차집합(A-B) 제공

- 새로운 원소 추가( add() ), 새로운 원소 여러개 추가( update([]) ) , 특정한 값을 갖는 원소 삭제( remove() ) 함수 제공

 

f-string

- 파이썬 3.6부터 사용 가능, 문자열 앞에 접두사 'f'를 붙여 사용하며 중괄호 안에 변수명을 기입하여 사용

ex) answer = 7 \n print(f:"정답{answer}입니다.") = 정답7입니다.

 

pass 키워드

- 아무것도 처리하고 싶지 않을 때 pass 키워드를 사용

ex) if score >= 80 pass

 

grobal 키워드

- 변수 지정시 해장 함수에서 지역변수를 만들지 않고, 함수 바깥에 선언된 변수를 바로 참조

 

○ 실전에서 유용한 표준 라이브러리

1. 내장함수 : 기본 입출력 함수부터 정렬 함수까지 기본적인 함수들을 제공

- 파이썬 프로그램 작성시 필요한 필수적인 기능을 포함

① eval() => 수식계산결과를 수형태로 반환 ex) eval("(3+5)*7") = 56

② sorted(array, key=labad x:x[1], reverse=True) = 두번째 원소를 오름차순으로 정렬

 

2. itertools : 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들을 제공

- 특히 순열과 조합 라이브러리는 코딩테스트에서 자주 사용

 

3. heapq : 힙 자료구조를 제공

- 일반적으로 우선순위 큐 기능을 구현하기 위해 사용

 

4. bisect  : 이진탐색 기능을 제공

 

5. collection : 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함

 

6. math : 필수적인 수학적 기능을 제공

- 펙토리얼, 제곱근, 최대공약수(GCD), 삼각함수 관련 함수부터 파이 같은 상수를 포함