자료구조 (3)

TIL(Today I Learned)

5/30 (월) 자료구조-3️⃣ 이진트리, BFS/DFS

 

 

 

 

 

❑ 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();

 

 

 

 

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

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

 

 

읽어주셔서 감사합니다.

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

 

 

 

저작자표시

'TIL(Today I Learned)' 카테고리의 다른 글

6/7 (화) 네트워크-1️⃣ 브라우저의 작동 원리  (0) 2022.06.08
5/31 (화) 코딩 테스트 준비 - 1️⃣ 알고리즘, 의사코드, 시간복잡도(Big-O)  (0) 2022.06.01
5/27 (금) 자료구조 - 2️⃣ Tree 와 Graph  (0) 2022.05.29
5/26(목) 자료구조 - 1️⃣ Stack, Queue 스택과 큐  (0) 2022.05.26
Java 심화-2️⃣ 람다식, 스트림  (0) 2022.05.23
TIL(Today I Learned)

5/27 (금) 자료구조 - 2️⃣ Tree 와 Graph

 

 

 

Tree구조를 발이 아닌 손으로 그린 거다.

 

 

 

❑ Tree

 

➤ 데이터 사이의 계층 관계를 나타내느 자료구조

➤ 이름 그대로 나무 모양이다.

➤ 비선형 구조

 

 

※ 용어 정리

  • node(노드) : 가지로 연결되어 있는 하나하나의 요소
  • edge(가지) : 노드 사이를 연결
  • root(루트) : 트리의 가장 윗부분에 위치한 노드
  • leaf(리프) : 가장 아랫부분에 위치한 노드, 아래에 노드가 더 이상 없는 노드
  • 안쪽노드 : 리프를 제외한 나머지 노드(루트 포함)
  • child node(자식 노드) : 가지로 연결된 아래쪽 노드, 노드는 자식을 여러 개 가질 수 있습니다
  • parent node(부모 노드) : 가지로 연결된 윗쪽 노드, 자식 노드는 하나의 부모 노드만 가질 수 있습니다.
  • sibling(형제) : 같은 부모를 가진 노드
  • ancestor(조상) : 어떤 노드의 위쪽으로 뻗어 나간 모든 노드
  • descendant(자손) : 어떤 노드의 아래쪽으로 뻗어 나간 모든 노드
  • level(레벨) : 루트로부터 얼마나 떨어져 있는지를 나타낸 값, 루트는 레벨 0
  • degree(차수) : 노드가 갖는 자식의 수, 모든 노드의 차수가 n 이하인 트리를 'n진 트리'라고 함(위의 그림은 2진 트리)
  • height(높이) : 루트에서 가장 멀리 떨어진 노드까지의 거리(리프 레벨의 최댓값)
  • subtree(서브트리) : 트리 안에서 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리
  • null tree(널 트리) : 노드가 전혀 없는 트리

 

 

 

▶️ 순서 트리(Ordered tree)와 무순서 트리(Unordered tree)

 

형제 노드의 순서를 따지면 순서트리

형제 노드의 순서를 따지지 않으면 무순서 트리

 

 

 

▶️ 트리 = 상속

 

트리 관계를 보니까 자바의 상속이 떠오른다.

아무래도 모양이 상속관계랑 똑같은 것 같다.

상속에서 자식 클래스는 하나의 부모 클래스만 가질 수 있고

부모 클래스는 여러 자식 클래스를 가질 수 있다.

트리에서도 하나의 노드는 하나의 부모만 가질 수 있고

부모 노드는 여러 자식을 가질 수 있다.

상속 관계를 그림으로 그리면 트리 모양이다.

 

 

 

▶️ 순서 트리 탐색 방법 알아보기

 

순서 트리를 검색하는 방법에는 두가지 방법이 있다.

너비 우선 탐색(가로형 탐색)

깊이 우선 탐색(세로형 탐색)

 

 

 

 

❑ Graph

 

 

Graph

 

➤ 자료구조에서 그래프는 네트워크망 처럼 복잡하게 연결된 모양이다.

➤ 비선형 구조

 

※ 용어

  • vertex(정점) : 하나의 점
  • edge(간선) : 점들을 이어주는 선
  • 직접적인 관계(인접하다) : 두 점을 직접적으로 이어주는 선 존재
  • 간접적이 관계 : 두 점이 두개 이상의 선을 거쳐가야 하는 관계
  • weighted Graph(가중치 그래프) : 연결의 강도(추가적인 정보)가 있는 그래프
  • unweighted Graph(비가중치 그래프) : 연결의 강도가 없는 그래프
  • in-degree(진입차수) / out-degree(진출차수) : 한 정점에 진입하고 진출하는 간선이 몇 개인지
  • self loop (자기 루프) : 정점에 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 '자기 루프를 가졌다'고 표현
  • cycle (사이클) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 '사이클이 있다'고 표현

 

 

