'전체 글'에 해당되는 글 120건

  1. 2019.03.04 이진검색트리 (Binary Search Tree) (정리중,,,,,,)
  2. 2019.03.03 큐(Queue) 개념 및 사용법 정리
  3. 2019.03.03 [BOJ]10828. 스택

이진검색트리 (Binary Search Tree) (정리중,,,,,,)

자료구조
posted by 귀염둥이채원 2019. 3. 4. 18:20

# 이진검색트리 (Binary Search Tree) 개념

- 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조

- 데이터는 정렬이 되어 있어야하며, 탐색 작업에 효율적

- 한 노드에 자식이 최대 2개까지만 존재할 수 있는 트리


1. 모든 노드의 키는 유일하다. 

  - 중복된 데이터를 갖는 노드가 없다는 뜻이다. 

  - 여기서 키의 의미는 노드 안에 들어 있는 데이터 값을 의미한다.


2. 왼쪽 서브 트리의 키들은 루트의  키보다 작다. 

  - 예를 들어 루트노드의 데이터가 5라고 하면, 왼쪽 서브트리에는 무조건 5보다 작은 값들만 존재해야 한다.


3. 오른쪽 서브 트리의 키들은 루트의 키보다 크다.  

  - 위와 같은 원리로 오른쪽에는 루트의 데이터 값보다 더 큰 값들만 존재한다.

4. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 

  - 순환적으로 정의되었다는 뜻이다.

  - 즉 왼쪽 서브트리로 내려가든, 오른쪽 서브트리로 내려가든 동일한 법칙이 적용된다는 뜻이다.


# 이진검색트리 (Binary Search Tree) 예시

- 전화번호부에서 전화번호를 찾거나 

- 서점에서 책을 찾거나 

- 지도에서 목적지를 찾는것


# 이진검색트리 (Binary Search Tree) 목적

- 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logn)으로 빠르지만 자료 입력, 삭제가 불가능합니다.

- 연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 O(1)로 효율적이지만 

  탐색하는 데에는 O(n)의 계산복잡성이 발생합니다.

- 이진탐색트리 핵심 연산인 탐색, 삽입, 삭제의 계산복잡성은 모두 O(h) 입니다.


# 이진검색트리 (Binary Search Tree) 용어

successor: 삭제 대상 노드의 오른쪽 서브트리 가운데 최소값

redecessor: 삭제 대상 노드의 왼쪽 서브트리 가운데 최대값


# 시간복잡도 정리

삽입, 삭제, 탐색 모두 최선의 경우(트리의 균형이 잘 잡혀있는 경우, 즉, 왼쪽 오른쪽 자식이 잘 분배되어 있는 경우) O(logN)의 시간복잡도를 가지고, 최악의 경우 (자식 노드가 한쪽으로 쏠려 있는 경우) O(N)이다.

최악의 경우에는 경우에는 균형잡힌 이진 검색트리(balanced binary search tree)으로 사용하면 좋다.


# Binary Searh Tree의 3가지 순회방법

참고 강의: https://www.youtube.com/watch?v=QN1rZYX6QaA&index=2&list=PLjSkJdbr_gFY8VgactUs6_Jc9Ke8cPzZP

- Inorder (Left -> Root -> Right)

- Preorder (Root -> Left -> Right)

- Postorder (Left -> Right -> Root)


# 이진검색트리 (Binary Search Tree) 정리

- array와 비교시 tree는 add/remove 연산 속도가 빠르다.

- balanced binary search tree의 경우 insert/delete가 O(log N)이다. (자바에서 TreeMap으로 구현)


# 유투브 영상

https://www.youtube.com/watch?v=9ZZbA2iPjtM&t=3s

https://www.youtube.com/watch?v=9ZZbA2iPjtM&index=8&list=PLjSkJdbr_gFY8VgactUs6_Jc9Ke8cPzZP


# 참고사이트

★★https://kingpodo.tistory.com/29

★★http://ivis.kr/images/a/a5/2018_DS_ch09.pdf

★★https://songeunjung92.tistory.com/31

