그래프의 정의

그래프는 트리를 포함하는 개념이고, 트리는 사이클을 포함하지 않는 그래프라고 볼 수 있다.
그래서 모든 트리는 그래프이지만, 모든 그래프는 트리가 아니다.

그래프는 정점의 모음과 간선의 모임이 결합한 것이다.

정점 자체는 아무것도 아니지만 이들이 간선을 통해 서로 연결되면 관계가 형성되고 이로 인해 그래프가 만들어진다.

• 인접 (adjacent) : 간선으로 연결된 두 정점을 가리켜 서로 인접 또는 이웃 관계에 있다고 말한다.
  (A, B), (A, D), (A, E), (B, C), (B, E), (C, D)가 서로 이웃 관계
• 경로(Path) : 정점 A에서 정점 C까지는 A, B, C와 A, D, C가 각각 하나의 경로
• 경로의 길이 : 정점과 정점 사이에 있는 간선의 수
  경로 A, B, C 사이에는 간선이 (A, B)와 (B, C) 2개가 있으니 길이가 2

• 사이클(Cycle) : 정점 하나를 두 번 이상 거치도록 되어 있는 경로, 사이클은 트리에서 볼 수 없는 특징

방향성 그래프(Directed Graph)와 무방향성 그래프(Undirected Graph)

• 무방향성 그래프 내의 두 정점 사이에 경로가 존재하면 이 두 정점이 연결되어 있다고 표현
• 그래프 내의 각 정점이 다른 모든 정점과 연결되어 있으면 이 그래프는 연결되었다고 표현

그래프 표현 방법

그래프의 인접 관계를 표현 방법에는 아래와 같은 종류가 있다.

• 인접 행렬(Adjacency Matrix)
• 인접 리스트(Adjacency List)

인접 행렬

무방향성 그래프에서의 인접 행렬

• 그래프의 정점 수를 N이라고 했을 때 N×N 크기의 행렬을 만든다.
• 한 정점과 또 다른 정점이 인접해 있는 경우(즉, 정점 사이에 간선이 존재하는 경우) 행렬의 각 원소를 1로 표시하고 인접해 있지 않은 경우 0으로 표시
• 주 대각선을 기준으로 대칭(symmetric)을 이룸

방향성 그래프에서의 인접 행렬

• 방향성 그래프에서의 정점은 자신이 직접 간선을 통해 가리키고 있는 정점에 대해서만 인접해 있다고 표현
• 아래 그림에서 정점 1은 정점 2, 3, 4, 5에 인접해 있지만 3, 4는 인접한 정점이 하나도 없음

인접 리스트

그래프 내 각 정점의 인접 관계를 표현하는 리스트

무방향성 그래프에서의 인접 리스트

• 각 정점이 자신과 인접한 모든 정점의 목록을 리스트로 관리
• 모든 정점을 죽 늘어놓고 각 정점의 인접 정점을 옆에 나열
• 인접 정점들끼리 리스트로 연결한 후 이를 각 정점에 연결

방향성 그래프에서의 인접 리스트

• A -> B 와 같이 방향성이 있을 때는 A의 인접리스트에 B 원소만 추가한다.

인접 행렬과 인접 리스트 비교

인접 행렬
장점 - 정점 간의 인접 여부를 빠르게 알 수 있음
단점 - 인접 관계를 행렬 형태로 저장하기 위해 사용하는 메모리의 양이 ‘정점의 크기×N²’ 만큼 커짐

인접 리스트
장점 - 정점과 간선의 삽입이 빠르고 인접 관계를 표시하는 리스트에 사용되는 메모리의 양이 적음
단점 - 정점 간의 인접 여부를 알아내기 위해 인접 리스트를 타고 순차 탐색이 필요

둘 다 어느 쪽도 장점이 압도적으로 많지 않다.

따라서 어느 자료구조를 선택할 것인가는 구현하고자 하는 프로그램의 목적에 따라 결정해야 한다.

그래프 순회 기법

reference : https://lemidia.github.io/

DFS(Depth First Search)

DFS에는 스택을 이용한 방법과 재귀를 이용한 방법이 있지만 이 글에서는 스택을 이용한 방법을 다룬다.

방문할 인접 정점들을 저장할 Stack과 정점들의 방문 표시를 할 visited[] 배열을 선언한다.
스택을 이용한 DFS 알고리즘은 다음과 같은 순서로 실행된다.

1. 탐색을 시작할 스타팅 노드를 스택에 넣는다.
2. 스택이 빈 공간이 아닐 때 까지 다음을 실행한다.
3. 스택에서 정점 하나를 꺼내 방문하지 않았으면 방문 표시를 하고 그 정점에 인접한 모든 정점을 스택에 넣는다.(방문 하지 않은 정점들만)
4. 2번으로 간다.

아래의 예는 현재 정점과 인접한 정점이 여러개면 번호가 작은 순서대로 방문한다.
물론 번호가 큰 순서대로 방문할 수도 있다.

탐색은 0번 정점부터 시작한다고 가정한다.

탐색을 시작할 0번 정점을 스택에 넣는다.

스택에서 가장 위에있는 원소를 하나 꺼낸다. (여기서는 제일 왼쪽 칸이 top이다.)

0번 정점을 방문표시 하고 0번 정점과 인접한 정점들 중에서 방문하지 않는 정점들을 모두 스택에 넣는다.
(0번 정점과 1, 2, 3번 정점이 인접해 있다.) 

위의 방문 우선순위에 따라 인접한 정점이 여러개면 번호가 [작은 순서대로] 방문해야 하므로 3, 2, 1순으로 스택에 삽입한다. (후입 선출)

계속해서, 스택에서 가장 위에있는 1번 정점을 꺼낸다. 

1번 정점을 방문표시 하고 1번 정점과 인접한 정점들 중에서 방문하지 않는 정점들을 모두 스택에 넣는다.

여기서는 2번 정점을 스택에 삽입한다.

그 다음, 스택에서 가장 위에있는 2번 정점을 꺼낸다.

2번 정점을 방문표시 하고 2번 정점과 인접한 정점들 중에서 방문하지 않는 정점들을 모두 스택에 넣는다.

여기서는 4번 정점을 스택에 삽입한다.

그 다음, 스택에서 가장 위에있는 4번 정점을 꺼낸다.

4번 정점을 방문표시 하고 4번 정점과 인접한 정점들 중에서 방문하지 않는 정점들을 모두 스택에 넣는다.

4번 정점과 인접한 정점 중에서는 방문하지 않은 정점들이 없으므로 다음 스탭으로 간다.

그 다음, 스택에서 가장 위에있는 3번 정점을 꺼낸다.

3번 정점을 방문표시 하고 3번 정점과 인접한 정점들 중에서 방문하지 않는 정점들을 모두 스택에 넣는다.

3번 정점과 인접한 정점 중에서는 방문하지 않은 정점들이 없으므로 다음 스탭으로 간다.

스택이 모두 비었으니 알고리즘을 끝낸다.
스택을 이용한 DFS의 방문순서는 0 1 2 4 3 순이다.

BFS(Breadth First Search)

BFS는 큐를 이용하여 탐색한다.

위에서 보이는 트리에서 정점들의 번호는 너비우선탐색을 적용한 뒤 정점들의 방문 순서와 같다.
1번 정점을 루트로 하여 탐색을 시작하면, 1번 정점을 방문하고 그 인접한 정점 2, 3, 4를 순서대로 방문한다.
그 다음 레벨의 5, 6, 7, 8을 순서대로 방문하고 그 다음 레벨 9, 10, 11, 12순으로 방문하게 된다.

가정
현재 방문하고 있는 정점에서 인접한 왼쪽 간선을 오른쪽 간선보다 먼저 선택한다.
정점들의 방문은 중복되지 않는다.
1번 정점 부터 탐색을 시작한다.

먼저 1번 정점을 루트로 하여 BFS 탐색을 시작한다.

1번 정점을 큐에 넣는다.
Queue: [1]

큐에서 제일 앞에 있는 1번을 pop하고, 1번 정점을 방문한다.
1번 정점과 인접한 정점 중에서 방문하지 않은 2, 3, 4번을 순서대로 큐에 넣는다.
Queue: [2, 3, 4]

큐에서 제일 앞에 있는 2번을 pop하고, 2번 정점을 방문한다.
2번 정점과 인접한 정점 중에서 방문하지 않은 5, 6번을 순서대로 큐에 넣는다.
Queue: [3, 4, 5, 6]

