[JAVA] 개념 정리 3

NaSC·2022년 12월 11일
Java
0

JAVA 기본개념

목록 보기
3/6

1. Hash

  • Hashing은 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 의미함.
    이를 이용해 특정한 배열의 인덱스나 위치나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다.
    기존에 사용했던 자료구조들은 탐색이나 삽입에 선형시간이 걸리기도했지만, 해쉬를 이용하면 즉시 저장하거나 찾고자 하는위치를 참조 할 수 있으므로 더욱 빠른 속도로 처리 가능하다.

Hash Table
해시함수를 사용해서 변환한 값을 index로 삼아 key-vlaue를 저장하는 자료구조
기본연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다

Direct Addressing Table
가장 간단한 형태의 해시테이블로 key값을 직접적으로 주소로 사용하는 테이블
찾고자하는 key값만 알고있으면 즉시 위치를 찾을 수 있으므로, 탐색,저장,삭제,갱신은 모두
선형시간인 O(1)로 매우 빠른속도로 처리 가능하지만, 한계점 존재함

  • 최대 키값에 대해 알고 있어야 함.
  • 최대 키값이 작을 때 실용적으로 사용할 수 있음.
  • 키 값들이 골고루 분포되어있지 않다면 메모리 낭비 심함.

2. 제네릭이란 / 제네릭은 왜 필요한가

  • ArrayList, LinkedList 등을 생성 할 때,
    ArrayList list1 = new ArrayList();
    이런 식으로 <> 괄호안에 타입을 넣어주는데, 이처럼 타입을 미리 정해놓지않고
  • 클래스 내부에서 지정하는 것이 아닌 외부에서 사용자에 의해 지정되는 것을 의미한다.

    제네릭을 사용하면 잘못된 타입이 들어올 수 있는 것을 컴파일 단계에서 방지가능하다.
    클래스 외부에서 타입을 지정해주기 때문에 따로 타입을 체크하고 변환해줄 필요가 없다.(관리의 용이)
    비슷한 기능을 지원하는 경우 코드의 재사용성이 높아진다.

반드시 한글자일 필요는 없다. 다만 대중적으로 통상하는 통상적 선언이다.

  • 클래스 및 인터페이스 선언
    public class ClassName<T> { … }

public Interface InterfaceName<T> { … }
    기본적인 제네릭타입의 클래스나 인터페이스는 위와같이 선언한다. T타입은 해당 블럭 { … } 안에서까지 유효하다.
    public class ClassName <T, K> { ... }
public Interface InterfaceName <T, K> { ... }
 
// HashMap의 경우 아래와 같이 선언되어있을 것이다.
public class HashMap <K, V> { ... }
    제네릭 타입을 두개로 둘 수도있다. ( 대표적으로 타입인자를 두개 받는 HashMap ) 이렇게 생성된 제네릭클래스를 사용할 땐
    public class ClassName <T, K> { ... }
 
public class Main {
	public static void main(String[] args) {
		ClassName<String, Integer> a = new ClassName<String, Integer>();
	}
}
    이런식으로 된다. T는 String이 되고 K는 Integer가 되는 것이다. 주의해야 할 점은 타입 파라미터로 명시할 수 있는 것은 참조타입(Reference Type)밖에 올 수 없다. 즉 int, double, char 같은 primitive type은 올 수 없다. 그래서 Integer, Dobule 같은 Wrapper Type으로 사용한다. 제네릭클래스
    // 제네릭 클래스
class ClassName<E> {
	
	private E element;	// 제네릭 타입 변수
	
	void set(E element) {	// 제네릭 파라미터 메소드
		this.element = element;
	}
	
	E get() {	// 제네릭 타입 반환 메소드
		return element;
	}
	
}
 
class Main {
	public static void main(String[] args) {
		
		ClassName<String> a = new ClassName<String>();
		ClassName<Integer> b = new ClassName<Integer>();
		
		a.set("10");
		b.set(10);
	
		System.out.println("a data : " + a.get());
		// 반환된 변수의 타입 출력 
		System.out.println("a E Type : " + a.get().getClass().getName());
		
		System.out.println();
		System.out.println("b data : " + b.get());
		// 반환된 변수의 타입 출력 
		System.out.println("b E Type : " + b.get().getClass().getName());
		
	}
}
    ClassName 이란 객체를 생성 할 때,<>안에 타입파라미터를 지정한다. 그러면 a객체의 ClassName의 E 제네릭 타입은 String으로 모두 변환된다. 반대로 b객체의 ClassName의 E 제네릭 타입은 Integer로 모두 변환된다. < 결과 >
    a data : 10
    a E Type : java.lang.String b data : 10 b E Type : java.lang.Integer

3. Big-O(시간복잡도)

