티스토리 뷰
1. 정적배열(Array)
- 동일한 타입의 데이터를 연속메모리 위치에 저장할 수 있는 자료구조
- 고정된 저장공간에 같은 타입의 변수들로 이뤄져 있다.
- 중복을 허용하고 순차적으로 데이터를 저장한다.
- 시간복잡도
- 조회 : O(1) → 인덱스를 알면 조회가 빠르다.
- 삽입, 삭제 : O(n)
- 마지막에 값 삽입할 때, 크기가 고정되어 변경 불가. 현재보다 긴 배열 선언 후 배열복사하고 마지막에 새로운 값을 삽입한다
2. 동적배열(Vector)
- 저장공간이 유동적이기 때문에 저장공간이 부족하면 자동적으로 크기를 늘려 데이터 추가/저장가능한 자료구조
- 데이터의 접근과 할당이 빠르다
- 필요이상의 메모리 공간을 할당받기때문에 메모리 낭비가 발생한다.
- 중복을 허용하며 숫자인덱스 기반의 랜덤접근을 한다
- 시간복잡도
- 참조 : O(1)
- 탐색 : O(n)
- 맨끝 삽입/삭제 : O(1)
- 맨끝 제외 삽입/삭제 : O(n)
[참고] arrayList in JAVA
//JAVA : 자바에서 동적배열은 ArrayList를 사용해 구현한다.
//정적 배열
public static void main(){
int[] array1; // 선언
array1 = new int[5]; // 런타임에 메모리 할당. 배열크기 지정 후 변경 불가
int[] array2 = new int[5]; // 길이를 지정해서 선언가능
int[] array3 = new int[]{1,2,3,4,5}; // 고정값지정 가능
for(int i=0;i<array3.length;i++){
System.out.print(array3[i]); // 12345
}
System.out.println(array1.length); // 5
}
//동적배열
public static void main(){
ArrayList<integer> list = new ArrayList<>(); //선언
// 리스트명.add(내용물) : 리스트 값 추가 + addAll
list.add(1);
list.add(2);
list.add(3);
System.out.println(list); //[1, 2, 3]
// 리스트명.add(위치,내용물) : 원하는 위치에 값 추가
list.add(1,10);
System.out.println(list); //[1, 10, 2, 3]
// 리스트명.set(위치,내용물) : 위치 변경
list.set(3,10);
System.out.println(list); //[1, 10, 2, 10]
// 리스트명.remove() : 삭제
list.remove(3); // [1, 10, 2]
// 특정요소 접근
System.out.println(list.get(1)); //10
// string타입일경우 문자열 자르기도 가능하다.
//리스트명.get(위치).split("문자열을 자를 기준")[자른 후 선택할 문자열]
}- 자바에서 사용할 수 있는 자료구조 → array, List, ArrayList
- arrayList = array장점 + List장점
- array : 인덱스를 통한 검색의 용이함
- List : 포인터를 통한 추가/삭제성능이 좋음 + 동적할당
3. 연결리스트
- 각 노드가 데이터와 포인터를 가지고 한줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구
- 메모리 위치가 아닌 독립적으로 요소를 저장한다.
- next, next-prev 포인터로 서로 연결된 선형적인 자료구조
- 시간복잡도
- 참조 : O(n)
- 탐색 : O(n)
- 삽입/삭제 : O(1)
1) 연결리스트 종류
- 싱글 연결리스트
- 이중 연결리스트
- 원형 연결리스트
① 싱글연결리스트 (Singly Linked List)
- next포인터만 존재하는 단방향 연결리스트
- 한방향으로만 데이터가 연결된다.
- 단방향이기 때문에 뒷부분에 있는 요소에 접근하려면 시간이 오래걸린다.
② 이중연결리스트 (Doubly Linked List)
- prev,next 두개의 포인터가 있는 양방향 연결리스트
- 양방향으로 데이터가 연결된다.
- 싱글연결리스트보다 각 요소에 대한 접근과 이동이 쉽다.
③ 원형 연결리스트 (Circular Linked List)
- 첫번째 노드와 마지막노드가 연결되어 원을 형성하는 연결리스트
- 원형싱글연결리스트, 원형이중 연결리스트 두가지 종류가 있다.
[개념] 랜덤접근과 순차접근
- 랜덤접근 ( =직접접근 )
- 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능
- vector, array = 랜덤접근이 가능하기 때문에 n번째 요소 접근시 O(1)의 시간복잡도를 가진다.
- 순차적접근
- 데이터를 저장된 순서대로 검색한다.
- 연결리스트, 스택, 큐 = 순차적 접근만 가능, n번째 요소 접근시 O(n)의 시간복잡도를 가진다.
[참고] LinkedList in JAVA (double linkedList로 구현되어 있다.)
- ArrayList : 내부적으로 배열을 이용해서 메서드로 이리저리 조작 가능하게 만드는 컬렉션
- LinkedList : 노트끼리 주소 포인터를 서로 가리키며 링크함으로써 이어지는 구조
// int타입 객체 생성 -> 초기값은 미리 지정 불가
// 배열처럼 미리 공간할당하고 사용하는 것이 아니라 노드 추가할때마다 동적으로 추가된다.
LinkedList<Integer> listEx = new LinkedList<>();
LinkedList<String> list = new LinkedList<String>(Arrays.asList("A","B","C"));
// 요소 추가
list.addFirst("new"); //맨 앞에 "new" 추가 [new,A,B,C]
list.addLast("last"); //맨 뒤에 "last" 추가 [new,A,B,C,last]
//요소 삽입
list.add(1,"one"); // index1에 "one" 삽입 [new,one,A,B,C,last]
//요소 삭제
list.removeFirst(); //첫번째 값 제거 [one,A,B,C,last]
list.removeLast(); //마지막 값 제거 [one,A,B,C]
list.remove(1); //index1 값 제거 [one,B,C]
list.clear(); //모든 값 제거
//해당 값을 가지고 있는 요소 위치를 반환 (앞에서 부터 검색)
list.indexOf("B"); // 1
// 해당 값을 가지고 있는 요소 위치를 반환 (뒤에서 부터 검색)
list.lastIndexOf("D"); // -1 : 찾고자 하는 값이 없으면
//노드 값 변경
LinkedList<String> list1 = new LinkedList<>();
list1.add("10");
list1.add("20");
list1.add("30");
list1.set(1, "A"); // index 1번의 데이터를 문자열 "A"로 변경한다.
System.out.println(list); // // [10, A, 30]4. 스택(Stack)
- 가장 마지막에 들어간 데이터가 가장 먼저 나오는 후입선출을 가진 자료구조
- 재귀적인 함수, 알고리즘,브라우저 방문기록에 사용된다.
- 시간복잡도
- n번째 참조 : O(n)
- 가장 앞부분 참조 : O(1)
- 탐색 : O(n)
- 삽입 / 삭제(n번째 제외) : O(1)
Stack<Integer> stack = new Stack<>();
for(int i=0;i<5;i++){
stack.push(i); // push() : value 추가
System.out.println(stack.peek()); // peek() : 스택의 가장 위 요소를 반환
}
// 결과 출력
//0
//1
//2
//3
//4
stack.pop(); // pop() : 가장 위에 있는 요소를 제거
System.out.println(stack.peek()); //3출력
System.out.println(stack.search(3)); //1출력
System.out.println(stack.empty()); //false출력5. 큐(queue)
- 먼저 집어넣은 데이터가 먼저 나오는 성질인 선입선출을 지닌 자료구조
- 스택과 반대개념
- cpu작업을 기다리는 프로세스, 스레드행렬,네트워크 접속을 기다리는 행렬, 너비우선탐색, 캐시등에 사용됨
- 시간복잡도
- n번째 참조 : O(n)
- 가장 앞부분 참조 : O(1)
- 탐색 : O(n)
- 삽입 / 삭제(n번쨰 제외) : O(1)
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(1); // queue에 값 1 추가
queue.add(2); // queue에 값 2 추가
queue.offer(3); // queue에 값 3 추가
while(!queue.isEmpty()) {
System.out.println(queue.poll());
}
//1
//2
//36. 그래프이론의 기초
- 정점 (vertex) : 노드, 그래프를 형성하는 기본단위
- 분할할 수 없는 객체이자 점으로 표현되는 위치 사람 물건등이 될 수 있다.
- 간선(edge) : 정점을 잇는 선
- 관계 경로 등이 될 수있다.
- ex) 어떠한 위치나 어떠한 사람으로부터 무언가를 통해간다
- 어떠한 위치나 어떠한 사람 : 정점
- 무언가를 통해 간다 : 간선
[개념] 단방향간선 & 양방향 간선
- 단방향간선 : 한방향으로 연결된 간선
- a와 b는 정점이라 할 수 있고 a->b 또는 b->a 에 대한 마음을 간선이라고 할 수 있다,
- 한쪽만 마음이 있다면 짝사랑인데 이걸 단방향 간선이라 할 수 있다.
- 양방향 간선 : 양방향으로 연결된 간선
- 단방향 간선이 짝사랑이면 양방향 간선은 쌍방향
[개념] 간선의 종류, 가중치, 그래프
- outdegree : a정점에서 또다른 b정점으로 가는 간선
- indegree : b정점으로 들어오는 간선
- 가중치 : 정점과 정점 사이에 드는 비용
- 그래프 : 위에 설명한 정점과 간선들로 이루어진 집합
7. 트리
- 트리 : 자식노드와 부모노드로 이루어진 계층적인 구조를 가진 무방향 그래프의 일종이자 사이클이 없는 자료구조
- 부모 자식계층구조를 가진다.
- 간선수(E) = 노드수(V) -1
- 두 노드 사이의 경로는 유일무이하게 존재한다. -> 경로는 단 하나만 존재한다.
[개념] 노드
- 루트노드 : 가장 위에 있는 노드
- 내부노드 : 루트노드와 리프노드 사이에 있는 노드
- 리프노드 : 자식노드가 없는 노드
[개념] 트리의 높이와 레벨
- 깊이 : 루트노드에서 특정 노드까지의 최단거리로 갔을 때의 거리
- 높이 : 루트노드부터 리프노드까지의 거리중 가장 긴거리
- 레벨 : 깊이와 같은 의미.
- 서브트리 : 트리 내의 하위집합 혹은 트리 내에 있는 부분집합
- 숲 : 트리로 이루어진 집합
8. 이진트리와 이진탐색 트리
① 이진트리
- 모든 노드들이 둘 이하(0,1,2)의 자식을 가진 트리
② 이진트리 종류
- 정이진 트리(Full binary tree) : 자식노드가 0 또는 2개인 이진트리
- 완전 이진트리 (complete binary tree) : 왼쪽부터 채워져 있는 이진트리를 의미한다. 마지막 레벨 제외하고 모든레벨이 채워져 있으며 마지막레벨의 경우 왼쪽부터 채워져있다 -> 힙과 관련있다.
- 변질 이진트리 (degenerate binary tree) : 자식노드가 하나밖에 없는 이진트리
- 포화 이진트리 (perfect binary tree) : 모든 노드가 꽉차있는 이진트리
- 균형 이진트리 (balanced vinary tree) : 모든 노드의 왼쪽 하위 트리와 오른쪽 하위트리의 차이가 1이하인 트리.
② 이진탐색 트리 (BST, Binary Search Tree)
- 노드의 오른쪽 하위 트리에는 노드의 값보다 큰 값이 있는 노드만 포함되고 왼족 하위트리에는 노드의 값보다 작은값이 들어있는 트리
- 이런 구조는 검색을 하기에 편하다. => 전체 탐색을 하지 않아도 된다
- 왼쪽은 작은값, 오른쪽은 큰 값이 정해져 있기 때문에 특정 수를 찾으려면 그 숫자를 기준으로 큰값, 작은값을 찾으면 되기때문
- 시간복잡도 : O(logN) -> 균형잡히게 분포되어있으면 탐색,삽입,삭제,수정 모두 같은 시간복잡도를 갖는다.
9. 맵(Map)
- 고유한 키를 기반으로 key-value쌍으로 이루어져있는 정렬된 자료구조
- 고유한 키를 갖기 때문에 하나의 키에 중복된 값이 들어갈 수 없고, 자동으로 오름차순 정렬 -> 아스키코드순으로 정렬된 값 기반으로 탐색
- 균형잡힌 이진탐색트리(레드-블랙트리)로 구현된다.
- 시간복잡도
- 참조 : O(logN)
- 탐색 : O(logN)
- 삽입/삭제 : O(logN)
// 자료 구조이므로 key: value 값 타입 모두 객체 자료형이다.
HashMap<Integer, String> map = new HashMap<>();
for(int i=0; i<5; i++) {
map.put(i, "value " + i);
}
System.out.println(map);
// key=0에 대한 value 값을 새로운 값으로 갱신
map.put(0, "modified value");
System.out.println(map);
String data = map.get(0);
System.out.println("data: " + data); //data: modified value
// hashMap 값 존재 여부 확인
HashMap<String, String> map = new HashMap<>();
// Map에 데이터 추가
map.put("harbang", "jeju");
// key 확인
if(map.containsKey("harbang")) {
System.out.println("Key 존재!"); // Key존재!
}
// value 확인
System.out.println(map.containsValue("jeju")); //true
}
10. 셋(set)
- 고유한 요소만을 저장하는 자료구조
- 중복을 허용하지 않는다.-> 중복값은 제거
- 자동정렬된다.
- 맵처럼 key-value쌍으로 안넣어도 된다.
- 시간복잡도
- 참조 : O(logN)
- 탐색 : O(logN)
- 삽입/삭제 : O(logN)
11. 해시테이블(Hash Table)
- 큰 범위를 가진 데이터들을 해싱을 통해 한정된 범위의 정수값의 해시로 만들고 그 키에 원본데이터를 매핑시켜놓은 테이블
- 해시테이블은 기본적으로 key-value로 데이터를 저장하는 자료구조
- 빠르게 데이터를 검색할 수 있음 → 내부적으로 배열을 사용해서 데이터를 저장하기 때문
- key값에 해시함수를 적용해 배열의 고유 index를 생성하고 이것을 활용해 값을 저장하거나 검색한다.
- 실제 저장되는 장소 : 버킷 or 슬롯
- 해싱구조로 데이터를 저장하면 key값으로 데이터를 찾을 때 해시함수를 1번만 수행하면 빠르게 데이터를 저장,삭제,조회 할수 있다 → 시간복잡도 : O(1)
[개념] 해시, 해싱, 해시함수
- 해시 : 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값
- 해싱 : 임의의 데이터를 해시로 바꿔주는 일, 해시함수가 담당한다
- 해시함수 : 임의의 데이터를 입력으로 받아 일정한 길이의 데이터로 바꿔주는 함
① 해시테이블이 쓰이는 곳
- DB에 개인정보를 암호화해서 저장할 때
- 대표적으로 MD5 와 bcrypt 해시 알고리즘을 사용한다.
- MD5 : 레인보우 테이블을 통한 취약점 때문에 최근엔 사용 X
- bcrypt : 현재 DB에서 값을 암호화해서 저장할 때 많이 쓰인다.
② 해시값이 충돌하는 경우
- key값을 해시함수로 해싱했는데 해시테이블에 동일한 hash값이 있다. -> 충돌문제가 발생한다.
- 해시테이블의 충돌문제는 무조건 일어난다. -> birthday paradox에 의해 발생확률이 높다.
③ 해시값 충돌 해결법
- 체이닝 : 충돌시 연결리스트에 할당하고 충돌시 연결리스트를 탐색하는 기법
- 연결리스트 + 동적배열 + 레드블랙트리 사용 (균형잡힌 이진트리)
- O(n)의 시간복잡도를 O(log n)으로 개선했다.
- 장점 : 구현이 간단해서 해시테이블에 많은 데이터를 집어넣을 수 있다.
- 단점 : 연결리스트 기반이라 캐시성능이 좋지않다. 체인이 길어지면 최악의 경우 O(n)이 된다.
- 개방 주소법 : 충돌시 다른 비어있는 해시테이블 공간에 데이터를 삽입하는 기법
- 선형탐색 : 현재의 버킷 index로부터 고정폭 만큼씩 이동해 차례대로 검핵한 후 비어있는 버킷에 데이터 저장
- 제곱탐색 : 해시의 저장순서 폭을 제곱으로 저장하는 방식.
- 이중해싱 : 해시된 값을 한번더 해싱해서 해시의 규칙성을 없애버리는 방식.
12. 힙 (Heap tree or heap)
- 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조
- 여러개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기위해 만든 완전 이진트리
- 힙의 종류
- 최대 힙 : 부모노드의 값은 자식노드의 값보다 항상 큰 규칙을 지키는 힙
- 최소 힙 : 부모노드의 값은 자식노드의 값보다 항상 작은 규칙을 지키는 힙
- 최대 힙, 최소힙의 시간 복잡도 : O(1)
- 힙의 삽입 & 삭제
- 이진탐색트리와 힙의 차이점
| 이진탐색트리 | 힙 | |
| 노드 작은쪽의 위치 | 왼쪽이 작은값 오른쪽이 큰 값 |
왼쪽이 클 수도 있다. -> 정해지지 않았다. |