전체 글
-
너비 우선 탐색(BFS) 란?Computer Science/Data_Structure 2020. 1. 4. 05:30
그래프 탐색에는 2가지가 있다고 했는데 그 중에 하나인 BFS 탐색에 대해서 정리하려고 한다. 너비 우선 탐색(breath first search : BFS) 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 위와 같은 그래프에서 화살표의 방향대로 탐색을 한다. (시작 정점에서 가까운 노드부터 탐색하는 것을 알 수 있다) 너비 우선 탐색을 위해서는? 가까운 거리에 있는 정점들을 차례로 정한 후 꺼낼 수 있는 자료구조인 큐(queue)가 필요함 무조건 큐에서 정점을 꺼내서 정점을 반물하고 인접 정점들을 큐에 추가한다.(큐가 소진될 때 까지 반복) 너비 우선 탐색 과정 다시한번 정리하자면 다음과 같다. 위의 과정을 큐가 공백 상태가 될 때 까지 계속한다...
-
깊이 우선 탐색(DFS) 란?Computer Science/Data_Structure 2020. 1. 4. 00:36
그래프의 탐색 그래프 탐색은 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 그래프 탐색은 아주 중요하다 도시를 연결하는 그래프가 있을 때, 특정 도시에서 다른 도시로 갈 수 있는지 없는지는 탐색하여 체크 그래프의 탐색 방법은 깊이 우선 탐색과 너비 우선 탐색의 두 가지가 있다. 이 글에서는 깊이 우선 탐색에 대하여 알아보겠다. 깊이 우선탐색(DFS : depth first search) 트리에서 생각하면 이해하기 쉽다(트리도 그래프의 일종이라는 점을 명심하자) 트리를 탐색할 때 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사 위와 같은 그림의 그래..
-
그래프(Graph) 란?Computer Science/Data_Structure 2020. 1. 3. 21:49
그래프의 소개 그래프(graph)는 객체 사이의 연결 관계를 표현할 수 있는 자료 구조다. (대표적인 예 : 지도) 지도를 그래프로 표현하면 지하철의 특정한 역에서 다른 역으로 가는 최단 경로를 쉽게 찾을 수 있다. 운영 체제에서는 프로세스와 자원들이 어떻게 연관되는지를 그래프로 분석하여 시스템의 효율이나 교착상태 유무 등을 알아낼 수 있다. 그래프로 표현할 수 있는 것들 도로 미로 선수과목 1. 그래프의 정의와 용어 그래프의 정의 그래프는 정점(vertex)와 간선(edge)들의 유한 집합이라 할 수 있다. 수학적으로는 G = (V,E)와 같이 표시한다. V(G)는 그래프의 G의 정점들의 집합, E(G)는 그래프 G의 간선들의 집합이다. 정점 : 여러 가지 특성을 가질 수 있는 객체 간선 : 이러한 정..
-
[JAVA] Call by Value 와 Call by reference 란 ?Language/Java 2020. 1. 3. 15:29
C언어를 주로 공부 했던 나는 Call by value 와 Call by reference 에 대해서 call by value 는 값을 넘기는 거고 call by reference 는 포인터를 이용해서 주소를 넘긴다고 알고 있다. 하지만 누군가 나에게 이 개념에 대해서 자세히 묻는다면 나도 깊이있게 이해한 것이 아니기 때문에 위에서 말한 대답정도로만 대답을 할 거 같다. 그래서 먼저 이 개념을 한번 더 정리를 한 후에 JAVA 에서의 Call by value 와 Call by reference 에 대해서 알아보겠다. https://wayhome25.github.io/cs/2017/04/11/cs-13/ 강의노트 12. 함수 호출방식(call-by-value, call-by-reference, call-b..