자료구조와 알고리즘3

김동현·2022년 6월 27일
0

이진 검색

검색할 범위를 절반으로 줄여가며 검색하는 방법

정렬된 선형 리스트에서만 사용할 수 있다.

정렬이 되어있고 임의 접근이 가능하다면 이진검색이 정말 빠르다.
정렬이 안되어있다면 선형검색을 해야한다.

임의 접근이 가능해야 함

시간복잡도는 O(logN) 이다.

// arr : 정렬된 배열
// size : 배열의 크기
// value : 찾고자 하는 값
bool BinarySearch(int* arr, int size, int value)
{
    // 범위는 [s, e)로 표현한다. 구현에 따라 다르게 할 수 있다. [ : 포함 ) : 비포함
    int s = 0, e = size; // 인덱스에 접근할 수 있는 타입 int or size_t
    while (s < e) // 시작지점이 끝 위치보다 작은경우 끝낸다
    {
        int m = (s + e) / 2;
        // 오버플로우를 방지하기 위해 아래처럼도 사용할 수 있다.
        // int m = s + (e - s) / 2;
 
        // 찾았다면 true다.
        if (arr[m] == value)
            return true;
            
        // 배열이 정렬되어 있기 때문에
        // 중간값과 비교하여 범위를 조정한다.
        else if (arr[m] < value)
            s = m + 1;
            
        else
            e = m;
    }
 
    return false;
}

그래프

관계에 특화된 자료구조
비선형 자료구조

정점과 간선으로 구성

정점 : 고유하게 식별되는 객체
간선 : 정점 간의 관계

종류

간선이 방향성을 가지는 지에 따라 방향 그래프와 무방향 그래프로 구분

무방향 그래프는 둘다 연결되어 있다고 치고 구현하면 된다.

간선이 단순 연결 이상의 정보(가중치)를 가지는 가중치 그래프도 있다.

그래프는 추상적이기에 자료구조로 재공되지 않는다.

간선으로 연결된 정점끼리는 인접 하다고 한다.
해당 간선은 연결된 정점에 부속 되어 있다고 한다.

정점에 부속되어 있는 간선의 수를 차수라 하고 나가는 방향에 따라 진입차수 진출 차수 로 나누어진다

한 정점에서 다른 정점까지 간선으로 연결된 정점으로 순서대로 나열한 리스트를 경로라고 한다.
경로를 구성하는 간선 수를 경로길이라 한다.
모두 다른 정점으로 구성된 경로룰 단순경로라 한다.
단순경로 중 시작정점과 마지막 정점이 같은 경로를 사이클이라 한다.
경로가 있으면 정점끼리 연결 되어 있다고 한다.

모든 정점이 연결되어 있다면 연결그래프, 아니면 단절 그래프 라 한다.

표현

그래프를 표현하는 방법에는 인접 행렬인접 리스트가 있다.

인접 행렬로 표현하기

정점이 N개 있을 경우 N x N 크기의 2차원 배열로 그래프를 표현할 수 있다.
배열의 원소는 간선의 가중치를 나타내게 된다.
가령 edges[i][j] 는 정점 i 에서 j로 가는 간선을 나타낸 것이다.

2차원 배열을 사용하기 때문에 그래프에 간선이 적다면* 그만큼 메모리를 낭비하게 된다.(희소 그래프를 표현할 때면)

정점의 개수에 비해서 간선이 적은 그래프를 희소 그래프 반대는 밀집 그래프이다.

인접 리스트로 표현하기

각 정점에 연결된 정점의 ID만 저장하는 방식으로 그래프를 표현하는 것

완전 연결 그래프라면 N(N-1) / 2로 간선의 개수를 구할 수 있다.

그래프 만드는 법

#include <vector>
#include <algorithm>

#define 김재민 0
#define 김재성 1
#define 안중재 2
#define 성권문 3
#define 이승일 4

std::vector<int> graph2[]; // 백터

// true : 연결, false : 비연결
bool graph[5][5];

// find 함수는 iterator를 반환해줌

// 인접했는지 알려면?? => 인접 행렬 버전
bool isAdhacent(int** graph, int v1, int v2)
{
	if (graph[v1][v2] | graph[v2][v1])
	{
		return true;
	}
	else
	{
		return false;
	}
}

