정렬된 상태의 데이터에서 특정 값을 빠르게 탐색하는 방법 - 찾고자 하는 값과 데이터 중앙에 있는 값을 비교 - 찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서 이진 탐색 - 찾고자 하는 값이 더 크면 데이터 오른쪽 부분에서 이진 탐색 알고리즘 시간 복잡도 : O(logn) 이진 탐색의 구현 1. 탐색의 대상이 되는 자료들이 array[low] 에서부터 array[high]에 들어있다고 가정하자. (정렬되어 있어야 함) 즉 어떤 시점에서 탐색되어야 할 범위는 low에서 high 까지가 된다. 맨 처음 low에는 0번 인덱스의 값, high에는 n-1번 인덱스의 값이 들어갈 것이다. 2. low와 high값에 의거해 중간값mid 값은 (low + high) / 2이다. 즉, array[low] ~ arr..

배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 방법 두 개 포인터의 배치 방법 - 같은 방향에서 시작 : 첫 번째 원소에 둘다 배치 - 서로 다른 방향에서 시작 : 첫 번째 원소와 마지막 원소에 배치 다중 for문의 복잡도를 좀 더 선형적으로 풀 수 있음 sum의 값이 5보다 작다면, end를 1 늘려준다. sum의 값이 여전히 5보다 작으니 end를 1 늘려준다. sum의 값이 5보다 크니, start를 빼주고 값을 늘려준다. sum의 값이 5와 같아져서 cnt를 1 올려주고, start와 end를 둘 다 올려준다. sum의 값이 5와 같아져서 cnt를 1 올려주고, start와 end를 둘 다 올려준다. sum이 5보다 크니, start를 빼주고 옆으로 움직인다. sum의 값이 5와 같으니 ..

힙(Heap) 완전 이진 트리 형태 - 중복 값 허용 - 반 정렬 상태 최소값 또는 최대값을 빠르게 찾아내는데 유용한 자료구조 - 최소 힙, 최대 힙 힙의 종류 최대 힙 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 key(부모 노드) >= key(자식 노드) 최소 힙 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 key(부모 노드) 1 && heap.get(cur / 2) 1 && heap.get(cur / 2) > heap.get(cur)){ // 방금 들어온 data가 부모 data 보다 작다면 int parentVal = heap.get(cur / 2); heap..

그래프(Graph) 정점과 간선으로 이루어진 자료구조 - 연결된 정점간의 관계를 표현 할 수 있는 자료구조 그래프의 용도 - 지하철 노선도, 통신 네트워크,.... 정점(Vertex) : 각 노드 간선(Edge) : 노드와 노드를 연결하는 선(link, branch) 인접 정점(Adjacent vertex) : 가선 하나를 두고 바로 연결된 정점 정점의 차수(Degree) - 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배 진입 차수(In-degree) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(Out-degree) : 방향 그래프에서 외부로 나가는 간선의 수 경로 길이(Path length) : 경로를 구성하는데 사용된 간..

이진 탐색 트리의 편향 발생(불균형 이진트리) Case 1) 이진 탐색 트리에 삽입되는 순서 : 20 → 10 → 30 → 5 Case 2) 이진 탐색 트리에 삽입되는 순서 : 5 → 10 → 20 → 30 균형 이진 탐색 트리 Balanced Binary Search Tree 노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 트리 AVL 트리, Red-Black 트리 AVL 트리 노드가 삽입, 삭제될 떄 트리의 균형을 체크하고 유지하는 트리 각 노드의 BF를 [-1, 0, 1] 만 가지게 하여 균형을 유지 BF(Balance Factor) # 왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이 AVL 트리 - Rebalancing 균형이 꺠진 경우, BF가 ' + ' 이면 왼쪽 서브 트리에 이상이 있..

