[패스트캠퍼스] Java & SpringBoot로 시작하는 웹 프로그래밍 : 자바 인강_5주차 학습일지

# 자료구조

   1. 메모리 상에서 자료를 관리하는 여러 구현 방법들

   2. 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 효율적으로 자료를 관리할 수 있다.

 

# 선형 자료구조

   앞뒤의 자료가 일대일의 관계

 

   1. 배열(array)

      1) 정해진 크기의 메모리를 먼저 할당받아서 사용하고, 자료의 물리적 위치와 논리적 위치가 같다.

      2) 자료를 추가/편집하는데 느리다.

      3) 빠르게 특정 요소를 찾아낼 수 있다.

 

   2. 연결리스트(linkedlist)

      1) 자료가 추가될 때마다 메모리를 할당받고, 자료는 링크로 연결된다. 자료의 물리적 위치와 논리적 위치가 다를 수 있다.

      2) 자료를 추가/편집하는데 빠르다.

      3) 특정 요소를 찾는데는 느리다.

 

   3. 스택(stack)

      1) 가장 나중에 입력된 자료가 가장 먼저 출력되는 구조(후입선출)

      2) top에서만 요소의 추가와 삭제가 일어난다.

 

   4. 큐(queue)

      1) 가장 먼저 입력된 자료가 가장 먼저 출력되는 구조(선입선출)

      2) 자료는 맨 뒤(rear)에서만 추가(enqueue)되고, 맨 앞(front)에서만 삭제(dequeue)된다.

 

# 비선형 자료구조

   앞뒤의 자료가 일대다의 관계

 

   1. 트리(tree)

      부모 노드와 자식 노드간의 연결로 이루어진 자료구조

 

      1) 힙(heap)

         1. priority queue를 구현

         2. max heap : 부모 노드는 자식 노드보다 항상 크거나 같은 값을 가진다.

         3. min heap : 부모 노드는 자식 노드보다 항상 작거나 같은 값을 가진다.

 

      2) 이진 트리(binary tree)

         부모 노드에 자식 노드가 두 개 이하인 트리구조

 

      3) 이진 검색 트리(binary search tree)

         1. 자료(key)는 중복되지 않는다.

         2. 왼쪽 자식 노드는 부모 노드보다 작은 값, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가진다.

            ex) AVL Tree, Red-Black Tree (균형 있는 트리)

         3. 자료 검색이 걸리는 시간은 log2(n)

         4. inorder traversal 탐색을 하게 되면, 왼쪽 자료부터 읽고 오른쪽 자료를 읽는 순서로, 자료가 정렬되어 출력된다.

 

   2. 그래프(graph)

      1) 정점과 간선들로 이루어진 자료구조

      2) 정점(vertex) : 여러 특성을 가지는 객체, 노드(node)

      3) 간선(edge) : 이 객체들의 연결 관계, 링크(link)

      4) 간선은 방향성이 있는 경우와 없는 경우가 있다.

      5) 그래프 구현 방법 : 인접행렬(adjacency matrix), 인접리스트(adjacency list)

      6) 그래프 탐색 방법 : BFS(bread first search), DFS(depth first search)

 

3. 해싱(hashing)

      1) 자료를 검색하기 위한 자료구조

      2) 키(key)에 대한 자료를 검색하기 위한 사전(dictionary) 개념

      3) 키(key)는 유일하고 이에 대한 value를 쌍으로 저장

 

# 재네릭 프로그래밍(generic programming)

   1. 다양한 자료형이 적용될 수 있도록 하는 프로그래밍

   2. 목적에 맞는 자료형 변환을 보장하는 안전한 프로그래밍 방식이다.

   3. 같은 매커니즘으로 구성된 클래스들의 중복을 없애고, 그로 인해 생기는 자료형 지정의 불확실성을 해결해준다.

   4. 컬렉션 프레임워크에서 많이 사용되고 있다.

   5. 자료형 매개변수 T(type parameter)에는 기본 자료형이 아닌 참조형 자료형이 들어가야 한다.

    => 기본 자료형 int나 double을 사용하기 위해서는 wrapping이 필요한데, int의 wrapper class인 Integer, double의                     Double로 wrapping 해주면 된다.

 

Generic programming 예시

 

# T extends 활용하기

   1. T 자료형을 사용하면, 어떤 자료형이든 받을 수 있게 된다. 프로그램의 목적 상 특정 자료형은 받지 않게 해야 된다면, T extends를 활용하면 된다.

   2. 상위 클래스를 하나 만들고, 들어갈 자료형이 될 클래스들을 그 상위 클래스로 하여금 상속받게 한다.

   3. 이렇게 되면, T 자료형을 써주더라도, 들어가면 안될 자료형은 거를 수 있게 된다.

 