큐에서 제일 앞에 있는 3번을 pop하고, 3번 정점을 방문한다.
3번 정점과 인접한 정점 중에서 방문하지 않은 정점이 없으므로 다음 스탭으로 간다.
Queue: [4, 5, 6]

큐에서 제일 앞에 있는 4번을 pop하고, 4번 정점을 방문한다.
4번 정점과 인접한 정점 중에서 방문하지 않은 7, 8번을 순서대로 큐에 넣는다.
Queue: [5, 6, 7, 8]

큐에서 제일 앞에 있는 5번을 pop하고, 5번 정점을 방문한다.
5번 정점과 인접한 정점 중에서 방문하지 않은 9, 10번을 순서대로 큐에 넣는다.
Queue: [6, 7, 8, 9, 10]

큐에서 제일 앞에 있는 6번을 pop하고, 6번 정점을 방문한다.
6번 정점과 인접한 정점 중에서 방문하지 않은 정점이 없으므로 다음 스탭으로 간다.
Queue: [7, 8, 9, 10]

큐에서 제일 앞에 있는 7번을 pop하고, 7번 정점을 방문한다.
7번 정점과 인접한 정점 중에서 방문하지 않은 11, 12번을 순서대로 큐에 넣는다.
Queue: [8, 9, 10, 11, 12]

큐에서 제일 앞에 있는 8번을 pop하고, 8번 정점을 방문한다.
8번 정점과 인접한 정점 중에서 방문하지 않은 정점이 없으므로 다음 스탭으로 간다.
Queue: [9, 10, 11, 12]

큐에서 제일 앞에 있는 9번을 pop하고, 9번 정점을 방문한다.
9번 정점과 인접한 정점 중에서 방문하지 않은 정점이 없으므로 다음 스탭으로 간다.
Queue: [10, 11, 12]

큐에서 제일 앞에 있는 10번을 pop하고, 10번 정점을 방문한다.
10번 정점과 인접한 정점 중에서 방문하지 않은 정점이 없으므로 다음 스탭으로 간다.
Queue: [11, 12]

큐에서 제일 앞에 있는 11번을 pop하고, 11번 정점을 방문한다.
11번 정점과 인접한 정점 중에서 방문하지 않은 정점이 없으므로 다음 스탭으로 간다.
Queue: [12]

큐에서 제일 앞에 있는 12번을 pop하고, 12번 정점을 방문한다.
12번 정점과 인접한 정점 중에서 방문하지 않은 정점이 없으므로 다음 스탭으로 간다.
Queue: [ ]

큐가 비었으므로 너비우선탐색(BFS)가 완료되었다.

힙과 우선순위 큐

결론부터 말하자면, 우선순위 큐는 ADT(Abstract Data Type) 이고, 힙은 우선순위 큐의 개념을 구현한 것이다.

ADT
구현하고자 하는 구조에 대해 구현 방법은 명시하지 않고 자료구조의 특성들과 어떤 기능이 있는지를 설명하고 나열한 것.
즉, 구현은 하지 않고 어떠한 기능과 어떠한 작동원리를 가지는지 추상적으로 설명한 것이다.

우선순위 큐는 단순 FIFO구조가 아니라, 각 큐에 들어오는 원소마다 우선순위가 정해져 있다.

1. 만약, 우선순위가 높은 순서대로 큐에서 제거하기로 했다면 큐에 들어온 순서대로 원소가 제거되는 것이 아니라 우선순위가 높은 순서대로 큐에서 제거된다.
2. 만약, 우선순위가 낮은 순서대로 큐에서 제거하기로 했다면 큐에 들어온 순서대로 원소가 제거되는 것이 아니라 우선순위가 낮은 순서대로 큐에서 제거된다.

우선순위 큐는 단순히 ADT이고, 이를 구현한 것이 힙이라고 위에서 말했다.

따라서 1의 경우를 구현한 것을 Max Heap(최대 힙), 2의 경우를 구현한 것을 Min Heap(최소 힙)이라고 한다.

• 우선순위 큐는 완전 이진트리를 이용하여 힙으로 구현한다.
• 시간 복잡도는 삽입과 삭제 모두 O(log N)이다.

자세한 내용은 아래의 동영상을 보고 학습하는 것을 추천한다.

https://youtu.be/P-FTb1faxlo?si=Pak-seuRg2veRZFz

자바에서 우선순위 큐 사용하기

PriorityQueue 클래스

• PriorityQueue를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야 한다.
• Comparable 또는 Comparator 인터페이스를 구현하면 compareTo() 또는 Compare() 메소드를 오버라이딩 하게 되고 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue 가 알아서 우선순위가 높은 객체를 추출해준다.

최소 힙

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

• 처리될 원소가 integer 타입인 최소 힙 선언
• java.util.PriorityQueue를 import해줘야 한다.

최대 힙

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

또는

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return - Integer.compare(o1,o2);
        }
    });

• 처리될 원소가 integer 타입인 최대 힙 선언
• java.util.PriorityQueue를 import해줘야 한다.
• 첫 번째 방법은 Collections클래스의 정적 메소드인 reverseOrder()를 이용해서 최소힙과 반대로 정렬을 하여 최대힙을 만든다.
• 두 번째 방법은 Comparator인터페이스의 구현 객체를 익명으로 만들고, compare메소드를 오버라이딩하여 최소힙과 반대로 정렬을 하여 최대힙을 만든다.

메소드

추가

heap.add(1); // 1을 삽입
heap.offer(1); // 1을 삽입

add()메소드와 offer() 메소드의 차이점은 문제 상황에서 예외를 발생시키는가 아니면 false를 리턴하느냐에 있다.

add()는 삽입에 실패할 경우 예외를 발생시키지만, offer는 false를 리턴한다.

삭제

heap.poll(); //우선순위가 가장 높은 원소를 삭제
heap.remove(); //우선순위가 가장 높은 원소를 삭제
heap.clear(); //힙을 초기화

remove()메소드와 poll() 메소드의 차이점은 문제 상황에서 예외를 발생시키는가 아니면 null을 리턴하느냐에 있다.

remove()는 삭제에 실패할 경우(또는 큐가 비어있을 경우) 예외를 발생시키지만, poll()는 null을 리턴한다.

우선순위가 가장 높은 값 확인

heap.peek(); //우선순위가 가장 높은값 리턴
heap.element(); //우선순위가 가장 높은값 리턴

element()는 큐가 비어있을 경우 예외를 발생시키지만, peek()는 null을 리턴한다.

이 글은 누구나 자료 구조와 알고리즘(저자 : 제이 웬그로우)의 내용을 개인적으로 정리하는 글임을 알립니다.

패스트푸드점에서 손님이 음식을 주문하는 프로그램을 작성 중이고, 음식마다 각각 가격이 있는 메뉴를 구현하고 있다고 상상해 보자.

메뉴 배열 안에 메뉴의 이름과 가격을 포함하는 배열이 또 있다고 가정하면, 메뉴 배열안에 있는 하위 배열을 찾는데 O(N)의 단계가 걸린다.

정렬된 배열이라면 이진탐색을 통해O(logN)이 걸린다.

하지만 해시 테이블을 사용하면 데이터를 O(1)만에 룩업할 수 있다.

해시 테이블

해시 테이블은 다양한 프로그래밍 언어에서 서로 다른 이름으로 불린다.

해시, 맵, 해시맵, 딕셔너리, 연관 배열 등의 이름을 갖는다.

대부분의 프로그래밍 언어는 해시 테이블(hash table)이라는 자료구조를 포함하며, 해시 테이블에는 빠른 읽기라는 놀랍고 엄청난 능력이 있다.

해시 테이블은 쌍으로 이뤄진 값들의 리스트다.

첫 번째 항목을 키라 부르고, 두 번째 항목을 값이라 부른다.

french fries가 키이고, 0.75가 값이다.

이렇게 해시 테이블로 구성되어 있다면 프랜치프라이가 가격이 얼마인지 딱 한 단계만에 알 수 있다.

해시 테이블의 값 룩업은 딱 한 단계만 걸리므로 평균적으로 효율성이 O(1)이다.

해시 함수로 해싱

비밀 코드를 만들고 해독한다고 가정해보자.

예를 들어 아래처럼 단순하게 글자와 숫자를 짝지을 수 있다.

