개발정리

그래프 란 그래프는 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 것 그래프에는 방향성이 있을수도 있고 없을수도 있다. 트리는 그래프의 한 종류이다. 모든 그래프가 트리는 아니다. 트리는 사이클이 없는 하나의 연결 그래프 그래프는 여러 개의 고립된 부분 그래프로 구성될 수 있다. 모든 점점 쌍간에 경로가 존재하는 그래프는 '연결 그래프' 라고 부른다. 그래프에는 사이클이 존재할 수도 있고 존재하지 않을 수도 있다. 그래프를 시각적으로 그려보면 아래와 같다. 그래프를 표현하는 방법 1) 인접행렬 2차원 배열에 표현하는 방법 그래프를 표에다 표현하는 방법 서로 연결된 노드들은 1로 표현하고 연결이 없으면 0으로 2차원 배열방을 채우는 방법이다. 2) 인접리스트 배열에 노드들을 나열하고 관계를 연결 리스..

트리(Tree) 란? 하나의 루트 노드를 갖고, 0개 이상의 자식노드로 이루어져 있는 구조. 자식노드 또한 0개 이상의 자식노드를 가질 수 있다. 트리(Tree) 종류 이진트리 각 노드가 최대 2개의 자식 노드를 갖는 트리 이진탐색트리 모든 노드가 특정 순서를 따르는 속성이 있는 이진트리를 일컫는다. "모든 왼쪽 자식들 ≤ n < 모든 오른쪽 자식들" 모든 노드 n 은 해당 조건을 반드시 충족해야한다. 바로 아래 자식 뿐만아니라 내 밑에있는 모든 노드가 충족되어야 한다. 모든 노드에 대해서 그 왼쪽 자식들의 값이 현재 노드 값보다 작거나 같도록 하고, 오른쪽 자식들의 값은 현재 노드의 값보다 반드시 커야 한다. 완전 이진 트리 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리 마지막 단계는 꽉 차 있지..

LinkedList 란? LinkedList에 대한 설명은 이전에 정리해놓은 글을 참고하자. https://hyokeun0419.tistory.com/25?category=888578 [자료구조] ArrayList & LinkedList ArrayList 란? ㄴ 데이터를 추가하는데로 사이즈가 늘어나는 자료구조 ㄴ 기본적으로 자바에서 제공되는 Array 의 경우에는 객체 생성시 배열의 크기를 지정해주어야한다. ㄴ ArrayList 를 이용하면 데 hyokeun0419.tistory.com LinkedList 구현 header 가 삭제되었음에도 이 후 노드들이 계속해서 header 의 주소값을 가지고 있으면 안된다. 이 문제를 쉽게 해결하기 위해 LinkedList 클래스 안에서 Node 클래스를 구현하고..

ArrayList 란? ㄴ 데이터를 추가하는데로 사이즈가 늘어나는 자료구조 ㄴ 기본적으로 자바에서 제공되는 Array 의 경우에는 객체 생성시 배열의 크기를 지정해주어야한다. ㄴ ArrayList 를 이용하면 데이터를 추가하는데로 사이즈가 늘어나 크기를 지정해주지 않고도 사용가능하다. ArrayList 특징 ArrayList 는 배열 방이 다 차면, 배열의 크기를 2배로 늘려준다. 현재 배열보다 2배 큰 크기로 새로운 배열을 생성하고, 기존 배열에 있었던 데이터를 전부 복사하는 작업을 진행하는데 이를 더블링 이라 한다. 더블링 소요시간은 기존 가지고 있던 데이터 길이가 n 이라 할 때 O(n) 만큼이 소요된다. ArrayList 성능 검색시간은 고정된 배열에서 검색되기 때문에 O(1) 이다. 입력시간 또..

1. HashTable 이란? ㄴ Key & Value 로 데이터를 저장하는 자료구조 ㄴ 데이터 검색이 빠르다는 장점을 가지고 있다. ㄴ 내부적으로는 고유한 인덱스를 가진 버킷과 해시함수를 이용하여 값을 저장한다. (대표 버킷은 배열) ㄴ 예를들어, 검색하고자 하는 Key 를 입력받으면, 해시함수를 이용하여 해시코드를 반환받고, 해시코드를 버킷의 인덱스로 환산해서 데이터에 접근하는 방식의 자료구조이다. ( * 해시를 이용하면 데이터 암호화, 간소화를 통하여 빠른비교가 가능하다. ) 2. HashTable 장점 Func(Key) → HashCode → Index → Value 검색속도가 빠르다. ㄴ 해시함수를 통해 만든 해시코드는 정수이다. ㄴ 버킷공간을 고정된 크기만큼 미리 만들어놓고, 해시코드를 배열의..