제로베이스 백엔드 부트캠프 2주차 정리 - Chapter02. 선형자료구조

자료구조의 기본적인 개념들은 알고있었지만 배열과 ArrayList로 구현해보면서 각 자료구조들의 근본적인 원리를 이해하는 시간들이었다. 어려웠지만 하나씩 계속 해보면서 이해가 되는 것이 신기하고 뿌듯했다 ..!

 

7/12

- 자료구조란 ? ) 자료를 효율적으로 관리하기 위한 구조

  목적에 맞게 사용한 좋은 자료구조는 실행시간 단축 or 메모리 용량 절감 효과가 있음. (둘은 양립하기가 어려움 실행시간 단축에 중점.)

  나중에 배울 알고리즘과 밀접한 관계.

- 자료구조의 분류 : 선형 자료구조, 비선형 자료구조

 

- 선형자료구조 ) 앞뒤로 연결된 데이터의 관계가 1 : 1

  배열 : 물리적으로도 연결되어있음

  연결리스트 : 물리적인 연결은 X, 다음 데이터의 연결 정보를 가지고있음.

  스택, 큐, 데크 : 배열과 연결리스트로 구현 가능 + 규칙이 더 있

  해시테이블

 

- 비선형 자료구조 ) 앞뒤로 연결된 데이터의 관계가 1 : N

 트리 : 노드로 이루어져있고 계층적

 그래프 : 노드로 이루어져있고 싸이클을 이루고있음.

 힙/우선순위 큐 : 트리구조 + 규칙이 추가

 트라이 : 트리의 일종. 문자열을 다룰 때 효과적

 

- 자료구조의 구현

  * 추상자료형 (Abstract Data Type : ADT)

  자료형태와 자료에 대한 연산을 정의한 것

  구체적인 구현 방법은 명시하지 않음. (추상 클래스, 인터페이스 참고)

 

  * 대부분 자료구조는 자바에서 클래스로 제공 -> 이해한 후 알맞은 메소드 사용

  * 실습에서는 가급적 처음부터 구현 진행. -> 자료형태, 사이즈, 각 기능에 대해 구현

---

<배열> 

- 많은 수의 데이터를 다룰 때 사용하는 자료구조

- 각 데이터가 인덱스와 1 : 1

- 데이터가 메모리 상에 연속적으로 저장.

 

장점 : 인덱스를 이용해 데이터에 빠르게 접근 가능

 (컴퓨터는 데이터를 읽어올 때 덩어리로 읽어옴. 따라서 인접한 데이터는 빠르게 엑세스가 가능)

단점 : 데이터의 추가/삭제가 번거로움

  - 미리 최대 길이 정해서 생성해야함

  - 가변 길이 배열은 배열 크기 변경할 때마다 새로운 배열을 생성해야함

  - 데이터 삭제 시, 인덱스를 유지하기 위해 빈공간 유지

 

---

7/13

<연결리스트>

- 데이터를 링크로 연결해서 관리하는 자료구조

- 자료의 순서는 정해져 있지만, 메모리상 연속성이 보장되지는 않음.

 

장점 

- 데이터 공간을 미리 할당할 필요 없음.

- 즉, 리스트 길이 가변적. 데이터 추가/ 삭제 용이 (구현관점 용이 X, 메모리 관리 측면)

 

단점

- 연결구조를 위한 별도 데이터 공간 필요

- 연결 정보 찾는 시간 필요 (접근 속도 상대적으로 느림)

- 데이터 추가, 삭제 시 앞뒤 데이터의 연결을 재구성하는 작업 필요

- 기본구조 : 노드. 데이터 저장 단위로, 값과 포인터(다음/이전 노드의 연결정보)로 구성

- 연결리스트 기본 연산 : 데이터 추가, 데이터 삭제. 추가/삭제하는 위치에 따른 연결 작업 필요

  데이터 추가 : 

  1. 가장 앞에 데이터 추가 시 :

추가할 데이터를 담을 노드 생성 -> 링크 연결 작업 -> head 연결 작업

 2. 중간에 데이터 추가 시 :

추가할 데이터를 담을 노드 생성 -> head로부터 추가할 위치 직전까지 노트 순회 -> 링크 연결 작업

 3. 가장 끝에 데이터 추가 시 : 

추가할 데이터를 담을 노드 생성 -> head로부터 끝 노트까지 순회 -> 링크 연결 작업

 

데이터 삭제 :

1. 가장 앞 데이터 삭제 시 : (자바 가비지컬렉션 때문에 delete_node명시적으로 하지 않아도 지워줌)

삭제 대상 노드 지정(delete_node) -> head이전 작업 -> dlete_node 삭제

2. 가장 끝 데이터 삭제 시 :

head로부터 가장 끝까지 순회 -> 끝 노드 삭제 -> 삭제 이전 노드의 링크 처리

3. 중간 데이터 삭제 시 :

head로부터 삭제 대상 노트까지 순회 및 해당 노드 지정(delete_node) -> 삭제 대상 이전/이후 노드의 링크 연결 작업 -> delete_node삭제 

 

---

7/14

<스택>

- 후입선출 (Last In First Out ; LIFO) 자료구조

 : 마지막에 들어온 데이터가 먼저 나가는 구조

- 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용

 ex ) 함수 콜 스택, 수식 계산, 인터럽트 처리 등

 

- 스택 기본 연산 : push(), pop(), peek(), contains(값), size(), empty(), clear()

 

---

<큐>