위 코드에 따르면, ACE는 135로, CAB는 312로, DAB는 412로, BAD는 214로 변환된다.

• 문자를 가져와 숫자로 변환하는 과정을 해싱(hasing)이라 부른다.
• 글자를 특정 숫자로 변환하는데 사용한 코드를 해시 함수(hash function)라 부른다.

이 밖에도 해시 함수는 많다. 또 다른 해시 함수 예제는 각 문자에 해당하는 숫자를 가져와 모든 수를 합쳐 반환하는 것이다.

이렇게 하면 BAD는 아래와 같은 두 단계의 과정을 거쳐 숫자 7이 된다.

1. 먼저 BAD를 214로 변환한다.
2. 각 숫자를 가져와 합한다.

2 + 1 + 4 = 7

또 다른 해시 함수 예제는 문자에서 해당하는 모든 수를 곱해서 반환하는 것이다.

1. BAD를 214로 변환한다.
2. 각 숫자를 가져와 곱한다.

2 x 1 x 4 = 8

실제 쓰이는 해시 함수는 이보다 더 복잡하지만 이러한 "곱셈" 해시 함수를 사용하면 예제가 명확하고 간단해진다.

해시 함수가 유효하려면 딱 한 가지 기준을 충족해야 한다.

해시 함수는 동일한 문자열을 해시 함수에 적용할 때마다 항상 동일한 숫자로 변환해야 한다.

주어진 문자에 대해 반환하는 결과가 일관되지 않으면 그 해시함수는 유효하지 않다.

따라서 난수나 현재 시간을 계산에 넣어 사용하는 해시 함수는 유효하지 않다.

하지만 곱셈 해시 함수를 쓰면 BAD는 항상 8로 변환된다.

B는 항상 2고, A는 항상 1이고, D는 항상 4이기 때문이다.

따라서 2 x 1 x 4는 항상 8이다.

곱셈 해시 함수를 쓰면 DAB역시 BAD처럼 8로 변환된다는 것에 유의한다. 이로 인해 실제로 문제가 발생한다.

유의어 사전 만들기

사용자가 당신이 만든 사전에서 단어를 룩업하면 구식 유의어 사전 앱처럼 가능한 유의어를 모두 반환하는 대신 유의어를 딱 하나만 반환한다.

모든 단어에는 각각 연관된 동의어가 있으므로 동의어는 해시 테이블의 좋은 사용 사례다.

다음과 같이 해시테이블로 유의어 사전을 표현한다고 하자.

배열과 유사하게 해시 테이블은 내부적으로 데이터를 한 줄로 이뤄진 셀 묶음에 저장한다.

각 셀마다 주소가 있다.

예를 들면 아래와 같다.

첫 번째 항목을 해시 테이블에 추가하자

컴퓨터는 해시 테이블을 만들기 위해 키에 해시 함수를 적용한다.

BAD = 2 x 1 x 4 = 8

키("bad")는 8로 해싱되므로 컴퓨터는 값("evil")을 아래와 같이 셀 8에 넣는다.

다시 한번 컴퓨터는 키를 해싱한다.

CAB = 3 x 1 x 2 = 6

결괏값이 6이므로 컴퓨터는 값("taxi")를 셀 6에 저장한다.

ACE = 1 x 3 x 5 = 15

ACE는 15로 해싱되고 "star"는 셀 15로 들어간다.

해시 테이블 룩업

해시 테이블에서 항목을 룩업할 때는 키를 사용해 연관된 값을 찾는다.

키 bad의 값을 룩업하고 싶다고 하자.

bad의 값을 찾기 위해 컴퓨터는 간단히 두 단계를 실행한다.

1. 컴퓨터는 룩업하고 있는 키를 해싱한다. BAD = 2 x 1 x 4 = 8
2. 결과가 8이므로 셀 8을 찾아가서 저장된 값을 반환한다. 즉, evil을 반환한다.

해시 테이블에서 각 값의 위치는 키로 결정된다.

즉, 키 자체를 해싱해 키와 연관된 값이 놓여야 하는 인덱스를 계산한다.

키가 값의 위치를 결정하므로 이 원리를 사용하면 룩업이 아주 쉬워진다.

어떤 키가 있고 그 키의 값을 찾고 싶으면 키 자체로 값을 어디서 찾을 수 있는지 알 수 있다.

이제 왜 해시 테이블의 값 룩업이 전형적으로 O(1)인지 명확해졌다.

단방향 룩업

키를 사용해 값을 찾을 때만 O(1) 룩업이 가능하다.

거꾸로 값을 이용해 연관된 키를 찾을 때는 해시 테이블의 빠른 룩업 기능을 활용할 수 없다.

이는 키가 값의 위치를 결정한다는 해시 테이블의 대전제 때문이다.

하지만 이 전제는 한 방향으로만, 다시 말해 키를 사용해 값을 찾는 식으로만 동작한다.

세부적으로는 언어에 따라 다르지만 어떤 언어는 값 바로 옆에 키를 저장한다.

이렇게 저장하면 다음 절에서 다룰 충돌에서 매우 유용하다.

또한 각 키는 해시 테이블에 딱 하나 존재할 수 있으나 값은 여러 인스턴스가 존재할 수 있다.

처음에 살펴봤던 메뉴 예제를 떠올리면 같은 햄버거를 두 번 나열할 수 없다.

하지만 값은 여러 인스턴스가 존재할 수 있다.

즉 다른 햄버거라도 가격은 같을 수 있다.

대부분의 언어는 이미 존재하는 키에 키/값 쌍을 저장하려 하면 키는 그대로 두고 기존 값만 덮어쓴다.

충돌 해결

해시 테이블은 좋은 자료구조이지만 문제도 있다.

유의어 사전 예제를 살펴보자.

아래와 같은 항목을 예제의 유의어 사전에 추가하면 아래와 같은 일이 벌어진다.

DAB = 4 x 1 x 2 = 8

pat을 해시 테이블의 셀 8에 추가하려 한다.

셀 8에는 이미 값이 존재한다.

이미 채워진 셀에 데이터를 추가하는 것을 충돌이라 부른다.

다행히 이 문제를 해결하는 방법들이 있다.

충돌을 해결하는 고전적인 방법하나가 분리 연결법이다.

충돌이 발생했을 때 셀에 하나의 값을 넣는 대신 배열로의 참조를 넣는 방법이다.

이렇게 되어 있던 배열을 아래와 같이 바꾼다.

이렇게 바꿨을 때 해시 테이블 룩업은 thesaurus["dab"]을 룩업할 때 컴퓨터는 아래와 같은 단계를 거친다.

1. DAB = 4 x 1 x 2 = 8
2. 셀 8을 룩업 한다. 컴퓨터는 셀 8이 하나의 값이 아닌 배열들의 배열을 포함하고 있음을 알게 된다.
3. 각 하위 배열의 인덱스를 찾아보며 룩업하고 있는 단어인 dab을 찾을 때까지 배열을 차례대로 검색한다.
   일치하는 하위 배열의 인덱스 1에 있는 값을 반환한다.

컴퓨터가 확인 중인 셀이 배열을 참조할 경우 다수의 값이 들어 있는 배열을 선형 검색해야 하므로 검색 단계가 더 걸린다.

만약 모든 데이터가 해시 테이블의 한 셀에 들어가게 된다면 해시 테이블은 배열보다 나을게 없다.

따라서 최악의 경우 해시 테이블 룩업 성능은 사실상 O(N)이다.

이렇기 때문에 해시 테이블에 충돌이 거의 없도록 O(N) 시간이 아닌 O(1) 시간 내에 일반적으로 룩업을 수행하도록 디자인해야 한다.

효율적인 해시 테이블 만들기

궁극적으로 해시 테이블은 아래 세 요인에 따라 효율성이 정해진다.

1. 해시 테이블에 얼마나 많은 데이터를 저장하는가
2. 해시 테이블에서 얼마나 많은 셀을 쓸 수 있는가
3. 어떤 해시 함수를 사용하는가

처음 두 요인이 중요한 이유는 적은 셀에 많은 데이터를 저장하면 충돌이 많을 테고 해시 테이블의 효율성은 떨어진다.

세 번째 요인이 중요한 이유는

이러한 셀이 있다고 가정하면, 어떤 해시 함수를 사용하면 10에서 16 사이의 셀은 이용할 수 없다고 하면 셀의 낭비가 되고 낭비되는 만큼 효율이 저하된다.

