無테고리 인생살이

그래프 정의 용어 정리 그래프 종류 그래프 VS 트리 그래프란? : 데이터 간의 관계를 점과 선으로 나타낸 자료구조 용어정리 정점 (Vertex) : 위치 (= node) 간선 (Edge) : 두 정점을 연결한 선, 관계 (= link, branch) 차수 : 정점에 연결된 edge 수 진입 차수 : 방향 그래프에서 정점으로 들어오는 edge 수 진출 차수 : 방향 그래프에서 정점에서 나가는 edge 수 경로 : 연결된 정점을 나열한 것 단순경로 : 중복된 정점이 없는 경로 경로 길이 : 경로에 쓰인 edge 수 사이클 : 시작과 끝 정점이 같은 경로 그래프 종류 그래프를 G=(V,E)와 같이 표기 ( V : 정점의 집합, E : edge의 집합 ) 1. 무방향 그래프 : edge에 방향(화살표)가 없는..

힙이란? : 완전 이진 트리 형태이며, 우선순위 큐를 위해서 만들어진 자료구조 완전 이진 트리(complete binary tree) : 이진 트리 종류 중 하나로, 마지막 level을 제외하고 모든 level이 두 자식 노드로 완전히 채워져 있는 이진 트리 (level - 이진 탐색 트리 게시글의 그림 확인) 언제 사용하는가 : 우선순위 큐와 같이 최대/최소값을 빠르게 찾아야하는 자료구조 및 알고리즘 구현에 사용된다. EX) java.util.PriorityQueue 사용 이유 : 배열을 통해 최대/최소값 찾으려면 O(N)이 걸리지만, 힙은 O(log N)이 걸린다. (시간복잡도를 줄이기 위해서) 힙의 종류 1. 최대 힙 : 부모노드의 값이 자식노드 값보다 크거나 같다 (Root node가 최대값) 2..

트리 : node, branch를 사용한 자료구조 이진트리 : branch가 최대 2개인 트리(=최대 2개의 자식노드를 갖는 트리) 배열과 연결리스트로 구현할 수 있지만, 일반적으로 연결리스트로 이진트리를 구현한다. (노드 - 1.데이터 2.왼쪽 자식 포인터 3.오른쪽 자식 포인터) 이진 탐색 트리 (BST) : 부모노드보다 작은 값은 왼쪽 자식노드, 큰 값은 오른쪽 자식노드에 위치시키는 특성을 가진 이진트리. 같은 값을 같는 노드가 없다는 특징이 있다. 이진 탐색 트리의 용도 : 데이터 탐색 시간복잡도 : O(log N) 장단점 장점 : 탐색속도 O(log N)으로 개선 단점 : 균형이 무너진 최악의 경우, O(N)까지 시간복잡도가 증가할 수 있다. EX) 4라는 데이터를 탐색할 때, O(N)의 시간복..

hash 관련 용어정리 hash table hash table의 장단점 hash collision (해시 충돌) 해시 알고리즘 hash collision 해결법 Hashtable, HashMap 공통점과 차이점 자바 Object 클래스에 선언된 메서드들은 스레드와 객체를 처리하기 위한 메서드로 나눠져있다. 객체를 처리하기 위한 메서드에는 toString(), equals(), hashCode(), getClass(), clone(), finalize() 이 있다. 그 중, hashCode() 메서드는 객체에 대한 해시코드 값을 int 형태로 리턴한다는 설명을 봤고 hash code가 무엇을 의미하는지 자세히 알아보기로 했다. hash code를 검색하면, hash, hashing, hash functio..