입력된 N의 크기에 따라 실행되는 조작의 수를 말한다. 표기법 (Big-O)

 a. O(1) - 상수시간 : 입력값 n이 주어졌을 때 연산 1번만 수행

 b. O(log N) - 로그시간 : 입력값 n이 주어졌을 때, 특정한 요건에 따라 필요한 단계가 연산이 줄어든다. (이진트리검색)

 c. O(n) - 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1관계 (반복문)

 d. O(n^2) - 2차 시간 : 문제를 해결 하기 위한 단계의 수는 입력값의 제곱(이중 반복문)

시간복잡도에서 중요하게 보는 것은 가장 큰 영향을 미치는 n의 단위이다.

e. O(C^n) - **지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수 C의 n제곱**

실행시간은 
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!) < O(n^n) 순으로 오래걸린다.

4. ArrayList와 LinkedList 차이

  • ArrayList는 내부인덱스를 이용하여 검색이 한번에 이루어지기 때문에 빠른검색속도를 보장하지만, 데이터 추가 / 삭제 시 많은 데이터가 밀리거나 당겨지기 때문에 많은 시간이 소요된다.
    (검색 강점)

  • LinkedList는 추가 / 삭제 시 인근 노드들의 참조값만 수정해 줌으로써 빠른 처리가 가능하지만, 데이터를 검색할 경우 해당 노드를 찾기 위해 처음부터 순회검색을 해야 하기 때문에, 데이터의 수가 많아질수록 효율이 떨어진다.
    (데이터 추가/삭제 강점)

5. Stack

  • LIFO(Last in First Out) 후입선출이라 부른다. 
    Stack st = new Stack(); // 타입 설정x Object로 선언
    Stack<StackDemo> demo = new Stack<StackDemo>(); // class타입으로 선언
    Stack<Integer> i = new Stack<Integer>(); // Integer타입 선언
    Stack<Integer> i2 = new Stack<>(); // 뒤의 타입 생략 가능
    		
    Stack<String> s = new Stack<String>(); // String타입 선언
    Stack<Character> ch = new Stack<Character>(); // Char타입 선언

스택의 선언방법이다.
Stack<타입> 변수명 = new Stack<타입>(); 

타입선언을 생략해도 되지만 처음들어간 타입으로 입력을 계속하지않으면 타입오류가 발생하므로 명확하게 선언해주는것이 좋다.

- push()  :값을 추가한다.
- pop() : 값을 삭제한다. <맨마지막에 들어간값 삭제>
- clear()  : 초기화
- firstElement() : 처음 값 불러오기
- lastElement() : 마지막값 불러오기
- peek() : 마지막값 불러오기
- get(int i) : 스택의 index값 출력
- contains(Object) : 값의 여부를 찾아 true, false 반환
- indexOf(int index) : 값의 위치를 반환
    import java.util.Iterator;
    import java.util.Stack;
    
    public class StackDemo {
    	public static void main(String[] args)  {
    		Stack<String> s = new Stack<String>();
    		
    		// Stack 값 추가
    		s.push("Hello");
    		s.push("World");
    		
    		// firstElement(), lastElement(), peek()을 사용 -> 처음, 마지막, 마지막 값을 불러온다
    		System.out.println("처음 값 : " + s.firstElement());
    		System.out.println("마지막 값 : " + s.lastElement());
    		System.out.println("마지막 값 : " + s.peek());
    		
    		// get(i) 메서드를 사용하여 Stack의 Index 값을 출력
    		for(int i = 0; i < s.size(); i++)
    			System.out.print(s.get(i) + " ");
    		
    		System.out.println();
    		
    		// 향상된for문을 사용하여 Stack의 값을 출력
    		for(String str: s)
    			System.out.print(str + " ");
    		
    		// Iterator를 사용하여 Stack의 값을 출력 
    		Iterator iter = s.iterator();
    		while(iter.hasNext())
    			System.out.print(iter.next() + " ");
    	}
    }

6. Queue

  • FIFO( First In First Out )

Enqueue : 큐 맨 뒤에 데이터 추가
Dequeue : 큐 맨 앞쪽의 데이터 삭제

- 큐 한쪽 끝은 Front로 정해 삭제 연산만 수행
- 다른 한쪽 끝은 Rear로 정해 삽입연산만 수행
- 그래프의 넓이 우선탐색(BFS)에서 사용
- 컴퓨터 버퍼에서 주로 사용, 마구 입력이 되었으나 처리하지 못할 때, 버퍼(큐)를 만들어 대기
    import java.util.LinkedList; //import
    import java.util.Queue; //import
    Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언, linkedlist 이용
    Queue<String> queue = new LinkedList<>(); //String형 queue 선언, linkedlist 이용
  • 큐는 LinkedList를 활용하여 생성해야함.
    • add(value) , offer(value) : 값추가 add는 삽입 성공시 true 반환
    • poll(), remove() : 값제거, poll은 큐가 비어있으면 null 반환
    • clear() : 초기화
    • peek() : 첫번째 값 불러오기

7. Tree

  • 비-선형구조

  • 노드 : 트리에서 각각의 구성요소

  • 레벨 : 트리에서 각각의 층을 나타내는 단어 ( 루트 노드는 0 )

