알고리즘 1

알고리즘 정리

 

정보 = 구조화 된 데이터 = 자료구조

처리 = 논리적 절차 = 알고리즘

자료구조 + 알고리즘 = 프로그램

 

데이터 표현 형식

Primitive Type

byte, short, int, long, float, double, char, boolean

메모리에 변수명과 변수값이 같이 존재함 (변수가 가르키는 메모리 위치에 실제값이 들어있다.)

 

Reference Type(= Object Type)

String, 

메모리에 변수명(변수값을 가르키는 변수가 됨, 참조 주소)과 변수값이 따로 존재함

 

call by value

void main(){
  int v = 42;
  // 실제 값 전달
  method(v);  //42
}

void method(int v){
  // 실제 값이 84로 변경되었으나
  // method 를 빠져나오면서 사라진다.
  v = v * 2;
}

call by reference

void main(){
  Data v = new Data(); // 인스턴스화
  v.d = 42;
  // 주소값 전달
  method(v); // 84
}

void method(Data v){
  // 주소값이 가르키는 d값이 변경되었기 때문에
  // 주소 값이 반환되지 않아도 v.d는 84가 된다.
  v.d = v.d * 2;
}

class Data { 
  int d;
}

자료구조란?

데이터를 어떻게 구성하는가

 

알고리즘이란?

데이터를 어떻게 처리하는가

 

Mutable, Immutable

Mutable : 변경 할 수 있는 값

 

Immutable  : 변경 할 수 없는 값

final이 붙은 primitive 값, Wrapper class, String 등

String의 내용이 변경 되는 경우 기존의 값이 변경되는 것이 아니라 새로운 인스턴스가 생성되는 것.

같은 내용의 문자열은 기존에 생성되었던 인스턴스를 재사용하게 되므로 같은 인스턴스를 가르키게 된다.

String str1 = "Hello";
String str2 = str1 + " World";
System.out.println(str1 == str2); // false

String str3 = "Hello";
System.out.println(str1 == str3); // true

알고리즘 성능 측정 기준

1. 정확성 : 동일한 입력에 대해 항상 동일한 결과를 반환하는가

2. 작업량 : 얼마나 적은 연산으로 결과를 만들어 내는가 ( 시간 복잡도 )

3. 메모리 사용량 : 얼마나 적은 메모리를 사용하여 결과를 만들어 내는가( 공간 복잡도 ) 

4. 단순성 : 얼마나 단순한 구현으로 결과를 만들어 내는가

5. 최적성 : 컴퓨터의 동작 기준, 최적화 되어 있는가

 

Big-O notation(빅 오 표현식) 이란?

알고리즘의 시간 복잡도를 나타내는 표기법으로 O(f(n))으로 나타낸다.

실행시간은 최대한 이만큼 커지지만 더 천천히 커질 수도 있다는 점근적 표기법

 

 

 

Array

1. 여러개의 데이터를 다룰 수 있다.

2. 첫번째 위치만 알면 index로 빠르게 데이터를 찾을 수 있다.

3. 미리 공간을 확보해 놓고 써야 한다. 

4. 한번 만들어진 공간은 크기가 고정된다.(크기 변경X)

5. 메모리 상에 공간을 연달아 확보한다.

6. Object는 아니지만 Reference Value로 취급된다.

결론 : 데이터를 읽어오는건 빠르지만 유연하지 못하다.

 

List

1. 여러개의 데이터를 한꺼번에 다룰 수 있다.

2. 첫번째 위치에서 원하는 위치를 알려면 한칸한칸 이동하면서 찾아야 한다. (접근성이 떨어짐)

3. 미리 공간을 확보해 놓지 않아도 된다.

4. 필요에 따라 데이터가 늘어나거나 줄어든다.

5. 메모리 상에 공간이 연속되지 않아도 된다.

결론 : 배열보다 데이터를 찾는데는 오래걸리지만 유연하게 메모리를 사용할 수 있다.

 

ArrayList vs LinkedList

  - 순차적으로 데이터를 추가/삭제하는 경우에는 ArrayList가 더 빠르다.

    ArrayList 의 크기가 충분하지 않으면, 새로운 크기의 ArrayList를 생성하고 데이터를 복사하는 일이 발생하므로

    순차적으로 데이터를 추가해도 ArrayList가 LinkedList보다 더 느릴 수 있다.

  - 중간에 데이터를 추가/삭제하는 경우에는 LinkedList가 더 빠르다.

     LinkedList 는 각 요소 간의 연결만 변경해주면 되기 때문에 처리속도가 빠른 반면,

     ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야 하기 때문에 처리속도가 늦다.

 

 

Map

유연하면서 빠른 자료구조, Array와 List의 장점을 합친 자료구조

 

key의 범위(배열 크기)를 bucket이라고 한다.

bucket은 겹치지 않은 index로 구성되어져 있다.

이 index는 hashing값으로 되어있다. (hash function을 이용하여 hash code를 생성한다.)

따라서 키를 찾을 때 hashcode라는 함수로 키 값을 해쉬하여 찾아야 한다.

키 값이 중복되면 hash collision이 발생한다.

// key값이 hash function에 의해 hash 값으로 변경되고,
// 그 hash값이 bucket의 index가 되기 때문에
// custom data를 map의 key 값으로 사용 하려면 hash값을 알아야 한다.
class MyData {
	int v;
	public MyData(int v) {this.v = v;}
	
	@Override
	public String toString() {return ""+ v;}

