datastructure (2)

 

 

 

 

 

❑ Binary Search Tree(이진 검색 트리)

 

 

모든 노드의 자식 노드가 단 두 개 뿐인 트리

오른쪽, 왼쪽 자식 두 개만 존재

왼쪽, 오른쪽 자식을 구분

한 쪽만 있거나 둘다 없는 노드가 있어도 됨

모든 왼쪽 자식의 값이 루트나 부모보다 작고, 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다

 

 

➤ 이진 트리 종류

 

이진 트리의 종류

 

완전 이진 트리(Complete binary tree)

  • 마지막 레벨을 제외한 레벨은 노드를 빠짐없이 가득 채워야 한다
  • 마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드를 빠짐없이 채우되 반드시 끝까지 채울 필요는 없다
  • 마지막 레벨의 왼쪽은 채워져 있어야 한다

 

정 이진 트리(Full binary tree)

  • 각 노드가 0개 혹은 2개의 자식 노드를 가짐

 

포화 이진 트리(Perfect binary tree)

  • 완전 이진 트리이면서 정 이진 트리인 이진 트리
  • 모든 리프의 레벨이 같다
  • 모든 레벨이 가득 차 있다

포화 이진 트리

 

 

 

 

❑ BFS/DFS

 

 

➤ 너비 우선 탐색(BFS, breadth-first search)

 

너비 우선 탐색

 

1. 낮은 레벨부터 왼쪽에서 오른쪽 방향으로 탐색하고

2. 한 레벨의 탐색이 끝나면 다음 레벨로 내려감

이 과정을 반복

 

 

➤ 깊이 우선 탐색(DFS, depth-first search)

 

깊이 우선 탐색

 

리프에 도달할 때까지 아래로 내려가면서 탐색

더 이상 탐색할 곳이 없으면 부모에게 돌아감

그런 다음 다시 자식 노드로 내려감

자식 노드가 2개 있을 때 부모 노드를 총 3번 거쳐가는데 언제 부모 노드의 값을 탐색할지는 3가지 방법이 있다.

예를 들어 D, H, I에서

전위 순회(preorder)는 부모 노드를 먼저 탐색한다.

D -> H -> I

중위 순회(inorder)는 부모 노드를 중간에 탐색한다.

H -> D -> I

후위 순회(postorder)는 부모 노드를 마지막에 탐색한다.

H -> I -> D

 

 

 

 

 

선배적 참견시점(선참시)

 

면접에서 반드시 물어보는 질문

어떤 어려움을 겪었고 어떻게 해결했는가!

자기가 블로그에 쓴 글에 대한 질문에 답변을 못하면 안된다

동기들과 함께 한다는 마음으로 응원도 많이 하고 소통 활발히 하자

선참시

좋은 리프레쉬 시간이었다.

 

 

 

그외) 배열 깊은 복사 쉽게하기

 

Arrays.clone() 메소드 이용

arr2 = arr.clone();

 

 

 

 

정리해놓고 포스팅을 늦게 올렸다.. ㅇ.ㅇ

점점 게을러 지고 있는데 정신 차릴 필요가 있다. 😡

 

 

읽어주셔서 감사합니다.

오개념에 대한 지적은 언제나 환영입니다.😍

 

 

 

 

 

 

Stack

 

 

Queue

 

 

❑ 자료구조란?

 

여러 자료(데이터)를 다루는 구조

자료(데이터)란?

휴대폰 번호, 방문기록, 고객명단, 대기열 등 모든 것이 자료이다.

자료를 정리하는 방식은 자료의 형태마다 달라야한다.

만약에 규칙없이 저장하거나 하나의 구조만으로 저장하면 자료마다 활용하는 것이 불편하다.

자료를 효율적으로 정리하면 저장하고 활용하는데 있어서 훨씬 유리하게 된다.

 

자료를 효율적으로 정리하는 방법은 여러가지가 있다.

 

자료를 다루는 구조 그 자체를 뜻하고 구현하는 방식에는 제약이 없음

 

주로쓰는 자료구조 : stack, queue, graph, tree

 

❑ Stack?

 

FILO(First In Last Out) / LIFO(Last In First Out)

먼저 들어간놈이 나중에 나오고 나중에 들어간 놈이 먼저 나오는 자료 구조

출입구가 하나고 끝이 막힌 구조를 생각하면 된다.

 

 

자바에서 Stack을 배열로 구현해보기

더보기

Doit! 자료구조와 함께 배우는 알고리즘 입문(자바편)에서 참고해서 작성하였다.

 

package stack;

public class IntStack {
    private int[] stk;  // 스택용 배열
    private int capacity;   // 스택 용량
    private  int ptr;   // 스택 포인터

    // 실행시 예외: 스택이 비어있음
    public class EmptyIntStackException extends RuntimeException {
        public EmptyIntStackException(){};
    }

    // 실행시 예외: 스택이 가득 참
    public class OverflowIntStackException extends RuntimeException {
        public OverflowIntStackException(){};
    }

    // 생성자
    public IntStack(int maxlen) {
        ptr = 0;
        capacity = maxlen;
        try {
            stk = new int[capacity];
        } catch (OutOfMemoryError e) {
            capacity = 0;
        }
    }

    // 스택에 x push
    public int push(int x) throws OverflowIntStackException {
        if(ptr >= capacity) {
            throw new OverflowIntStackException();
        }
        return stk[ptr++] = x;
    }

