자료구조 알고리즘 List, Set, Map은 다 배열과 LinkedList로 만들어진다.
시간 복잡도
시간복잡도는 빅오(big-O) 표기법으로 나타낸다.
O(1) < O(log n) < O(n) < ... 순으로 표현하며, 뒤로 갈 수록 성능이 낮아진다.
ArrayList의 값 접근속도는 O(1)이지만, 삭제속도는 O(n)이다. LinkedList는 접근속도가 O(n)지만 삭제속도는 O(1)이다. 하지만, ArrayList도 무조건 삭제속도가 O(n)인 것은 아닌데, 맨 끝에 있는 값을 삭제할 때는 O(1)이 된다. 그렇기 때문에 Stack을 ArrayList로 구현하는 것이다. Stack은 맨 마지막의 값만 삭제하기 때문. 참고로 보통 빅오 표기법은 최악의 경우만 표현한다.
Set
set은 입력 순서가 상관이 없으며, 똑같은 값이 들어갈 수 없다. 작동 원리는 LinkedList와 거의 똑같지만, Node를 연결하는 방법이 다르다. 자주 사용을 하지는 않지만 보통 탐색을 할 때 사용한다. ex) 욕설 필터링 등... 아지만, 그건 DB에서도 할 수 있다... 또한, 문자열을 set으로 다루기 위해선 복잡한 과정이 들어가기 때문에 잘 안쓰인다.
장점: 탐색 속도가 매우 빠르고 자동적으로 정렬돼서 출력된다.
단점: add 과정이 복잡하기 때문에 속도가 매우 느리며, 값의 삭제는 있어서는 안되는 수준이다.
- TreeSet: TreeSet은 이진트리 방식으로 숫자의 크기에 따라 Node를 연결한다. TreeSet의 노드는 value, next만 존재하는 LinketList와 달리, TreeSet의 Node는 left, value, right 가 있다. 당연히 value에는 입력 받은 값이 있으며, left, right에는 값이 연결된다. TreeSet에는 LinkedList에 있는 first와 같이 시작점인 root가 존재하는데, add가 진행되면 root를 따라서 값이 연결된다. 첫번째 add에는 root에 입력 받은 값이 노드로 연결되고, 다음부터 진행되는 add는 첫번째 Node의 value와 값의 크기를 비교한 후 연결이 된다. 값이 첫번째 Node의 value보다 크다면 rigth에 저장이 되고, 작다면 left에 저장이 되며, 얘도 결국 Node를 타고 null값을 찾아 다니는것이기 때문에 값을 입력받아서 비교 후 값을 넣으려고 left나 right를 봤을때 그 값이 null이 아니라면 또 그 값을 타고 가서 다음 Node로 가서 값을 비교하고 null값인지를 확인하길 반복하다가, null값을 찾았으면 그곳에 입력 받았던 값의 Node를 연결한다. 그렇기 때문에 양쪽으로 값이 연결되는 이진 트리 구조인 것이다.
TreeSet 예시
여기서, 저 값이 몇번째로 들어왔는지는 알 수 없다. 값의 크기로만 값을 연결하기 때문에.
[p0]
package p0;
import java.util.ArrayList;
import java.util.List;
public class App {
public static void main(String[] args) {
List<Integer> set = new ArrayList<>();
set.add(10);
set.add(15);
set.add(5);
set.add(7);
set.add(20);
set.add(10); // 값의 중복이 안됨.
set.add(6);
for(int e : set) {
System.out.println(e);
}
// 출력을 해보면 작은 숫자 순서로 출력이 된다.
// 정렬 되어있기도 하고, 값을 찾을때 무조건 왼족의 마지막 값을 찾아서 출력하고
// 쭉 올라가면서 출력하고, 거기서 오른쪽으로 가서 출력하고 맨 왼쪽으로 가서...
}
}[p1]
package p1;
import java.util.ArrayList;
import java.util.List;
public class App {
public static void main(String[] args) {
List<Integer> result = new ArrayList<>();
while(true) {
int randomNumber = (int)(Math.random()*46) + 1;
// 중복 값인지 확인 - 풀 스캐닝
// 중복된 값인지 확인하는 과정에서 매우 많은 반복이 생긴다.
// boolean isDuplicated = false;
// for(int e : result) {
// if(randomNumber == e) {
// isDuplicated = true;
// }
// }
// if(!isDuplicated) {
// result.add(randomNumber);
// if(result.size() >= 6) {
// break;
// }
// }
// 이렇게 쓸 수도 있지만 아래처럼 contains 쓸 수도 있다.
// set과 같은 contains를 호출 하지만, 반복의 구조는 완전히 다르다.
if(!result.contains(randomNumber)) {
result.add(randomNumber);
if(result.size() >= 6) {
break;
}
}
}
}
}[p2]
package p2;
import java.util.Set;
import java.util.TreeSet;
public class App {
public static void main(String[] args) {
Set<Integer> result = new TreeSet<>();
while(true) {
int randomNumber = (int)(Math.random() * 46) + 1;
if(!result.contains(randomNumber)) {
// set계열의 핵심 API: contains
result.add(randomNumber);
if(result.size() >= 6) {
break;
}
}
}
}
}Map
- Hash: HashMap을 설명하기 전에, Hash 알고리즘을 먼저 설명 해야한다. Hash 알고리즘은 보안, 암호화, 비트코인, 파일 결함 확인 등에 쓰인다. 암호화 알고리즘에는 복호 가능한 알고리즘과 복호가 불가능한 알고리즘이 있는데, Hash알고리즘은 복호가 불가능한 알고리즘이다. 데이터를 비트 단위로 잘게 쪼개서 연산 후, 특정 범위의 값으로 만든다. f(x) = y 를 반복하며, y값을 가지고 x 값을 유추 할 수 없다. 입력된 값을 자릿값으로 나누고, 부호를 바꾸고, 뒤집고, 뭐하고뭐하고... 하면서 값을 비틀어 저장을 하게 된다. Hash를 거친 후의 값이 랜덤이라고 생각될 정도의 값이 나와야 하며, 한글자만 바뀌어도 아예 다른 값이 되어야 한다. Hash를 거쳐서 나온 결과값이 64개의 bit로 이루어진다면 64bit Hashing인 것. Hash의 핵심은 "입력의 경우의 수는 무한에 해당하고, 64bit Hash알고리즘을 통하면, 결과값은 유한해진다." 가 된다. 이 경우 결과값의 범위는 2의 64제곱이 된다. 이걸 반대로 할 경우 유한한 값에서 무한한 값을 알아내야 하기 때문에 복호화가 불가능 한 것이다.
- HashMap: 배열과 LinkedList의 조합으로 이루어진다. 키와 값으로 저장하며, 키를 가지고 Hash를 해서 나온 결과값을 배열의 Index로 사용한다. 배열을 사용하기 때문에 put, get 속도가 매우 빠르다. 무한한 값을 가지고 유한한 값을 만들어내기 때문에 Hash 충돌이 무조건 일어나며, 이럴땐 그 인덱스에 LinkedList로 연결한다.
HashMap 예시
[p3]
package p3;
import java.util.Objects;
public class App {
public static void main(String[] args) {
// Hash 알고리즘
int result = Objects.hash("안녕하세요!!!");
System.out.println(Integer.toHexString(result));
result = Objects.hash("반갑습니다");
System.out.println(Integer.toHexString(result));
result = Objects.hash("1111");
System.out.println(Integer.toHexString(result));
result = Objects.hash("안녕하세요!!!");
System.out.println(Integer.toHexString(result));
}
}[p4]
package p4;
import java.util.HashMap;
import java.util.Map;
public class App {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
// 나중에는 그냥 Map<String, Object> 로 쓰는게 정답.
map.put("철수의 점수", 40);
map.put("철수의 점수", 40); // key의 중복이 안되기 때문에 값이 수정 됨.
map.put("영수의 점수", 80);
map.put("민수의 점수", 50);
map.get("철수의 점수");
// map의 API는 put, get 밖에 없음
}
}자료구조 정리
자료구조는 데이터 저장을 위한 구조 알고리즘이다.
배열의 특징과 LinkedList(Node) 특징을 정확하게 이해하고 시작해야한다. 모든 자료구조 알고리즘은 배열 특징, LinkedList 특징을 확장해서 이용 하기 때문에.
사실 주요 알고리즘은 이미 컬렉션 프레임워크로 다 구현 되어있다. 하지만 이해를 하면 할 수록 컬렉션 프레임워크를 잘 이용 할 수 있고 이해를 잘 못하더라도 다형성을 이용해서 코딩하면, 언제든지 바꿀 수 있다. 또한, 이미 big-O 표기법으로 속도가 다 정리 되어 있기 때문에 필요시 검색을 통해 어떠한 것이 필요한지 잘 선택해서 쓰면 된다. 주의할건, 관점에 따라서 조금 그래프, 표가 바뀔 수있기 때문에 잘 봐야한다.
크게 구분 해보면, List(순서가 있음), Set(탐색 위주), Map(여러 형태의 데이터를 키와 값으로 "묶는" 용도)으로 나뉜다. 나머지는 이 아래에 속하는게 됨
제일 많이 사용되는 API는 ArrayList, HashMap이다. 극단적으로 많이 쓰이는 수준. 거의 99%정도는 이 두개만 쓴다. 추가적으로 쓰이는게, ArrayDeque(Queue, Stack, Deque)이다. Queue, Stack, Deque를 쓸 때는 무조건 ArrayDeque으로 써라. 그리고, Set을 쓸 때는 HashSet을 쓴다. 공부를 할 때는 TreeSet을 공부해야 하지만, 쓸때는 HashSet을 쓴다. HashSet은 날먹수준. HashMap을 그냥 안에 넣어놨다. 우선 순위 큐인 PriorityQueue(Heap)도 쓰인다. PriorityQueue는 이진 트리구조이며, add를 할때마다 재구성을 해서 작은 값, 혹은 큰 값을 맨위(root)로 올린다. 참고: HashMap은 비정석 코딩의 진수이다. 느슨하게 날로 먹는 느낌.
콜백
메서드를 미리 만들어두고, 실행할 로직은 사용하는 쪽이 정의해서 전달하며, 그 로직을 메서드를 제공한 쪽이 내부에서 호출하는 구조를 콜백이라고 한다.
[p5]
package p5;
public class App {
public static void main(String[] args) {
// 콜백
SomeComponent someComponent = new SomeComponent();
someComponent.doProcess(new MyFunction());
}
}
class MyFunction implements Function {
public void execute() {
System.out.println("App 만든 사람이 정의한 로직");
}
}
// App을 만드는 사람과 SomeComponent를 만드는 사람이 다른 사람이라고 가정하자.
// 이곳을 기준으로 위쪽 코드는 A라는 사람이 만들었고, 이 알는 B라는 사람이 만들었다.
interface Function {
public void execute();
}
class SomeComponent {
public void doProcess(Function function) {
// 상속 다형성 오버라이딩을 사용하는 방법이다.
System.out.println("직접 정의한 어떠한 코드들...1");
// 여기 로직은? 내가 구현할게 아닌데? (너무 추상적이게 될것 같음)
// 파라미터로 메서드를 주고 싶음. 근데 파라미터는 항상 값(변수)이었는데, 가능한가?
// 가능함. 인터페이스 문법을 쓰면 됨. 원래 인터페이스가 이 용도.
function.execute();
// 사실 Dependency Injection 코드가 다 이 경우였다. 얘도 DI인것..
System.out.println("직접 정의한 어떠한 코드들...2");
}
}람다식
코드를 최대한 어떻게든 줄이자. 추가적인 기능X (가독성 향상)
코드를 좀 트렌드하게 짜는 법이고 사용하는 경우가 정해져 있음. 기초적인 문법이 아니기 때문에, 어설프게 쓸거면 안쓰는게 나음. 근데 JavaScript에서는 무조건 써야 해서 몸에 익을거임. 근데 지금은 아님.
람다식 문법: 추상 메서드가 하나인 인터페이스(함수형 인터페이스)를 구현하는 것.
new 키워드로 익명 클래스를 생성하는 정석적인 방식 대신 컴파일러가 구현체 인스턴스를 자동으로 만들어 참조변수에 바로 대입할 수 있게 해주는 문법이 람다식이다.[람다식 기본구조] - 사용할 인터페이스 타입 참조변수 = () -> 구현부; // 이게 베스트 케이스 - 사용할 인터페이스 타입 참조변수 = () -> { 구현부 };또한, 람다식은 코드를 2줄 이상 쓰는것을 권장하지 않는다.
[p6]
package p6;
public class App {
public static void main(String[] args) {
// 람다식 문법
// 1. 인터페이스에 단 하나의 abstract 메서드가 호출된다.
// 정석 - 인터페이스 상속
AAA a1 = new AAAImpl();
// 옛날에 존재했던 방법 (익명 클래스) - 요즘은 권장되지 않음 (코드 단축이 목적)
AAA a2 = new AAA() {
@Override // 여기는 다 Interface를 상속받은 애들임
public void testA() {
// AAA를 상속받은 클래스이기는 한데, 이름이 없다.
// 아래에 클래스를 새로 생성하기 귀찮기 때문에 사용. - 코드의 단추을 위해서
// 클래스 명이 없지만 클래스 선언과 동시에 참조변수 a1에 생성된 인스턴스의
// 주소를 넣어줬기 때문에 클래스 이름 없이도 참조변수 이름으로 사용 가능.
System.out.println("안녕하세요!!");
} // 이렇게만 하면 sysout실행안됨 a2.testA(); 해야 실행 됨
};
a2.testA();
// 람다식 - 이거 잘 알기. a3에 넣을 수 있는게 무엇인지 잘 알기.
// a3에는 AAA를 상속받은 모든것이 들어갈 수 있다.
AAA a3 = () -> { // = 의 오른쪽에 들어갈 것은 적어도 AAA를 상속받은 클래스의 인스턴스여야 함.
System.out.println("반갑습니다.");
System.out.println("반갑습니다.");
System.out.println("반갑습니다."); // 람다식에서는 이것도 너무 길다.
}; // ; 붙는 이유는 a3 = 해서 값 넣는거라서
a3.testA();
}
}
interface AAA {
public void testA();
// public void testB(); 이러면 메서드가 하나가 아니라 람다식 사용이 불가능하다
}
class AAAImpl implements AAA {
@Override
public void testA() {
// ...
}
}[p7]
package p7;
public class App {
@SuppressWarnings("unused")
public static void main(String[] args) {
AAA a1 = () -> {
// 구현 로직
}; // 여기 ;은 a1 = 에 해당하는 것.
// 리턴 타입 O, 파라미터 X
BBB b1 = () -> {
// 여기에 return 없으면 오류. BBB의 리턴타입이 void가 아닌 int니까.
// 이건 그냥 클래스 문법. 모르면 안됨
System.out.println("...");
return 0;
};
// 리턴 타입 O, 파라미터 2개
CCC c1 = (a, b) -> {
// 오버라이딩이라 변수 이름 달라도 됨. 오버라이딩 할때는 변수 이름을 바꿀 수 있다.
// 변수 타입도 안써줘도 됨. 어차피 아래에 정의 되어있음. 극한으로 코드 줄이기
System.out.println("...");
return a + b;
};
// 리턴 타입 O, 파라미터 1개
// 파라미터가 한개일때는 소괄호 제거 가능하다. 제일 중요 케이스 - 다른때는x
DDD d1 = a -> {
System.out.println("...");
return 1;
};
// 코드가 한줄인 경우, 중괄호 제거 가능 - 대괄호에 붙어있는 ;도 제거 가능
AAA a2 = () -> System.out.println("...");
// 코드가 한줄이고, 리턴타입이 있는 경우는 대부분이 제거 가능
// 일반적으로 이게 베스트 케이스 코드. C와 D가 제일 유리
CCC c2 = (a, b) -> a+b; // return 생략해서 a+b를 리턴하고, {}도 제거함
// 람다식을 적용하는 기호가 화살표(->)인 이유:
// 코드를 보면 c2는 함수이고, c2는 변수 a, b를 가지고 코드를 만든다.
// 그니까, c2가 이렇게 되는거야. 라고 화살표를 통해서 말하는 것.
int result = c2.testC(3, 5);
System.out.println(result);
// 그러니까.. CCC를 상속받아서 인스턴스를 생성한걸 c2가 받은거고, c2는 CCC안에
// 있는 메서드 testC가 있고. 그러니까 결국 c2는 testC를 가지고 있는거니까.
// c2.testC로 메서드 호출이 되는것이다...?
// 코드가 한줄이고, 메서드를 그대로 호출하는 경우. 메서드를 참조 할 수 있다.
// 일반적인 베스트 케이스
CCC c3 = (a, b) -> {
return Math.ceilDiv(a, b);
};
// 위에 이거를 아래처럼 쓰는게 베스트 케이스..
// 근데 파라미터 값은 어디서? - 메서드 호출할때 받음. c4.testC(10, 20); 이렇게.
CCC c4 = Math::ceilDiv;
EEE e1 = System.out::println;
// 메서드 참조를 할때 파라미터가 없는 클래스를 상속 받았으면 파라미터가 없는
// 메서드만 사용 가능하고, 파라미터가 있는 클래스를 상속받으면 파라미터가 있는
// 메서드만 참조 가능
}
}
interface AAA {
public void testA();
}
interface BBB {
public int testB();
}
interface CCC {
public int testC(int a, int b);
}
interface DDD {
public int testD(int a);
}
interface EEE {
public void testE(int a);
}[p8]
package p8;
import java.util.ArrayList;
import java.util.List;
public class App {
public static void main(String[] args) {
// stream API - 배열을 생각하면 좋다. 절차대로 앞에서부터 하나하나 실행되니까.
// 람다식 사용
List<String> nameList = new ArrayList<>();
nameList.add("민수");
nameList.add("철수");
nameList.add("영수");
// 왠만해서는 사용하면 안되는 방법. 일반적인 구조에선 절대x
// 특수한 알고리즘 같은 경우엔 이것밖에 답이 없을때도 있음
for(int i = 0; i < nameList.size(); i++) {
System.out.println(nameList.get(i));
}
// 문법을 활용한 일반적인 방법 (향상된 for)
for(String name : nameList) {
System.out.println(name);
}
// 위에 있는 fot랑 forEach랑 같은거임.
nameList.forEach(System.out::println);
// 람다식은 stream API를 쓸 때가 아니면 잘 쓰이진 않음.
}
}람다식은 보통 stream API를 쓸때 자주 쓰이며, 그걸 함수형 프로그래밍 기법이라고 부른다. 장점으로는 메서드의 명칭이 매우 명확하다.
Consumer: 값을 받아서 “사용만” 하고, 결과를 돌려주지 않음
Predicate: 값을 받아서 조건 검사 → true / false 반환
Function: 값을 받아서 다른 값으로 변환해서 반환
[p9]
package p9;
import java.util.ArrayList;
import java.util.List;
import java.util.function.Consumer;
public class App {
public static void main(String[] args) {
// Consumer, Predicate, Function
// Consumer
List<String> nameList = new ArrayList<>();
nameList.add("민수");
nameList.add("진희");
nameList.add("철수");
nameList.add("영희");
nameList.add("철수");
nameList.stream().forEach(new Hello());
// stream(). 을 했을때 나오는게 함수형 프로그래밍을 지원하는 인터페이스
// 여기 안에 있는것들은 forEach 내부에서 nameList에 있는 요소들의 갯수 만큼
// 반복해서 자동으로 호출해준다. (함수 전달해줘, 우리가 실행 시켜줄게. 라는 뜻)
nameList.stream().forEach(System.out::println);
// Predicate
for(String name : nameList) {
if(!name.contains("수")) {
System.out.println(name);
}
}
// ㄴ 옛날 방식
// stream API가 만능은 아님. 이 코드 되게 위험할 수 있음 - 메소드 체이닝
nameList.stream() // 보통 여기부터는 내려서 쓴다. ;이 없으니까 한줄이긴 함.
.filter(NameFilter::notSu)
.filter(name -> name.length() < 5) // 이름이 5자 이상이면 거름
.forEach(System.out::println);
// ㄴ 요즘 방식
// filter는 값이 false면 걸러내겠다는 뜻. 즉 위에 코드는 이름에 "수"가
// 들어가거나, 이름의 길이가 5 이상이면 걸러낸다.
// 사실 filter가 나올때마다 요소의 갯수만큼 계속 반복문을 돌리기 때문에
// 위에있는 for문을 쓰면 반복 5번으로 끝날걸 이거는 지금 15번정도 반복이 돈다.
}
}
class NameFilter {
public static boolean notSu(String name) {
return !name.contains(name);
}
}
class Hello implements Consumer<String> { // 하나의 요소가 있는데 그게 String임
@Override
public void accept(String name) {
System.out.println(name);
}
}
취업하고싶다...