1. O(n) 저장소 활용  값이 없으면 딕셔너리에 저장하고, 값이 있으면 그 즉시 원소를 리턴해주면 된다. def find_same_number(some_list): container = {} for ele in some_list: if ele in container: return ele container[ele] = True 2. 저장소 활용하지 않고 풀기  사실 N+1 크기의 리스트에 1~N까지 자연수가 할당되려면 무조건 중복되는 놈이 하나씩 생긴다.그 중복되는 값만 찾으면 되므로 중복되는 녀석이 있는 범위를 좁혀나가면서 구하면 될 듯 하다.줄여 나간다는 것은 divide 한다는 것이고 이는 재귀적으로 문제를 해결해나간다는..

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 수익율이 최대인 구간은 리스트 중앙을 기준으로 왼쪽에 있거나 오른쪽에 있거나 중앙을 관통할 수 있다.리스트를 좌 우 로 나누는 것은 재귀로 해결 중앙을 관통하는 구간의 최대값을 알기 위해서는 따로 함수의 분리 필요 -..

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