내 개발공부 필기노트

1. 개념: 계층적인 구조를 가지는 트리중에서 각 노드의 자식이 최대 2개인 이진 트리이며, 정렬된 데이터를 빠르게 검색, 삽입, 삭제 할 수 있도록 설계된 자료구조 2. 구조와 특징1) 각 노드의 왼쪽 서브트리에는 "현재 노드보다 작은 값"이 저장됨2) 각 노드의 오른쪽 서브트리에는 "현재 노드보다 큰 값"이 저장됨3) 각 서브트리도 위의 규칙을 만족해야 함 8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13 3. 이진 탐색 트리의 연산1) 검색- 탐색과정① 루트에서 시작해서 찾고자 하는 값 X가 현재 노드 값보다 작으면 왼쪽으로 이동② 크다면 오른쪽으로 이동③ 탐색 2) 삽입- 삽입과정① 루트에서 ..

1. 해시테이블: 키(key) 값(value)을 한쌍으로 저장하는 구조. 키를 기준으로 값을 저장하는 구조.각 키는 해싱되어 값을 가리키는 고유한 식별자 역할대부분의 경우 O(1)의 시간복잡도를 가짐더보기* 해시 : 임의의 길이를 가진 데이터를 '해시 알고리즘'을 사용해 고정된 길이를 가진 데이터로 출력한 값1) 기본개념(1) 키 - 데이터를 저장하고 찾기 위해 사용되는 고유한 식별자 - 해시함수를 거쳐 데이터를 보관할 수 있는 식별코드(해시코드)로 전환된다. (2) 값 - 키를 기준으로 한 위치에 저장되는 데이터 - 키를 통해 값에 엑세스 할 수 있다. (3) 해시함수 - 입력된 키를 해시테이블의 주소(해시코드)로 변환하는 함수 - 자료구조의 성능을 결정짓는 중요한 요소 - 보관하고자 하는 테이블의 크..

스택과 큐는 배열, 리스트와 달리 인덱스를 통해 데이터에 접근 할 수 없음.원소의 삽입과 삭제를 자주 반복해야 할 경우 리스트보다 스택과 큐를 사용하는 것이 메모리 측면에서 훨씬 좋다.길찾기 문제에서 이동할 수 있는 다음 노드를 큐에 저장할 경우 BFS, 스택에 저장할 경우 DFS  1. 스택 (Stack) : LIFO (Last In First Out): 후입선출. 데이터를 추가할 때 탑을 쌓듯이 차곡차곡 데이터가 쌓이게 됨.데이터를 꺼내고자 하면 가장 최근에 쌓았던 데이터를 반환 받음.  1) 삽입: Stack.Push(); - 가장 마지막에 데이터를 추가하기 때문에 O(1)의 시간 복잡도를 가짐 - 단, 내부 배열 최대 크기에 도달했다면 두배 크기로 재할당하기 때문에 O(n)의 시간 복잡도를 가짐 ..

배열의 경우 미리 정해놓은 배열의 크기 이상의 데이터를 추가할 수 없다는 단점이 있다.(데이터를 더 많이 추가하고자 한다면 배열을 새로 할당하고 기존의 데이터를 옮겨줘야 함)그와 달리 리스트는 크기를 넘어서 데이터를 추가할 수 있다. 1. 리스트 (LIST ): 자료구조를 더 편하게 사용할 수 있게 제네릭으로 선언됐기 때문에 다양한 타입을 다룰 수 있고 *박싱과 *언박싱에서도 비교적 자유로운 모습을 보인다.더보기* 박싱 : 값 형식의 데이터를 참조 형식의 데이터로 변환하는 것* 언박싱 : 참조 형식의 데이터를 값 형식으로 변환하는 것박싱과 언박싱은 최적화의 관점에서 지양해야 함. - 리스트는 기존의 크기를 넘어서 데이터를 추가할 수 있다. - 단, 기존의 크기를 넘어설 경우 기존 크기의 2배를 메모리에 ..