따라서 좋은 해시 함수란 사용 가능한 모든 셀에 데이터를 분산시키는 함수이다.

데이터를 넓게 퍼뜨릴수록 충돌이 적다.

충돌 조정을 위해 컴퓨터 과학자는 해시테이블에 저장된 데이터가 7개면 셀은 10개여야 한다고 말한다.
데이터와 셀 간 이러한 비율을 부하율이라 부른다.
데이터를 더 추가하기 시작하면 새 데이터가 새로운 셀들에 균등하게 분산되도록 컴퓨터는 셀을 더 추가하고 해시 함수를 바꿔서 해시 테이블을 확장한다.

이 글은 누구나 자료 구조와 알고리즘(저자 : 제이 웬그로우)의 내용을 개인적으로 정리하는 글임을 알립니다.

배열의 크기와 인덱스

• 배열의 크기 : 배열에 데이터 원소가 얼마나 들어있는지를 나타낸다. 위 그림에서 배열의 크기는 5이다.
• 배열의 인덱스 : 특정 데이터가 배열의 어디에 있는지 알려주는 숫자다.

자료구조 연산

대부분의 자료 구조는 네 가지 기본 방법을 사용하며 이를 연산이라 부른다.

연산은 아래와 같다.

• 읽기
• 검색
• 삽입
• 삭제

연산의 속도 측정

연산이 얼마나 '빠른가'를 측정 할 때는 순수하게 시간 관점에서 연산이 빠른가가 아니라,

얼마나 많은 단계가 필요한지를 논해야 한다.

왜 코드의 속도를 시간으로 측정하지 않을까?
누구도 어떤 연산이, 정확히 몇초가 걸린다고 단정할 수 없기 때문이다.
같은 연산도 어떤 컴퓨터에서는 1초가 걸리고, 구형 하드웨어에서는 더 오래걸릴 수 있기 때문이다.
슈퍼 컴퓨터는 훨씬 빠를 수도 있다.
시간은 실행하는 하듸웨어에 따라 항상 바뀌므로 시간을 기준으로 속도를 측정하면 신뢰할 수 없다.

연산의 속도를 측정할 때 얼마나 많은 단계(step)가 필요한가를 따져볼 수 있다.

같은 작업을 처리하는데, A 알고리즘은 5단계가 필요하고, B 알고리즘은 500단계가 필요하면, 모든 하드웨어에서 연산 A가 연산 B보다 항상 빠를 거라고 가정할 수 있다.

결국 단계 수 측정이 연산 속도를 분석하는 핵심 비결이다.

읽기

읽기는 배열 내 특정 인덱스에 어떤 값이 들어있는지 찾아보는 것이다.

컴퓨터는 딱 한 단계로 배열에서 읽을 수 있다.

위 배열에서 인덱스 2를 찾아본다면 컴퓨터는 인덱스 2로가서 cucumbers라는 값이 있다고 알려줄 것이다.

컴퓨터의 메모리는 어떻게 단 한 단계로 배열의 인덱스를 찾아볼 수 있는가?
컴퓨터의 메모리는 셀로 구성된 거대한 컬렉션이라 할 수 있다.
어떤 셀은 비어 있고, 어떤 셀에는 데이터가 들어있다.

예를 들어 원소 다섯 개를 넣을 배열을 생성하면 컴퓨터는 한 줄에서 5개의 빈 셀 그룹을 찾아 사용자가 사용할 배열로 지정한다.

컴퓨터 메모리 내에 각 셀에는 특정 주소가 있다.
각 셀의 메모리 주소는 앞 셀의 주소에서 1씩 증가한다.

-컴퓨터는 모든 메모리 주소에 한 번에 갈 수있다.(특정 메모리의 값을 조사 요청을 받으면 검색 과정 없이 바로 간다)
-컴퓨터는 배열을 할당할 때 어떤 메모리 주소에서 시작하는지도 기록해 둔다.
위와 같은 점들이 컴퓨터가 배열의 첫 번째 값을 어떻게 한 번에 찾아내는지 설명한다.

컴퓨터에 인덱스 3에 있는 값을 읽으라고 명령하면 컴퓨터는 아래와 같은 과정을 밟는다.
1. 배열의 인덱스는 0부터 시작하며 인덱스 0의 메모리 주소는 1010이다.
2. 인덱스 3은 인덱스 0부터 정확히 세 슬롯 뒤에 있다.
3. 따라서 인덱스 3을 찾으려면 1010 + 3인 1013 메모리 주소로 간다.

인덱스 3의 메모리 주소가 1013임을 알아낸 컴퓨터는 바로 접근해서 "dates"라는 값을 찾을 수 있다.

검색

검색은 배열에 특정 값이 있는지 알아본 후, 있다면 어떤 인덱스에 있는지 찾는 것이다.

• 읽기는 컴퓨터에 인덱스를 제공하고 그 인덱스에 들어있는 값을 반환하라고 요청
• 검색은 컴퓨터에 값을 제공하고 그 값이 들어 있는 인덱스를 반환하라고 요청

읽기와 검색은 비슷해 보이지만 효율성 측면에서 매우 큰 차이를 보인다.

검색은 컴퓨터가 특정 값으로 바로 갈 수 없으니 오래 걸린다.

왜냐하면, 컴퓨터는 모든 메모리 주소에 한 번에 접근하지만 각 메모리 주소에 어떤 값이 있는지 바로 알지 못하기 때문이다.

배열에서 어떤 원소를 찾으려면 컴퓨터는 각 셀을 한 번에 하나씩 조사하는 방법밖에 없다.

아래의 그림은 'dates'를 찾는 과정이다.

dates를 찾았고, 인덱스 3에 있음을 알았다.

찾고 있던 값을 발견했으니 컴퓨터는 배열의 다음 셀로 이동해서 검색할 필요가 없다.

컴퓨터는 찾으려던 값을 발견할 때까지 4개의 셀을 확인하므로 이 연산에는 총 4단계가 걸렸다고 할 수 있다.

컴퓨터가 한 번에 한 셀씩 확인하는 방법을 선형 검색이라고 부른다.

N칸의 배열에서의 선형 검색을 수행하는데 필요한 최대 단계수는 N개이다.

• 크기가 5인 배열에서 선형 검색을 수행하는데 필요한 최대 단계수는 5개
• 크기가 100인 배열에서 선형 검색을 수행하는데 필요한 최대 단계수는 100개

삽입

배열에 새 데이터를 삽입하는 연산은 배열의 어디에 데이터를 삽입하는가에 따라 효율성이 다르다.

맨 끝에 데이터 삽입

배열의 맨 끝에 데이터를 추가하는 것은 딱 한 단계만 필요하다.

문제점 하나
애초에 컴퓨터는 배열에 5개의 메모리 셀을 할당했고 6번째 원소를 추가하려면 이 배열에 셀을 추가로 할당해야 할 수 있다.

많은 프로그래밍 언어가 내부에서 자동으로 처리하지만 언어마다 방식이 다르다.

중간에 삽입

데이터를 중간에 삽입하면 삽입할 공간을 만들기 위해 많은 데이터 조각을 이동시켜야 하므로 단계가 늘어난다.

"figs" 가 들어가려는 자리 뒤에 3개가 있었고, 마지막에 데이터를 삽입하는 단계 1을 합해서 4단계가 걸렸다(3+1)

맨앞에 삽입

배열 삽입에서 최악의 시나리오, 즉 삽입에 가장 많은 단계가 걸리는 시나리오는 데이터를 배열의 맨 앞에 삽입할 때다.

배열의 앞에 삽입하면 배열 내 모든 값을 한 셀씩 오른쪽으로 옮겨야 하기 때문이다.

N개의 원소를 포함하는 배열에서 최악의 시나리오일 때 삽입에는 N+1단계가 걸린다.

• N개의 모든 원소를 뒤로 밀어버린다.
• 데이터를 맨 앞에 삽입한다.

삭제

삭제는 특정 인덱스의 값을 제거하는 과정이다.

인덱스 2의 값을 삭제해보자.

원소 삭제에서 최악의 시나리오는 배열의 첫 번째 원소를 삭제하는 것이다.

원소 5개를 포함하는 배열이면 1단계는 첫 번째 원소 삭제에, 4단계는 남아 있는 원소 4개를 이동하는데 쓰인다.

