코딩하는 문과생

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

대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다. 그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다. [1, 1, 2, 3, 5, 8, .] 지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다. 타일의 개수 N이 주어질 때, N개의 타일로..

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

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. def solution(numbers, target): cnt = 0 def operator(numbers, target, idx=0): if idx < len(number..