알고리즘3 [알고리즘] 이진탐색에서 한 나의 실수 1. left와 right 초기화 단순히 리스트의 길이를 right로 초기화 하면 인덱스의 길이와 맞지 않아 런타임 에러(IndexError)가 발생한다. lst = [1,2,3,4] # 인덱스의 최대값은 3, 길이는 4 left, right = 0, len(lst) -1 # 여기서 1을 빼주지 않으면 lst[4]를 할 수 있어 인덱스 에러 발생 2. while left target: right = mid - 1 elif ns[mid] < target: left = mid + 1 2022. 2. 19. [엘리스 AI 트랙 2기] Day 10 - 동적계획법, 그래프 동적계획법 정의 계산 복잡도가 큰 문제를 풀 때, 중복되는 문제는 풀지 않고 이전에 계산한 결과를 참조하여 중복 연산의 수를 줄여 빠르고 효율적으로 문제를 푸는 방식이다. 참조는 리스트의 인덱싱을 사용할 수도 있고 해시테이블(딕셔너리)를 사용할 수도 있다. 기저조건은 미리 딕셔너리나 리스트에 저장해두고 시작한다. 탑 다운 방식의 풀이 우리가 구하고자 하는 함수를 F라고 했을 때, F(n)의 값에서부터 f(n) = f(n-1) + f(n-2) 식으로 계속 내려와 기저조건까지 오는 방법이다. (딕셔너리 사용) 바텀-업 방식의 풀이 n=1일 때, n=2일 때 정도까지의 값을 미리 저장해두고, 리스트에 n=3, n=4, ... 처럼 하나씩 값을 계속 추가하면서 N까지 도달하는 방법이다. 그래프 그래프는 표현하는.. 2021. 7. 11. [엘리스 AI 트랙 2기] Day 8 - 알고리즘 이론 강의 강사님의 좋은 말씀 이게(자료구조, 알고리즘) 하루아침에 되는 분야는 아니다 ~ 꾸준히 많이 해라~ 필수과목들도 공부하고, 좋은 책들(리팩토링 등)도 읽어봐라~~~ 재귀함수 자신을 재참조하는 함수 런타임 에러 ~ 콜스택 ~ 정렬 버블정렬: 플래그 두개를 세워 비교하면서 앞이 더 크면 스왑 O(N^2) 퀵 정렬: 피벗(기준)을 잡고 작은 건 왼쪽, 큰 건 오른쪽에 둔다. DFS, BFS DFS는 재귀(스택), BFS는 큐로 구현 가능 DP 메모이제이션 (기억하며 풀기), 재귀함수로 구현했으면 터졌을 텐데 DP로 하면 연산량을 엄청 줄여서 시간 복잡도를 어느정도 해결 탐욕 알고리즘 순간 순간의 최적해를 찾아 전체 문제를 해결하는 알고리즘. 전역최적해를 보장하지는 않는다. 강사님께서 굉장히 친절하시.. 2021. 7. 4. 이전 1 다음