▶️ 그래프의 종류

 

- undirected Graph(무방향 그래프): 간선의 방향이 없는 그래프

- directed Graph(방향 그래프): 간선에 방향성이 있는 그래프

- weighted Graph(가중치 그래프) : 연결의 강도(추가적인 정보)가 있는 그래프

- 루트 없는 트리: 간선을 통해 정점 간 잇는 방법이 한가지인 그래프

- 이분 그래프: 그래프의 간선을 두 그룹으로 나눈 후 다른 그룹끼리만 간선이 존재하게 분할할 수 있는 그래프

- 사이클이 없는 그래프: 정점에서 출발해 자기 자신으로 돌아오는 경로가 없는 그래프

 

 

▶️ 그래프의 표현

 

인접 행렬

 

- 인접행렬 : 2차원 배열로 정점 간의 간선의 존재 여부를 1 또는 0으로 표시

                  가중치 그래프일 경우 가중치로 표시하면 좋음

                  가장 빠른 경로를 찾고자 할 때 주로 사용

 

인접 리스트

 

- 인접 리스트 : 정점 개수만큼 리스트를 만들어 각각의 정점 리스트에 간선 추가

인접 행렬은 간선이 없는 경우에도 확인하기 때문에 간선이 적은 경우 간선이 있는 경우만 확인하는 인접 리스트보다 오래걸린다.

 

 

▶️ 그래프의 표현

 

관계 표현이 필요한 모든 경우에 사용 가능

활용도가 높음

- 최단 경로 탐색

- 소셜 네트워크 관계망

- 인터넷 네트워크망(전송속도 계산)

 

 

 

 

트리에 대해서 조사하다 보니까 지금 내가 보고 있는 건 빙산의 일각인 것 같다..

 

 

너무 욕심부려서 다 알려고 하지말고 궁금한건 그때그때 찾아보자

지금 공부하면 허우적거리다가 진도 못 따라갈 것 같다 ㅋㅋ

금요일에 배운것도 이틀이 지난 오늘에서야 정리한 걸 보면

내 속도가 많이 느리긴 하다.

Today I Learned인데..

이번건 Two days ago I Learned의 TIL이다..

 

 

 

 

읽어주셔서 감사합니다. 도움이 되셨기 바랍니다.

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

 

 

 

저작자표시

'TIL(Today I Learned)' 카테고리의 다른 글

5/31 (화) 코딩 테스트 준비 - 1️⃣ 알고리즘, 의사코드, 시간복잡도(Big-O)  (0) 2022.06.01
5/30 (월) 자료구조-3️⃣ 이진트리, BFS/DFS  (0) 2022.06.01
5/26(목) 자료구조 - 1️⃣ Stack, Queue 스택과 큐  (0) 2022.05.26
Java 심화-2️⃣ 람다식, 스트림  (0) 2022.05.23
5/19 (목) Java 심화-1️⃣ Enum, Annotation  (0) 2022.05.20
JAVA/JAVA 기초

자바에서 Stack과 Queue 배열로 구현하기

 

 

 

 

자료구조에서 중요한 개념인 Stack과 Queue를 코드로 직접 구현해보았다.

 

'Doit! 자료구조와 함께 배우는 알고리즘 입문 자바편'을 참고하여 작성하였습니다.

 

 

❑ 자바에서 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();
        }
    }
}

 

 

❑ 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;
            }

        }
    }
}

 

 

 

❑ 자바에서 Queue 배열로 구현하기

더보기 
public class IntQueue {
    private int[] que;      // 큐용 배열
    private int capacity;   // 큐의 용량
    private int front;      // 맨 앞의 요소 커서
    private int rear;       // 맨 뒤의 요소 커서
    private int num;        // 현재 데이터 개수

    // 실행 시 예외 : 큐가 비어 있음
    public class EmptyIntQueueException extends RuntimeException {
        public EmptyIntQueueException() {}
    }

    // 실행 시 예외 : 큐가 꽉 차있음
    public class OverflowIntQueueException extends RuntimeException {
        public OverflowIntQueueException() {}
    }

    // 생성자
    public IntQueue(int maxlen) {
        num = front = rear = 0;
        capacity = maxlen;
        try {
            que = new int[capacity];        // 큐 본체용 배열을 생성
        } catch (OutOfMemoryError e) {      // 생성할 수 없을 경우
            capacity = 0;
        }
    }

    // 큐에 데이터 인큐
    public int enque(int x) throws OverflowIntQueueException {
        if(num >= capacity) {
            throw new OverflowIntQueueException();  // 큐가 가득참
        }
        que[rear++] = x;
        num++;
        if(rear == capacity)
            rear = 0;
        return x;
    }

