2022.09.26 월 - 연결 리스트, 해시 테이블, 힙트리

📄 학습내용

연결 리스트(Linked List)

• 연결 리스트 : 값와 다음 노드의 주소를 가진 하나의 노드들이 선형적으로 이어진 자료구조
• 구조 : 노드들이 흩어진 공간에 위치함
• 특징
  1. 쉽고 빠른 노드의 추가 및 삭제 : 시간 복잡도 : O(1)
  2. 특정 노드의 값을 찾기 위해서 최대 전체 순회 필요 : 시간 복잡도 : O(N)
• head node : 연결 리스트의 첫번째 노드
• 사용하는 경우
  1. 삽입 및 삭제가 빈번히 일어나는 경우
  2. 동적 기억장소 관리(dynamic storage managemnet) : 필요한 메모리만 할당
  3. 걸비지 컬렉션(Garbage Collection)

 

해시 테이블(Hash Table)

• 해시 테이블 : 해시함수으로 생성된 해시를 키와 데이터를 저장하는 위치로 사용한 자료구조
• 인자가 키(key)인 해시함수(Hash function)는 해시(hash)를 생성하고, 해시는 메모리 위치를 가리키고 이 메모리 위치에 데이터(value)를 저장
• 구조
  • 키(key) : 해시함수의 인력값으로, 중복허용 X
  • 해시함수(hash function) : 키를 해시로 변경하는 함수, 해시 충돌을 최대한 줄이는 것을 목표로 함
  • 해시(hash) : 키를 햄시함수에 넣어서 생성된 값, 데이터 저장되는 메모리 인덱스
  • 데이터(value) : 메모리에 저장되는 값으로, 중복허용 O
  • 해시 출돌(Hash collision) : 서로 다른 키가 같은 해시를 가지는 경우
• 특징
  1. 빠른 저장, 삭제, 검색 : 시간복잡도 O(1), 해시 충돌 시 시간복잡도 O(N)
  2. 해시 충돌 발생 가능
  3. 낮은 공간 효율성 : 데이터 저장 전 메모리 공간을 미리 생성
  4. 해시함수에 대한 높은 의존도 : 해시함수 복잡도 ↑ ∝ 데이터 삭제, 저장, 검색의 시간 복잡도 ↑ 
• 해시 알고리즘
  • Division Method : 키(숫자)를 메모리 크기로 나눈 나머지가 해시 값으로 사용하는 알고리즘
  • Digit Folding : 키(문자열)를 ASCII 코드로 변경 후 값들의 합을 해시 값으로 사용하는 알고리즘
  • Multiplication Method : (kn mod 1) * a의 값을 해시 값으로 사용하는 알고리즘(k는 키(숫자), n은 0과 1 사이의 실수, a는 2의 제곱수)
  • Universal Hashing : 여러 해시 함수 중 무작위로 해시함수 사용
• 해시 충돌 해결 방법
  1. 개방 연결법(open addressing) : 해시 충돌이 발생하면 다른 메모리 위치에 데이터를 저장하는 방식
     
     1. Linear Probing : 고정된 숫자만큼 메모리 위치 변경
     2. Quadratic Probing : 충돌이 발생한 횟수만큼 제곱해서 메모리 위치 변경
     3. Double Hasing Probing : 다른 해시함수를 이용해서 새로운 메모리 위치 생성
  2. 분리 연결법(Seperate Chaining)
     • 해시충돌이 발생하면 다양한 자료구조를 이용해서 데이터 주소를 저장하는 방식
     • 동일한 메모리 주소에 저장되는 값들이 많아지면 검색의 시간복잡도 ↑
  3. 저장소 확장(Resize)
     • 메모리의 공간을 두 배로 늘려서 해시충돌 발생 가능성 ↓

 

힙트리(Heap Tree)

• 힙트리 : 값들에 우선순위를 부여해서 빠른 검색이 가능한 트리구조인 자료구조
• 느슨한 정렬 구조
  • 부모 노드의 값이 자식 노드이 값보다 항상 크거나 작게 정렬
  • 자식 노드끼리는 정렬되지 않음
