각종 학습 요약/DataStructure
-
자료구조: 그래프Graph의 기본적인 활용각종 학습 요약/DataStructure 2022. 5. 30. 23:40
그래프 graph (3) - 기본적인 활용 그래프의 기본 개념을 설명한 이전 포스팅(개념1, 개념2)에 이은 글입니다. 소개했던 그래프 탐색 방법 두 가지를 실제로 활용하는 법─DFS와 BFS를 java 코드로 구현하는 법에 대해 알아보겠습니다. 깊이 우선 탐색DFS과 넓이 우선 탐색BFS의 주요 구현 방식 DFS는 주로 Stack(자료구조)이나 재귀를 통해 구현됩니다. BFS는 주로 Queue(자료구조)를 이용해 구현됩니다. DFS는 왜 재귀 || Stack으로 구현? DFS에 대해 공부를 하고 오셨거나 개념에 대한 이전 두 포스팅을 보고 오셨다면 아시겠지만 다시 한 번 정리해서 말해보겠습니다. 깊이 우선 탐색은 끝 조건에 도달할 때까지 계속 반복해서 들어간 후, 끝 조건을 만나면 리턴을 시작해서, 호..
-
자료구조: 그래프Graph의 기본적인 이해 (2)각종 학습 요약/DataStructure 2022. 5. 28. 22:07
그래프 graph (2) - 기본 개념 이해 그래프의 기본 개념을 설명한 이전 포스팅에 이어서 그래프 정보를 기록하는 두 가지 방법을 소개하고, 탐색 방법 두 가지를 소개합니다. 그래프를 코드로 기록하는 방법 그래프를 기록하는 데에는 인접행렬Adjacency Matrix이라는 방법과 인접리스트Adjacency List라는 두 가지 방식이 존재해요. 인접행렬 방식은 행렬 형태로 이차원 배열을 만들어주고 서로 연결되었는지를 기록하고요. 인접리스트 방식은 정점과 연결된 정점의 정보를 링크드리스트로 연결합니다. 두 가지 방식을 예시로 설명하기 위한 구조를 정의해야 할 것 같은데요. 아래와 같은 그래프가 존재한다고 해볼게요. 그래프의 예시를 하나 그려봤어요. 이 그림을 가지고 설명해보겠습니다. 인접 행렬 Adja..
-
자료구조: 그래프Graph의 기본적인 이해 (1)각종 학습 요약/DataStructure 2022. 5. 28. 21:17
그래프 graph (1) - 기본 개념 이해 그래프를 설명하는 글의 카테고리를 Concept로 할지 Data Structure로 할지 고민하다가 후자로 하기로 했습니다! 우리가 프로그래밍을 하다보면 어떤 이유에서든 '탐색'이라는 걸 필요로 할 때가 있죠? '탐색'이란 누구에게나 일상적이고 익숙한 개념이지만, 컴퓨터는 우리와 달리 알려준 것만 알 수 있으니까, 좀 더 구체적이고 명시적으로 알려줄 필요가 있을 거에요. 그래서 컴퓨테이셔널하게 좀 더 풀어서 설명해보자면, 탐색이라는 건 관계를 가지는 어떤 node들을, 정해진 방문 방법을 가지고 순차적으로 방문하며 처리하는걸 말해요. 그리고 이렇게 탐색을 할 수 있도록 정의된 대상을 그래프graph라고 합니다. 이렇게 말하니 좀 낯..
-
자료구조 - Tree와 순회, 코드로 알아보기각종 학습 요약/DataStructure 2022. 5. 28. 20:35
자료구조 - Tree와 순회 구현 지난 포스트에서는 binary tree에 대한 기본 개념을 익혀보았습니다. 이번 포스트에서는 Java를 이용해서 지난번 설명한 개념을 토대로 구현해보도록 하겠습니다. Tree - 구현된 코드 살펴보기 👇Node를 구현한 Class와 설명 하나의 node는 자기 자신(의 데이터), 그리고 child node-left & right의 정보를 가지고 있습니다. 자식이 부모를 기억하거나, 자식과 부모가 서로를 참조하고 있거나 할 수도 있는데 일단 여기서는 parent node가 child node를 갖고 있는 걸로 간단하게 구현해보았어요. class Node { T data; Node left; Node right; } 👇Tree를 구현한 코드와 설명 Tree는 Node들을 갖..
-
자료구조: 트리Tree의 기본 개념각종 학습 요약/DataStructure 2022. 5. 28. 19:57
자료구조: 트리Tree의 기본 개념 Graph Concept를 이해하기 위한 아주 기본적인 tree 개념에 대해 알아봅니다. 트리가 어떤 개념인지, 트리의 특성, 트리의 종류, 그리고 탐색방식에 대해서요. 이진트리 child node가 최대 2개 붙는 경우 이진트리binary tree입니다. 세 개, 혹은 그 이상도 존재하는 트리도 있긴 해요. 이진탐색트리 Binary search tree root node보다 값이 작은 child node는 왼쪽에, 값이 큰 child node는 오른쪽에 배치해서 탐색을 용이하게 한 트리 구조입니다. 줄여서 BST라고들 말해요. 밸런스 - balanced / unbalanced 왼쪽/오른쪽 child node의 개수가 균형을 이루지 않아 트리로 판단하기 어려운 정도가 ..
-
Stack과 Queue의 기본적인 이해각종 학습 요약/DataStructure 2022. 5. 26. 16:23
Stack과 Queue의 기본적인 이해 데이터를 효율적으로 다룰 수 있는 방법들을 모두 정리하여 둔 자료구조라는 것이 있습니다. 이 글에서는 자료구조의 대표주자 격인 스택(Stack)과 큐(Queue)의 특징와 원리를 이해해보고, 기능까지 간단히 알아보겠습니다. 스택과 큐의 공통점 둘 다 데이터를 담는 모양이 빨대처럼 생겼어요. 길다란 통로에 줄지어서 데이터들이 존재합니다. 데이터가 하나씩 들어가고, 하나씩 나갑니다. 스택과 큐의 차이점 줄지어서 입장한 데이터들이 있었죠. 이제 나갈때를 상상해보면, 스택은 나중에 들어온 데이터가 먼저 나갑니다. 가장 먼저 들어온 데이터가 가장 늦게 나가요. 빨대의 한 쪽 끝이 막혀있다고 생각하면 쉽겠네요. 입구가 곧 출구이기 때문에, 늦게 들어온 데이터가 먼저 나가는 것..