    // 큐에 데이터를 디큐
    public int deque() throws EmptyIntQueueException {
        if(num <= 0)
            throw new EmptyIntQueueException();
        int x = que[front++];
        num--;
        if(front == capacity)
            front = 0;
        return x;
    }

    // 큐에서 데이터를 피크(front 데이터를 들여다봄)
    public int peek() throws EmptyIntQueueException {
        if(num <= 0)
            throw new EmptyIntQueueException();    // 큐가 비어있음
        return que[front];
    }

    // 큐를 비움
    public void clear() {
        num = front = rear = 0;
    }

    // 큐에서 x를 검색하여 인덱스(찾지 못하면 -1)를 반환
    public int indexOf(int x) {
        for(int i = 0; i < num; i++) {
            int idx = (i + front) % capacity;
            if(que[idx] == x)       // 검색 성공
                return idx;
        }
        return -1;      // 검색 실패
    }

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

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

    // 큐가 비어있나요?
    public boolean isEmpty() {
        return num <=0;
    }

    // 큐가 가득 찼나요?
    public boolean isFull() {
        return num >= capacity;
    }

    // 큐에서 임의의 데이터를 검색
    public int search(int x) {
        for(int i = 0; i < num; i++) {
            if(que[(i + front) % capacity] == x)
                return i + 1;
        }
        return 0;
    }

    // 큐 안의 모든 데이터를 front -> rear 순으로 출력
    public void dump() {
        if(num <= 0)
            System.out.println("큐가 비어있습니다.");
        else {
            for(int i = 0; i < num; i++) {
                System.out.println(que[(i + front) % capacity] + " ");
            }
            System.out.println();
        }
    }
}

 

 

❑ Queue 클래스 테스트하기

 

더보기 
public class IntQueue {
    private int[] que;      // 큐용 배열
    private int capacity;   // 큐의 용량
    private int front;      // 맨 앞의 요소 커서
    private int rear;       // 맨 뒤의 요소 커서
    private int num;        // 현재 데이터 개수

    // 실행 시 예외 : 큐가 비어 있음
    public class EmptyIntQueueException extends RuntimeException {
        public EmptyIntQueueException() {}
    }

    // 실행 시 예외 : 큐가 꽉 차있음
    public class OverflowIntQueueException extends RuntimeException {
        public OverflowIntQueueException() {}
    }

    // 생성자
    public IntQueue(int maxlen) {
        num = front = rear = 0;
        capacity = maxlen;
        try {
            que = new int[capacity];        // 큐 본체용 배열을 생성
        } catch (OutOfMemoryError e) {      // 생성할 수 없을 경우
            capacity = 0;
        }
    }

    // 큐에 데이터 인큐
    public int enque(int x) throws OverflowIntQueueException {
        if(num >= capacity) {
            throw new OverflowIntQueueException();  // 큐가 가득참
        }
        que[rear++] = x;
        num++;
        if(rear == capacity)
            rear = 0;
        return x;
    }

    // 큐에 데이터를 디큐
    public int deque() throws EmptyIntQueueException {
        if(num <= 0)
            throw new EmptyIntQueueException();
        int x = que[front++];
        num--;
        if(front == capacity)
            front = 0;
        return x;
    }

    // 큐에서 데이터를 피크(front 데이터를 들여다봄)
    public int peek() throws EmptyIntQueueException {
        if(num <= 0)
            throw new EmptyIntQueueException();    // 큐가 비어있음
        return que[front];
    }

    // 큐를 비움
    public void clear() {
        num = front = rear = 0;
    }

    // 큐에서 x를 검색하여 인덱스(찾지 못하면 -1)를 반환
    public int indexOf(int x) {
        for(int i = 0; i < num; i++) {
            int idx = (i + front) % capacity;
            if(que[idx] == x)       // 검색 성공
                return idx;
        }
        return -1;      // 검색 실패
    }

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

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

    // 큐가 비어있나요?
    public boolean isEmpty() {
        return num <=0;
    }

    // 큐가 가득 찼나요?
    public boolean isFull() {
        return num >= capacity;
    }

    // 큐에서 임의의 데이터를 검색
    public int search(int x) {
        for(int i = 0; i < num; i++) {
            if(que[(i + front) % capacity] == x)
                return i + 1;
        }
        return 0;
    }

    // 큐 안의 모든 데이터를 front -> rear 순으로 출력
    public void dump() {
        if(num <= 0)
            System.out.println("큐가 비어있습니다.");
        else {
            for(int i = 0; i < num; i++) {
                System.out.println(que[(i + front) % capacity] + " ");
            }
            System.out.println();
        }
    }
}

 

 

 

저작자표시
1

티스토리툴바