[방학의 PS] 그리디 알고리즘 - BOJ_1931, BOJ_1541
그리디 알고리즘의 정의 그리디 알고리즘이란 어떤 문제를 해결해야 할 때, 그 문제를 반복되는 여러 단계로 나눈 뒤에, 각 단계의 문제에 대한 최적해를 구하는 것을 반복하는 알고리즘입니다. 그리디 알고리즘의 예 간단한 예를 통해 말씀드리면, 거스름돈 구하기 문제를 셍각해 볼 수 있습니다. 만일 여러분이 편의점 알바생이고, 손님에게 X원의 현금을 거슬러주어야 할 때, 누구나 자연스럽게 가장 큰 단위의 화폐부터 거슬러주게 됩니다. 예를 들어 6670원을 거슬러준다면, 5000원짜리 한 장, 1000원 짜리 한 장, 500원 한 개, 100원 한 개, 50원 한 개, 10원 2개 순서로 거슬러 드릴 것입니다. 즉 X원을 거슬러 드리는 문제를 5000원을 거슬러 드리는 문제, 1000원을 거슬러 드리는 문제.....
2022. 7. 2. 04:21
[방학의 PS] set, deque, 리스트의 참조 복사
오늘은 원래 DFS와 BFS를 공부하고자 하였으나, 몇 가지 추가적인 공부가 필요하여 이를 보충하도록 하겠습니다. 1. set set은 파이썬의 데이터 타입입니다. 딕셔너리나 리스트와 같이 말입니다. 이는 수학에서 집합과 매우 유사한 특징을 지니는데, 우선 다음과 같이 선언 및 정의하게 됩니다. s1 = set([1, 2, 3, 3]) # [1, 2, 3, 3]이라는 리스트를 set 자료형으로 바꿔 s1에 저장한다는 의미입니다. s1 >> {1, 2, 3} set의 중요한 특징은 다음과 같습니다. 중복을 허용하지 않는다. 순서가 존재하지 않는다. 위의 코드에서 보신 것처럼 set은 중복을 허용하지 않습니다. 또한 순서가 존재하지 않는데, 이는 인덱스로 접근할 수 없다는 것을 의미합니다. 예를 들면 s1 ..
2022. 6. 15. 06:35
