개발자의 기록장 블로그

탈수가 나지 않으려면 현재 포인트에서 다음 포인트까지 물 소모량보다 물 용량이 작거나 같을때만 움직일 수 있다.만약 아니라면, 물을 채워주어야한다. 물을 채우면 다음 포인트까지 이동할 양도 빼주어야한다. def select_stops(water_stops, capacity): MaxCapacity = capacity capacity -= water_stops[0] container = [] for i in range(1, len(water_stops)): diff = water_stops[i] - water_stops[i-1] if capacity >= diff: capacity -= diff els..

logN의 시간복잡도를 가지려면 문제의 크기가 절반씩 줄어들어야 한다. 그렇다면 문제의 크기를 절반 씩 줄이는 것에 목표를 두자. power(3,5)라면, power(3,2) * power(3,2) * power(3,1) -> power(3,1)*power(3,1)*power(3,1)*power(3,1)*power(3,1)원래라면 5의 시간복잡도가 3이 됐다. 즉 y값에 따라서 문제의 크기를 절반씩 줄여주면 된다.  def power(x, y): if y == 0: return 1 if y % 2 == 0: return power(x, y//2)*power(x,y//2) else: return power(x,y//2)*power(x,y//2)*..

1. Brute Force기본 값으로 가장 첫 날의 수익을 지정 수익은 지금까지의 구한 수익 + 당일 수익 으로 구할 수 있다. def sublist_max(profits): profit = [profits[0]] for i in range(1, len(profits)): profit.append(profit[i-1] + profits[i]) return max(profit) 2. Divide and Conquer basecase는 start == end 수익율이 최대인 구간은 리스트 중앙을 기준으로 왼쪽에 있거나 오른쪽에 있거나 중앙을 관통할 수 있다.리스트를 좌 우 로 나누는 것은 재귀로 해결 중앙을 관통하는 구간의 최대값을 알기 위해서는 따로 함수의 분리 필요 -..

다이나믹 프로그래밍은 이름처럼 문제 해결과정을 역동적으로 진행해 나가는 알고리즘 풀이 방식이다.예를들어, divide and conquer 방식의 경우 문제의 크기를 줄여나가면서 그 문제를 정복해 나가며 합치는 과정을 진행한다. 하지만! 다이나믹 프로그래밍은 단순히 문제의 크기를 나누어 가는 것이 아니라, 중복된 부분에 대한 효율적인 처리 방법에 대해서 고민한다. 어떤 때에 이 방식을 사용할 수 있을까?최적부분구조가 있을 때중복된 부분이 있을 때. 최적 부분 구조란 부분문제의 '최적의 답'을 이용해 전체 문제의 '최적의 답'을 찾을 수 있는 구조이다.  예를들어 피보나치의 경우 전체 큰 문제를 계속 나눠가며 그 값들을 합쳐 올라가는데, 이 나누어진 값들을 최적부분구조라고 한다. *divide가 된다면, ..

문제의 크기가 너무나 커서 접근하기 어려울 때, 우리는 그 문제의 크기를 줄여나가면서 해결책을 찾아보기도 한다.예를들어 크기가 100인 문제가 있으면 이를 각각 50의 크기로 쪼개 부분문제를 만들어 이를 각각 해결하고,해결한 문제의 답을 합쳐서 100의 크기의 문제를 해결하는 식이다. 이 알고리즘은 총 3종류의 단계가 있다. DivideConquerCombineDivide 단계는 문제의 크기를 나누는 과정으로 문제의 크기를 계속 줄여준다는 점에서 recursive case로 표현된다Conquer 단계는 문제의 크기가 충분히 작아 답을 찾을 수 있는 단계라는 점에서 base case로 표현 가능하다.그런데... 이게 말처럼 쉽지는 않다.conquer를 하는 과정에서 문제 크기가 예상외로 충분히 작지 않아 ..

우리가 알고리즘 문제를 만났을 때, 가장 먼저 해보아야 할 방식이 Brute force 접근 방식이다.Brute = 무식한 , Force = 힘 으로, 무식하게 접근하는 알고리즘 문제 접근 방법이다. 해가 존재할 것이라 기대되는 영역의 처음부터 끝까지를 조사하는 방식으로, 알고리즘 설계 방식에서가장 기초적인 방식이라 할 수 있다.원하는 답을 설계시 영역을 잘 설정했다면 100% 얻어낼 수 있는 방식이지만 input이 매우 큰 경우에도 과연 그럴까? 이 알고리즘은 답을 찾을 확률이 상대적으로 높으나 반드시 찾을 수 있는 것은 아니다. input의 값이 매우 크거나 컴퓨터 성능이 좋지않다거나해서 모든 범위를 탐색하는 것이 유의미한 시간 범위를 넘어가는순간에 답을 찾는 것이 의미가 없어지는 상황이 발생할 수 ..

이진 탐색을 사용하기 위해선, 정렬된 리스트를 사용해야 한다고 했다. 그러면 그냥 sort 메소드나 sorted 함수를 사용하면 될탠데... 이런 기능이 어떻게 작동하는지 알아보자! 선택 정렬선택 정렬은 기준 값을 하나 선택해서 모든 다른 리스트의 값과 비교해가며 더 작은 값들을 찾아서 정렬해가는 알고리즘을 사용한다.-> 각 위치에 어떤 값이 들어갈지 찾는 것. def selectSort(list_): for i in range(len(list_)): minIndex = i for j in range(i+1,len(list_)): if list_[i] list_[j]: minIndex = j temp = list_..

우리가 늘상 사용하는 index(list, data)는 과연 어떤 원리로 동작하는 것일까?기본적으로 어떠한 리스트에서 데이터의 위치를 찾는 것을 목표로 동작해야한다. 즉, 데이터의 값이 어디있는지 찾고, 그 값의 인덱스를 리턴해주어야 한다. 우리는 보통 무언가를 찾을 때 처음부터 쭈욱~ 찾아보거나 어떤 기준을 잡고 살펴보기 시작한다.한 뭉텅이씩 눈에 들어오는 양만큼 그룹을 묶어서 찾는다거나, 절반을 먼저보고 나머지를 본다거나... 컴퓨터도 똑같이 리스트에서 데이터를 찾을 때, 처음부터 쭉 살펴보거나 어떠한 기준을 가지고 리스트를 살펴보기 시작한다. 가장 기본적인 탐색 방법으로 선형 탐색과 이진 탐색에 대해서 살펴보자. 선형 탐색선형 탐색은 말 그대로 리스트를 linear하게 살펴보면서 데이터의 위치를 찾..