스터디/알고리즘 공부

[이것이 코딩 테스트다] PS를 위한 파이썬 문법 (부록)

부록A : 파이썬 문법

1. 자료형

수 자료형

  • 정수형
  • 실수형(소수점 붙인 수)

지수형 1e9 ⇒ 1,000,000,000(10억)

round() 함수

round(실수형 데이터, 반올림하고자 하는 위치 - 1)

+) 흔히 코딩 테스트는 실수형 데이터를 비교할 때 소수점 다섯 번째 자리에서 반올림한 결과 같으면 정답으로 인정한다.

b = 0.3
c = 0.6
a = b+c
print(a)
print(round(a,4))

if(round(a,4) == 0.9) :
  print("True")
else:
  print("False")
  • 수 자료형의 연산
a = 7
b = 3

# 나누기(실수형으로 처리)
print(a / b)

# 나머지
print(a % b)

# 몫
print(a // b)

# 거듭제곱
print(a ** b)

# 제곱근
print(a ** 0.5)

 

리스트 자료형

c나 자바와 같은 프로그래밍 언어의 배열기능, 내부적으로 연결리스트 자료구조(append(), remove()등의 메소드 지원)

c++의 STL vector와 유사.

 

  • 리스트 만들기
a = [1,2,3,4,5,6,7,8,9]
print(a)

print(a[4])

# 빈 리스트 생성 방법 1)
a = list()
print(a)

# 빈 리스트 생성 방법 2)
a = []
print(a)

# 크기가 n이고, 모든 값이 0인 1차원 리스트 초기화
n = 10
a = [0] * n
print(a)

 

  • 리트스의 인덱스와 슬라이싱
a = [1,2,3,4,5,6,7,8,9]

# 두 번째 원소부터 네 번째 원소까지
print(a[1:4])

 

  • 리스트 컴프리헨션
# 리스트 초기화 방법 중 하나
array = [i for i in range(20) if i % 2 == 1]
print(array)

# 일반적인 소스코드
array = []
for i in range(20) :
  if (i % 2 == 1) :
    array.append(i)
print(array)

# 1부터 9까지의 수의 제곱 값을 포함하는 리스트
array = [i * i for i in range(1,10)]
print(array)

# N * M 크기의 2차원 리스트 초기화
n = 2
m = 3
array = [[0] * m for i in range(n)]
print(array)

array[1][1] = 5
print(array)

# N * M 크기의 2차원 리스트 초기화(잘못된 방법)
n = 3
m = 4
array = [[0] * m] * n
print(array)

array[1][1] = 5
print(array)
# 특정한 크기를 가지는 2차원 리스트를 초기화할 때에는 리스트 컴프리헨션을 이용해야 한다.

 

  • 리스트 관련 기타 메서드
a = [1,4,3]
print("기본 리스트 : ",a)

# 리스트에 원소삽입
a.append(2)
print("삽입 : ",a)

# 오름차운 정렬
a.sort()
print("오름차순 정렬 : ",a)

# 내림차순 정렬
a.sort(reverse = True)
print("내림차순 정렬 : ",a)

# 변수를 변경하지 않고 내장 함수를 사용해 정렬된 리스트 반환
b = [2,3,6,1,4]
result = sorted(b)

print(b)
print(result)

# 리스트 원소 뒤집기
a.reverse()
print("원소 뒤집기 : ",a)

# 특정한 인덱스에 데이터 추가
a.insert(2,3)
print("인덱스2에 3추가 : ",a)

# 특정 값인 데이터 개수 세기
print("값이 3인 데이터 개수 : ",a.count(3))

# (맨 앞의)특정 값 데이터 삭제
a.remove(3)
print("값이 3인 데이터 삭제 : ",a)
append() : O(1)
sort() : O(NlongN)
reverse(), insert(), remove(), count() : O(N)
a = [1,2,3,4,5,5,5]
remove_set = [3,5]

# remove_set에 포함되지 않은 원소들만 새로운 리스트에 저장
result = [i for i in a if i not in remove_set]
print(result)

 

 

문자열 자료형

 

  • 문자열 초기화
data = "Don't you know \"Python\""
print(data)

 

  • 문자열 연산
a = "Hello"
b = "World"
print(a + " " + b)
print(a * 3)

print(a[:2])

 

 

튜플 자료형

 

한번 선언된 값을 변경할 수 없다. (대입도 불가능)

튜플은 소괄호(()) 이용

일반적으로 그래프 알고리즘에서 사용

ex) 다익스트라 알고리즘 ⇒ 우선순위 큐에 들어간 값은 변경되지 않는다. ( +) (비용, 노드번호)와 같이 서로 다른 성질의 데이터를 함께 묶어 관리할 때 튜플을 사용)

 

 