- 선입선출(First In First Out) 자료구조

- 입력 순서대로 데이터 처리가 필요할 때 사용

 ex) 프린터 출력 대기열, BFS(Breath - First Search)너비우선 탐색 등

 

- 큐 기본 구조 : 선입선출, 데이터 추가, 꺼내기, 큐 공간 확인.

 * 데이터 꺼내지는 쪽 Front , 꺼내는 동작 Dequeue

 * 데이터 추가하는 쪽 Read, 추가하는 동작 Enqueue

 

- 메소드 : add(), poll() 값이 없으면 null 반환, peek(), contains(값), size(), clear(), isEmpty()

 

실습에서 원형 큐 구현해서 사용. front, rear만 조절해주면 되니까 훨씬 편하다 !

Queue q = new LinkedList(); //LinkedList로 생성해서 사용.

(Queue는 인터페이스이기 때문에)

---

7/15

<데크>

- 양쪽에서 삽입, 삭제 가능

   Deque = Doubly - ended Queue.

  Stack + Queue 합친 형태

- 기본구조

  양방향 삽입, 삭제 가능, 일부 기능을 제한하여 용도에 맞게 변형 가능.

  front , rear에서 모두 offer, poll 연산 가능.

 

 *add / remove는 예외 발생 -> 처리해줘야함.

 *offer / poll은 null, false 반환

 

- 입력제한 데크 (Scroll) : 한 쪽의 입력을 제한한 데크 (방향 무관)

- 출력제한 데크 (Shelf)

 

실습 : Deque deque = new ArrayDeque(); 로 생성해서 씀.

addFirst(값), addLast(값)

removeFirst(), removeLast();

pollFirst(), pollLast();

 

stack이랑 queue가 합쳐진 느낌이라 배열로 구현하는게 전보다 수월했다. 역시 복습의 힘인가 .. 성취감 쩐

---

<해시테이블>= 해시 맵, 해시 표

- 키(key), 값(value)을 대응시켜 저장하는 데이터 구조

  키를 통해 해당 데이터에 빠르게 접근 가능.

- 해싱 : 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정

 

<해시 테이블 구조>

- 키 : 해시 테이블 접근을 위한 입력 값

- 해시함수 : 키를 해시값으로 매핑하는 연산

- 해시 값 : 해시 테이블의 인덱스

- 해시 테이블 : 키-값 연관시켜 저장하는 데이터 구조

 

<해시 충돌>

- 해시 테이블의 같은 공간에 서로 다른 값을 저장하려고 하는 경우

  서로 다른 key 값의 해시 함수를 통한 해시 값이 동일한 경우

- 해시 충돌 해결 방법으로는 개방주소법과 분리연결법이 있음.

 

<해시 충돌 해결방법 1>

- 개방주소법(Open Address)

 충돌시, 테이블에서 비어있는 공간의 hash를 저장.

 hash와 value가 1:1 관계 유지

 비어있는 공간 탐색법에 따른 분류 : 선형 탐사법, 제곱탐사법, 이중해싱

 

   * 선형 탐사법 (Linear Probing)

       빈공간 순차적 탐사 방법 : 충돌 발생 지점부터 이후의 빈 공간 순차적 탐사.

       일차 군집화 문제 발생 : 반복된 충돌 발새 시 해당 지점 주변에 데이터가 몰리는 경우 발생

 

  * 제곱 탐사법 (Quadratic Probing)

       빈공간을 n 제곱만큼의 간격을 두고 탐사하는 방법

         충돌 발생 지점부터 이후의 빈공간을 n제곱 간격으로 탐사.

       일차 군집화 문제 일부 보완 but, 이차 군집화 문제 발생 가능성

 

   * 이중 해싱 (Double Hashing)

       해싱함수를 이중으로 사용

          - 해시함수1 : 최초 해시를 구할 때 사용

          - 해시함수2 : 충돌 발생 시, 탐사 이동 간격을 구할 때 사용

          - 선형탐사, 제곱 탐사에 비해 데이터 고르게 분포

 

<해시 충돌 해결방법 2>

- 분리연결법(Separate Chaining)

 해시테이블을 연결리스트로 구성

 충돌 발생시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결리스트를 이용하여 해당 테이블에 데이터를 연결.

   단점 : 1 :1이 아니라 원하는 값 get할 때 앞의 다른 방법들보다 오래걸림.

 

<실습>

HastTable <Key,Value> ht = new HashTable();

HashTable 값에 접근하는 방법 :

for(Map.Entry <String, Integer> map : ht.entrySet()){

  item.getKey(), item.getValue();로 값을 뽑아 씀 처음본다 ! 

 

 

*HashMap VS Hashtable

HashMap은 키 값으로 null 사용 가능. Hashtable은 불가

 

Hashtable은 thread-safe. HashMap은 thread-Unsafe

HashMap을 safe하게 사용하려면 synchronizedMap, ConcurrentHashMap을 사하면 된다.

---

이번 주차는 3주차지만 다행스럽게도 2주차 복습시간이 있어서 이렇게 포스팅도 할 수 있고 이해도 할 수 있게 된 것 같다. 처음 자료구조들의 개념은 알고 있었지만 이것들을 배열로 구현할 때는 정말 막막했었다.

그래도 이해하려고 계속 노력한 보람이 있는 것 같다. 복습하면서 실습코드를 다시 내가 작성했는데 술술 써지는게 정말 .... 성취감이 너무 든다. 더 하고 싶다 더 배우고 싶다