분류 전체보기33 트리 트리 계층적 구조가 있는 자료구조 계층적 관계가 있는 데이터를 컴퓨터에서 사용 컴퓨터과학의 다양한 문제 기발하게 해결 흔히 사용하는 여러 추상 자료형 구현 이진트리 각노가 최대 2개의 자식 노드를 가질수있는 트리 이진 트리 종류 정 이진 트리 (full binary tree) 2개 or 0개의 노드를 가지는 트리 완전 이진 트리 (complete binary tree) 마지막 레벨을 제외한 모든 레벨이 차있어야하며 마지막 레벨은 왼쪽에서 오른쪽으로 차있음 완전 이진 트리의 높이 O(lg(n)) 포화 이진 트리 (perfect binary tree) 모든 트리 처럼 모든 레벨이 빠짐없이 다 노드로 채워져있는 이진트리 높이나 노드수 둘중 하나만 알아도 다른 하나의 값을 알 수있다. 트리 순회 순회 : 자료구.. 2024. 1. 12. 추상 자료형 기능과 구현 기능 : 연산이 무엇을 하는지 구현 : 연산의 기능을 어떻게 하는지 추상 자료형 자료구조를 추상화 한 것 -> 데이터를 저장, 사용할 때 기능만 생각 추상화 구현을 몰라도 기능만 알면 프로그래밍을 할수있게 해주는 개념 자료구조는 구현까지 알아야해서 생각할 부분이 기능 뿐만 아니라 구현까지 해서 복잡해지지만 추상 자료형은 기능에만 집중 할 수있기 때문에 조금더 생각을 줄일 수있다. ⇒ 추상 자료형을 생각하면 코드의 흐름에 집중 할 수있다. 파이썬 추상화가 많이된 고수준 언어 많은 자료형 이름이 추상 자료형 리스트 데이터간 순서 관계를 유지 할 수있다. 접근 연산 : 특정 위치에 있는 데이터를 가지고 오거나 수정한다. 탐색 연산 : 특정 조건을 만족하는 데이터를 찾는다. 삽입 연산 : 특정 위치.. 2024. 1. 11. 해시테이블 해시함수 특정 값을 원하는 범위의 자연수로 바꿔주는 함수 해시함수의 조건 한 해시 테이블의 해시함수는 결정론적이어야한다. 결과 해시값이 치우치지 않고 고르게 나온다. 빨리 계산 할수 있어야 한다. 해시테이블 고정된 크기의 배열을 만든다. 해시함수를 이용해서 key를 원하는 범위의 자연수로 바꾼다. 해시함수 결과 값 인덱스에 key-value쌍을 저장한다. 충돌 (collision) 사용하고 있는 인덱스에 또 다른 키 밸류 쌍을 저장하는 것 Chaining 충돌이 일어나는 값들을 사슬처럼 묶는것 링크드 리스트를 통해 Chaining한 해시테이블 시간 복잡도 아래의 세연산은 모두 링크드 리스트의 탐색을 동반하기 때문에 O(n)의 시간 복잡도를 지닌다. 동작 (Operation) 시간 복잡도 탐색 (searc.. 2024. 1. 9. 링크드 리스트 싱글 링크드 리스트 데이터를 순서대로 저장해준다. 요소를 계속 추가 가능하다. 💡 노드들은 메모리상에서 여기저기 흩어져있다. 접근연산 O(n) : 무조건 처음부터 살펴봐야한다. 탐색연산 O(n) : 배열과 비슷하며 선형탐색으로 처음부터 하나씩 비교해봐야한다. 삽입/ 삭제 연산 O(1): 레퍼런스만 수정하는 연산으로서 순서에 상관없이 걸리는 시간이 항상 일정하다. 연산 시간 복잡도 접근 O(n) 탐색 O(n) 삽입 O(1) 삭제 O(1) 하지만! 내가 지우고자 하는 노드를 찾아와야하기 때문에 탐색과 접근 연산이 필요하다 그렇다면 위의 시간 복잡도는 아래와 같이 된다. 연산 링크드 리스트 접근 O(n) 탐색 O(n) 원하는 노드에 접근 또는 탐색 + 삽입 O(n+1) 원하는 노드에 접근 또는 탐색 + 삭제 .. 2024. 1. 8. 배열 C 배열과 파이썬 리스트 차이 C배열 : 메모리에 값자체를 연속적으로 저장한다 파이썬 리스트 : 메모리에 레퍼런스를 저장하고 이 레퍼런스는 다른 값들을 가르킨다. 💡 배열에서 값을 받아오거나 저장하는건 램의 특성으로 O(1)으로 접근 가능하다. 배열탐색 선형 탐색이라고도 불리며 인덱스 0번부터 차례대로 배열을 살펴본다. ⇒ 즉, 탐색은 O(n)이 걸린다. 정적 배열 : 크기가 고정된 배열 동적 배열 : 크기가 변하는 배열 정적 배열로 만들어진 자료 구조 정적 배열의 크기를 상황에 맞게 조절한다. 동적 배열 연산 추가연산 정적배열에 남는 공간이 있을때 O(1) 정적배열이 꽉찼을 때 : O(n) 분할 상환 분석 연산을 n번 했을 때 총 드는 시간 X를 n으로 나눠주는 할부 개념 ⇒ 최악의 경우로 시간 복잡도.. 2024. 1. 7. 이전 1 2 3 4 5 6 7 다음
