Algorithms, Data Analytics

그래프

 -> 그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node)와 간선(Edge)로 표현하기 위해 사용

방향 그래프

 -> 간선에 화살표가 있는 경우

무방향 그래프

 -> 간선에 화살표가 없는 경우

그래프 관련 용어

 -> 1) 정점의 차수( Degree ) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 ( 위 그림에서는 2 )

 -> 2) 진입 차수( In - Degree ) : 방향 그래프에서 외부에서 오는 간선의 수 ( 지하철의 경우에 진입 차수는 1, 자기자신에게 들어오는 간선의 수)

 -> 3) 진출 차수 ( Out - Degree ) : 방향 그래프에서 외부로 향하는 간선의 수( 지하철의 경우에 진출 차수는 1, 집의 경우는 2)

 -> 4) 경로 길이 ( Path - Length ) : 경로를 구성하기 위해 사용된 간선의 수 ( 집에서 회사까지의 경로의 길이는 2개의 간선을 거치기 때문에 경로 길이는 2)

 -> 5) 단순 경로 ( Simple Path ) : 처음 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로( 집에서 회사를 갈 때 가능한 단순 경로는 집 -> 버스 -> 회사, 집 -> 지하철 -> 회사, 단 집 -> 버스 -> 회사 -> 지하철 -> 회사 등이 있는데, 중간경로 중 중복되는 것이 없는 경우 단순경로로 본다.)

 -> 6) 사이클 ( Cycle ) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우 ( 집 -> 지하철 -> 회사 -> 버스 -> 집 일 경우 시작과 끝이 같기 때문에 사이클로 본다)

이진 탐색

 -> 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

예시 문제

 1~30 번째 병뚜껑에는 각각 1~100 사이의 번호가 표시되어 있습니다.

이 중에 70이 있을지 없을지를 확인하는 방법을 찾아보세요

조건 : 가장 적게 병을 따야 한다.

         각 병뚜껑에 씌여진 번호는 낮은 번호 순으로 기입되어 있다.

def binary_search(data, search):
    if (len(data) == 1 and search == data[0]):
        return True
    
    if (len(data) == 1 and search != data[0]):
        return False
    
    if (len(data) == 0):
        return False
    
    medium = len(data) // 2
    
    if (search == data[medium]):
        return True
    
    else:
        if search > data[medium]:
            return binary_search(data[(medium + 1):], search)
        
        else:
            return binary_search(data[:medium], search)

재귀로 구현해보았다.

먼저 데이터의 길이가 1이고 찾고자 하는 데이터와 같을 경우에는 True를 반환, 데이터는 1개인데 찾고자 한느 데이터가 아닐 경우에는 False 그리고 방어적으로 데이터에 아무것도 안들어갔을 경우에도 False를 반환하게 하였다.

전체 데이터를 반으로 나눠주는 변수를 선언해주고

혹시 그 반으로 나눈 경계가 찾고자 하는 데이터일 경우에는 True를

아닐 경우에는 찾고자 하는 값이 더 큰 경우에는 오른쪽으로 탐색을 해준다.

반으로 나누는 경계값이 찾고자하는 데이터가 아니기 때문에 그 다음 값부터 탐색을 해준다.

찾고자 하는 값이 더 작을 경우는 왼쪽을 탐색해준다.

병합정렬의 시간복잡도

몇 단계 깊이까지 만들어지는지를 depth라고 하고 i로 놓자. 맨 위 단계는 0으로 놓자

 -> 다음 그림에서 n/(2^2) 는 2단계 깊이라고 해보자.

 -> 각 단계에 있는 하나의 노드 안의 리스트 길이는 n/(2^2)가 된다.

 -> 각 단계에는 2^i 개의 노드가 있다.

따라서 각 단계는 항상 2^i * n/(2^2) = O(n)

단계는 항상 log n(밑은 2)개 만큼 만들어짐, 단계별 개수는 O(log n)

따라서 단계별 시간 복잡도 O(n) * O(log n) = O(n log n)