입출력시 공백으로 구분된 데이터의 개수가 많으면,
data = list(map(int,input(),split())으로 해주는 것이 좋다. 그게 아니고 데이터의 개수가 적다면
data = map(int,input(),split())으로 해줘도 된다.
만약에 PS 문제에서 시간초과 문제가 발생할 경우를 막기위해 속도가 최대한으로 빠른 방법도 존재한다. 외우자.
import sys
# 문자열 입력받기
data = sys.stdin.readline().rstrip()sys 라이브러리를 사용할 때는 한 줄 입력을 받고 나서 rstrip() 함수를 꼭 호출해야 한다. readline() 으로 입력하면 ㅇ비력 후 엔터가 줄 바꿈 기호로 입력되는데, 이 공백 문자를 제거하려면 rstrip() 함수를 사용해야 한다.
주요 라이브러리 6가지
내장함수 : print(), input() 과 같은 기본 입출력 기능부터 sorted() 와 같은 정렬 기능을 포함하고 있는 기본 내장 라이브러리이다. 파이썬 프로그램을 작성할 때 없어서는 안 되는 필수적인 기능을 포함하고 있다.
itertools : 파이썬에서 반복되는 형태의 데이터를 처리하는 기능을 제공하는 라이브러리이다. 순열과 조합 라이브러리를 제공한다.
heapq : 힙(Heap) 기능을 제공하는 라이브러리이다. 우선순위 큐 기능을 구현하기 위해 사용한다.
bisect : 이진 탐색(Binary Search) 기능을 제공하는 라이브러리이다.
collections : 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함하고 있는 라이브러리이다.
bisect
bisect_left(a,x) : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
bisect_right(a,x) : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드
부록 A완
그리디 - 현재 상황에서 지금 당장 좋은 것만 고르는 방법
그리디 알고리즘은 문제 유형이 너무나도 다양하기 때문에 외워봤자 의미가 없다.
보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 그리디 알고리즘은 대개 정렬 알고리즘과 짝을 이뤄 출제된다.
예제 3-1 거스름돈
손남에게 거슬러줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라.
그냥 '가장 큰 화폐 단위부터' 돈을 거슬러 주는것이다. 문제에서 나와 있는 돈의 단위는 500, 100, 50, 10 원 순이다.
n = int(input())
count = 0
coin_types = [500,100,50,10]
for coin in coin_types:
count += n // coin
n %= coin
print(count)위와 같이 코딩해주면 된다.
그리디 알고리즘의 정당성
그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아니다. 하지만 동전 문제처럼 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이다.
그리디 알고리즘으로 문제의 답을 찾았을 때는, 그 해답이 정당한지 검토해야 한다.
위 문제를 그리디로 풀 수 있었던 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 만약에 800원을 거스름돈으로 주어야 하고 동전은 500,400,100원 짜리가 존재 한다고 가정하자.
그리디 알고리즘으로 문제를 풀 경우에는 4개의 동전(500 + 100 + 100 + 100) 을거슬러 줘야 한다고 나오는데, 최적의 해는 2개의 동전 (400 + 400) 을 거슬러 주는 것이다. 이렇듯 대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
출처: https://itlearning.tistory.com/entry/TIL-20210524 [Write Code:티스토리]