★★https://swalloow.tistory.com/35

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC

https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/

https://wkdtjsgur100.github.io/binary-search-tree/

https://mattlee.tistory.com/30

https://kka7.tistory.com/78

'자료구조' 카테고리의 다른 글

큐(Queue) 개념 및 사용법 정리  (0) 2019.03.03
스택(stack) 개념 및 사용법 정리  (0) 2019.03.03
배열 리스트(ArrayList) 개념 및 사용법  (0) 2019.03.03
자바 배열 사용법 정리  (0) 2019.03.03

큐(Queue) 개념 및 사용법 정리

자료구조
posted by 귀염둥이채원 2019. 3. 3. 22:41

# 큐(Queue)란?

- 먼저 삽입된 데이터가 가장 먼저 제거되는 선입선출(FIFO - First In First Out) 형태의 자료구조


# 큐(Queue) API

* Object element(): 저장된 요소를 불러옴

* boolean offer(Object o ): Queue에 객체 저장 ( true:성공, false:실패) 반환

* Object peek(): 저장된 객체를 반환 / 없을경우 Null 을 반환

* Object poll(): 객체를 꺼내온다 / 꺼낸객체는 사라짐


# 큐(Queue) 클래스 사용법

LinkedList 클래스로 Queue를 인스턴스화하여 사용

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
    static Queue <Integer> q;
    public static void main(String[] args) {
        // queue는 LinkedList 클래스로 선언한다.
        q = new LinkedList<Integer>();
        
        // queue 초기화
        q.clear();
        
        // queue에 데이터 1 삽입
        q.add(1);
        
        // queue에 데이터 5 삽입
        q.add(5);
        
        // queue의 size 출력
        System.out.println("queue size: " +q.size());
        
        // queue에서 데이터 확인 및 제거
        System.out.println("data(pool): " +q.poll());
        
        // queue에서 데이터 확인
        System.out.println("data(peek): " +q.peek());
        
        // queue에서 데이터 확인 및 제거
        System.out.println("data(pool): " +q.poll());
        
        // queue에 데이터가 존재하는지 확인
        if (q.isEmpty()) {
            System.out.println("queue is empty");
        }
    }
}
 
/*********** 결과 ***************
queue size: 2
data(pool): 1
data(peek): 5
data(pool): 5
queue is empty
*/
cs


# 큐(Queue) 구현 - 배열 사용

# 문제

주어진 N(2<= N <=100)개의 수를 순서대로 Queue에 넣은 후 하나씩 꺼내 화면에 출력


# 입력

2

5

1 2 3 4 5 

5 

5 4 2 3 1


# 출력

#1 1 2 3 4 5 

#2 5 4 2 3 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.io.FileInputStream;
import java.util.Scanner;
 
class Main2 {
    static final int MAX_N = 100;
 
    static int front;
    static int rear;
    static int queue[] = new int[MAX_N];
 
    static void queueInit() {
        front = 0;
        rear = 0;
    }
 
    static boolean queueIsEmpty() {
        return (front == rear);
    }
 
    static boolean queueIsFull() {
        if ((front + 1) % MAX_N == rear) {
            return true;
        } else {
            return false;
        }
    }
 
    static boolean queueEnqueue(int value) {
        if (queueIsFull()) {
            System.out.print("queue is full!");
            return false;
        }
        queue[front] = value;
        front++;
        if (front >= MAX_N) {
            front = MAX_N;
        }
 
        return true;
    }
 
    static Integer queueDequeue() {
        if (queueIsEmpty()) {
            System.out.print("queue is empty!");
            return null;
        }
 
        Integer value = new Integer(queue[rear]);
 
        rear++;
        if (rear >= MAX_N) {
            rear = MAX_N;
        }
        return value;
    }
 