• 특징
  1. 완전 이진 트리 : 삽입 및 삭제의 성능을 위해서
  2. 중복된 값 저장
  3. 최대힙 및 최소힙
     
     • 최대힙 : 루트 노드 - 최댓값, 부모노드 > 자식노드
     • 최소힙 : 루트 노드 - 최솟값, 부모노드 < 자식노드
• 데이터 처리 방식
  1. 데이터 검색
     • 최대힙인 경우 최댓값 검색 : 시간복잡도 O(1)
     • 최소힙인 경우 최솟값 검색 : 시간복잡도 O(1)
  2. 데이터 삽입
     1. 마지막 노드에 값 추가
     2. 추가한 노드의 값과 부모 노드의 값 비교
     3. 최대힙인 경우) 부모 노드의 값보다 추가 노드의 값이 크면 위치 변경
        최소힙인 경우) 부모 노드의 값보다 추가 노드의 값이 작으면 위치 변경
     4. 위치 변경이 일어나지 않을때까지 2, 3 과정 반복
  3. 데이터 삭제
     1. 루트 노드 삭제
     2. 루트 노드 자리에 마지막 노드 삽입
     3. 삽입한 노드의 값과 자식 노드의 값 비교
     4. 최대힙인 경우) 자식 노드의 값보다 삽입한 노드의 값이 작으면 위치 변경
        최소힙인 경우) 자식 노드의 값보다 삽입한 노드의 값이 크면 위치 변경
     5. 위치 변경이 일어나지 않을때까지 3, 4 과정 반복
• 구현 : 배열
  • 1번째 인덱스부터 사용, 0번째 인덱스 사용 X
  • 수식을 통해서 부모 노드와 자식 노드의 인덱스 찾기 가능

왼쪽 자식 노드의 인덱스 : (현재 노드의 인덱스) * 2
오른쪽 자식 노드의 인덱스 : (현재 노드의 인덱스) * 2 + 1
부모 노드의 인덱스 : (자식 노드의 인덱스) / 2 내림

• 사용되는 곳
  • 우선순위 큐
  • 힙 정렬

 

🧶 발생한 문제 및 해결방법

• 문제점) 같은 문자열을 여러 번 반복해서 일정한 문자열 크기로 지정해야할 경우
• 해결방법) StringBuilder 이용

int length = 10; // 원하는 문자열 크기
String str = "ABC";
StringBuilder sb = new StringBuilder();
for(int i=0; i<length; i++)
    sb.append(str.charAt(i % str.length()));
String result = String.valueOf(sb); // ABCABCABCA

 

• 문제점) 문자열에 숫자가 포함된지 확인하는 방법 (java string contains int)
• 해결방향) 문자열을 문자로 분리하고, Character.isDigit(Char ch)를 이용해서 문자가 숫자인지 확인

String str = "123ABC";
for(char c : str.toCharArray()) {
    if(Character.isDigit(c)) { // 문자가 숫자일 때 true
        // 1, 2, 3일 때 동작
    }
}

 

• 문제점) 문자열을 forEach문으로 순회화는 방법
• 해결방향) toCharArray() 메서드로 String을 char형 배열로 변경

String str = "Hello";
for(char c : str.toCharArray()) {
    System.out.println(c);
}
/* 실행결과
H
e
l
l
o
*/

 

⭐ 공부 난이도

연결 리스트, 해시 테이블, 힙트리 ☆☆★★★

 

🎡 페어리뷰

 

🌕 느낀점

  역시 DFS와 BFS 구현은 어렵다. DFS 구현을 위해서 재귀, 스택을 이용하고, BFS 구현을 위해서 큐를 이용한다. 예전에는 어떻게 구현했는지 감이 하나도 안잡혔는데, 이제는 어떻게 구현해야할지 약간 감이 잡힌다. 코플릿의 마지막 13번 문제를 풀 때 꼼수(?)를 이용했다. 반복되는 부분이 있어서 이를 이용해서 문제를 구현하였다. 이렇게 풀어도 되는건지... BFS로 구현하는건 어떻게 할 수 있겠는데 아직까지는 DFS 구현은 어렵다.