코딩하는 문과생

완전탐색 (Brute-Force) BP라고 불리는 완전탐색은 말 그대로 모든 경우의 수를 다 해보는 것! 알고리즘을 풀 때 강력한 방식이지만, 시간은 최대로 들어간다. 예를 들어 비밀번호가 4자리이고 숫자로만 이루어져 있다면, 0~9999까지 총 10,000가지의 경우의 수가 발생한다. 만약 한 숫자 당 1초가 걸린다면, 10,000초 = 2.7시간 정도 걸린다. 완전탐색을 풀기 위한 대표적인 4가지 1. for문 사용 2. 순열, 조합 사용 from itertools import permutations per = permutations(['빨','주','노','초'],2) from itertools import combinations com = combinations('1234',2) 3. 재귀함수 사..

탐욕 알고리즘(Greedy Algorithm)이란, 최적해를 구하는 데 사용되는 근사적인 방법으로 여러 경우 중 하나를 결정해야할 때마다 그 '순간'에 최적이라고 생각되는 것을 선택해 나가는 방식으로 최종적인 해답에 도달하는 최적화 방법이다. '순간'은 Local하게는 최적이지만, 그 선택을 계속 수집하여 Global하게 해답을 만들었다고 해서 그 결과가 반드시 최적이라는 보장은 없다. Greedy 알고리즘이 잘 동작하기 위해서? - Optimal Substructure(최적 부분 구조) : 부분 문제를 최적화하는 것이 곧 전체를 최적화하는 것이다. - Greedy Chocie Property(탐욕적 선택 속성) :각 단계에서의 탐욕스런 선택이 최종 답을 구하기 위한 최적의 선택 이 두가지 속성을 만족하..

동적계획법 : 어떤 문제에서 최적해를 구해야할 때, 문제를 더 이상 쪼갤 수 없는 단위로 쪼개서 제일 작은 부분부터 최적해를 누적해 나가는 방식으로 문제를 푸는 알고리즘 특징 - Overlapping Subproblems : 중복되는 하위문제가 있다. - Optimal Subproblems : 하위문제를 해결하면 원래문제를 해결할 수 있게 되는 구조다. 핵심: 초기조건 & 점화식 초기조건: 문제를 가장 작은 단위로 쪼개었을 때, 연산없이 확정되어있는 최적해 점화식: 부분 문제의 계산을 통해 전체 문제의 답을 구할 수 있도록 구성되어 있다. #재귀 사용 def fibonacci(i): if i

파이썬은 힙정렬을 위해 heapq라는 모듈을 제공한다. import heapq def heap_sort(nums): heap = [] for num in nums: heapq.heappush(heap, num) print(heap) sorted_nums = [] while heap: sorted_nums.append(heapq.heappop(heap)) print(sorted_nums) heap_sort([4, 1, 7, 3, 8, 5]) [출력] [1, 3, 5, 4, 8, 7] [1, 3, 4, 5, 7, 8]