my practice

데이터 군을 저장하는 클래스들을 표준화한 설계

컬렉션 Collection : 다수의 데이터, 데이트 그룹

프레임웍 Framework : 표준화된 프로그래밍 방식

Vector, Hashtable, Properties 같은 컬렉션 클래스, 다수의 데이터를 저장할 수 있는 클래스들을 서로 다른 각자의 방식으로 처리해야 했으나, 컬렉션 프레임웍이 등장하며 다양한 종류의 컬렉션 클래스가 추가, 모든 컬렉션 클래스를 표준화된 방식으로 다룰 수 있도록 체계화됨

컬렉션 데이터 그룹 크게 3가지 타입이 존재한다고 인식, 각 컬렉션을 다루는데 필요한 기능을 가진 3개의 인터페이스

List , Set -> Collection

Map

List : 순서가 있는 데이터의 집합, 중복 허용 : ArrayList, LinkedList, Stack, Vector

Set : 순서를 유지하지 않는 데이터의 집합, 중복 허용 안됨 : HashSet, TreeSet

Map : 키와 값의 쌍으로 이루어진 데이터 집합, 순서 유지 안됨, 키는 중복 허용 안됨, 값은 중복 가능 : HashMap, TreeMap, HashTable, Properties 등

컬렉션 프레임워크의 모든 컬렉션 클래스들은 List, Set, Map 중의 하나를 구현하고 있고 인터페이스 이름이 클래스 이름에 포함되어 있어

Vector, Stack, Hashtable, Properties 같은 클래스들은 컬렉션 프레임웤이 만들어지기 전부터 있던거라 명명법 따르지 않음

Object > Abstract Collection  > Abstract List > Vector

 Collection > List  > Vector

Collection 인터페이스는 컬렉션 클래스에 저장된 데이터를 읽고 추가하고 삭제하는 컬렉션을 다루는데 가장 기본적인 메서드 정의

add, addAll : 지정된 객체/Collection 객체를 컬렉션에 추가

clear() : 컬렉션의 모든 객체 삭제

contains, containsAll : 지정된 객체/Collection 객체가 컬렉션에 포함되어있는지 확인

equals() : 동일한 컬렉션인지 비교

hashCode : Collection의 hash code 반환

isEmpty()

iterator : Collection의 iterator 얻어서 반환

remove() 지정된 객체 삭제

removeAll(c) : 지정된 컬렉션에 포함된 객체 삭제

retainAll(c) : 지정된 컬렉션에 포함된 객체만 남기고 나머지 삭제, 이 작업으로 컬렉션에 변화가 생기면 true

size() : 컬렉션에 저장된 객체 개수 반환

toArray() : 컬렉션에 저장된 객체를 객체배열로 반환

List 인터페이스 : 중복 허용 , 저장 순서 유지

add addAll get(index) indexof(Object) remove, set(index, element), sort(comparator), subList(from to)

- Vector, Stack, ArrayList, LinkedList

Set 인터페이스 : 중복 허용안됨, 저장 순서 유지 안됨

HashSet, SortedSet, TreeSet

Map 인터페이스 : 키는 중복 안됨

HashTable, HashMap, LinkedHashMap, SortedMap, TreeMap

Map.Entry 인터페이스 : Map 인터페이스 내부 인터페이스

보다 객체지향적으로 설계하도록 유도하기 위한 것, Map 인터페이스를 구현하는 클래스에서는 Map.Entity 인터페이스 함께 구현해야 함

ㅔ

현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘

탐욕법

출제 폭이 매우 넓다. 

키워드 : 가장 큰 순서대로, 가장 작은 순서대로 

정당성:

모든 알고리즘 문제에 적용할 수 없다. 

최적의 해를 못찾을 가능성이 더 높음

탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때 매우 효과적

문제 풀이를 위한 최소한의 아이디어와 정당한지 검토

기초 알고리즘에 기반하는 문제

완전탐색

그리디 

구현

DFS/BFS

이진 탐색

정렬

고급 : 다이나믹 프로그래밍, 그래프이론, 정수론, 최단경로

일반적 코테 : 2~5 시간 시간 동안 8개 이하 문제 풀기 - 심리적 부담

복잡도 : 알고리즘의 성능을 나타내는 척도

복잡도 = 시간 복잡도 + 공간 복잡도

시간 복잡도 : 특정 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지

공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지

동일 기능 수행하는 알고리즘이 있다면 일반적으로 복잡도 낮을 수록 좋은 알고리즘

효율적 알고리즘 : 시간 복잡도와 공간 복잡도는 거래 관계 

메모리를 더 사용하는 대신 반복되는 연산 생략/ 더 많은 정보 관리하며 계산 복잡도 줄임

시간 복잡도 = 시간 제한

Big O 표시 : 가장 빠르게 증가하는 항 만 고려하기

단순한 이중 반복문의 경우 N * N 이겠지만 내부적 함수 호출이 있다면 더 늘어난다.

일반적으로 N^3 을 넘어가면 문제 풀이 때 못쓴다.

연산 횟수가 10억을 넘으면( N이 5000을 넘으면) 못씀

시간 복잡도 분석이 문제 풀이의 핵심- 문제의 조건을 보고 얼마나 효율적인 알고리즘을 짜야 하는지 파악함

N : 1000만, 제한시간 1초 

최악의 경우 O(N) 으로작성해야

시간 제한 1초 기준

N : 500 -> N3

N : 2000 -> N2

N : 100000 -> NlogN

N : 10000000 : N

으로 작성해야 풀이가 가능

공간 복잡도 = 메모리 제한

코테는 대부분 리스트를 사용하는데, int 가 4B인거 생각하면

128 MB는 데이터가 1000만 단위가 넘어가지 않도록 설계 해야 한다

선택 정렬은 30초단위라면 기본 정렬 라이브러리는 1초도 안걸린다.

-> 설계한 알고리즘 성능 확인이 필요