파이썬으로 코딩테스트 1

나동빈님 유투브 강의 보면서, youtu.be/m-9pAwq1o3w

내가 잘 안쓰거나 몰랐던 파이썬 문법/함수 등등 정리

 

 

알고리즘 측정시간

# 알고리즘 측정시간
import time
start_time = time.time() # 측정 시작

# 프로그램 소스코드
end_time = time.time() # 측정 종료
print('time: ', end_time - start_time) # 수행 시간 출력

 

파이썬의 실수형

오늘날 가장 널리 쓰이는 IEEE754 표준에서는 실수형을 저장하기 위해 4바이트, 혹은 8바이트의 고정된 크기의 메모리를 할당하므로,

컴퓨터 시스템은 실수 정보를 표현하는 정확도에 한계를 가집니다. 예를 들어, 10진수 체계에서는 0.3과 0.6을 더한 값이 0.9로 정확히 떨어집니다. 하지만 2진수에서는 0.9를 정확히 표현할 수 있는 방법이 없습니다. 컴퓨터는 최대한 0.9와 가깝게 표현하지만, 미세한 오차가 발생하게 됩니다. 이때, round를 사용하여 실수를 반올림하면 우리가 원하는 값을 얻을 수 있습니다. 

23 -> 10111

0.3 -> 0.0100110011.....(0011 무한반복)

소숫점 숫자를 2진수로 바꾸는 증명 영상 -> youtu.be/8afbTaA-gOQ

a = 0.3 + 0.6
print(a) # 0.89999999

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

# round 함수를 사용하기 -> 반올림
a = 0.3 + 0.6
print(round(a, 4))

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

 

 

리스트 자료형(List)

리스트 컴프리헨션(List Comprehension)

# 0부터 9까지의 수를 포함하는 리스트 
a = [i for i in range(10)]

print(a)

# 0부터 19까지의 수 중에서 홀수만 포함하는 리스트
array = [i for i in range(20) if i % 2 == 1]
# array = [i * i for i in range(1,10)]

print(array)

 

N x M 2차원 리스트를 초기화할 때 효과적

n = 4
m= 3
# array = [[0] * m for _ in range(n)]
# 잘못된 예시- 전체 리스트 안에 포함된 각 리스트가 모두 같은 객체로 인식
# 하나의 행이 모두 같은 주소값을 가지기 때문에 각 리스트가 모두 같은 객체로 인식됨
array = [[0] * m] * n
print(array)

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

 

리스트에서 특정 값을 가지는 원소를 모두 제거하기

a = [1, 2, 3, 4, 5, 5, 5]
remove_set = {3,5} # 집합 자료형

# remove_list에 포함되지 않은 값만을 저장
result = [ i for i in a if i not in remove_set]
print(result)

 

문자열 자료형 백슬래쉬 /를 사용하면 원하는 만큼 따옴표를 사용할 수 있다.

data = "Don't you knoow \"Python\"?"
print(data) # Don't you knoow "Python"?

 

 

튜플 자료형(Tuple)

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

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

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

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

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

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

 

 

사전 자료형(dictionary)

사전 자료형은 키와 값의 쌍을 데이터로 가지는 자료형입니다.

- 앞서 다루었던 리스트나 튜플이 값을 순차적으로 저장하는 것과는 대비됩니다.

사전 자료형은 키와 값의 쌍을 데이터로 가지며, 원하는 '변경 불가능한(Immutable) 자료형'을 키로 사용할 수 있습니다.

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

O(1) -> 상수의 시간

data = dict()
data['a'] = 1
data['b'] = 2

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

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

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

 

 

집합 자료형(set)

집합은 다음과 같은 특징이 있다. -> 사전 자료형(dictionary)와 비슷

-중복을 허용하지 않습니다.

-순서가 없습니다.

집합은 리스트 혹은 문자열을 이용해서 초기화할 수 있습니다.

-이때 set()함수를 이용합니다.

혹은 중괄호 ({}) 안에 각 원소를 콤마(,)를 기준으로 구분하여 삽입함으로써 초기화 할 수 있습니다.

데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리할 수 있습니다.

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

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

 

집합 자료형의 연산

기본적으로 집합 연산으로는 합집합, 교집합, 차집합 연산 등이 있습니다.

