알고리즘15 Python 자료구조 & 알고리즘 - 복잡도 1. 알고리즘 복잡도 표현방법 1-1. 알고리즘 복잡도 계산이 필요한 이유 하나의 문제를 푸는 알고리즘은 다양함 * 정수의 절대값을 구하는 방법 * 방법1 : 값이 음수인지 확인해서 0보다 작은 음수일 때 -1을 곱하기 * 방법2 : 정수값을 재곱한 값에 루트를 씌우기 디양한 알고리즘 중 어떤 알고리즘이 더 좋은지 분석하기 위해 복잡도를 정의하고 계산함 1-2. 알고리즘 복잡도 계산 항목 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈 시간 복잡도 : 알고리즘 실행 속도 1-3. 알고리즘 성능 표기법 오메가 표기법 알고리즘 최상의 실행 시간을 표기 세타 표기법 알고리즘 평균 실행시간을 표기 빅오 표기법 최악의 실행 시간을 표기 아무리 최악의 상황이라도 이 정도의 성능은 보장함을 의미 가장 많이 사용 1.. 2023. 2. 20. Python 자료구조&알고리즘 - 트리(Tree), 이진 탐색 1. 트리(Tree) Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조 트리중 이진 트리(Binary Tree)형태의 구조로 탐색(검색)알고리즘을 구현을 위해 많이 사용됨 2. 알아둘 용어 Node: 트리에서 데이터를 저장하는 기본 요소(데이터와 다른 연결된 노드에 대한 Branch 정보를 포함) Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 했을 때 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 상위 레벨에 연결된 노드 Child Node: 어떤 노드의 하위 레벨에 연결된 노드 Leaf Node: Child Node가 하나도 없는 노드 Sibling Node: 동일한 Parent Node를 가진 .. 2023. 1. 31. Python 자료구조&알고리즘 - 해쉬 테이블(Hash Table) 1. 해쉬 테이블(Hash Table) 키(key)에 데이터(value)를 저장하는 데이터 구조 파이썬에서는 딕셔너리(dick)타입이 해쉬 테이블의 예 key를 통해 데이터를 바로 찾을 수 있으므로 검색 속도가 빠름 보통 배열로 미리 Hash Table 사이즈 만큼 생성 후에 사용 2. 알아둘 용어 해쉬(Hash) : 임의의 값을 고정 길이로 변환하는 것 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해쉬 함수(Hashing Function) : key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 해쉬 값(Hash Values) 또는 해쉬 주소(Hash Address) : key를 해싱 하무로 연산해서 해쉬 값을 알아내고 이를 기반으로 해쉬 테이.. 2023. 1. 30. Python 자료구조&알고리즘 - 스택(stack) 1. 스택(stack) 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 구조 LIFO(Last Input First Out) 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 1-1. 스택의 구조 스택은 LIFO 또는 FILO 데이터 관리 방식 스택의 활용 : 컴퓨터 내부의 프로세스 구조의 함수 동작 방식 기능 push() : 데이터를 스택에 쌓기 pop() : 데이터를 스택에서 꺼내기 1-2. 스택의 장점 구조가 단순해서 이해와 구조가 쉬움 데이터 저장/읽기 속도가 빠름 데이터 최대 개수를 미리 정해야 함(파이썬의 쟝우 재귀함수는 1000번까지만 호출이 가능) 저장 공간의 낭비가 발생할 수 있음(미리 최대 개수만큼 저장공간을 미리 확보하기 때문) 스택은 단순하고 빠른 성능을 위해 사용하므로 보통 배열 .. 2023. 1. 27. 이전 1 2 3 4 다음
