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 한다는 것이고 이는 재귀적으로 문제를 해결해나간다는..

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

12345611+21+2+31+2+3+41+2+3+4+51+2+3+4+5+6 3번째 항은 2번째항 + 3, 4번재 항은 3번째 항 + 4n번째 항은 n-1번째 항 + n1번째 항은 참조당하기만 함!! 즉, base case는 Value로 구분되어지며, 1번항임.def triangle_number(n): if n == 1: return 1 return n + triangle_number(n-1)