# List 순서형

# Set 집합형 ( 중복된 요소 없이 유일한 요소를 구성 )

 

# 컬렉션 프레임워크

   1. 프로그램 구현에 필요한 자료구조를 구현해놓은 JDK 라이브러리

   2. java.util 패키지에 구현되어 있다.

   3. 효율적인 개발에 도움을 주고, 시간을 절약해줄 수 있다.

컬렉션 프레임워크

   1. Collection 인터페이스

      1) 하나의 객체를 관리하기 위한 메서드가 선언된 인터페이스

        ( 하나의 객체라면 Student만, Employee만, 오직 하나만을 관리하기 위한 )

      2) 하위에 List 인터페이스, Set 인터페이스가 있다.

 

   2. List 인터페이스

      1) 순서를 통해 자료를 관리하기 위해 필요한 메서드들이 선언된 인터페이스

      2) 중복을 허용

      3) 하위에 ArrayList, Vector, LinkedList, Stack, Queue 등의 클래스들이 있다.

 

   3. Set 인터페이스

      1) 순서와 관계없이 집합형으로 자료를 관리하기 위해 필요한 메서드들이 선언된 인터페이스

      2) 중복을 허용하지 않는다.

      3) 유일한 값 ( 사번, 회원번호 ) 등을 관리하는 데 주로 쓰인다.

      4) 저장되는 순서와 출력되는 순서는 다를 수 있다.

      5) 하위에 HashSet, TreeSet 등의 클래스들이 있다.

 

   4. Map 인터페이스

      1) 쌍으로 이루어진 객체를 관리하기 위해 필요한 메서드들이 선언된 인터페이스

      2) 객체는 key-value의 쌍으로 이루어지고, key는 중복을 허용하지 않는다.

      3) 하위에 HashTable, HashMap, Properties, TreeMap 등의 클래스들이 있다.

 

# 요소 순회

   1. 컬렉션 프레임워크에 저장된 요소들을 하나씩 차례로 참조하는 것

   2. List 인터페이스는 Iterator를 사용하지 않고 get(i) 메서드로 활용 가능

   3. Set 인터페이스는 get(i) 메서드가 제공되지 않으므로 Iterator를 활용

 

Iterator를 활용한 boolean 타입의 remove 메서드 예시

# HashSet 클래스

   1. Set 인터페이스의 하위 클래스

   2. 중복이 되지 않게 인스턴스의 동일성을 체크해야 하고, 그 체크하는 메서드는 equals()와 hashCode() 메서드를 재정의 해서 쓴다.

 

동일성 체크 여부를 위해 equals(), hashCode() 메서드를 재정의하는 예시

 

# TreeSet 클래스

   1. 객체의 중복을 허용하지 않고, 오름차순과 내림차순 정렬에 사용하는 클래스

   2. Comparable, Comparator 인터페이스를 구현해야 한다.

 

      1) Comparable 인터페이스 구현 - java.lang 패키지 안에 있다.

 

Comparable 인터페이스 구현한다고 선언

Comparable 인터페이스의 compareTo 메서드 재정의 / 요소가 하나 추가되면 자기 자신과 비교해서 판별 / 양수인지 음수인지 같은지 판별해서 나누는 작업 (오름차순)

오름차순 정렬의 또 다른 예

내림차순

      2) Comparator 인터페이스 구현 - java.util 패키지 안에 있다.

 

Comparator 인터페이스 구현한다고 선언

어떤 클래스의 타입으로 생성한 것인지 표시

Comparator 인터페이스의 compare 메서드 재정의 ( 오름차순 ) / 어떠한 요소와 또 다른 요소를 비교해서 판별

 

# HashMap 클래스

   1. 가장 많이 사용되는 Map 인터페이스 기반 클래스

   2. key - value를 쌍으로 관리하는 메서드를 구현한다.

   3. 검색을 위한 자료구조

   4. key가 되는 객체는 중복이 불가능하고, 유일성을 비교하기 위한 equals()와 hashCode() 메서드를 구현해야 한다.

   5. value가 되는 객체는 Collection 인터페이스 기반이기에 중복이 가능한 객체가 들어갈 수 있다.

 

# TreeMap 클래스

   1. HashMap 클래스와 함께 Map 인터페이스 기반의 클래스이고 key에 대한 정렬을 구현할 수 있다.

   2. key가 되는 클래스에 Comparable이나 Comparator 인터페이스 구현을 통해 key-value 쌍의 자료를 key값을 기준으로 정렬하여 관리할 수 있다.