Algorithms11 그림으로 개념을 이해하는 알고리즘 - CH 11 CH 11 더 공부해야할 것 - 이진 탐색 트리 : 왼쪽에는 더 작은 값은 가진 정점, 오른쪽에는 더 큰 값을 가진 정점이 위치 > 항목 탐색 시 평균적으로 O(log n), 최악의 경우 O(n) > 단점 : 임의 접근 불가, 트리가 얼마나 균형 잡혀 있는가에 따라 평균 성능 달라짐 ** B-트리 : 하나의 노드가 여러 데이터를 가질 수 있는 트리** 레드-블랙 트리 : 스스로 균형을 맞추는 이진 탐색 트리** 힙 트리 : 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 트리** 스플레이 트리 : 자주 탐색하는 키를 가진 노드가 루트에 가깝게 위치한 트리 - 역 인덱스 : 데이터 값과 위치를 매핑한 자료 구조 (검색 시스템에 유용)ex. 안녕 이라는 단어 검색 시 웹페이지 A, B를 보여줌 .. 2024. 6. 26. 17:40 그림으로 개념을 이해하는 알고리즘 - CH 10 CH 10 KNN 알고리즘 - KNN 알고리즘 : 가장 가까운 k개의 이웃과 비슷한 종류로 분류 1) 분류 : 그룹으로 나누기 2) 회귀 : (숫자로 된) 반응 예측 - 특징 추출 : 항목을 비교 가능한 몇 개의 숫자로 만드는 일 ** 코사인 유사도 : 두 벡터 사이의 각도 측정** 스팸 필터 : 나이브 베이즈 분류기 알고리즘 사용참고자료Hello Coding 그림으로 개념을 이해하는 알고리즘 2024. 6. 26. 17:14 그림으로 개념을 이해하는 알고리즘 - CH 09 CH 09 동적 프로그래밍 - 동적 프로그래밍 : 하위의 작은 문제(격자)를 풀어 이를 이용해 더 큰 문제를 푸는 방법 > 제한 조건이 주어졌을 때 무언가 최적화 해야하는 경우 유용 > 하위 문제가 서로 의존하지 않는 경우에만 사용 가능 * 최장 공통 부분 문자열 : 공통으로 가지는 가장 긴 부분 문자열* 최장 공통 부분열 : 순서가 바뀌지 않고 공통으로 들어간 글자의 갯수가 가장 긴 경우 ** 래밴슈타인의 거리 : 두 문자열의 유사성 측정 참고자료Hello Coding 그림으로 개념을 이해하는 알고리즘 2024. 6. 26. 17:09 그림으로 개념을 이해하는 알고리즘 - CH 08 CH 08 탐욕 알고리즘 - 탐욕 알고리즘 : 각각의 단계에서 최적의 수 찾기 (=국소최적해) > 최종적으로 전역 최적해를 산출 - 근사 알고리즘 : 정답과 가장 비슷한 값 유추 (정확한 답 계산에 시간이 너무 오래걸릴 경우) > 성능 기준 : 얼마나 빠른지, 최적해에 얼마나 가까운지 - 집합 커버링 문제 : 가능한 모든 집합을 계산해야 풀이 가능 > 모든 경우의 수를 따져서 최단/최소를 구하는 문제 => NP-완전 문제 ** NP-완전 문제 특징1) 항목에 적을 때는 알고리즘이 빠른데, 항목이 늘어나면 갑자기 느려짐2) 'X의 모든 조합'과 같은 표현3) 더 작은 하위 문제로 변환할 수 없어 X의 가능한 모든 버전을 계산해야하는 경우 ## CH 08. 탐욕 알고리즘states_needed = se.. 2024. 6. 26. 16:57 그림으로 개념을 이해하는 알고리즘 - Ch 07 CH 07 다익스트라 알고리즘 - 다익스트라 알고리즘 : 구간별 가중치가 있는 그래프에서 전체 가중치의 합이 가장 적은 구간 > 방향성 비순환 그래프(DAG) 또는 가중치가 양의 값인 사이클을 보유할 때만 적용 > 음의 가중치를 가진 그래프의 최단 경로 → 벨만-포드 알고리즘 (매 단계마다 모든 간선을 확인) - 사이클 : 어떤 쟁점에서 출발해서 한 바퀴 돌아 같은 쟁점에서 끝나는 경로 graph = {}graph["you"] = ["alice", "bob", "claire"]# 간선의 가중치graph["start"] = {}graph["a"] = {}graph["b"] = {}graph["fin"] = {}graph["start"]["a"] = 6graph["start"]["b"] = 2graph.. 2024. 6. 23. 16:16 그림으로 개념을 이해하는 알고리즘 - Ch 06 CH 06. 너비 우선 탐색 - 너비 우선 탐색 : 두 항목 간 최단 경로- 그래프 : 정점과 간선으로 이루어짐 > 바로 이어진 정점은 이웃 > 그래프 종류 : 방향, 무방향 > 키/값 쌍을 넣을 때 순서는 중요하지 않음 (해시테이블은 순서를 가지지 않으므로) > 최소 실행시간 : O(사람의 수 + 간선의 수) graph = {}graph["you"] = ["alice", "bob", "claire"]graph["bob"] = ["anuj", "peggy"]graph["alice"] = ["peggy"]graph["claire"] = ["thom", "jonny"]graph["anuj"] = []graph["peggy"] = []graph["thom"] = []graph["jonny"] =.. 2024. 6. 23. 15:45 그림으로 개념을 이해하는 알고리즘 - Ch 05 CH 05. 해시 테이블 - 해시 함수 : 문자열을 받아 숫자(인덱스)를 반환하는 함수 = 문자열에 숫자를 할당- 해시 테이블 (=딕셔너리=연관배열) : 해시 함수 + 배열, 키와 값으로 구성 최악의 경우 O(n) 최선의 경우 O(1) book = dict()book["apple"] = 0.67book["milk"] = 1.49book["avocado"] = 1.49print(book)print(book["avocado"]) - 해시 테이블 사용 예1. 조회 시 (전화번호부, DNS 확인 작업)phone_book = {} ## dict()phone_book["jenny"] = 8675309phone_book["emergency"] = 911print(phone_book["jenny"]) 2. 중복 방.. 2024. 6. 21. 22:35 그림으로 개념을 이해하는 알고리즘 - Ch 04 CH 04. 퀵 정렬 - 분할 정복 전략① 여러 작은 단계로 분할② 작은 단계 해결 # 분할 정복def sum(arr): total = 0 for x in arr: total += x return totalprint(sum([1, 2, 3, 4])) ** 유클리드 호제법 : 최대공약수 찾기 알고리즘https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm - 퀵 정렬 : 기준 원소를 기준으로 모든 원소를 기준 원소보다 큰지 작은지 분류 > 하위 배열이 정렬된 경우 : 왼쪽 배열 + 기준 원소 + 오른쪽 배열 > 하위 배열이 정렬되지 않은 경우 : 왼쪽, 오.. 2024. 6. 21. 17:58 그림으로 개념을 이해하는 알고리즘 - Ch 03 CH 03. 재귀 - 재귀 : 자기 자신을 호출하는 것 ** 주의해야할 점 : 무한 반복하는 함수 주의 → 언제 재귀를 멈출 지 정확하게 명시def look_for_key(box): for item in box: if item.is_a_box(): look_for_key(item) elif item.is_a_key(): print "열쇠를 찾았습니다" - 재귀 함수 구조 ① 기본 단계 (함수가 자기 자신을 다시 호출하지 않는 부분) ② 재귀 단계 (함수가 자기 자신을 호출하는 부분)def countdown(i): print i if i 1이면 i-1로 countdown 함수를 호출한다) countdown(i-1) countdown(5) - 호출 스택 :.. 2024. 5. 6. 10:16 이전 1 2 다음
