코테 공부 [그리디]

[ 기본 원리 ]

탐욕적 : 매 순간마다 최선의 선택을 하는 알고리즘

노드 관점 : 루트 노드부터 거쳐가는 노드의 합을 최대로?

• 그리디 알고리즘은 실제로는 최적의 해가 아님

• 코딩 테스트에서는 최적의 해가 되는 경우에 한해서 출제

[ 거스름돈 문제 ]

거스름돈의 최소 개수

• 가장 큰 화폐부터

• 무조건 최소 개수가 연산되는 최적의 해

리스트 컴프리헨션

• 1차원

• 2차원

• 참고사항

튜플 (변경 불가)

• 최단 경로 (비용, 노드번호)

• 해싱 키 값

딕셔너리

• hashtable → 조회나 수정에 O(1)

집합

• 얘도 → 조회나 수정에 O(1 )

[ 입력 ]

공백을 기준으로 map

• 정수 입력

• 빠른 입력
• 이진 탐색, 그래프 정렬 등에서 사용

[ 출력 ]

• 기본

• f-string 문법

[ 람다식 ]

• 정렬 기준

• 각 리스트의 연산합

[ 라이브러리 ]

itertools

• 순열 조합
• 모든 경우의 수
• 완전 탐색

heapq

• 힙
• 우선순위 큐
• 다익스트라

bisect

• 이진탐색

collections

• deque

• counter 등

math

• factorial

• GCD (최대공약수)