따라서 원소 N개를 가지는 배열에서 삭제에 필요한 최대 단계 수는 N단계라고 할 수 있다.

집합 배열

집합은 중복 값을 허용하지 않는 자료구조다.

집합의 종류는 다양하지만 여기서는 배열 기반 집합을 다룬다.

일반 배열과 집합 배열의 차이점은 집합은 중복 값의 삽입을 절대 허용하지 않는다는 점이다.

예를 들어 ["a", "b", "c"]라는 집합에 b를 추가하려고 하면 b가 이미 있으므로 삽입을 허용하지 않는다.

• 집합 배열의 읽기 : 컴퓨터는 특정 인덱스에 들어 있는 값을 한 단계 만에 찾는다.
• 집합 배열의 검색 : 집합에서 어떤 값을 찾는 데 최대 N단계가 걸린다.
• 집합 배열의 삭제 : 집합에서 어떤 값을 삭제하고 배열을 옮겨 빈공간을 메꾸는 데 최대 N단계가 걸린다.

이렇게 집합과 집합 배열은 읽기, 검색, 삭제는 모두 동일한 단계 수를 가진다.

하지만 삽입만큼은 배열과 배열 집합은 다르다.

배열에서 최선의 시나리오였던 맨 끝에 삽입하는 경우 한 단계만에 값을 끝에 삽입했다.

하지만 집합 배열에서는 먼저 이 값이 이미 집합에 들어 있는지 결정해야 한다.

중복 데이터를 막는 게 집합의 역할이기 때문이다.

중복 데이터 삽입을 막기위해 삽입하려는 값이 집합에 이미 있는지부터 먼저 검색해야 한다.

집합에 새 값이 없을 때에만 컴퓨터는 삽입을 허용한다.

따라서 모든 삽입에는 검색이 우선이다.

모든 원소를 검색해야하므로 N단계가 소요되고, 삽입까지 총 N+1 단계가 소요된다.

값을 집합의 맨 앞에 삽입하는 최악의 시나리오일 때 컴퓨터는 셀 N개를 검색해서 집합이 그 값을 포함하지 않음을 확인한 후, 또 다른 N단계로 모든 데이터를 오른쪽으로 옮겨야 하며, 마지막 단계에서 새 값을 삽입해야한다.

그러하여 총 2N+1단계이다.

일반 배열보다 집합 배열이 안좋다는 것이 아니다.

중복을 허락하지 않아야할 때는 무조건 집합을 써야 한다.

즉, 애플리케이션의 요구사항에 따라 어떤 자료구조를 써야할지 선택해야 한다.

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

큐

큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조이다. 하지만 큐는 스택과 다르게 선입선출(FIFO, First In First Out)이다.

아래의 그림과 같이 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조로 되어 있다.

큐에 데이터를 넣는 작업을 인큐라 하고, 데이터를 꺼내는 작업을 디큐라고 한다.

인큐와 디큐

인큐

위 그림에서 리어(rear)인 53 뒤에 24를 인큐 한다.

이 처리의 시간복잡도는 O(1)이고 적은 비용으로 구현할 수 있다.

디큐

위 그림에서 프론트(front)인19와 22을 디큐 한다. 디큐한 후에는 모든 요소를 앞으로 옮겨야 한다.

이 처리의 시간복잡도는 O(N)이며 데이터를 꺼낼 때마다 이런 처리를 하게 되면 효율이 떨어진다.

구현

IntAryQueue 클래스 (int형 배열로 구현)

public class IntAryQueue {
    private int max; //큐 용량
    private int num; //현재 데이터 수
    private int[] que;

    IntAryQueue(int capacity) //생성자
    {
        this.max = capacity;
        que = new int[max];
        num = 0;
    }

    private boolean isFull() {return num >= max;} //큐의 공간이 모두 사용중인지 리턴

    private boolean isEmpty() {return num <= 0;} //큐의 공간이 비어있는지 리턴

    public int capacity() {return max;} //큐의 용량을 리턴

    public int size() {return num;} //큐의 현재 데이터 수를 리턴

    public void enque(int value)
    {
        if(!isFull()) que[num++] = value;
        else System.out.println("큐의 공간을 모두 사용중입니다.");
    }

    public void deque()
    {
        if(!isEmpty())
        {
            for (int i = 1; i < num; ++i)
            {
                que[i-1] = que[i];
            }
            que[--num] = 0;
        }
        else System.out.println("이미 큐의 공간이 비어있습니다.");
    }

    public void peek() //큐의 front를 리턴
    {
        if(num > 0) System.out.println("front : " + que[0]);
        else System.out.println("큐의 공간이 비어있습니다.");
    }

    public void back() //큐의 rear을 리턴
    {
        if(num > 0) System.out.println("rear : " + que[num- 1]);
        else System.out.println("큐의 공간이 비어있습니다.");
    }

    public void indexOf(int value) //큐에서 찾는 데이터가 있는지 출력
    {
        for(int i = 0; i < num; ++i)
        {
            if(que[i] == value)
            {
                System.out.println("찾는 값이 있습니다. 인덱스 : " + i);
                return;
            }
        }
        System.out.println("찾는 값이 없습니다.");
    }

    public void clear() {num = 0;} //큐의 front를 초기화 시킴

    public void dump() //모든 큐의 값을 출력
    {
        if(isEmpty())
        {
            System.out.println("큐가 비어있습니다.");
            return;
        }
        for (int i = 0; i < num; ++i)
        {
            System.out.println("[" + i + "]" + "=" + que[i]);
        }
    }
}

실행 예제

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("큐 용량 입력 : ");
        int command = sc.nextInt();
        IntAryQueue que = new IntAryQueue(command);
        while(true)
        {
            System.out.println();
            System.out.println("현재 데이터 수 : " + que.size() + "/" + que.capacity());
            System.out.println("(1)inqueue (2)dequeue (3)search (4)front (5)back (6)dump (7)clear (8)exit");
            System.out.print("cmd : ");
            command = sc.nextInt();
            if(command == 1)
            {
                System.out.print("value : ");
                command = sc.nextInt();
                que.enque(command);
            }
            else if(command == 2) que.deque();
            else if(command == 3)
            {
                System.out.print("Data for Search: ");
                command = sc.nextInt();
                que.indexOf(command);
            }
            else if(command == 4) que.peek();
            else if(command == 5) que.back();
            else if(command == 6) que.dump();
            else if(command == 7) que.clear();
            else if(command == 8) System.exit(0);
            else continue;
        }
    }
}

링 버퍼(Ring Buffer)

일반 큐는 디큐를 하고나서 모든 배열의 요소를 맨 앞으로 옮기는 작업을 해야 했다.

그래서 시간복잡도가 증가하였다.

링 버퍼 큐는 배열의 요소를 앞쪽으로 옮기지 않는 큐이다.

링 버퍼 큐는 배열의 처음과 끝이 연결되었다고 보는 자료구조이다.

여기서 논리적으로 어떤 요소가 첫 번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위한 변수가 front와 rear이다.

• front : 맨 처음 요소의 인덱스
• rear : 맨 끝 요소의 하나 뒤의 인덱스(다음 요소를 인큐 할 위치를 미리 지정)
• front와 rear는 논리적인 데이터 순서를 말한다. 배열의 물리적 요소의 순서가 아니다.

인큐, 디큐, 검색

인큐

인큐를 할 때, 데이터는 que[rear]에 저장된다. 즉, 데이터는 rear에 저장된다.

만약 rear가 배열의 공간과 같다면(배열의 최대 인덱스보다 크다면), rear를 배열의 가장 작은 인덱스로 바꿔줘야 한다.

que[rear++] = value;
++num;
if(rear == max) rear = 0;

디큐

디큐를 할 때, que[front]의 데이터가 삭제된다.

만약 front가 배열의 공간과 같다면(배열의 최대 인덱스보다 크다면), front를 배열의 가장 작은 인덱스로 바꿔줘야 한다.

que[front++] = 0;
--num;
if(front == max) front = 0;

검색

for(int i = 0; i < num; ++i)
{
    int index = (i + front) % max;
    if(que[index] == value)
    {
        System.out.println(value + "는 큐의 " + (i+1) + "번째 데이터이고, 배열의 " + index + "인덱스에 있습니다.");
        return;
    }
}
System.out.println("찾는 값이 없습니다.");

front가 6이고, 배열의 길이가 12라면 i와 index는 아래와 같다.