어떻게 저장???

  • 데이터와 연결상태를 저장 할 클래스 공간(=노드) 생성
  • 각각의 노드들에 값 저장
  • 노드 간 연결상태 정의

이진트리(자식노드가 최대 2개인 트리)

— Node

  • void addLeft(Node node) : 현재 노드 좌측에 노드연결정보 추가
  • void addRight(Node node) : 현재 노드 우측에 노드연결정보 추가
  • void deleteLeft() : 현재 노드 좌측 노드 연결정보 삭제
  • void deleteRight() : 현재 노드 우측 노드 연결정보 삭제

— Tree

  • node addNode(Object data) : 노드 새롭게 생성 (저장될데이터는 data 변수안에 존재하는 값)
  • void preOrder(Node node) : 전위 순회방법을 이용해 출력
  • void inOrder(Node node) : 중위 순회방법을 이용해 출력
  • void postOrder(Node node) : 후위 순회방법을 이용해 출력

Tree Class

package Tree;

public class Tree {
	int count;
	
	public Tree() {
		count = 0;
	}
	
	public class Node {
		Object data;
		Node left;
		Node right;
	
		// 생성 시 매개변수를 받아 초기화하는 방법으로만 선언 가능
		public Node(Object data) {
			this.data = data;
			left = null;
			right = null;
		}

		public void addLeft(Node node) {
			left = node;
			count++;
		}

		public void addRight(Node node) {
			right = node;
			count++;
		}

		public void deleteLeft() {
			left = null;
			count--;
		}

		public void deleteRight() {
			right = null;
			count--;
		}
	}
	
	public Node addNode(Object data) {
		Node n = new Node(data);
		return n;
	}
	
	public void preOrder(Node node) {
		if(node == null) {
			return;
		}
		
		System.out.print(node.data + " ");
		preOrder(node.left);
		preOrder(node.right);
	}

	public void inOrder(Node node) {
		if(node == null) {
			return;
		}
		
		inOrder(node.left);
		System.out.print(node.data + " ");
		inOrder(node.right);
	}

	public void postOrder(Node node) {
		if(node == null) {
			return;
		}
		
		postOrder(node.left);
		postOrder(node.right);
		System.out.print(node.data + " ");
	}
}

Run Class

import Tree.*;
import Tree.Tree.Node;

public class Run {
	public static void main(String[] args) {
		// 트리 생성
		Tree tree = new Tree();
		
		// 노드 생성
		Node node1 = tree.addNode(1);
		Node node2 = tree.addNode(2);
		Node node3 = tree.addNode(3);
		Node node4 = tree.addNode(4);
		Node node5 = tree.addNode(5);
		Node node6 = tree.addNode(6);
		Node node7 = tree.addNode(7);
		
		// 트리 연결관계 생성
		/*  트리 모양       
		 *        1
		 *     2     3
		 *   4  5  6   7
		 */
		node1.addLeft(node2);
		node1.addRight(node3);
		node2.addLeft(node4);
		node2.addRight(node5);
		node3.addLeft(node6);
		node3.addRight(node7);
		
		// 순회
		tree.preOrder(node1);
		System.out.println();
		tree.inOrder(node1);
		System.out.println();
		tree.postOrder(node1);
		System.out.println();
		
		// 삭제
		node2.deleteLeft();
		node3.deleteRight();
		/* 삭제 이후 트리 모양
		 *        1
		 *     2     3
		 *      5  6   
		 */
		
		// 순회
		System.out.println();
		tree.preOrder(node1);
		System.out.println();
		tree.inOrder(node1);
		System.out.println();
		tree.postOrder(node1);
		System.out.println();
	}
}

참조: https://readerr.tistory.com/35

8. check exception, uncheck exception ( exception 구조도 참고 )

  • 예외처리 필수적으로 해야하는 Checked Exception
  • 안해도 되는 Unchecked Exception

    Error 및 RuntimeException을 상속하지 않는 클래스는 Checked Exception,
    상속한 클래스는 Unchecked Exception.

9. 함수형 인터페이스에 선언문이 하나인 이유는?

  • 람다 기능을 용이하기 하기 위해서..
    람다식은 하나의 메서드에 대해서만 구현을 제공할 수 있으므로..
    두개 이상의 추상 메소드를 사용한다면 어떤 메소드를 호출해야할지 모를것…
    @FunctionalInterface
interface MyInterface {
    void display();
    void display(int x, int y);
}
    public class LambdaExpression {
    public static void main(String[] args) {
        MyInterface ref = () -> System.out.print("It is display from sout");
        ref.display(2, 3);
    }
}
    [https://stackoverflow.com/questions/23342499/why-functional-interfaces-in-java-8-have-one-abstract-method]
profile
NaSC
데이터엔지니어 😘
이전 포스트

[JAVA] 개념 정리 2

다음 포스트

[JAVA] 개념 정리 4

0개의 댓글