계란 블로그

- tree는 규칙이 없던 그래프와 다르게 규칙이 있다. 1. Bynary tree - Bynary tree: child는 두 개만 - 왼쪽부터 빠짐없이 채우면 => Complete Binary Tree - 빈 칸 없이 다 채우면 => Perfect Binary Tree 2. Tree읽는 방법 1) DFS - In Order Travel: left -> root -> right - Pre Order Travle: root -> left -> right - Post Order Travel: left -> right -> root 2) BFS - Level Order Travel 3. Heap - root에는 항상 최솟값이 있어야한다. => "Min heap' - root에는 항상 최댓값이 있어야한다. =>..

Note) 그래프 - 그래프는 비선형 자료구조이다. -> 노드와 엣지로 구성된다. -> 방향성과 가중치(weight)를 줄 수 있다. -> 자바에서는 그래프를 구성하는 노드와 엣지가 제공되지 않는다. -> 직접 노드와 엣지를 구성해서 그래프를 만든다. - 비선형 자료구조에서 원하는 데이터 찾기 1) 데이터 하나 읽기 2) 다음 번에 읽을 것을 예약 (연결된 데이터를 찾기) 3) 예약된 것을 하나 꺼내기 4) 2,3 반복 - 예약 목록을 스택, 큐에 따라 다르게 탐색할 수 있다. -> 큐 이용: 너비우선탐색 (BFS) -> 스택 이용: 깊이 이용 탐색 (DFS) -> 두 가지는 탐색 순서만 다르다. Ex) BFS - Queue를 이용해서 만든다. import java.util.*; // 방향성과 가중치가 ..

Note) - 선형 자료구조 -> list, array - 정렬: 순서를 규칙에 맞게 바꾸는 것 1. Bubble sort - 크기를 비교해서 작은 것을 왼쪽에 둔다. - index 0 을 inde = 1 ~ n-1 까지의 값과 비교한다. - index 1 을 inde = 2 ~ n-1 까지의 값과 비교한다. ... - 시간 복잡도: O(n) - 가장 느리고 확실 import java.util.Comparator; import java.util.LinkedList; import java.util.List; public class BubbleSort implements Sortable { public List sort(List list , Comparator comparator){ List copy = n..

- Collentions에 binarySearch()메서드를 제공한다. - API를 확인해보면 -> comparable 인터페이스를 구현해야한다. -> comparaTo 메서드를 implement해야한다. - indexOf()는 정확하지만 오래 걸린다. Ex) Binary Search import java.util.Collections; import java.util.LinkedList; import java.util.List; import java.util.Objects; class MyData implements Comparable{ int v; public MyData(int v) { this.v = v; } public String toString() { return "" + v; } @Overr..

Note) list interface의 메서드 - list.remove(인덱스) : 꺼내서 제거 - pop() -> 인덱스 말고 데이터의 값을 제거하려면? ex) 데이터가 int일 때 => list.remove(Integer.valueOf(지우고 싶은 값)) 으로도 표현 가능 - list.get(인덱스): 꺼내서 보여준다. - peek() 1. Stack - LIFO구조 - push / pop / peek 2. Queue - FIFO구조 - offer / poll / peek 3. Deque - 앞이나 뒤에서도 꺼낼 수 있다. - 인터페이스로 제공 - offer(First / Last) / poll(First / Last) / peek(First / Last) Ex) 올바른 괄호 - 괄호가 올바르게 입력..

1. 집합 (Set) - 선형 데이터 구조 + 탐색 알고리즘 - list와 다르게 set은 중복을 허락하지 않는다. - set은 순서를 보장하지 않는다. - 합집합: setA.addAll(setB) - B의 원소를 모두 A에 추가한다. - 차집합: setA.removeAll(setB) - A에서 B의 원소 모두 제거 - 교집합: setA.retainAll(setB) Ex) Set 연습 import java.util.LinkedHashSet; import java.util.Objects; import java.util.Set; class MyData{ int v; public MyData(int v) { this.v = v; } public String toString() { return "" + v; }..

1. Map - Map은 array와 list의 장점만 모아놓았다. Def) hashing - key를 범위(배열 크기)에 맞게 적절이 겹치지 않는 index로 변경한다. Ex) import java.util.Hashtable; public interface MapP { public static void main(String[] args) { Hashtable map = new Hashtable(); map.put("A", 1); map.put("B", 2); map.replace("A", 11); System.out.println(map.remove("B", 3)); // map에 B,2가 있으면 삭제된다. System.out.println(map); System.out.println(map.get("..

1. Array - 여러개의 데이터를 한 번에 다룰 수 있다. - Object는 아니지만 Reference Value로 취급된다. - 메모리상에 연달아 공간을 확보한다. - 미리 공간을 확보해 놓고 써야한다. - 단점 - 한 번 만들어진 공간은 크기가 고정된다. - 단점 - 첫 번째 위치만 알면 index로 상대적 위치를 빠르게 찾을 수 있다. -> array의 단점을 보완하기 위해 list가 등장 - System.out.println(Arrays.toString(배열명))을 이용해야 배열의 내용 출력 가능 2. List - 데이터를 추가: link를 늘린다. - LinkedList: 데이터를 서로 Link로 연결한다. - 데이터 삭제: link를 없앤다. - 양쪽으로 연결: double linked l..

1. primitive (기본형) - 자바는 기본형마다 래퍼 클래스 제공 - 자바에서는 string을 immutable 데이터로 취급 - call by value: value값이 그대로 전달된다. - call by reference 2. 시간 복잡도 (O(n)) Def) 시간 복잡도: 입력되는 데이터의 증가에 따른 성능의 변화를 예측 -> 작업량(시간 복잡도): 얼마나 적은 연산으로 결과를 만들어 내는가 Note) 메모리 사용량(공간 복잡도): 얼마나 적은 메모리를 사용하여 결과를 만드는가 ->Big O 표기법: O(n) -> O(1): 연산의 양이 변하지 않고 그대로 일 때 -> O(n): n에 비례하여 처리횟수가 증가하는 경우 -> O(n^2): -> O(log n): 입력 데이터가 n개 일 때, 처..

1. 동적 계획법(Dynamic Programming, DP) - 특별한 속성을 가진 복잡한 문제를 푸는 방법 - 단순한 하위 문제를 나눠서 푼다. Ex) 배낭 문제 - 물품 하나가 추가될 때마다 경우의 수가 2배씩 늘어난다. - 시간복잡도: O(2^n) 2. 메모이제이션(memoization) - 계산 결과를 캐시에 저장해둔 뒤, 나중에 재사용하는 기법 -> 처음 계산할 때, 그 결과를 캐시에 저장한다. - 메모이제이션에 "배열"이 가장 적합하다. -> 배열은 매개변수에 대해 값을 저장할 수 있다. Ex) 메모이제이션을 사용한 피보나치 함수 public static int fibonacciRecursive(int number, int [] cache) { if(number 동적 계획에서 메모이제이션이 ..