전체 글
-
배열에서 최대값 찾기C 자료구조/1. 재귀함수 2020. 7. 16. 23:26
1. 개념 배열에서 최대값을 찾는 문제는 반복문을 이용해서 쉽게 구할 수도 있지만, 재귀함수를 통해 구할 수 있다. 배열의 길이를 5라고 하면, 0번 인덱스에서 4번 인덱스까지의 범위에서 최대값을 찾는 문제라고 한다면 1번 인덱스에서 4번 인덱스까지의 범위에서 최대값을 구했다고 가정하면 0번 인덱스와 비교를 통해 최대값을 구하면 된다. 위 그림에서, 배열의 길이가 5칸이라고 가정하고 보도록하자. 파란색 숫자는 재귀함수의 호출 순서이다. fromIndex는 위의 노란색 화살표이다. fromIndex가 배열의 맨 마지막 인덱스이면, 맨 마지막 인덱스를 리턴한다. 그러면서, 현재의 인덱스와 그 이전의 인덱스를 서로 비교해서 큰 값을 갖는 인덱스를 리턴하면 된다. 2. 구현 프로그램 실행결과
-
Graph - Topological SortC 자료구조/Graph 2020. 7. 14. 00:17
내용 1. 개념 아래와 같은 그래프가 있다고 하자. 위와 같은 방향 그래프에서 간선가 있다면 정점u는 정점v를 선행한다고 한다. 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것을 방향 그래프의 위상 정렬이라 한다. 위의 그림에서 많은 위상 정렬이 가능한데, 몇 개만 예를 들어보자. A,B,C,D,E,F B,A,C,D,E,F 가 있다. 그러나, C,A,B,D,E,F는 위상 순서가 아니다. 위가 위상 순서가 아닌 이유는 간선가 존재하기 때문에 A번 정점이 끝나야만 C번 정점을 시작할 수 있기 때문이다. 2. Topological Sort 알고리즘 방향 그래프를 대상으로 위상 정렬을 하기 위한 알고리즘은 간단하다. 먼저 진입 차수가 0인 정점을 선택하고, 선택된 정점..
-
Graph - Connectedcomponent( 연결 성분 )C 자료구조/Graph 2020. 7. 11. 23:14
내용 앞에서 만든 DFS 내용을 그대로 가지고 와서 만든다. 1. 개념 연결 성분이란 최대로 연결된 부분 그래프를 말한다. 즉, 연결된 부분 그래프들 중에서 크기가 최대인 것을 연결 성분이라고 한다. 아래의 그래프에는 2개의 연결 성분이 있다. 위의 그래프를 연결 성분 함수를 호출하면 연결성분을 표시한 배열Visit는 아래의 그림과 같다. 즉, 정점의 집합 { A, B, C }와 집합 { D, E }가 연결 성분임을 알 수 있다. 연결 성분을 찾기 위해서 깊이 우선 탐색이나 너비 우선 탐색을 이용한다. 먼저, 그래프 상의 임의의 정점을 선택해 깊이 우선 탐색이나 너비 우선 탐색을 시작하면 시작 정점과 연결되어 있는 모든 정점들이 출력된다. 다음에 방문 안된 정점을 선택해서 다시 탐색을 실행하면 그 정점을..
-
Graph BFS with queueC 자료구조/Graph 2020. 7. 8. 19:05
내용 1. 개념 너비 우선 탐색( BFS )은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 너비 우선 탐색을 위해서는 방문한 정점들을 차례로 저장한 후, 꺼낼 수 있는 자료 구조인 큐가 필요하다. 큐는 앞에서 만든 것을 이용할 것이다. 즉, 정점이 방문될 때마다 큐에 방문된 정점을 삽입하고, 더 이상 방문할 인접 정점이 없는 경우에는 큐의 앞에서 정점을 꺼내어 그 정점과 인접한 정점들을 모두 차례대로 방문하게 된다. 초기 상태의 큐에는 시작 정점만이 저장되고, 너비 우선 탐색 과정은 큐가 소진될 때까지 계속한다. 여기에서도 pVisit배열을 쓴다. 너비 우선 탐색을 그림으로 보자. 아래에 임의의 그래프가 주어졌다고 가정하자. [그림 1] 위의..
-
Graph DFS with RecursionC 자료구조/Graph 2020. 7. 8. 00:39
내용 구현은 앞에서 만든 내용을 가지고 오자. 1. 개념 깊이 우선 탐색( DFS )은 미로를 탐색할 때, 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 깊이 우선 탐색은 그래프의 시작 정점에서 출발하여 먼저, 시작 정점StartVertex를 방문하고 방문하였다고 표시를 한다. StartVertex에 인접한 정점들 중에서 아직 방문 하지 않은 정점u가 있다면 u를 시작 정점으로 하여 깊이 우선 탐색을 다시 시작한다. 이 탐색이 끝나게 되면, 다시 StartVertex에 인접한 정점들 중에서 아직 방문이 안된 정점을 찾는다. 만약 없으면 종료하고, 있다면 다시 그 정점을 시작 정점..
-
Graph ( 비용 제외 )C 자료구조/Graph 2020. 7. 6. 09:08
인용 1. 개념 그래프는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조이다. 그래프의 대표적인 예시는 지도 이다. 지도에는 여러 개의 도시들이 있고, 도시들은 서로 연결되어 있다. 그래프 구조는 인접 행렬이나, 인접 리스트로 표현하고 처리할 수 있다. 그래프는 정점(Vertex)과 간선(Edge)들의 집합으로 구성된다. 수학적으로는, G = (V,E) 로 표시한다. 그래프의 대표적인 그림은 아래와 같다. 위의 그림은 대표적으로 무방향 그래프이다. 간선의 방향이 없기 때문. 2. 인접 리스트 방식 설명 우리가 만들려고 하는 그래프를 먼저 그려보자. 그리고, 위의 그래프의 모양을 아래와 같이 표현 가능하다. 여기서 그래프를 표현한 방식은 인접 리스트를 이용했다. 즉, 각 각의 정점에 인접한 정점들..