EddIT

깊이 우선 탐색

그래프 G와 시작점 S가 주어졌을 때 S에서 도달 가능한 모든 간선을 찾는 과정

동작원리

탐색 시작 위치의 vertex의 인접한 간선을 통해 다른 vertex로 이동한 후 인접한 간선이 없을 때까지

반복하여 내려간 후 다시 위로 올라가는 과정을 반복해서 탐색하는 것

아래로 깊이 내려가며 탐색하기에 깊이 우선 탐색이라고 불림

코드)

HashTable이란?

HashMap과 동일한 내부구조를 가지고 있는 Map 구현 클래스

HashMap vs HashTable

HashMap과 HashTable은 동일한 내부 구조를 가지고 있지만

HashTable의 경우는 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가

동시에 이 메소드를 실행할 수 없고, 하나의 스레드가 실행을 완료해야만 다른 스레드가 실행가능하다.

이는 멀티 스레드 환경에서 안전하게 객체를 추가, 삭제할 수 있다는 것을 의미한다.

Properties란?

Hashtable의 하위 클래스로 Hashtable의 모든 특징을 가지고 있다.

차이점은 Properties는 키와 값을 String으로 제한하였다는 것이다.

주로 애플리케이션의 옵션 정보, 데이터베이스 연결정보 그리고 국제화 정보가 저장된

프로퍼티(~.properties) 파일을 읽을 때 주로 사용

HashMap이란?

Map 인터페이스를 구현한 대표적인 Map 컬렉션

Map이란?

Key와 value으로 구성된 Entry 객체를 저장하는 구조를 가짐(key, value 모두 객체)

키는 중복 저장될 수 없지만 값은 중복 저장 가능

HashMap, HashTable, LinkedHashMap, Properties, TreeMap 등이 있다.

HashMap 특징

HashSet과 마찬가지로 hashcode()와 equals()로 동일한 키 여부를 결정한다.

기본 사용법 코드

hashcode( )와 eqauls( ) 재정의를 통한 동일한 키 삽입 예제 코드

키로 사용할 객체(hashcode() eqauls() 재정의)

이름과 나이가 같은 경우 동일한 키로 판단

HashSet

Set 인터페이스의 구현 클래스

HashSet은 객체들을 순서없이 저장하고 동일한 객체를 중복 저장하지 않는다.

HashSet의 가장 큰 특징

HashSet이 판단하는 동일한 객체란 꼭 같은 인스턴스를 뜻하지 않는다.

HashSet은 객체를 저장하기전 먼저 객체의 hashCode() 메서드를 호출하여 해시코드를 얻고

이미 저장되어 있는 객체들의 해시코드와 비교한다. 만약 동일한 해쉬코드가 있다면 다시 equals() 메소드로

두 객체를 비교해 참이면 동일한 객체로 저장하고 중복 저장하지 않는다.

예시 코드

Member 클래스

HashSet을 이용한 동일한 데이터를 가진 객체 저장

넓이 우선 탐색이란?

그래프 G와 시작점 S가 주어졌을 때 S에서 도달 가능한 모든 간선을 찾는 과정

동작 원리

먼저 거리가 1인 정점을 모든 찾은 후 2인 정점을 찾는 식으로 거리를 늘려가며 탐색

탐색을 하면서 시작점으로부터의 거리와 바로 직전 정점을 계산

직전정점 그래프(넓이 우선 탐색 트리)

시작점으로부터 각 정점에 들려야 하는 정점으로 만든 하위 그래프로 트리 형태

모든 정점이 연결되어 있고 nE(간선의 수) = nV(vertex의 수) - 1

예시)

주어진 그래프

1을 시작점으로한 넓이 우선 탐색 트리

코드 구현

인접리스트를 이용해 구현한 비방향성 그래프

인접행렬를 이용해 구현한 방향성 그래프

인접행렬를 이용해 구현한 방향성 그래프

ArrayList란?

배열을 사용하여 리스트를 구현한 것

ArrayList의 구성 - 엘리먼트들로 구성

element의 구성 - 데이터와 인덱스로 구성

장점 - 인덱스를 가지고 있기에 조회가 빠르다

단점 - 추가/삭제시 엘리먼트들을 밀고 당기는 작업이 필요하기 때문에 추가/삭제 속도가 느리다.

   데이터 공간의 낭비가 발생한다.

LinkedList란?

노드와 노드간의 연결로 리스트를 구현한 것

LinkedList의 구성 - Node(or vertex)로 구성, Head는 첫번째 Node를 가리킨다.

Node의 구성 - 데이터를 담는 data field, 연결정보를 담고 있는 linkd field

장점 - 추가/삭제가 빠르다. 데이터 공간의 낭비가 없다

단점 - 조회시 일일히 다 순회하기 때문에 느리다.

배열이란?

여러 데이터를 하나의 이름으로 그룹핑하여 관리하기 위한 자료구조

거의 모든 언어에 포함

배열의 구성

    public class ArrayTest {
         int[] numbers1 = new int[4];
       // int[]에서 
       // int는 엘리먼트의 데이터 타입, []은 배열을 의미
       // new int[4]에서
       // new는 생성자, [4]는 배열의 크기
    }
    

배열은 엘리먼트로 구성되어 있고,

엘리먼트는 index와 value로 구성되어 있다.

학생1과 0을 묶어서 엘리먼트 하나를 이룬다.

배열의 생성

    public class ArrayTest {
         int[] numbers1 = new int[4];
         int[] numbers2 = {10, 20, 30, 40};
         int[] numbers3 = new int[] {10, 20, 30, 40};
    }
    

배열에 들어갈 값을 미리 알고 있을 경우, 생성과 초기화를 한번에 할 수 있다.

배열의 조회

    public class ArrayTest {    
        public static void main(String[] args) {
                 int[] numbers1 = new int[4];
                 int[] numbers2 = {10, 20, 30, 40};
                 int[] numbers3 = new int[] {10, 20, 30, 40};
          
                 // 나중에 배열 초기화 방법
                numbers1[0] = 10;
                numbers1[1] = 20;
		
                //배열의 값조회(인덱스를 이용)
                System.out.println(numbers1[0]); //  10이 출력
                
               //배열의 길이
               System.out.println(numbers1.length);  // 4가 출력(처음 만들때 4개의 방을 만들었음)
	}     
    }

배열과 반복문 (배열 사용법!!)

  
               //배열의 길이
               System.out.println(numbers1.length);  // 4가 출력(처음 만들때 4개의 방을 만들었음)

               for(int i=0; i

배열의 단점과 장점

단점 : 배열의 크기가 조정이 불가능, 처음 생성할 때 크기로 고정

        별다른 기능(메서드)가 없다.

장점 : 크기가 고정되어있고, 별다른 기능이 없기 때문에 작고 가볍고 단순하다.

         이는 다른 곳의 부품이 되기 쉽다는 의미, 배열의 확장성이 강하다!! 다른 자료구조나 활용도 면에서...

참고: https://opentutorials.org/module/1335/8738