교육, 대외활동, 봉사95 [엘리스 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 9 - 알고리즘 1 재귀호출 여기서도 저번 강의와 비슷하게 알고리즘의 정의, 성질에 대한 내용으로 시작했다. 수학적 귀납법과 재귀적 증명법에 대한 개념도 나왔는데, 이는 재귀함수를 만드는 절차와도 비슷했다. 첫 단추인 기저조건 정하기가 참 중요하고 어려운 것 같다. 문제해결의 절차, 완전탐색, 시간 복잡도 문제 해결 절차를 잘 따라야 한다. 모든 경우를 탐색해도 괜찮은 경우라면 모든 경우를 탐색하는 방법으로 문제를 풀자. 분할정복법 분할정복으로 풀 수 있는 문제들 합병정렬 퀵정렬 거듭제곱 구하기 연속 부분 최대합 가장 가까운 두 점 찾기 히스토그램 탐욕적기법 순간의 최적의 선택이 궁극적으로 최적의 선택이라는 생각으로 문제를 해결하는 방식이다. 결정을 해야하는 순간마다 그 순간의 효용을 최대화하는 선택을 하는 것인데, 유현준.. 2021. 7. 11. [엘리스 AI 트랙 2기] Day 8 - 알고리즘 이론 강의 강사님의 좋은 말씀 이게(자료구조, 알고리즘) 하루아침에 되는 분야는 아니다 ~ 꾸준히 많이 해라~ 필수과목들도 공부하고, 좋은 책들(리팩토링 등)도 읽어봐라~~~ 재귀함수 자신을 재참조하는 함수 런타임 에러 ~ 콜스택 ~ 정렬 버블정렬: 플래그 두개를 세워 비교하면서 앞이 더 크면 스왑 O(N^2) 퀵 정렬: 피벗(기준)을 잡고 작은 건 왼쪽, 큰 건 오른쪽에 둔다. DFS, BFS DFS는 재귀(스택), BFS는 큐로 구현 가능 DP 메모이제이션 (기억하며 풀기), 재귀함수로 구현했으면 터졌을 텐데 DP로 하면 연산량을 엄청 줄여서 시간 복잡도를 어느정도 해결 탐욕 알고리즘 순간 순간의 최적해를 찾아 전체 문제를 해결하는 알고리즘. 전역최적해를 보장하지는 않는다. 강사님께서 굉장히 친절하시.. 2021. 7. 4. [엘리스 AI 트랙 2기] Day 7 - 자료구조 자료구조란? 자료을 어떻게 저장하여 삽입, 삭제, 추출 등을 빠르고 효과적으로 수행할 것인가? 내가 개발하고자 하는 프로그램의 원활한 작동을 위해 어떤 자료구조를 써야할까? 같은 숫자도 숫자형인지, 유니코드인지에 따라 완전히 다른 의미를 가질 수 있다. 배열, 연결리스트에 대해 학습했다. 스택과 큐 배열과 연결리스트를 사용하여 구현 트리 트리의 종류는 다양하게 있다. 이진트리 : 자식 노드를 최대 2개까지만 갖는 트리. 포화 이진 트리 : 모든 정점이 자식을 2개씩 갖고 모든 리프노드의 트리가 같은 트리 완전 이진 트리 : 마지막 깊이를 제외하고 모든 정점이 완전히 채워져있으며 가능한 한 왼쪽에 있는 트리 정 이진 트리 : 리프노드 제외하고 모든 노드가 2개의 자식을 갖는 트리 탐색방법은 크게 두가지이다.. 2021. 7. 4. 이전 1 2 3 4 5 6 7 8 ··· 24 다음