사전 자료형

 

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

내부적으로 '해시 테이블'을 이용하여 데이터의 검색 및 수정에 있어 O(1)의 시간에 처리

data = dict()
data['사과'] = 'Apple'
data['바나나'] = 'Banana'
data['코코넛'] = 'Coconut'

print(data)

if '사과' in data :
  print("'사과'를 키로 가지는 데이터가 존재합니다.")

# 사전 자료형 관련 함수

# 키 데이터만 담은 리스트
key_list = data.keys()

# 값 데이터만 담은 리스트
value_list = data.values()

print(key_list)
print(value_list)

# 각 키에 따른 값을 하나씩 출력
for key in data : 
  print(data[key])

 

 

집합 자료형

 

중복을 허용하지 않는다.

순서가 없다(사전 자료형도 마찬가지).

검색의 시간 복잡도는 O(1)

어떤 원소가 존재하는지를 빠르게 확인하는 경우 자주 사용

# 집합 자료형 초기화 방법1
data = set([1,1,2,3,4,4,5])
print(data)

# 집합 자료형 초기화 방법2
data = {1,1,2,3,4,4,5}
print(data)
print(a in data)

# 집합 자료형의 연산
a = {1,2,3,4,5}
b = {3,4,5,6,7}

print(a|b)  #합집합
print(a&b)  #교집합
print(a-b)  #차집합

# 집합 자료형 관련 함수
a = {1,2,3}
print(a)

# 새로운 원소 추가
a.add(4)
print(a)

# 새로운 원소 여러 개 추가
a.update([5,6,7])
print(a)
 
# 특정한 값을 갖는 원소 삭제
a.remove(4)
print(a)
add(), remove() 함수는 모두 O(1)이다

 

 

2. 조건문

# 조건문의 값이 참이어도 아무것도 실행하고 싶지 않을때
score = 85

if score >= 80 :
  pass
else : 
  print("성적이 80점 미만입니다")
print("프로그램을 종료합니다")
# 코드가 한 줄일 경우 줄바꿈을 하지 않고 표현
score = 85

if score>=80 : result = 'Success'
else : result = 'Fail'
print(result)

# 조건부 표현식1
score = 60

result = "Success" if score >= 80 else "Fail"
print(result)

# 조건부 표현식2

a = [1,2,3,4,5,5,5]
remove_set = [3,4]

result = [i for i in a if i not in remove_set]
print(result)

 

 

3. 반복문

 

while문

i = 1
sum = 0

while i <= 9 :
  if i % 2 == 1 :
    sum += i
  i = i+1
print(sum)

 

for문

# range()값의로 하나의 값을 넣으면 0으로 시작
scores = [54,80,90,30,100]

for i in range(5) :
  if scores[i] >= 80 :
    print(i+1,"번 학생은 합격입니다.")

# continue를 만나면 반복문의 처음으로
black_list = {4,5}
for i in range(5) :
  if i + 1 in black_list :
    continue
  if scores[i] >= 80 :
    print(i+1,"번 학생은 합격입니다.")

# 이중 반복문
for i in range(2,10) :
  for j in range(1,10) :
    print(i,"*",j,"=",i*j)
  print()

 

 

4. 함수

# 함수 안에서 함수 밖의 변수 데이터를 변경해야 하는 경우
a = 0

def func() :
  global a
  a += 1

for i in range(10) :
  func()

print(a)  

# lambad 표현식
def add(a,b) :
  return a+b

# 일반적인 add()메서드 이용
print(add(2,4))

# lambda 표현식으로 구현한 add()메서드
print((lambda a,b : a+b)(3,4))

# lambda와 map으로 리스트 각 원소끼리 더하기
list1 = [1,2,3,4,5]
list2 = [6,7,8,9,10]

result = list(map(lambda a, b : a + b, list1, list2))
print(result)

 

 

5. 입출력

파이썬에서 입력을 할 경우, 구분자가 줄바꿈이라면 int(input()) 을 여러 번 사용하면 되지만,

구분자가 공백이라면, list(map(int, input().split)) 을 이용한다.

⇒ input으로 입력받은 문자열을 split()을 이용해 공백으로 나눈 리스트로 바꾼 후에, map을 이용하여 해당 리스트의 모든 원소에 int()함수를 적용한다.

⇒ 최종적으로 그 결과를 list()로 다시 바꿈으로써 입력받은 문자열을 띄어쓰기로 구분하여 각각 숫자 자료형으로 저장하게 된다.

# 구분자가 줄바꿈일 경우
n = int(input())

data = []
for i in range(n) :
  data.append(int(input()))

data.sort(reverse = True)
print(data)

# 구분자가 띄어쓰기일 경우
m = int(input())

