Graph
-
자료구조: 그래프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라고 합니다. 이렇게 말하니 좀 낯..