• i : 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
• index : 7 -> 8 -> 9 -> 10 -> 11 -> 0 -> 1

구현

int형 배열을 이용한 IntQueue 클래스

public class IntQueue {
	private int max; //큐 용량
	private int num; //현재 데이터 수
	private int front; //디큐를 할 인덱스를 가리킴
	private int rear; //인큐를 할 인덱스를 가리킴
	private int[] que;
	
	IntQueue(int capacity) //생성자
	{
		this.max = capacity;
		num = front = rear = 0;
		que = new int[max];
	}
	
	private boolean isEmpty() {return num <= 0;} //큐가 비어있는지를 리턴
	
	private boolean isFull() {return num >= max;} //큐의 공간이 모두 사용중인지 리턴
	
	public int capacity() {return max;} //큐의 용량을 리턴
	
	public int size() {return num;} //큐가 현재 사용중인 공간을 리턴
	
	public void clear() {num = front = rear = 0;} //큐 초기화
	
	public void enque(int value)
	{
		if(!isFull())
		{
			que[rear++] = value;
			++num;
			if(rear == max) rear = 0;
			return;
		}
		else
		{
			System.out.println("큐의 모든 공간이 사용중입니다.");
			return;
		}
	}
	
	public void deque()
	{
		if(!isEmpty())
		{
			que[front++] = 0;
			--num;
			if(front == max) front = 0;
			return;
		}
		else
		{
			System.out.println("이미 큐가 비어있습니다.");
			return;
		}
	}
	
	public void peek() //front를 출력
	{
		if(!isEmpty()) System.out.println(que[front]);
		else System.out.println("큐가 비어있습니다.");
	}
	
	public void indexOf(int value) //값이 배열에 존재하는지와 몇 번째 데이터인지, 배열의 몇 번째 인덱스인지 출력
	{
		for(int i = 0; i < num; ++i)
		{
			int index = (i + front) % max;
			if(que[index] == value)
			{
				System.out.println(value + "는 큐의 " + (i+1) + "번째 데이터이고, 배열의 " + index + "인덱스에 있습니다.");
				return;
			}
		}
		System.out.println("찾는 값이 없습니다.");
	}
	
	public void dump() //큐에 저장중인 모든 데이터 출력
	{
		if(!isEmpty())
		{
			for(int i = 0; i < num; ++i)System.out.println(i+1 + "번째 데이터 : " + que[(i + front) % max]);
		}
		else System.out.println("큐가 비어있습니다.");
	}
}

실행 예제

import java.util.Scanner;
public class Main2{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("큐 용량 입력 : ");
		int command = sc.nextInt();
		IntQueue que = new IntQueue(command);
		while(true)
		{
			System.out.println();
			System.out.println("현재 데이터 수 : " + que.size() + "/" + que.capacity());
			System.out.println("(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit");
			System.out.print("cmd : ");
			command = sc.nextInt();
			if(command == 1)
			{
				System.out.print("value : ");
				command = sc.nextInt();
				que.enque(command);
			}
			else if(command == 2) que.deque();
			else if(command == 3)
			{
				System.out.print("Data for Search: ");
				command = sc.nextInt();
				que.indexOf(command);
			}
			else if(command == 4) que.peek();
			else if(command == 5) que.dump();
			else if(command == 6) que.clear();
			else if(command == 7) System.exit(0);
			else continue;
		}
	}
}
/*
큐 용량 입력 : 5

현재 데이터 수 : 0/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 1

현재 데이터 수 : 1/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 2

현재 데이터 수 : 2/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 3

현재 데이터 수 : 3/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 4

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 5

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 3/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 6

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 7

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 5
1번째 데이터 : 3
2번째 데이터 : 4
3번째 데이터 : 5
4번째 데이터 : 6
5번째 데이터 : 7

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 3
Data for Search: 5
5는 큐의 3번째 데이터이고, 배열의 4인덱스에 있습니다.

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 3/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 2/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 8

현재 데이터 수 : 3/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 9

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 1
value : 10

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 5
1번째 데이터 : 6
2번째 데이터 : 7
3번째 데이터 : 8
4번째 데이터 : 9
5번째 데이터 : 10

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 22

현재 데이터 수 : 5/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 4/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 3/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 2/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 1/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2

현재 데이터 수 : 0/5
(1)inqueue (2)dequeue (3)search (4)peek (5)dump (6)clear (7)exit
cmd : 2
이미 큐가 비어있습니다.
*/

링 버퍼의 활용

링 버퍼는 오래된 데이터를 버리는 용도로 사용할 수 있다.

예를 들면 요소의 개수가 n개인 배열에서 계속해서 데이터가 입력될 때 가장 최근에 들어온 데이터 n개만 저장하고 오래된 데이터는 버리는 용도로 사용한다.

예제
아래의 예제는 배열 a의 길이는 10이다. 인큐는 무한히 할 수 있지만, 배열에 저장되는 데이터는 가장 최근에 입력한 10개의 데이터만 링 버퍼에 남아있다.

import java.util.Scanner;
// 원하는 개수만큼 값을 입력 받아 요솟수 N인 배열에 마지막 N개를 저장

class LastNElements {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		final int N = 10;
		int[] a = new int[N];		// 입력 받은 값을 저장
		int cnt = 0;				// 입력 받은 개수
		int retry;					// 다시 한 번?

		System.out.println("정수를 입력하세요.");

		do {
			System.out.printf("%d번째 정수：", cnt + 1);
			a[cnt++ % N] = stdIn.nextInt();

			System.out.print("계속 할까요? (예.1／아니오.0）：");
			retry = stdIn.nextInt();
		} while (retry == 1);

		int i = cnt - N;
		if (i < 0) i = 0;

		for ( ; i < cnt; i++)
			System.out.printf("%2d번째의 정수 ＝ %d\n", i + 1, a[i % N]);
	}
}​

데크(deque)

deque(Double Ended Queue)는 인큐와 디큐가 배열의 양쪽 끝에서 모두 발생할 수 있는 자료구조이다.

즉, 큐의 양끝이 front이면서, rear인 형태인 것이다.

이러한 특성 때문에 데이터의 삽입과 삭제의 자유도가 높다.

Stack과 Queue의 장점만 모아서 구성한 자료구조이다.

int형 배열을 이용한 IntDeque 클래스

public class IntDeque {
	private int max; //큐 용량
	private int num; //현재 데이터 수
	private int front; //디큐를 할 인덱스를 가리킴
	private int rear; //인큐를 할 인덱스를 가리킴
	private int[] que;
	
	IntDeque(int capacity) //생성자
	{
		this.max = capacity;
		num = front = rear = 0;
		que = new int[max];
	}
	
	private boolean isEmpty() {return num <= 0;} //큐가 비어있는지를 리턴
	
	private boolean isFull() {return num >= max;} //큐의 공간이 모두 사용중인지 리턴
	
	public int capacity() {return max;} //큐의 용량을 리턴
	
	public int size() {return num;} //큐가 현재 사용중인 공간을 리턴
	
	public void clear() {num = front = rear = 0;} //큐 초기화
	
	public void enque(int value)
	{
		if(!isFull())
		{
			que[rear++] = value;
			++num;
			if(rear == max) rear = 0;
		}
		else
		{
			System.out.println("큐의 모든 공간이 사용중입니다.");
		}
		return;
	}
	
	public void enqueFront(int value)
	{
		if(!isFull())
		{
			if(--front < 0) front = max -1;
			que[front] = value;
			++num;
			if(rear == max) rear = 0;
		}
		else
		{
			System.out.println("큐의 모든 공간이 사용중입니다.");
		}
		return;
	}
	
	public void deque()
	{
		if(!isEmpty())
		{
			que[front++] = 0;
			--num;
			if(front == max) front = 0;
			return;
		}
		else
		{
			System.out.println("이미 큐가 비어있습니다.");
			return;
		}
	}
	
	public void dequeRear()
	{
		if(!isEmpty())
		{
			if(--rear < 0) rear = max -1;
			que[rear] = 0;
			--num;
			return;
		}
		else
		{
			System.out.println("이미 큐가 비어있습니다.");
			return;
		}
	}
	
	public void peek() //front를 출력
	{
		if(!isEmpty()) System.out.println(que[front]);
		else System.out.println("큐가 비어있습니다.");
	}
	