data = list(map(int, input().split()))
data.sort(reverse = True)

print(data)

# 공백을 기준으로 구분하여 적은 수의 데이터 입력
n, m, k = map(int, input().split())
print(n,m,k)

# 이차원 배열 입력 초기화
n = int(input())
m = int(input())

arr = []
for i in range(n):
	arr.append(list(map(int, input().split())))

print(arr)

 

  • 입력의 개수가 많은 경우 입력을 빠르게 받기(그래프, 정렬 등)
# sys.stdin.readline().rstrip
import sys

data = list(map(int, sys.stdin.readline().rstrip().split()))
data.sort(reverse = True)
print(data)
주의) readline()으로 입력하면 입력 후 엔터가 줄바꿈 기호로 입력되는데, 이 공백문자를 제거하려면 rstrip() 함수를 사용해야 한다.

파이썬에서 출력을 할 경우, 각 변수를 콤마로 구분하여 출력하면 의도치 않은 공백이 삽입될 수 있다.

(문자열과 다른 자료형을 +연산자를 사용하여 출력하면 오류)

# 줄바꿈 하지 않고 출력
print("hello",end = ' ')
print("World!")

# 변수를 문자열로 바꾸어 +연산자를 사용하여 출력
answer = 7
print("정답은 " + str(answer) + "입니다.")

# 각 변수를 콤마로 구분하여 출력
print("정답은",answer,"입니다.")
Python 3.6 이상의 버전부터 f-string문법 사용 가능.
접두사 f를 붙임으로써 중괄호 안에 변수를 넣어 자료형 변환없이 문자열과 정수를 같이 출력
answer = 7
print(f"정답은 {answer}입니다.")

 

 

6. 주요 라이브러리의 문법과 유의점

 

표준 라이브러리란?

특정한 프로그래밍 언어에서 자주 사용되는 표준 소스코드를 미리 구현해 놓은 라이브러리

 

내장 함수

별도의 import 명령어 없이 사용

# sum()
# iterable한 개겣의 모든 원소의 합 반환
result = sum([1,2,3,4,5])
print(result)

# max(), min()
# 두개 이상의 파라미터 중 가장 큰 값(작은 값) 반환
result = max(3,4,56,2)
print(result)

# eval()
# 문자열 형식의 수식을 계산한 결과를 반환
result = eval("2 + 3 * 5")
print(result)

# sorted()
# iterable객체를 정렬한 결과 반환
list = [3,1,9,8,5]
result = sorted(list)
print(result)

result = sorted(list, reverse = True)
print(result)

# 리스트의 원소로 튜플이나 리스트가 존재하는 경우 특정한 기준에 따라 정렬 수행 가능(key속성)
result = sorted([('홍길동',35),('이순신',75),('아무개',55)],key = lambda x : x[1], reverse = True)
print(result)
주의) iterable 객체의 메서드인 sort()함수는 (list.sort()) 리스트 객체의 내부 값이 정렬된 값으로 변경된다. 그에 비해 sorted()는 정렬된 리스트를 반환만 한다.

 

itertools

반복되는 데이터를 처리하는 기능

(모든 경우의 수를 고려해야하는 완전탐색의 경우 자주 사용)

 

  • permutations (순열)

iterable객체에서(n개) r개의 데이터를 뽑아 일렬로 나열하는 모든 경우(순열)를 계산한다.

⇒ nPr = n * (n-1) * ... * (n - r + 1)

(permutations는 클래스이므로 초기화 이후에는 리스트 자료형으로 변환하여 사용한다)

# 리스트['A','B','C']에서 3개를 뽑아 나열하는 모든 경우 출력
from itertools import permutations

data = ['A','B','C']
result = list(permutations(data,3))

print(result)

 

  • combination (조합)

iterable객체에서 r개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우(조합)를 계산한다.

⇒ nCr = (n * (n -1) * ... * (n - r -1)) / r!

(combonations는 클래스이므로 초기화 이후에는 리스트 자료형으로 변환하여 사용한다.)

# 리스트 ['A,'B','C']에서 2개를 뽑아 순서에 상관없이 나열하는 모든 경우를 출력
from itertools import combinations

data = ['A','B','C']
result = list(combinations(data,2))

print(result)

 

  • product (원소를 중복하는 순열)

(permutations와 동일, but 중복을 허용)

from itertools import product

data = ['A','B','C']
result = list(product(data,repeat = 2))  # 중복 허용

print(result)

 

  • combinations_with_replacement (원소를 중복하는 조합)

(combinations와 동일, but 중복을 허용)

from itertools import combinations_with_replacement

data = ['A','B','C']
result = list(combinations_with_replacement(data,2))  # 중복 허용

