cs 스터디 (1주차)

1. Array, ArrayList, Linked List

 

Array는 사이즈 수정이 안 된다. 그런데 ArrayList는 사이즈 수정이 된다.

둘 다 index를 활용하기 때문에 검색하는 상황에 유용하게 쓰인다.

 

하지만 삽입, 삭제를 할 때 앞 뒤 요소를 다 앞으로 땡기거나 뒤로 미는 작업이 이루어지기 때문에 cost가 크다.

 

→ 검색이 주가되고 수정이 드물 때, 사이즈 수정 여부를 고려해서 Array 또는 ArrayList를 사용하면 좋다.

 

LinkedList는 node라는 개념을 활용한다.

index라는 개념이 없고 삽입, 삭제를 할 때 그냥 link를 끊고 새로 연결만 하면 되기 때문에 Array, ArrayList보다 cost가 적다. 검색을 할 때는 순차적으로 하기 때문에 시간이 오래 걸려서 비효율적이다.

 

→ 검색을 덜 하고 수정이 잦은 data를 관리할 때 LinkedList를 사용하면 좋다.

 

[참고한 포스팅]

• https://www.nextree.co.kr/p6506/
• tech-interview-for-developer/Array vs ArrayList vs LinkedList.md at master · gyoogle/tech-interview-for-developer · GitHub
• https://dev-coco.tistory.com/19
• https://dev-coco.tistory.com/m/15

 

 

---

 

2. Stack and Queue, 우선순위 큐

 

스택

후입선출이다.

push(), pop(), peek(), empty(), search() 메서드가 있다.

 

자바에서 기본으로 제공하는 Stack 클래스를 써도 되고 직접 만들어서 써도 된다.

배열로 스택을 구현할 수 있고, Linked List로도 구현할 수도 있다.

 

참고로 자바의 Stack 클래스는 Linked List로 구현된 클래스이다.

 

[참고한 포스팅]

• https://go-coding.tistory.com/5

 

 

큐

선입선출이다.

 

스택처럼 자바에서 제공되는 게 있다. 하지만 클래스가 아닌 인터페이스로 제공된다는 차이가 있다.

이 또한 배열 또는 Linked List를 써서 직접 만들어 써도 된다.

 

enqueue는 data가 큐에 들어가는 것을 의미한다.

dequeue는 data가 큐에서 나오는 것을 의미한다.

 

• queuelsEmpty() : 큐 안이 비었는지 판단하는 함수
• queueIsFull() : 배열의 최대크기를 벗어나면 안되기에 큐에 더이상 들어갈 공간이 없는지 판단하는 함수
• size() : queue에 현재 들어가 있는 데이터의 개수를 return하는 함수
• push(int value) : 큐 안에 데이터를 집어넣는 함수
• peek() : 큐 안의 데이터들중 가장 먼저 나오는 데이터를 return 하는 함수
• pop() : 큐 안의 데이터들 중 가장 먼저 나올수 있는 데이터를 return 하고 삭제하는 함수

 

[참고한 포스팅]

• https://go-coding.tistory.com/6?category=967004 

 

 

우선순위 큐

 

선입선출이나 후입선출처럼 시간 개념에 따라 순번이 갈리는 게 아닌,

사용자가 부여한 기준에 따라 우선 순위가 정해지고 그 우선순위대로 data를 빼내는 구조이다.

 

[참고한 포스팅]

• https://yoongrammer.tistory.com/81

 

---

3. Tree

• Binary Tree (이진트리)

각 노드가 최대 2개의 자식 노드를 갖는 걸 말한다.

 

• Full Binary Tree (전이진트리)

모든 노드가 0개 또는 2개의 자식 노드를 갖는 걸 말한다.

 

• Complete Binary Tree (완전이진트리)

노드가 왼쪽에서 오른쪽 순으로 채워진다.

leaf node를 제외한 나머지는 다 차있다.

 

• BST (Binary Search Tree) (이진탐색트리)

부모 노드가 왼쪽 자식 노드보다 크다.

오른쪽 자식 노드가 부모 노드보다 크다.

이진탐색트리에서 노드에 저장된 값은 유일하다.

 

[참고한 포스팅]

• https://code-lab1.tistory.com/8
• https://code-lab1.tistory.com/m/10
• https://go-coding.tistory.com/8?category=967004 

---

 

4. Binary Heap (= Heap)

최대 힙, 최소 힙 2종류로 나뉘는 완전이진트리의 일종이다.

 

[참고한 포스팅]

• https://velog.io/@gnwjd309/data-structure-heap

 

---

5. Red Black Tree

• https://code-lab1.tistory.com/62

[자료구조] 레드-블랙 트리(Red-Black Tree)란? | 레드-블랙 트리 쉽게 이해하기

 

트리가 너무 한 쪽으로 쏠리는 걸 방지하기 위해 나온 트리이다.

특별히 생각할 게 없다. 그냥 규칙을 받아들이고 적용만 하면 된다.

 

 

전체적인 틀을 잡는 규칙은 아래와 같다.

 

1. 새로 삽입하는 노드는 빨간색.

2. 빨간색은 연속으로 2번 나올 수 없음. (검은색은 가능하단 얘기)

3. root node는 검은색

4. leaf 노드까지 가는 모든 경로에서의 검은색 node 갯수는 같다.

 

 

상황에 따라 아래와 같은 세부 규칙이 2개 더 존재한다.

 

1. recolor

2. restructure

 

삼촌 노드가 새로 삽입된 노드와 같이 빨간색이면 recolor, 검은색이면 restructure로 진행하는 것이다.

 

 

restructure

 

restructure는 새로 삽입된 N, 부모인 P, 조상인 G 노드를 오름차순으로 정렬하고 중간값을 G로 하여

완전이진트리 규칙에 맞게 작은 게 왼쪽, 큰 게 오른쪽으로 가게 배치한다.

이때 원래 딸려있는 게 있으면 set로 같이 움직인다.

 

배치를 마친 후 기본규칙을 다시 적용한다.

가령 root node가 빨간색이면 검정색으로 바꿔준다.

 

 

recolor

 

P,G,U 노드의 색을 다 뒤집는다. 이러면 끝이다.

그런데 이렇게 뒤집어 줬을 때 double red 이슈가 생기면 추가 작업이 생긴다.

이것도 별 건 없다. double red 이슈가 생긴 node를 기준으로 해서 또 P,G,U를 다 뒤집어주고 root를 검정색으로 맞춰주면 된다.