이진 탐색 트리(Binary Search Tree) - 왼쪽 자식 노드의 키는 부모 노드의 키보다 작음 - 오른쪽 자식 노드의 키는 부모 노드의 키보다 큼 - 각각의 서브 트리도 이진 탐색 트리를 유지 - 중복된 키는 허용하지 않음 - 이진 탐색 트리 규칙에 의해 데이터가 정렬됨 - 이진 트리에 비해 탐색 빠름(균형 유지 필요) - 균형 상태 : O(logN) - 불균형 상태 : O(N) 이진 탐색 트리 - 탐색 찾고자 하는 데이터를 루트 노드부터 비교시작 대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동 찾는 데이터가 없으면 null 반환 어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 이루어짐 이진 탐색 트리 - 삽입 Root부터 비교 시작(중복 키 발견 시 노드 추가하지 ..

트리(Tree) 노드와 링크로 구성되 자료구조(그래프의 일종, Cycle 없음) 계층적 구조를 나타낼 때 사용 - 폴더 구조(디렉토리, 서브 디렉토리) - 조직도, 가계도, ... 트리의 구조 노드(Node) : 트리 구조의 자료 값을 담고 있는 단위 에지(Edge) : 노드 간의 연결선 (=link, branch) 루트 노드(Root) : 부모가 없는 노드, 가장 위의 노드 잎새 노드(Leaf) : 자식이 없는 노드 (=단말) 내부 노드(Internal) : 잎새 노드를 제외한 모든 노드 부모(Parent) : 연결된 두 노드 중 상위의 노드 자식(Child) : 연결된 두 노드 중 하위의 노드 형제(Silbing) : 같은 부모를 가지는 노드 깊이(Depth) : 루트에서 어떤 노드까지의 간선의 수 ..

해시 테이블(Hash Table) 키(Key), 값(Value)을 대응시켜 저장하는 데이터 구조 -키를 통해 해당 데이터에 빠르게 접근 가능 해싱 -키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정 해시 테이블 구조 키 : 해시 테이블 접근을 위한 입력 값 해시 함수 : 키를 해시 값으로 매핑하는 연산 해시 값 : 해시 테이블의 인덱스 해시 테이블 : 키 - 값을 연관시켜 저장하는 데이터 구조 해시 충돌 해시 테이블의 같은 공간에 서로 다른 값을 저장 하려는 경우 - 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우 해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있음 해시 충돌 해결 방법(1) 개방 주소법(Open Address) -충돌 시, 테이블에서 비어 있는 공..

Queue Queue q = new LinkedList(); // 선언 // 값 추가 q.add(1); q.offer(2); q.poll(); // top 값 출력 후 제거 q.remove(); // top 값 제거 q.clear(); // 큐 초기화 q.peek(); // top 값 출력 q.size(); // 큐 크기 출력 q.isEmpty() // 큐가 비어있으면 true q.contains("str") // 큐에 포함되어 있으면 true Deque 양쪽에서 삽입과 삭제가 모두 가능한 자료구조 -Deque : Doubly-ended Queue -Stack 과 Queue를 합친 형태 데크의 기본구조 데크의 기본 구조는 양방향에서 삽입 삭제 가능한 구조 일부 기능을 제한하여 용도에 맞게 변형 가능 ad..

- 선형 자료구조- 순서를 가진 항목들의 모임 - 배열이 가지고 있는 인덱스라는 장점을 버리고 빈틈없는 데이터 적재라는 새로운 장점을 취한 자료구조 - 중복된 데이터의 저장 허용 - ArrayList , LinkedList등 여러 인터페이스를 구현한 자료형이 있다 - 자바스크립트,파이썬 같은 경우에는 리스트를 따로 구현하지 않고 배열에 List의 기능 중 일부를 제공 - List에서는 인덱스가 중요하지 않다 - 리스트의 핵심은 element간의 순서 - 다른말로 순서라는 의미의 시퀀스(sequence)라고도 함 - 수학적으로 유한수열을 표현한 것 기능(operation) - 처음,끝에 데이터 삽입기능 - 리스트에 데이터가 있는지를 체크하는 기능 - 리스트의 모든 데이터에 접근할 수 있는 기능 ArrayL..