재귀함수 썸네일형 리스트형 [Computer Science] 자료구조 다이나믹프로그래밍(Dynamic Programming) - 메모이제이션(Memoization) 다이나믹 프로그래밍 Dynamic Programming '문제의 일부분을 풀고 그 결과를 재활용하는 방법으로 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상 시키는 패러다임. 하나의 문제는 단 한번만 풀도록 하는 알고리즘 -탑다운과 보텀업으로 구성되어있다. DP를 사용하게 되는 상황 : 이진 검색, 최단경로 알고리즘, 최적화 문제, 외판원 문제 !!! 분할 정복과의 차이점? 분할정복(Divide and Conquer)과 유사한 개념. 분할정복 기법은 동일한 문제를 다시 푼다는 단점이 있다.(=부분 문제, 서브문의 중복) ('정렬'과 같은 문제는 다시 풀게 되는 단점 없다, 그 예시로 퀵정렬과 병합 정렬이 있고 이 또한 매우 빠름) 다이나믹 프로그래밍 방식 다이나믹 프로그래밍의 구현은 일반적으.. 더보기 [Computer Science] 자료구조 - 검색과 재귀(Searching and Recursion) 검색(Searching) 특정 노드를 추가하거나 삭제를 위해서는 검색이 우선되야 한다. 다양한 알고리즘을 활용하는 경우, 최적 알고리즘 경로를 측정하는데 쓰인다. 검색하는 컬렉션이 무작위이고 정렬되지 않은 경우, 선형검색이 기본적인 검색방법이다. linear search (선형 검색, (순차탐색)) 한 번에 하나씩 모두 검색 반복문을 활용해 배열의 변수(코드에서는 반복자 i)만큼 검색을 진행 # 선형 검색 알고리즘 # 하나의 반복문과 리스트의 인덱스, 조건문을 활용하여 특정값을 검색할 때까지 반복한다. def linear_search(arr, target): # 입력 배열 길이의 범위에서 각 idx를 반복 for idx in range(len(arr)): # 현재 idx의 항목이 비교 대상과 같은지 확인.. 더보기 이전 1 다음
