Data Structure
-
자료구조: 그래프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라고 합니다. 이렇게 말하니 좀 낯..
-
Stack과 Queue의 기본적인 이해각종 학습 요약/DataStructure 2022. 5. 26. 16:23
Stack과 Queue의 기본적인 이해 데이터를 효율적으로 다룰 수 있는 방법들을 모두 정리하여 둔 자료구조라는 것이 있습니다. 이 글에서는 자료구조의 대표주자 격인 스택(Stack)과 큐(Queue)의 특징와 원리를 이해해보고, 기능까지 간단히 알아보겠습니다. 스택과 큐의 공통점 둘 다 데이터를 담는 모양이 빨대처럼 생겼어요. 길다란 통로에 줄지어서 데이터들이 존재합니다. 데이터가 하나씩 들어가고, 하나씩 나갑니다. 스택과 큐의 차이점 줄지어서 입장한 데이터들이 있었죠. 이제 나갈때를 상상해보면, 스택은 나중에 들어온 데이터가 먼저 나갑니다. 가장 먼저 들어온 데이터가 가장 늦게 나가요. 빨대의 한 쪽 끝이 막혀있다고 생각하면 쉽겠네요. 입구가 곧 출구이기 때문에, 늦게 들어온 데이터가 먼저 나가는 것..