하지의 코딩일지/STUDY MEMO[BACKEND]17 이진 탐색 트리 왼쪽 자식 노드의 키는 부모 노드의 키보다 작음 오른쪽 자식 노드의 키는 부모 노드의 키보다 큼 각각의 서브 트리도 이진 탐색 트리를 유지 중복된 키를 허용하지 않음 이진 탐색 트리의 특징 이진 탐색 트리 규칙에 의해 데이터가 정렬됨 이진 트리에 비해 탐색 빠름 (균형 유지 필요) -균형 상태 : O (log N) -불균형 상태 : O (N) 이진 탐색 트리 -탐색 찾고자 하는 데이터를 루트 노드부터 비교 시작 대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동 찾는 데이터가 없으면 null을 반환 어떤 데이터를 찾더라도 최대 트리 높이만큼의 탐색이 이루어짐 이진 탐색 트리 - 삽입 Root 부터 비교 시작(중복 키 발견 시 노드 추가하지 않고 종료) 삽입할 키가 현재 노드의 키보다 .. 2023. 8. 3. 프로그래머스 코딩 테스트 메모장 Arrays.copyOfRange() 메서드는 다음과 같이 사용됩니다: javaCopy code public static T[] copyOfRange(T[] original, int from, int to) original: 원본 배열 from: 복사를 시작할 인덱스 (이 인덱스를 포함하여 복사) to: 복사를 끝낼 인덱스 (이 인덱스는 포함하지 않음) Arrays.copyOfRange() 메서드는 from 인덱스부터 to-1 인덱스까지의 요소를 복사하여 새로운 배열을 생성하고 반환합니다. from과 to는 배열의 유효한 인덱스 범위 내에서 지정되어야 합니다. 2023. 7. 29. 힙(Heap) 2023. 7. 18. 해시 테이블(Hash Table) @키(key), 값(Value)을 대응시켜 저장하는 데이터 구조 - 키를 통해 해당 데이터에 빠르게 접근 가능 @해싱 - 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정 해시 테이블 구조 키: 해시 테이블 접근을 위한 입력 값 해시 함수 : 키를 해시 값으로 매핑하는 연산 해시 값: 해시 테이블의 인덱스 해시 테이블 : 키-값을 연관시켜 저장하는 데이터 구조 해시 충돌 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우 -서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우 해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있음 해시 충돌 해결 방법 (1) 개방 주소법(Open Address) - 충돌 시 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장 .. 2023. 7. 13. 연결 리스트(Linked List) 데이터를 링크로 연결해서 관리하는 자료구조 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않음 연결 리스트의 장점 데이터 공간을 미리 할당할 필요 없음 즉, 리스트의 길이가 가변적이라 데이터 추가/삭제 용이 연결 리스트의 단점 연결 구조를 위한 별도 데이터 공간 필요 연결 정보를 찾는 시간이 필요(접근 속도가 상대적으로 느림) 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요' 연결 리스트 기본 구조 노드(Node) -데이터 저장 단위로, 값과 포인터로 구성 포인터(Pointer) : 다음 노드와 이전 노드의 연결 정보 데이터 추가 -데이터 추가 위치(head, 중간, tail)에 따른 연결 작업 필요 1. 추가할 데이터를 담을 노드 생성 2. 링크 연결 작업 3. head .. 2023. 7. 13. 배열(Array) 많은 수의 데이터를 다룰 때 사용하는 자료구조 각 데이터를 인덱스와 1:1 대응하도록 구성 데이터가 메모리 상에 연속적으로 저장됨 배열의 장점 인덱스를 이용하여 데이터에 빠르게 접근 가능 배열의 단점 데이터의 추가/삭제가 번거로운 편 -미리 최대 길이를 정해서 생성해야 함 가변 길이 배열은 배열의 크기를 변경할 때마다 새로운 배열을 생성 데이터 삭제 시, 인덱스를 유지하기 위해 빈 공간 유지 추가 스터디 [] = new []; 예를 들어, 정수(int)로 이루어진 배열을 선언하고 크기를 5로 지정하려면 다음과 같이 작성할 수 있다. int[] numbers = new int[5]; 배열을 선언한 후에는 각 요소에 값을 할당하거나 읽을 수 있다. 배열의 각 요소는 0부터 시작하는 인덱스를 가지며, 인덱스를.. 2023. 7. 12. 이전 1 2 3 다음 728x90