// 인접했는지 알려면?? => 인접 리스트 버전
bool isAdhacent(std::vector<int>* graph, int v1, int v2)
{
	if (graph[v1].end() != std::find(graph[v1].begin(), graph[v1].end(), v2))
	{
		return true;
	}

	if (graph[v2].end() != std::find(graph[v2].begin(), graph[v2].end(), v1))
	{
		return true;
	}

	return false;
}

// 진입차수를 구한다. => 인접 행렬 버전
int CountIndegree(int** graph, int vertex)
{
	int count = 0;
	for (int i = 0; i < 5; ++i)
	{
		if (graph[i][vertex])
		{
			++count;
		}
	}

	return count;
}

// 인접 리스트 버전
int CountIndegree(std::vector<int>* graph, int vertex)
{
	int count;
	for (int i = 0; i < 5; ++i)
	{
		if (graph[i].end() != std::find(graph[i].begin(), graph[i].end(), vertex))
		{
			++count;
		}
	}

	return count;
}

int main()
{
	// 그래프 구성 : 인접 행렬
	graph[김재민][이승일] = true;

	graph[김재성][안중재] = true;
	graph[김재성][성권문] = true;
	graph[김재성][이승일] = true;

	graph[안중재][김재민] = true;
	graph[안중재][김재성] = true;
	graph[안중재][성권문] = true;
	graph[안중재][이승일] = true;

	graph[성권문][김재성] = true;
	graph[성권문][안중재] = true;
	graph[성권문][이승일] = true;
	
	// [i][j]  i -> j
	// 0 0 0 0 1
	// 0 0 1 1 1
	// 1 1 0 1 1
	// 0 1 1 0 1
	// 0 0 0 0 0
	


	// 그래프 구성: 인접 리스트
	// [0] : { 4 } // 0 -> 4
	// [1] : { 2, 3, 4 } // 1 -> 2, 1 -> 3, 1 -> 4
	// [2] : { 0, 1, 3, 4 } // 2 -> 0, 2 -> 1, 2 -> 3, 2 -> 4
	// [3] : { 1, 2, 4 } // 3 -> 1, 3 -> 2, 3 -> 4
	// [4] : {}
	graph2[김재민].push_back(이승일);

	graph2[김재성].push_back(안중재);
	graph2[김재성].push_back(성권문);
	graph2[김재성].push_back(이승일);

	graph2[안중재].push_back(김재민);
	graph2[안중재].push_back(김재성);
	graph2[안중재].push_back(성권문);
	graph2[안중재].push_back(이승일);

	graph2[성권문].push_back(김재성);
	graph2[성권문].push_back(안중재);
	graph2[성권문].push_back(이승일);
}

문제를 보고 관계를 정의

그래프 구성

컴퓨터로 어떻게 옮겨야ㅕ 하는지 (코드) 행렬과 리스트 방식이 있다.
어떻게 저장되는것인지 차이점을 명확히 알아야댐

각각 구현 방법이 어떤 장단점이 있는지

행렬

장점 : 구현하기 쉬움(2차원 배열이라)
단점 : 메모리가 낭비될 수 있다.

리스트 :

장점 : 메모리를 아낄 수 있다.
단점 : 구현난이도가 있다.

순회

그래프 순회(탐색) : 한 정점에서 시작해 그래프에 있는 모든 정점을 한 번씩 방문하는 것

깊이 우선 탐색(DFS) : 스택을 사용
시작 정점의 한 방향으로 끝까지 가고 더이상 갈곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 돌아와 다른 방향의 간선으로 탐색을 계속하는 방법

너비 우선 탐색(BFS) : 큐를 사용
시작 정점에 인접한 정점을 모두 차례로 방문하고나서 방문했던 정점을 시작으로 다시 인접한 정점을 차례로 방문하는 방식

DFS , BFS 팁

  1. 방문 여부를 저장할 변수를 생성한다.
    => 왜> 재방문을 막기 위해서

  2. DFS라면 스택을 만들고, BFS라면 큐를 생성한다.
    => 스택이나 큐에 저장되는 데이터는 다음에 방문할 정점

  3. 더이상 방문할 정점이 없을 때까지 방문한다.

최단경로

가중치 그래프에서 두 정점을 연결하는 경로 중 가중치의 합이 최소인 경로

간선이 없다면 무한대 값으로 저장하며 가중치가 음수여선 안된다.

다익스트라 알고리즘

A*알고리즘

다익스트라 알고리즘에서 따왔다.

플로이드 알고리즘

트리

profile
해보자요

0개의 댓글