[S2 U2]자료구조 회고

정윤호·2023년 1월 18일
0

자료구조에 대한 회고

코드스테이츠 백엔드 부트캠프에 참여한지 한달... 엄청난 벽을 만났다... 자료구조라는 아주 문송하게 만드는 벽...
Stack부터 DFS까지... 3일간 짧지만 호되게 혼났다... 새벽 5시부터 화장실도 제대로 못 가고 저녁까지... 자면서도 도대체 무슨 개념인지... 어떻게 구현하고 활용하는지...
지난 Unit 1 재귀함수도 정말 어려운 개념이었는데... Stack과 Queue를 접하자... 재귀가 선녀구나... 또 Tree와 Graph, BinarySearchTree를 만나니... Stack과 Queue는 양반이네... DFS와 BFS는... 도대체... 뭐가 어떻게 돌아가는거야...
그래도 하나 하나 배워갈 때마다 자고 있던 머리가 깨어나는 느낌이랄까... 앞으로도 많은 알고리즘이란 벽이 나를 마주하겠지만... 매일 성장하는 나를 기대하며 화이팅!!


Stack vs Queue

[Stack과 Queue] 코드 예시

import java.util.*;

public class StackAndQueue {
    public static void main(String[] args) {
        Stack pringles = new Stack();
        Queue pipe = new LinkedList();

        pringles.push("입");
        pringles.push("구");
        pringles.push("와");
        pringles.push("출");
        pringles.push("구");
        pringles.push("가");
        pringles.push("같");
        pringles.push("다");

        pipe.add("입");
        pipe.add("구");
        pipe.add("와");
        pipe.add("출");
        pipe.add("구");
        pipe.add("가");
        pipe.add("다");
        pipe.add("르");
        pipe.add("다");


        System.out.println("스택은 프링글스와 유사하다.");
        while (!pringles.isEmpty()) {
            System.out.println(pringles.pop());
        }
        System.out.println("큐는 파이프관과 유사하다.");
        while (!pipe.isEmpty()) {
            System.out.println(pipe.poll());
        }
    }
}

[출력결과]

Stack과 Queue의 가장 큰 차이점은 입력된 데이터가 입력된 순서대로 출력되느냐 반대로 출력되는냐이다. 코드 예시를 살펴보면 Stack은 데이터의 입구와 출구가 같아 데이터가 입력되고 마지막에 입력된 데이터순으로 출력된다. Queue는 데이터의 입구와 출구가 달라 데이터가 입력된 순으로 출력되는 것을 알 수 있다.

경상계열 전공자로써 재고관리에 있어서 선입선출을 많이 사용하는데 항상 후입선출에 대해서 이해하지 못 했었다. 물건은 사용기한이 있고, 대부분 재고보다 신품이 유리하기 때문이다. 그러나 개발을 공부하면서 후입선출의 필요성에 대해서 잘 알 수 있었다.


Tree vs Graph

Tree는 Graph에 포함되는 개념이지만, 위에서 아래로 나열된 계층적 자료구조로 특성을 갖는다. 이에, Root(뿌리), 노드(Node) 등 Graph와는 다소 상이한 용어를 사용한다. Graph에서 노드(Node)는 정점(Vertex)라고하며, 점(노드 혹은 정점)과 점 사이를 연결하는 간선(Edge)가 중요한 개념으로 사용된다.

[Graph와 Tree 이미지]

실생활에서 접할 수 있는 예시를 살펴보면, Tree 구조는 회사의 조직도, 컴퓨터에서의 디렉토리 등으로 만히 접할 수 있고, Graph는 네비게이션, 항공노선 등에서 주로 접할 수 있다.


BFS vs DFS

BFS(Breathed First Search, 너비우선탐색)과 DFS(Depth First Search, 깊이우선탐색)은 Graph의 탐색 방법이다.

  • BFS는 가까운 정점(Vertex)부터 탐색하여 목적지까지 최단 경로를 찾을 때 주로 사용된다.
  • DFS는 각 경로의 끝까지 탐색하여 BFS보다 상대적으로 오래 시간 소요가 많이 되지만, 모든 정점(Vertex)를 완전히 탐색한다.

실생활에서 접할 수 있는 예시를 살펴보면, 정확한 비유는 아니지만, 이해의 편의성을 위해 BFS는 택시라면, DFS는 택배라고 할 수 있다. 택시는 승객을 목적지까지 빠르게 데려다주는 것을 목적으로하며, 택배는 각 배송지를 모두 방문하여 택배를 배송하는데 목적이 있다고 할 수 있다. 즉, BFS와 DFS는 목적에 따라 다르게 사용됨을 알 수 있다.

※ 택배의 경우 Unit 3에서 학습할 탐욕 알고리즘(Greedy)를 사용한다고 한다.

profile
오늘 하루도 최선을 다하자!!

0개의 댓글