- 합집합: 집합 A에 속하거나 B에 속하는 원소로 이루어진 집합(A U B)

- 교집합: 집합 A에도 속하고 B에도 속하는 원소로 이루어진 집합(A ∩ B)

- 차집합: 집합 A의 원소 중에서 B에 속하지 않는 원소들로 이루어진 집합(A - B)

a = set([1, 2, 3, 4, 5])
b = set([3, 4, 5, 6, 7])

# 합집합
print(a | b) # {1, 2, 3, 4, 5, 6, 7}

# 교집합
print(a & b) # {3, 4, 5}

# 차집합
print(a - b) # {1, 2}

집합 자료형의 추가 및 수정, 삭제

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

# 새로운 원소 추가
data.add(4)
print(data) # {1, 2, 3, 4}

# 새로운 원소 여러 개 추가
data.update([5, 6])
print(data) # {1, 2, 3, 4, 5, 6}

# 특정한 값을 갖는 원소 삭제
data.remove(3)
print(data) # {1, 2, 4, 5, 6}

 

 

사전 자료형과 집합 자료형의 특징

리스트나 튜플은 순서가 있기 때문에 인덱싱을 통해 자료형의 값을 얻을 수 있습니다.

사전 자료형과 집합 자료형은 순서가 없기 때문에 인덱싱으로 값을 얻을 수 없습니다.

- 사전의 키(Key) 혹은 집합의 원소(Element)를 이용해 O(1)의 시간 복잡도로 조회합니다.

 

 

자주 사용되는 표준 입력 방법

input() 합수는 한 줄의 문자열을 입력 받는 함수입니다.

map() 함수는 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용합니다.

예시) 공백을 기준으로 구분된 데이터를 입력 받을 때는 다음과 같이 사용합니다.

list(map(int, input().split()))

예시) 공백을 기준으로 구분된 데이터의 개수가 많지 않다면, 단순히 다음과 같이 사용합니다.

a, b, c = map(int, input().split())

 

 

 입력을 위한 전형적인 소스코드 1)

# 데이터의 개수 입력
n = int(input())

# 각 데이터를 공백을 기준으로 구분하여 입력
data = list(map(int, input().split()))
# data = input().split() # 각 원소들이 문자열로 출력

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

 

입력을 위한 전형적인 소스코드 2)

# n, m, k를 공백을 기준으로 구분하여 입력
n, m, k = map(int, input().split())

print(n, m, k) # 순서가 달라도 되고 같은 원소 중복되어도 된다.

 

 

빠르게 입력 받기

사용자로부터 입력을 최대한 빠르게 받아야 하는 경우가 있습니다.

파이썬의 경우 sys 라이브러리에 정의되어 있는 sys.stdin.readline()메서드를 이용합니다.

- 단, 입력 후 엔터(Enter)가 줄 바꿈 기호로 입력되므로 rstip() 메서드를 함께 사용합니다.

import sys

# 문자열 입력 받기
data = sys.stdin.readline().rstrip() # rstrip을 사용하면 줄바꿈도 같이 출력된다.
print(data)

 

 

출력을 위한 전형적인 소스코드

# 기본적으로 파이썬은 출력을 하게 되면 줄바꿈이 일어나는데, 이를 막기 위한 방법
# 출력할 변수들
a = 1
b = 2
print(a, b)
print(7, end=' ') # 7 뒤에 다음 것을 출력할 수 있는 ' '을 만든다.
print(8, end=' ')

# 출력할 변수
answer = 7
print('정답은' + str(answer) + '입니다.') # 7 8 정답은7입니다. 

 

 

조건문의 간소화

score = 85

if score >= 80: result = 'Success'
else: result = 'Fail'

result = 'Success' if score >= 80 else 'Fail'

print(result) # Success

 

 

global 키워드

# global 키워드로 변수를 지정하면 핻ㅇ 함수에서는 지역 변수를 만들지 않고,
# 함수 바깥에 선언된 변수를 바로 참조하게 됩니다.

a = 0

def func():
    global a
    a = a + 1

for i in range(10):
    func()

print(a) # 10

 

함수에서 전역변수 값을 참조해서 값을 바꾸고자 할 때,  global임을 꼭 밝히는 것이 좋다.

array = [1, 2, 3, 4, 5]

