Algorithm/코드트리 (2) 썸네일형 리스트형 [코드트리 조별과제] 동적계획법 동적계획법: 큰 문제에 대한 답을 얻기 위해 동일한 문제이지만 크기가 더 작은 문제들을 먼저 해결한 뒤, 그 결과들을 이용해 큰 문제를 비교적 간단하게 해결하는 기법for loop 이용재귀함수 이용메모이제이션: 값을 기록하고, 그 기록한 값을 참조하는 것memoization 이용시에는 함수 도입부에 -1이 아닌 경우 memo 값을 반환해주는 코드를 작성그렇지 않은 경우라면 반환해줘야 하는 값을 memo에 저장해준 뒤 해당 값을 반환해주면 됨탑다운 방식Tabulationfor문 이용하는 방법Tabulation이용 시 배열의 이름은 보통 dp라고 지음바텀업 방식💡 이론적인 시간복잡도는 두 방법이 동일하나, 탑다운 방식은 함수를 재귀적으로 여러번 실행해야 하므로 함수 처리에 추가적인 시간이 약간 더 붙어 실.. [코드트리 조별과제] 이진탐색 이진탐색시간복잡도O(logN)루프 한 번 돌 때마다 다루는 구간의 길이는 반으로 감소, 구간의 길이가 1이 될 때까지 계속 반복해서 탐색⇒ 루프 내부의 시간복잡도: O(N)⇒ 루프는 약 logN번 돌게 됨이진탐색의 단점반드시 정렬이 되어야 함배열이 정렬된 상태가 아니라면 정렬을 하기 위한 추가적인 연산을 필요로 함 정리탐색을 여러 번 진행해야 한다면 이진탐색을 사용하는게 좋음가장 큰 값이나 값을 딱 한개만 찾는다면 굳이 이진탐색을 사용할 이유가 없음이진탐색 시 이중연결리스트를 사용하게 되면 mid 위치를 찾는데 O(N)의 시간이 걸리므로 O(logN)보다 시간이 더 걸림Lower Bound: 원하는 값 target 이상이 처음으로 나오는 위치= target 보다 같거나 큰 원소의 위치들 중 가장 작은 값.. 이전 1 다음