    public static void main(String arg[]) throws Exception {
        //System.setIn(new FileInputStream("c:\\boj\\sample.txt"));
        Scanner sc = new Scanner(System.in);
 
        int T = sc.nextInt();
 
        for (int test_case = 1; test_case <= T; test_case++) {
            int N = sc.nextInt();
 
            queueInit();
            for (int i = 0; i < N; i++) {
                int value = sc.nextInt();
                queueEnqueue(value);
            }
 
            System.out.print("#" + test_case + " ");
 
            while (!queueIsEmpty()) {
                Integer value = queueDequeue();
                if (value != null) {
                    System.out.print(value.intValue() + " ");
                }
            }
            System.out.println();
        }
        sc.close();
    }
}
cs


# 참고사이트

https://hyeonstorage.tistory.com/263

https://swalloow.tistory.com/32

https://gamjatwigim.tistory.com/72

'자료구조' 카테고리의 다른 글

이진검색트리 (Binary Search Tree) (정리중,,,,,,)  (0) 2019.03.04
스택(stack) 개념 및 사용법 정리  (0) 2019.03.03
배열 리스트(ArrayList) 개념 및 사용법  (0) 2019.03.03
자바 배열 사용법 정리  (0) 2019.03.03

[BOJ]10828. 스택

PS(Problem Solving)/Stack
posted by 귀염둥이채원 2019. 3. 3. 22:10

# 문제링크

https://www.acmicpc.net/problem/10828


# 문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.


명령은 총 다섯 가지이다.

push X: 정수 X를 스택에 넣는 연산이다.

pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

size: 스택에 들어있는 정수의 개수를 출력한다.

empty: 스택이 비어있으면 1, 아니면 0을 출력한다.

top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.


# 풀이1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;
 
public class Main {
    static int N;
    static Stack <Integer> stk;
    
    static void func(String inputStr) {
        String strCommand[];
        if (inputStr.contains("push")) {
            strCommand = inputStr.split(" ");
            int number = Integer.parseInt(strCommand[1]);
            stk.push(number);
        }
        else if (inputStr.equals("pop")) {
            if (stk.size() > 0) {
                System.out.println(stk.pop());
            }
            else {
                System.out.println(-1);
            }
        }
        else if (inputStr.equals("size")) {
            System.out.println(stk.size());
        }
        else if (inputStr.equals("empty")) {
            if (stk.isEmpty()) {
                System.out.println(1);
            }
            else {
                System.out.println(0);
            }
        }
        else if (inputStr.equals("top")) {
            if (stk.isEmpty()) {
                System.out.println(-1);
            }
            else {
                System.out.println(stk.peek());
            }
        }
    }
    
    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(System.in);
 
        stk = new Stack <Integer>();
        stk.clear();
        
        N = sc.nextInt();
 
        for (int i=0; i<=N; i++) {
            func(sc.nextLine());
        }
        sc.close();
    }
}
cs


# 풀이2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    static int N;
    static Stack <Integer> stk;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        stk = new Stack <Integer>();
        stk.clear();
        
        N = Integer.parseInt(br.readLine());
        for (int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            switch (st.nextToken()) {
                case "push":
                    stk.push(Integer.parseInt(st.nextToken()));
                    break;
                case "pop":
                    if (stk.size() > 0) {
                        sb.append(stk.pop() + "\n");
                    }
                    else {
                        sb.append("-1" + "\n");
                    }
                    break;
                case "size":
                    sb.append(stk.size() + "\n");
                    break;
                case "empty":
                    if (stk.isEmpty()) {
                        sb.append(1 + "\n");
                    }
                    else {
                        sb.append(0 + "\n");
                    }
                    break;
                case "top":
                    if (stk.isEmpty()) {
                        sb.append(-1 + "\n");
                    }
                    else {
                        sb.append(stk.peek() + "\n");
                    }
                    break;
            }
        }
        
        System.out.println(sb);
    }
}
cs


# 회고

풀이 2에서 BufferedReader, StringBuilder를 사용해서 성능을 개선하였다.

(풀이1: 140ms, 풀이2: 436ms)


split 대신 StringTokenizer를 사용하여 문자열을 파싱함


# 풀이 참고

https://www.acmicpc.net/source/10582053

https://www.acmicpc.net/source/7385991

https://www.acmicpc.net/source/8726490

티스토리툴바