[패스트캠퍼스] Java & Spring 웹 개발 종합반 4주차 학습일지

 

내일배움카드, 국비지원교육

---

Chapter 5. 자바와 자료구조

01 ~ 02. 여러가지 자료구조 

 - 선형 자료구조 (한 줄로 자료를 관리)

   1. 배열 (Array)

   2. 연결 리스트 (LinkedList)

   3. 스택 (Stack) : 가장 나중에 입력된 자료가 가장 먼저 출력되는 자료구조 (LIFO)

   4. 큐 (Queue) : 가장 먼저 입력된 자료가 가장 먼저 출력되는 자료구조 (FIFO)

   5. 트리 (Tree) : 부모 노드와 자식 노드 간의 연결로 이루어진 자료구조

   6. 힙 (Heap) : Priority Queue를 구현 (우선순위 큐)

     Max Heap : 부모 노드는 자식 노드보다 항상 크거나 같은 값을 갖는 경우

     Min Heap : 부모 노드는 자식 노드보다 항상 작거나 같은 값을 갖는 경우

     이진 트리 (binary tree) : 부모 노드에 자식 노드가 두 개 이하인 트리

     이진 검색 트리 (binary search tree)

       자료(key)의 중복을 허용하지 않음

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

       자료 검색에 걸리는 시간은 평균 log(n)

       inorder traversal 탐색을 하게 되면 자료가 정렬되어 출력됨

       jdk 클래스 : TreeSet, TreeMap

   7. 그래프 (Graph) : 정점과 간선들의 유한 집합 G = (V,E)

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

     간선 (edge) : 이 객체들을 연결 관계를 나타냄, 링크 (link)

     간선은 방향성이 있는 경우와 없는 경우가 있음

     그래프를 구현하는 방법 : 인접 행렬, 인접 리스트

     그래프를 탐색하는 방법 : BFS(Bread First Search), DFS(Depth First Search)

   8. 해싱 (Hashing) : 자료를 검색하기 위한 자료구조

      키에 대한 자료를 검색하기 위한 사전 개념의 자료구조

      해시 함수가 키에 대한 인덱스를 반환해줌. 해당 인덱스 위치에 자료를 저장하거나 검색하게 됨

      해시 함수에 의해 인덱스 연산이 산술적으로 가능 O(1)

      jdk 클래스 : HashMap, Properties

 

 

 

 

 

 

04. LinkedList 구현하기

LinkedList의 특징

 - 자료를 저장하는 노드에는 자료와 다음 요소를 가리키는 링크가 있음

 - 자료가 추가될 때 노드 만큼의 메모리를 할당받고 이전 노드의 링크로 연결함

 - 연결 리스트의 i번째 요소를 찾는 데 걸리는 시간은 요소의 개수에 비례 O(n)

 

 

 

 

 

 

07. 무엇이든 담을 수 있는 제네릭 프로그래밍

제네릭 자료형

 - 클래스의 자료형을 특정하지 않고 추후 해당 클래스를 사용할 때 지정할 수 있도록 선언

 - 컬렉션 프레임워크에서 많이 사용되고 있음

 

자료형 매개변수 T : 이 클래스를 사용하는 시점에 실제 사용할 자료형을 지정, static 변수는 불가능

 

 

 

 

08. T extends 클래스 사용하기

상위 클래스의 필요성

 - T 자료형의 범위를 제한할 수 있음

 - 상위 클래스에서 선언하거나 정의하는 메서드를 활용할 수 있음

 - 상속을 받지 않는 경우 T는 Object로 변환되어 Object 클래스가 기본으로 제공하는 메서드만 사용 가능

 

 

 

 

09. 제네릭 메서드 활용하기

public class Point<T, V> {
	T x;
	V y;
	
	Point(T x, V y) {
		this.x = x;
		this.y = y;
	}

	public T getX() {
		return x;
	}

	public V getY() {
		return y;
	}
}

public class GenericMethod {
	public static <T, V> double makeRectangle(Point<T, V> p1, Point<T, V> p2) {
		double left = ((Number)p1.getX()).doubleValue();
		double right = ((Number)p2.getX()).doubleValue();
		double top = ((Number)p1.getY()).doubleValue();
		double bottom = ((Number)p2.getY()).doubleValue();
		
		double width = right - left;
		double height = bottom - top;
		
		return width * height;
	}
	
	public static void main(String[] args) {
		Point<Integer, Double> p1 = new Point<>(0, 0.0);
		Point<Integer, Double> p2 = new Point<>(10, 10.0);
		System.out.println(GenericMethod.makeRectangle(p1, p2));
	}
}

 

 

 

 

 

 

 

10. 자바에서 제공되는 자료구조 구현 클래스들 - 컬렉션 프레임워크

컬렉션 프레임워크 : 프로그램 구현에 필요한 자료구조를 구현해 놓은 JDK 라이브러리

Collection 인터페이스 : 하나의 객체를 관리하기 위한 메서드가 선언된 인터페이스의 하위에 List와 Set 인터페이스가 있음

 