	public void peekRear() //front를 출력
	{
		if(!isEmpty())
		{
			if(rear == 0) System.out.println(que[max -1]);
			else System.out.println(que[rear -1]);
		}
		else System.out.println("큐가 비어있습니다.");
	}
	
	public void indexOf(int value) //값이 배열에 존재하는지와 몇 번째 데이터인지, 배열의 몇 번째 인덱스인지 출력
	{
		for(int i = 0; i < num; ++i)
		{
			int index = (i + front) % max;
			if(que[index] == value)
			{
				System.out.println(value + "는 큐의 " + (i+1) + "번째 데이터이고, 배열의 " + index + "인덱스에 있습니다.");
				return;
			}
		}
		System.out.println("찾는 값이 없습니다.");
	}
	
	public void dump() //큐에 저장중인 모든 데이터 출력
	{
		if(!isEmpty())
		{
			for(int i = 0; i < num; ++i)System.out.println(i+1 + "번째 데이터 : " + que[(i + front) % max]);
		}
		else System.out.println("큐가 비어있습니다.");
	}
}

실행 예제

import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("큐 용량 입력 : ");
		int command = sc.nextInt();
		IntDeque que = new IntDeque(command);
		while(true)
		{
			System.out.println();
			System.out.println("현재 데이터 수 : " + que.size() + "/" + que.capacity());
			System.out.println("(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit");
			System.out.print("cmd : ");
			command = sc.nextInt();
			if(command == 1)
			{
				System.out.print("value : ");
				command = sc.nextInt();
				que.enque(command);
			}
			else if(command ==2)
			{
				System.out.print("value : ");
				command = sc.nextInt();
				que.enqueFront(command);
			}
			else if(command == 3) que.deque();
			else if(command == 4) que.dequeRear();
			else if(command == 5)
			{
				System.out.print("Data for Search: ");
				command = sc.nextInt();
				que.indexOf(command);
			}
			else if(command == 6) que.peek();
			else if(command == 7) que.peekRear();
			else if(command == 8) que.dump();
			else if(command == 9) que.clear();
			else if(command == 10) System.exit(0);
			else continue;
		}
	}
}
/*
큐 용량 입력 : 5

현재 데이터 수 : 0/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 1
value : 1

현재 데이터 수 : 1/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 1
value : 2

현재 데이터 수 : 2/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 1
value : 3

현재 데이터 수 : 3/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 2
value : 5

현재 데이터 수 : 4/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 2
value : 4

현재 데이터 수 : 5/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 8
1번째 데이터 : 4
2번째 데이터 : 5
3번째 데이터 : 1
4번째 데이터 : 2
5번째 데이터 : 3

현재 데이터 수 : 5/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 5
Data for Search: 3
3는 큐의 5번째 데이터이고, 배열의 2인덱스에 있습니다.

현재 데이터 수 : 5/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 4

현재 데이터 수 : 4/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 4

현재 데이터 수 : 3/5
(1)enque (2)enqueFront (3)deque (4)dequeRear (5)search (6)peek (7)peekRear (8)dump (9)clear (10)exit
cmd : 8
1번째 데이터 : 4
2번째 데이터 : 5
3번째 데이터 : 1
 */

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

스택

스택은 데이터를 일시적으로 저장하기 위한 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.

데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out)이다. 스택에 데이터를 넣는 작업을 푸시라 하고, 스택에서 데이터를 꺼내는 작업을 팝이라고 한다.

이렇게 푸시와 팝을 하는 위치를 꼭대기(top)라 하고, 스택의 가장 아랫부분을 바닥(bottom)이라고 한다.

int 배열을 이용한 IntStack 클래스

public class IntStack {
	private int max;
	private int ptr;
	private int []stk;
	
	public IntStack(int capacity) //생성자
	{
		max = capacity;
		ptr = 0;
		stk = new int[max];
	}
	
	private boolean isFull() {return ptr >= max;} //스택이 용량이 남아있는지 리턴
	
	private boolean isEmpty() {return ptr <= 0;} //스택 비어있는지 리턴
	
	public void push(int value)
	{
		if(!isFull()) stk[ptr++] = value;
		else System.out.println("스택의 남은 용량이 없습니다.");
		
	}
	
	public void pop()
	{
		if(!isEmpty()) --ptr;
		else System.out.println("이미 스택이 비어있습니다.");
	}
	
	public void peek() //스택의 꼭대기 값을 출력
	{
		if(!isEmpty()) System.out.println(stk[ptr-1]);
		else System.out.println("스택이 비어있습니다.");
	}
	
	public void indexOf(int value) //스택에서 원하는 값을 검색
	{
		for(int i = ptr -1; i >= 0; --i) 
			{
				if(stk[i] == value)
				{
					System.out.println("찾는 값이 있습니다. 인덱스 : " + i);
					return;
				}
			}
		System.out.println("찾는 값이 없습니다.");
	}
	
	public void clear() {ptr = 0;} //ptr을 0으로 바꿔줌으로서 스택에 쌓인 데이터가 0으로 인식
	
	public int capacity() {return max;} //스택의 최대용량 리턴
	
	public int size() {return ptr;} //데이터 수를 확인 하는 메소드
	
	public void dump() //스택 안에 있는 모든 데이터를 표시하는 메소드
	{
		if(isEmpty())
		{
			System.out.println("스택이 비어있습니다.");
			return;
		}
		
		for (int i = 0; i < ptr; ++i)
		{
			System.out.println("[" + i + "]" + "=" + stk[i]);
		}
	}
	
}

실행 예제

import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("스택 용량 입력 : ");
		int command = sc.nextInt();
		IntStack stk = new IntStack(command);
		while(true)
		{
			System.out.println("현재 데이터 수 : " + stk.size() + "/" + stk.capacity());
			System.out.println("(1) push (2)pop (3)search (4)peek (5)dump (6)exit");
			System.out.print("cmd : ");
			command = sc.nextInt();
			if(command == 1)
			{
				System.out.print("value : ");
				command = sc.nextInt();
				stk.push(command);
			}
			else if(command == 2) stk.pop();
			else if(command == 3)
			{
				System.out.print("Data for Search: ");
				command = sc.nextInt();
				stk.indexOf(command);
			}
			else if(command == 4) stk.peek();
			else if(command == 5) stk.dump();
			else if(command == 6) System.exit(0);
			else continue;
		}
	}
}

양쪽 스택

배열을 공유하여 2개의 스택을 구현하는 int형 스택 클래스를 작성

(스택에 저장하는 데이터는 int형 값으로 아래 그림처럼 배열의 처음과 끝을 사용)

IntStackX 클래스

public class IntStackX{
	private int max;
	private int Aptr;
	private int Bptr;
	private int []stk;
	
	public enum AB{A, B}; //열거 타입
	
	public IntStackX(int capacity) //생성자
	{
		max = capacity;
		stk = new int[max];
		Aptr = 0;
		Bptr = stk.length -1;
	}
	
	private boolean isFull() {return Aptr >= Bptr +1;}
		
	
	private boolean isEmpty(AB ab) {
		switch (ab)
		{
		case A:
			return Aptr <= 0;
		case B:
			return Bptr >= max-1;
		}
		return true;
	}
	
	public void push(int value, AB ab)
	{
		if(!isFull())
		{
			switch(ab)
			{
			case A:
				stk[Aptr++] = value;
				break;
			case B:
				stk[Bptr--] = value;
				break;
			}
		}
		else
		{
			System.out.println("스택이 모두 사용중입니다.");
			return;
		}
	}
	
	public void pop(AB ab)
	{
		if(!isEmpty(ab))
		{
			switch(ab)
			{
			case A:
				stk[--Aptr] = 0;
				return;
			case B:
				stk[++Bptr] = 0;
				return;
			}
		}
		else
		{
			System.out.println("스택이 이미 비어있습니다.");
			return;
		}
	}
	
	public void peek(AB ab) //스택의 꼭대기 값을 출력
	{
		if(!isEmpty(ab))
		{
			switch(ab)
			{
			case A:
				System.out.println("Top Data : " + stk[Aptr -1]);
				return;
			case B:
				System.out.println("Top Data : " + stk[Bptr +1]);
				return;
			}
		}
		else
		{
			System.out.println("스택이 이미 비어있습니다.");
			return;
		}
	}
	