print(result)

 

heapq

다익스트라 최단 경로 알고리즘 등 우선순위 큐 기능을 구현하기 위한 힙 기능 제공

파이썬의 힙은 최소힙(Min Heap)으로 구성

⇒ 힙에 원소를 전부 넣었다 빼는 것만으로 시간 복잡도 O(NlogN)

힙정렬의 시간 복잡도 → O(logN)

# 힙정렬(Quick Sort)을 heapq의 최소힙으로 구현하기
import heapq

def heapsort(iterable) :
  h = []
  result = []
  # 모든 원소를 차례대로 힙에 삽입
  for value in iterable :
    heapq.heappush(h,value)
  
  # 힙에 삽입된 모든 원소를 차례대로 꺼내에 담기
  for i in range(len(h)) :
    result.append(heapq.heappop(h))
  
  return result

result = heapsort([1,5,3,6,7,5,3,10])
print(result)
# 최대힙을 구현하여 오름차순 힙정렬 구현하기
import heapq

def heapsort(iterable) :
  h = []
  result = []
  # 원소를 삽입하기 전 부호를 바꾸어 저장
  for value in iterable :
    heapq.heappush(h,-value)
  
  # 힙에서 원소를 꺼낸 뒤 원소의 부호를 다시 바꾼다
  for i in range(len(h)) :
    result.append(-heapq.heappop(h))
  
  return result

result = heapsort([1,5,3,6,7,5,3,10])
print(result)

 

bisect

'정렬된 배열'에서 특정한 원소를 찾아야 할 때, 이진 탐색을 구현하기 위한 라이브러리

시간 복잡도는 O(logN)

# 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽/오른쪽 인덱스를 찾는 메서드
from bisect import bisect_left, bisect_right

a = [1,2,4,4,6]
x = 4

print(bisect_left(a,x))
print(bisect_right(a,x))
# bisect_left, bisect_right 두 메서드를 이용해 '정렬된 리스트'에서 값이 특정 범위에 속하는 원소의 개수를 구하는 메소드 구현
from bisect import bisect_left, bisect_right

def count_by_range(a,left_value,right_value) :
  left_index = bisect_left(a,left_value)
  right_index = bisect_right(a,right_value)
  return right_index - left_index

a = [1,2,3,3,3,3,4,4,8,9]

print(count_by_range(a,4,4))
print(count_by_range(a,3,8))
print(count_by_range(a,-2,2))

 

collections

유용한 자료구조를 제공

 

  • deque

일반적인 큐, 스택을 구현할 때 사용

리스트 자료형에 비해 앞쪽에 잇는 원소를 삭제하거나 앞쪽에 새 원소를 삽입할때 시간 복잡도가 O(1)

(리스트는 삽입, 삭제시 '가장 뒤쪽 원소'를 기준으로 하기 때문에 위의 두 경우 시간 복잡도가 O(N))

appendleft(), append(), popleft(), pop() 메서드 사용

from collections import deque

data = deque([2,3,4])
data.append(5)
data.appendleft(1)
print(data)

data.popleft()
print(data)

print(list(data))
# 리스트 자료형으로 변환

 

  • Counter

iterable객체가 주어졌을 때, 해당 객체 내부의 원소가 몇 번씩 등장했는지 세는 기능

from collections import Counter

counter = Counter(['red','blue','red','green','purple','blue','blue'])

print(counter['blue'])  # 'blue'가 등장하는 횟수 출력
print(counter['red'])
print(dict(counter))  # 사전 자료형으로 변환

 

math

자주 사용되는 수학적인 기능 포함

import math

# x!값을 반환하는 factorial(x)
print(math.factorial(3))

# 제곱근 값을 반환하는 sqrt(x)
print(math.sqrt(9))

# 최대공약수를 반환하는 gcd(a,b)
print(math.gcd(12,18))

print(math.pi)
print(math.e)
# 상수 pi와 자연상수 e

 

 

7. 자신만의 알고리즘 노트 만들기

예시)

'''2차원 리스트(행렬)를 90도 회전하는 메서드'''
def rotate_a_matrix_by_90_degree(a) :
  row_len = len(a)
  col_len = len(a[0])

  res = [[0]*row_len for _ in range(col_len)]
  for r in range(row_len) :
    for c in range(col_len) : 
      res[c][row_len-r-1] = a[r][c]
  return res

# 사용 예시
a = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
print(rotate_a_matrix_by_90_degree(a))
저작자표시

'스터디 > 알고리즘 공부' 카테고리의 다른 글

[바킹독의 실전 알고리즘] 0x03강 - 배열  (0) 2021.01.25
[바킹독의 실전 알고리즘] 0x01강 ~ 0x02강  (0) 2021.01.20