def func():
    global array
    array = [3, 4, 5]
    array.append(6)

func()
print(array) # [3, 4, 5, 6]

 

 

 람다 표현식(lambda)
 람다 표현식을 이용하면 함수를 간단하게 작성할 수 있습니다.
- 특정한 기능을 수행하는 함수를 한 줄에 작성할 수 있다는 점이 특징입니다. 

def add(a,b):
    return a + b

# 일반적인 add() 메서드 사용
print(add(3, 7)) # 10

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

 

람다 표현식 예시: 내장 함수에서 자주 사용되는 람다 함수

array = [('홍길동', 50), ('이순신', 32), ('아무개', 74)]

def my_key(x):
    return x[1]

# 참고로 sorted는 오름차순이 기본 => reverse = True는 내림차순
print(sorted(array, key=my_key))
print(sorted(array, key=lambda x: x[1]))

 

람다 표현식 예시: 여러 개의 리스트에 적용

list1 = [1, 2, 3, 4, 5]
list2 = [6, 7, 8, 9, 10]

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

print(list(result)) # [7, 9, 11, 13, 15]

 

 

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

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

- 파이썬 프로그램을 작성할 때 없어서는 안 되는 필수적인 기능을 포함하고 있습니다.

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

- 특히 순열과 조합 라이브러리는 코딩 테스트에서 자주 사용됩니다. -> 완전탐색문제에서 소스코드를 간결하게 작성 가능

heapq : 힙(heap) 자료구조를 제공합니다.

- 일반적으로 우선순위 큐 기능을 구현하기 위해 사용됩니다. -> 다이스트라같은 최단경로

bisect : 이진 탐색(Binary Search) 기능을 제공합니다.

collections : 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함합니다.

math : 필수적인 수학적 기능을 제공합니다.

- 팩토리얼, 제곱근, 최대공약수(GCD), 삼각함수 관련 함수부터 파이(pi)와 같은 상수를 포함합니다.

 

# eval()
result = eval('(3+5)*7')
print(result) # 56

 

 

순열과 조합

모든 경우의 수를 고려해야 할 때 어떤 라이브러리를 효과적으로 사용할 수 있을까요?

 

순열: 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열하는 것

- {'A', 'B', 'C'} 에서 세 개를 선택하여 나열하는 경우

[('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]

from itertools import permutations

data = ['A', 'B', 'C'] # 데이터 준비

result = list(permutations(data, 3)) # 모든 순열 구하기
print(result)

 

조합: 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하는 것
{'A', 'B', 'C'}에서 순서를 고려하지 않고 구 새를 뽑는 경우: [('A', 'B'), ('A', 'C'), ('B', 'C')]

from itertools import combinations

data = ['A', 'B', 'C'] # 데이터 준비

result = list(combinations(data, 2)) # 2개를 뽑는 모든 조합 구하기
print(result)

 

중복 순열과 중복 조합

 

중복 순열: [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]

from itertools import product

data = ['A', 'B', 'C'] # 데이터 준비

result = list(product(data, repeat=2)) # 2개를 뽑는 모든 순열 구하기 (중복 허용)

print(result) # [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]

중복 조합: [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

data = ['A', 'B', 'C'] # 데이터 준비

result = list(combinations_with_replacement(data, 2)) # 2개를 뽑는 모든 조합 구하기(중복 허용)

print(result) # [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

 

 

파이썬 collections 라이브러리의 Counter는 등장 횟수를 세는 기능을 제공합니다.

리스트와 같은 반복 가능한(iterable) 객체가 주어졌을 때, 내부의 원소가 몇 번씩 등장했는지를 알려줍니다.

from collections import Counter

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

print(counter['blue']) # 3
print(counter['green']) # 1
print(dict(counter)) # {'red': 2, 'blue': 3, 'green': 1}

 

 

최대 공약수를 구해야 할 때는 math 라이브러리의 gcd() 함수를 이용할 수 있습니다.

import math

# 최소 공배수(LCM)를 구하는 함수
def lcm(a, b):
    return a * b // math.gcd(a,b)

a = 21
b = 14

print(math.gcd(21, 14)) # 최대 공약수(GCD) 계산
print(lcm(21, 14)) # 최소 공배수(LCM) 계산
# 7
# 42