	public void indexOf(int value, AB ab) //스택에서 원하는 값을 검색
	{
		switch(ab)
		{
		case A:
			for(int i = Aptr -1; i >= 0; --i)
			{
				if(stk[i] == value) System.out.println("찾는 값이 있습니다. 인덱스 : " + i);
			}
			return;
		case B:
			for(int i = Bptr +1; i < max; ++i)
			{
				if(stk[i] == value) System.out.println("찾는 값이 있습니다. 인덱스 : " + i);
			}
			return;
		}
		System.out.println("찾는 값이 없습니다.");
	}
	
	public void clear(AB ab)
	{
		switch(ab)
		{
		case A:
			Aptr = 0;
			System.out.println("A스택이 초기화 되었습니다.");
			break;
		case B:
			Bptr = max -1;
			System.out.println("B스택이 초기화 되었습니다.");
			break;
		}
	}
	
	public int capacity() {return max;} //스택의 최대용량 리턴
	
	public int size(AB ab)
	{
		switch(ab)
		{
		case A: return Aptr;
		case B: return max - Bptr -1;
		}
	return 0;
	}
	
	public void dump(AB ab) //스택 안에 있는 모든 데이터를 표시하는 메소드
	{
		if(isEmpty(ab))
		{
			System.out.println("스택이 비어있습니다.");
			return;
		}
		else
		{
			switch(ab)
			{
			case A:
				for (int i = 0; i < Aptr; ++i) System.out.println("[" + i + "]" + "=" + stk[i]);
				return;
			case B:
				for (int i = max -1; i > Bptr; --i) System.out.println("[" + i + "]" + "=" + stk[i]);
				return;
			}
		}
	}
	
}

실행 예제

import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("스택 용량 입력 : ");
		int command = sc.nextInt();
		IntStackX stk = new IntStackX(command);
		IntStackX.AB AB = IntStackX.AB.A;
		while(true)
		{
			if(AB == IntStackX.AB.A) {System.out.println("Stack A, 현재 데이터 수 : " + stk.size(AB) + "/" + (stk.capacity() - stk.size(IntStackX.AB.B)));}
			else {System.out.println("Stack B, 현재 데이터 수 : " + stk.size(AB) + "/" + (stk.capacity() - stk.size(IntStackX.AB.A)));}
			System.out.println("(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)exit");
			System.out.print("cmd : ");
			command = sc.nextInt();
			if(command == 0) AB = IntStackX.AB.B;
			else if(command == 1)
			{
				System.out.print("value : ");
				command = sc.nextInt();
				stk.push(command, AB);
			}
			else if(command == 2) stk.pop(AB);
			else if(command == 3)
			{
				System.out.print("Data for Search: ");
				command = sc.nextInt();
				stk.indexOf(command,AB);
			}
			else if(command == 4) stk.peek(AB);
			else if(command == 5) stk.dump(AB);
			else if(command == 6) stk.clear(AB);
			else if(command == 7) System.exit(0);
			else continue;
		}
	}
}
/*
 스택 용량 입력 : 10
Stack A, 현재 데이터 수 : 0/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 1
Stack A, 현재 데이터 수 : 1/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 2
Stack A, 현재 데이터 수 : 2/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 3
Stack A, 현재 데이터 수 : 3/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 4
Stack A, 현재 데이터 수 : 4/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 5
Stack A, 현재 데이터 수 : 5/10
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 0
Stack B, 현재 데이터 수 : 0/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 1
Stack B, 현재 데이터 수 : 1/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 2
Stack B, 현재 데이터 수 : 2/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 3
Stack B, 현재 데이터 수 : 3/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 4
Stack B, 현재 데이터 수 : 4/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 5
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 5
[9]=1
[8]=2
[7]=3
[6]=4
[5]=5
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 6
스택이 모두 사용중입니다.
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 0
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 1
value : 6
스택이 모두 사용중입니다.
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 5
[9]=1
[8]=2
[7]=3
[6]=4
[5]=5
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 3
Data for Search: 5
찾는 값이 있습니다. 인덱스 : 5
Stack B, 현재 데이터 수 : 5/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 2
Stack B, 현재 데이터 수 : 4/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 2
Stack B, 현재 데이터 수 : 3/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 5
[9]=1
[8]=2
[7]=3
Stack B, 현재 데이터 수 : 3/5
(0)change AB (1) push (2)pop (3)search (4)peek (5)dump (6)clear (7)
cmd : 
 */

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

클래스 배열이란 클래스로 부터 만들어진 객체로 이루어진 배열을 뜻한다.

클래스 자체가 자료형이되어서 데이터를 더 쉽게 다룰 수 있다.

아래는 이름, 키, 시력을 저장하는 클래스의 객체로 이루어진 배열을 활용하여

평균 키와 시력 분포를 출력하는 예제 코드이다.

public class Main{
	static class PhyscData { //이름, 키, 시력을 저장하는 클래스
		String name;
		int    height;
		double vision;

		PhyscData(String name, int height, double vision) { //생성자
			this.name 	= name;
			this.height = height;
			this.vision = vision;
		}
	}

	static double aveHeight(PhyscData[] arr) { //평균 키를 리턴하는 메소드
		double sum = 0;

		for (int i = 0; i < arr.length; i++)
			sum += arr[i].height;

		return sum / arr.length;
	}

	static void distVision(PhyscData[] arr) { //시력 분포를 출력하는 메소드
		int[] distribution = new int[5];
		for (int i = 0; i < arr.length; i++)
		{
			if(0.0 <= arr[i].vision && arr[i].vision < 0.5) ++distribution[0];
			else if(arr[i].vision < 1.0) ++distribution[1];
			else if(arr[i].vision < 1.5) ++distribution[2];
			else if(arr[i].vision < 2.0) ++distribution[3];
			else if(2.0 <= arr[i].vision) ++distribution[4];
		}
		
			System.out.println("0.5 미만 " + distribution[0] + "명");
			System.out.println("1.0 미만 " + distribution[1] + "명");
			System.out.println("1.5 미만 " + distribution[2] + "명");
			System.out.println("2.0 미만 " + distribution[3] + "명");
			System.out.println("2.0 이상 " + distribution[4] + "명");
	}
	
	public static void main(String[] args) {
			PhyscData[] arr = { //PhyscData타입 객체를 저장하는 배열
			new PhyscData("박현규", 162, 0.3),
			new PhyscData("함진아", 173, 0.7),
			new PhyscData("최윤미", 175, 2.0),
			new PhyscData("홍연의", 171, 1.5),
			new PhyscData("이수진", 168, 0.4),
			new PhyscData("김영준", 174, 1.2),
			new PhyscData("박용규", 169, 0.8),
		};
		System.out.println("이름\t키\t시력");
		for(int i = 0; i < arr.length; ++i) System.out.println(arr[i].name + "\t" + arr[i].height + "\t" + arr[i].vision);
		System.out.printf("평균 키 : %.2fCM\n", aveHeight(arr));

		distVision(arr);

	}
}
/*
이름	키	시력
박현규	162	0.3
함진아	173	0.7
최윤미	175	2.0
홍연의	171	1.5
이수진	168	0.4
김영준	174	1.2
박용규	169	0.8
평균 키 : 170.29CM
0.5 미만 2명
1.0 미만 2명
1.5 미만 1명
2.0 미만 1명
2.0 이상 1명
*/

시력 분포를 위 사진처럼 기호 문자 *를 사람 수만큼 반복하여 출력

static void distVision(PhyscData[] arr) { //시력 분포를 출력하는 메소드
    int[] distribution = new int[5];
    for (int i = 0; i < arr.length; i++)
    {
        if(0.0 <= arr[i].vision && arr[i].vision < 0.5) ++distribution[0];
        else if(arr[i].vision < 1.0) ++distribution[1];
        else if(arr[i].vision < 1.5) ++distribution[2];
        else if(arr[i].vision < 2.0) ++distribution[3];
        else if(2.0 <= arr[i].vision) ++distribution[4];
    }

    for(int i = 0; i < distribution.length; ++i)
    {
        if(i == 0) System.out.print("0.5 미만 : ");
        else if(i == 1) System.out.print("1.0 미만 : ");
        else if(i == 2) System.out.print("1.5 미만 : ");
        else if(i == 3) System.out.print("2.0 미만 : ");
        else if(i == 4) System.out.print("2.0 이상 : ");
        for(int j = 0; j < distribution[i]; ++j)
        {
            System.out.print("*");
        }
        System.out.println();
    }
}