	@Override
	public int hashCode() {return Objects.hash(v);}

	@Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof MyData)) return false;
        MyData myd = (MyData)o;
        return this.v == myd.v;
    }
}
public class MapTraining {	
	public static void main(String[] args) {
		Hashtable<MyData, Integer> map = new Hashtable<>();
		map.put(new MyData(1), 1); // {1 = 1}
		map.put(new MyData(2), 2); // {2 = 2}
		map.replace(new MyData(1),  1, 11); // 1이 1이면 11로 변경
		method1(map);	
	}
	
	static void method1(Map<MyData, Integer> map) {
        System.out.println(map); // {1=11, 2=2}
        System.out.println(map.remove(new MyData(2),  3)); // false. 2 = 3 일 경우 삭제
        // hashCode와 equals를 override 해줘야 값이 나타난다.
        System.out.println(map.get(new MyData(1))); // 11
        System.out.println(map.getOrDefault(new MyData(1), -1)); // 11, key=1 에 값을 가져오거나 값이 없을 경우 -1 반환.
        System.out.println(map.values()); // [11,2], 값 반환
        System.out.println(map.keySet()); // [1,2], 키 반환
	}
}

Key - Value 형태의  Dictiionary 를 가지고 있다.

 

참고 :  [Java] equals() & hashcode() 메서드는 언제 재정의해야 할까?

Map Interface를 implement하는 대표 Class

 - HashMap

   key-value의 쌍으로만 구성이 될 뿐 자료구조 안에 묶인 쌍들에 대한 순서는 보장할 수 없다.

   즉, 사용자는 키와 값이 구성되는 위치를 결정하거나 알 수 없다.

 

- TreeMap

    key의 값을 이용해 순서대로 정렬하여 데이터를 저장하는 자료구조

    key값을 통한 탐색 뿐 아니라 key값의 정렬을 통한 탐색 등을 하기에 용의하다.

 

- LinkedHashMap

    데이터를 입력한 순서대로 쌓아지며 데이터를 저장하는 자료구조

    배열, 리스트 처럼 인덱싱 접근을 하기에 용이하다.

 

 

Set

중복된 값을 허용하지 않는다.

선형데이터 구조 + 탐색 알고리즘

Set<Integer> setA = new HashSet<>(); // 순서를 보장하지 않는다.
Set<Integer> setB = new HashSet<>();

// A 집합
setA.add(1);
setA.add(2);
setA.add(3);

// B 집합
setB.add(2);
setB.add(3);
setB.add(4);

// 합집합 A+B
setA.addAll(setB); // [1, 2, 3, 4]

// 차집합 A-B
setA.removeAll(setB); // [1]

// 교집합 A*B
setA.retainAll(setB); // [2, 3]

 Stream을 사용하여 중복제거

List<String> list = Arrays.asList("A", "B", "C", "A", "B", "C");
List<String list2 = list.stream().distinct().collect(Collectors.toList()); // [A, B, C]
// distinct : 중복 제거
// collect : stream을 다시 list로 만들어 줌

Stack

• public class Stack<E> extends Vector<E>
• 마지막에 들어온 값이 가장 먼제 삭제되는 last-in-first-out (LIFO, 후입선출) 의 대표적인 구조로 클래스이다. 
• Vector를 Stack으로 처리 할 수 있도록 5가지 operations(method)를 가지고 있다.

Method	반환타입	Description
push(E item)	E	E 타입의 값을 stack 맨 위에 추가
pop()	E	stack 맨 위에 있는 값를 삭제하고 삭제된 값을 반환
peek()	E	stack 맨 위에 있는 값을 조회 ( 값 삭제 X )
search(Object o)	int	입력 값의 위치 반환
empty()	boolean	stack이 비어있는지 확인

Stack<Integer> stack = new Stack<>();
		
stack.empty();  // true

for(int i=1; i<=5; i++) {
	stack.push(i); // [1, 2, 3, 4, 5]
}

stack.empty();   // false
stack.search(7); // 4
stack.peek();    // 5
stack.pop();     // 5
stack.peek();    // 4

 

활용 예

• 뒤로가기 : 마지막에 열린 페이지로 돌아간다.
• 실행 취소(undo) : 마지막에 실행한 것부터 실행을 취소한다.
• 깊이 우선 탐색(DFS, Depth-First Search), 역순 문자열 만들기  등등

Queue

• public interface Queue<E> extends Collection<E>
• 먼저 들어온 값을 먼저 처리하는 First-in-first-out(FIFO, 선입선출)  의 대표적인 구조로 인터페이스다.
• 동시에 처리해야하는 프로그램에 대해서 블로킹 처리를 하지 않는다. ( BlockingQueue interface에서 처리)

메소드 유형	반환타입	예외 처리하는 메소드	Description	값을 반환하는 메소드	Description
Insert	boolean	add(E e)	E 타입의 값 삽입후 true 반환 용량 초과시 IllegalStateException	offer(E e)	E 타입의 값 삽입후 true 반환
Remove	E	remove()	값이 없으면 NoSuchElementException	poll()	값이 없으면 null 반환
Examine	E	element()	값이 없으면 NoSuchElementException	peek()	값이 없으면 null 반환

활용 예

• 우선 순위가 같은 작업 (ex, 프린트)
• 프로세스 관리
• 캐시(Cache) 구현
• 너비 우선 탐색(BFS, Breadth-First Search)

-- 다음에 할거

Linear Search

Sort 정렬

Graph와 Non-Linear Search

Tree