List 인터페이스 : 객체를 순서에 따라 저장하고 관리하는데 필요한 메서드가 선언된 인터페이스

 - 자료구조 리스트의 구현을 위한 인터페이스

 - 중복을 허용함

 

Set 인터페이스 : 순서와 관계없이 중복을 허용하지 않고 유일한 값을 관리하는데 필요한 메서드가 선언됨

 

Map 인터페이스 : 쌍으로 이루어진 객체를 관리하는데 사용하는 메서드들이 선언된 인터페이스

 

 

 

 

 

 

 

11. 순차적으로 자료를 관리하는 List 인터페이스를 구현한 클래스와 그 활용

Member 클래스를 만들고, 아이디와 이름을 멤버 변수로 선언 Member 클래스로 생성된 인스턴스들을 관리하는 클래스를 컬렉션 프레임워크 클래스들을 활용하여 구현

public class Member {
	private int memberId;
	private String memberName;
	
	public Member(int memberId, String memberName) {
		this.memberId = memberId;
		this.memberName = memberName;
	}

	public int getMemberId() {
		return memberId;
	}

	public void setMemberId(int memberId) {
		this.memberId = memberId;
	}

	public String getMemberName() {
		return memberName;
	}

	public void setMemberName(String memberName) {
		this.memberName = memberName;
	}
	
	@Override
	public String toString() {
		return memberName + " 회원님의 아이디는 " + memberId + "입니다.";
	}
}

import java.util.ArrayList;

public class MemberArrayList {
	private ArrayList<Member> arrayList;
	
	public MemberArrayList() {
		arrayList = new ArrayList<>();
	}
	
	public MemberArrayList(int size) {
		arrayList = new ArrayList<>(size);
	}
	
	public void addMember(Member member) {
		arrayList.add(member);
	}
	
	public boolean removeMember(int memberId) {
		for(int i=0; i<arrayList.size(); i++) {
			Member member = arrayList.get(i);
			int tempId = member.getMemberId();
			if(tempId == memberId) {
				arrayList.remove(i);
				return true;
			}
		}
		
		System.out.println(memberId + "가 존재하지 않습니다.");
		return false;
	}
	
	public void showAllMember() {
		for(Member member : arrayList) {
			System.out.println(member);
		}
		System.out.println();
	}
}

public class MemberArrayListTest {
	public static void main(String[] args) {
		MemberArrayList memberArrayList = new MemberArrayList();
		
		Member member1 = new Member(1001, "이순신");
		Member member2 = new Member(1002, "김유신");
		Member member3 = new Member(1003, "강감찬");
		Member member4 = new Member(1004, "홍길동");
		
		memberArrayList.addMember(member1);
		memberArrayList.addMember(member2);
		memberArrayList.addMember(member3);
		memberArrayList.addMember(member4);
		
		memberArrayList.showAllMember();
		memberArrayList.removeMember(member2.getMemberId());
		memberArrayList.showAllMember();
	}
}

 

 

 

 

 

 

 

12. Collection 요소를 순회하는 Iterator

 - boolean hasNext() : 이후에 요소가 더 있는지를 체크하는 메서드

 - E next() : 다음에 있는 요소를 반환

public boolean removeMemberIterator(int memberId) {
	Iterator<Member> ir = arrayList.iterator();
	while(ir.hasNext()) {
		Member member = ir.next();
		int tempId = member.getMemberId();
		if(tempId == memberId) {
			arrayList.remove(member);
			return true;
		}
	}
		
	System.out.println(memberId + "가 존재하지 않습니다.");
	return false;
}

 

 

 

 

 

 

 

13. 중복되지 않게 자료를 관리하는 Set 인터페이스를 구현한 클래스와 그 활용

HashSet 클래스

 - Set 인터페이스를 구현한 클래스와 멤버의 중복 여부를 체크하기 위해 인스턴스의 동일성을 확인해야 함

 - 동일성 구현을 위해 필요에 따라 equals()와 hashCode() 메서드를 재정의함

 

 

 

 

 

 

 

14. 정렬을 위해 Comparable과 Comparator 인터페이스 구현하기

TreeSet 클래스 활용하기

 - 객체의 정렬에 사용하는 클래스 

 - Set 인터페이스를 구현하여 중복을 허용하지 않고, 오름차순이나 내림차순으로 객체를 정렬할 수 있음

 - 내부적으로 이진검색트리로 구현됨

 - 이진검색트리에 저장하기 위해 각 객체를 비교해야 함

 - 비교 대상이 되는 객체에 Comparable이나 Comparator 인터페이스를 구현해야 TreeSet에 추가될 수 있음

 

 

 

 

 

 

15. 쌍으로 자료를 관리하는 Map 인터페이스를 구현한 클래스와 그 활용

TreeMap 클래스

 - Map 인터페이스를 구현한 클래스이고 key에 대한 정렬을 구현할 수 있음

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

https://github.com/easyspubjava/FastCampus/tree/master/Chapter5

 

 

 

 

---