    // 스택에서 데이터를 pop
    public int pop() throws EmptyIntStackException {
        if(ptr <= 0) {
            throw new EmptyIntStackException();
        }
        return stk[--ptr];
    }

    // 스택에서 데이터를 peek
    public int peek() throws EmptyIntStackException {
        if(ptr <= 0) {
            throw new EmptyIntStackException();
        }
        return stk[ptr - 1];
    }

    // 스택을 비움
    public void clear() {
        ptr = 0;
    }

    // 스택에서 x를 찾아 인덱스(없으면 -1)을 반환
    public int indexOf(int x) {
        for(int i = ptr - 1; i >= 0; i--) {
            if (stk[i] == x)
                return i;
        }
        return -1;
    }

    // 스택의 용량 반환
    public int getCapacity() {
        return capacity;
    }

    // 스택에 쌓여 있는 데이터 개수를 반환
    public int size() {
        return ptr;
    }

    // 스택이 비어있는가?
    public boolean isEmpty() {
        return ptr <= 0;
//        return ptr == 0; 으로도 가능
    }

    // 스택이 가득 찼는가?
    public boolean isFull() {
        return ptr >= capacity;
    }

    // 스택 안의 모든 데이터를 bottom-> top 순서로 출력
    public void dump() {
        if(ptr <= 0) {
            System.out.println("Stack is Empty!");
        }
        else {
            for(int i = 0; i < ptr; i++)
                System.out.print(stk[i]+ " ");
            System.out.println();
        }
    }
}

 

 

테스트할 코드도 구현해보았다.

package stack;

import java.util.Scanner;

public class IntStackTester {
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        IntStack s = new IntStack(64);

        while(true) {
            System.out.println();
            System.out.printf("present data count: %d / %d\n", s.size(), s.getCapacity());
            System.out.print("(1)push (2)pop (3)peek (4)dump (5)clear (6)getCapacity (7)indexOf (8)isFull (0)exit  : ");

            int menu = stdIn.nextInt();

            if(menu == 0) break;    //exit

            int x;
            switch(menu) {
                case 1 :    // push
                    System.out.print("데이터: ");
                    x = stdIn.nextInt();
                    try {
                        s.push(x);
                    }catch (IntStack.OverflowIntStackException e) {
                        System.out.println("Stack is full!!");
                    }
                    break;
                case 2:     // pop
                    try {
                        x = s.pop();
                        System.out.println("pop data is " + x + ".");
                    } catch (IntStack.EmptyIntStackException e) {
                        System.out.println("Stack is Empty!!");
                    }
                    break;
                case 3:     // peek
                    try {
                        x = s.peek();
                        System.out.println("peek data is " + x + ".");
                    } catch (IntStack.EmptyIntStackException e) {
                        System.out.println("Stack is Empty!!");
                    }
                    break;
                case 4:     // dump
                    s.dump();
                    break;
                case 5:     // clear
                    s.clear();
                    break;
                case 6:     // getCapacity
                    System.out.println("Capacity : " + s.getCapacity());
                    break;
                case 7:     //indexOf
                    System.out.print("input you want to find : ");
                    x = stdIn.nextInt();
                    System.out.println(x + " is in " + s.indexOf(x));
                    break;
                case 8:
                    System.out.println("Stack is Full? " + s.isFull());
                    break;
            }

        }
    }
}

 

 

자바에서는 Stack 자료구조가 클래스로 이미 지원되고 있다.

여러가지 메소드들을 이용해서 효과적으로 관리할수 있다.

  • push : 데이터를 넣는다.
  • pop : 데이터를 꺼낸다.
  • peek : 스택의 꼭대기에 있는 요소를 반환한다.
  • empty : 스택이 비었는지 확인한다.
  • search : 찾고자 하는 요소가 꼭대기부터 맨 처음으로 등장하는 index를 반환한다.

 

 

 

❑ Queue?

 

FIFO / LILO

먼저 들어간 놈이 먼저 나온다

줄 서서 기다리는 것을 이미지하면 된다.

은행이나 마트에서 줄서서 기다리면 먼저 온 사람 먼저 처리해준다

인큐 : 큐안에 들어옴

디큐 : 큐안에서 나감

 

자바에서 배열로 구현한 Queue..작성중..

 

 

➤ 현실적인 예시

 

문서를 출력하면 문서가 들어간 순서대로 인쇄 된다.

컴퓨터(출력버튼)-(임시기억장치)Queue에 하나씩 들어옴 - Queue에 들어온 순서대로 문서 인쇄

인쇄할 때 CPU가 인쇄 데이터를 보내는 속도가 프린터가 인쇄하는 속도보다 빠르기 때문에 인쇄 데이터를 잠시 보관할 임시저장공간이 필요하다.

만약에 CPU가 프린터가 하나씩 인쇄 되는것을 기다렸다가 데이터를 전송하면 CPU가 그 시간동안 다른일을 처리하지 못하기 때문에 비효율적이다.

컴퓨터 장치간에 데이터를 주고받을 때 장치 사이 속도가 존재한다.

시간차이나 속도차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용

-> 버퍼(Buffer) 라고 함

 

 

 

 

 

읽어주셔서 감사합니다.😍

오개념에 대한 지적은 언제나 환영입니다.

 

 

 

1