pjaehyun의 개발일지

깊이 우선 탐색(Depth-First Search) 란?

• 대표적인 그래프 탐색 알고리즘
• 정점의 자식 노드들을 먼저 탐색하는 방식이다.

깊이 우선 탐색(Depth-First Search) 이해

위와 같은 형태의 그래프가 있을 때 깊이 우선 탐색은 처음 시작 정점을 방문한 뒤,  인접 정점의 자식을 타고 끝까지 방문한 후, 다시 돌아와서 다른 형제의 자식노드를 타고 모든 정점을 방문한다. 넓이 우선 탐색과 다르게 깊이 우선 탐색은 탐색할 때 스택을 이용해야 한다.

첫 번째 노드에서 출발하기 때문에 1번 노드를 방문예약(need_visit) 스택에 넣은 뒤 1번 노드를 방문예약 스택에서 빼고 인접한 노드인 2, 5번 노드를 방문예약 스택에 넣어준다. (이후부터 스택이라 칭함)

5번 노드를 방문한 후 인접 노드인 4번 노드를 스택에 넣어준다.

마찬가지로 4번 노드를 방문한 후 인접 노드인 6번 노드를 스택에 넣어준다.

6번 노드를 방문한 후 더이상 자식 노드가 없기 때문에 이후에는 2번노드를 방문하게 된다.

같은 방식으로 계속 수행하게 되면

더이상 방문예약스택에 남아있는 정점이 없을 때 탐색을 종료한다.

깊이 우선 탐색(Depth-First Search) 구현

def dfs(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    return visited

깊이 우선 탐색(Depth-First Search) 시간 복잡도

• 노드 수: V
• 간선 수: E
• 깊이 우선 탐색의 시간 복잡도는 노드 수 + 간선 수로 표현된다. O(V+E)

너비 우선 탐색(Breadth-First Search) 란?

• 대표적인 그래프 탐색 알고리즘
• 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식이다.

너비 우선 탐색(Breadth-First Search) 이해

위와 같은 형태의 그래프가 있을 때 넓이 우선 탐색은 처음 시작 정점을 방문한 뒤, 정점에서 인접한 모든 정점을 방문한다.

다른 모든 정점들에 대해서도 방문하지 않은 정점이 없어질 때 까지 반복한다. 넓이 우선 탐색은 선입선출원칙을 기반으로 한 탐색법이기 때문에 큐를 이용한다.

첫 번째 노드에서 출발하기 때문에 1번 노드를 방문예약(need_visit)에 넣은 뒤 1번 노드를 방문예약큐에서 빼고 인접한 노드인 2, 5번 노드를 방문예약에 넣어준다.

방문예약큐 가장위에있는 2번노드를 큐에서 뺀 뒤 2번 노드와 인접한 노드인 1, 3번 노드를 방문예약큐에 넣어준다.

마찬가지로 5번 노드를 빼고 5번노드와 인접한 1, 6, 8번 노드를 방문노드큐에 넣어준다.

1번 노드는 이미 방문했던 노드니까 방문노드큐에서 빼기만 하고 바로 3번노드를 빼준다. 이 후 같은방식으로 2, 4번 노드를 방문예약큐에 넣어준다.

같은 방식으로 계속 수행하면

더이상 방문예약큐에 남아있는 정점이 없을 때 탐색을 종료한다.

너비 우선 탐색(Breadt-First Search) 구현

def bfs(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    return visited

너비 우선 탐색(Breadt-First Search) 시간 복잡도

• 노드 수: V
• 간선 수: E
• 너비 우선 탐색의 시간 복잡도는 노드 수 + 간선 수로 표현된다. O(V+E)

그래프(Graph) 란?

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

       집에서 학교로 가는 경로를 그래프로 표현

그래프(Graph) 관련 용어

• 노드(Node): 위치를 말함, 정점(Vertex)라고도 한다.
• 간선(Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선이다.(branch라고도 한다.)
• 인접 정점(Adjacent Vertex): 간선으로 직접 연결된 정점
• 참고 용어
• 정점의 차수(Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
• 진입 차수(In-Degree): 방향 그래프에서 외부에서 오는 간선의 수
• 진출 차수(Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수
• 경로 길이(Path Length): 경로를 구성하기 위해 사용된 간선의 수
• 단순 경로(Simple Path): 같은 정점을 두 번 이상 방문하지 않는 경로
• 사이클(Cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

그래프(Graph)의 종류

무방향 그래프(Undirected Graph)

• 방향이 없는 그래프
• 간선을 통해 노드는 양방향으로 이동이 가능하다.
• (A,B) 또는 (B,A)로 표기

방향 그래프(Directed Graph)

• 간선에 방향이 있는 그래프
• A에서 B로가는 간선으로 연결되어 있을 경우, <A,B>로 표기 <B,A>와는 다르다.

가중치 그래프(Weighted Graph) 또는 네트워크(Network)

• 간선에 비용 또는 가중치가 할당된 그래프

연결 그래프(Connected Graph)와 비연결 그래프(Disconnected Graph)

• 연결 그래프(Connected Graph)
• 무방향 그래프에 있는 모든 노드에 대해 항상 경로가 존재하는 경우
• 비연결 그래프(Disconnected Graph)
• 무방향 그래프에 있는 특정 노드에 대해 경로가 존재하지 않는 경우

사이클(Cycle)과 비순환 그래프(Acyclic Graph)

• 사이클(Cycle)
• 단순 경로의 시작 노드와 종료 노드가 동일한 경우
• 비순환 그래프(Acyclic Graph)
• 사이클이 없는 그래프

완전 그래프(Complete Graph)

• 그래프의 모든 노드가 서로 연결되어 있는 그래프

순차 탐색(Sequential Search) 이란?

• 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교하여 원하는 데이터를 찾는 방법

순차 탐색(Sequential Search) 구현

def sequential_search(data, search):
    for index in range(len(data)):
        if data[index] == search:
            return index
    return -1

순차 탐색(Sequential Search) 시간 복잡도

• 최악의 경우 리스트의 길이가 n일 때, n번 비교해야한다.
• O(n)

이진 탐색(Binary Search) 이란?

• 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법
• 정렬이 되어있는 배열에서 특정한 값을 찾아내는 알고리즘이다.

분할 정복 알고리즘과 이진 탐색

• 분할 정복 알고리즘(Divide and Conquer)
• Divide: 문제를 하나 또는 둘 이상으로 나눈다.
• Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않으면 다시 나눈다.
• 이진 탐색(Binary Search)
• Divide: 리스트를 두 개의 서브 리스트로 나눈다.
• Conquer
• 검색 할 숫자(search) > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
• 검색 할 숫자(search) < 중간값 이면, 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.

이진 탐색(Binary Search) 구현

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

이진 탐색(Binary Search) 시간 복잡도

• n x $\frac{1}{2}$ x $\frac{1}{2}$ x $\frac{1}{2}$... = 1
• n x $\frac{1^k}{2}$ = 1
• n = $2^k$ = $log_2 n$ = $log_2 2^k$
• $log_2 n$ = k
• Big-O 표기법으로는 k + 1이 최종 시간복잡도이고 결국 O($log_2 n$ + 1)이기 때문에 시간 복잡도는 O($log_n$)

퀵 정렬(Quick Sort)란?

• 정렬 알고리즘의 꽃
• 기준점을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성한다.
• 각 왼쪽, 오른쪽의 데이터들은 재귀용법을 사용해서 위 과정을 반복한다.

퀵 정렬(Quick Sort) 이해

• 하나의 리스트를 기준점(pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽으로 분할하고, 기준점보다 큰 데이터는 오른쪽으로 분할한 다음, 정렬된 부분 리스트들과 기준점을 합하여 전체가 정렬된 리스트로 만들어준다.

퀵 정렬(Quick Sort) 구현

def quick_sort(data):
    pivot = data[0]
    left, right = list(), list()
    for i in range(1, len(data)):
        if pivot < data[i]:
            right.append(data[i])
        else:
            left.append(data[i])
    return quick_sort(left) + [pivot] + quick_sort(right)
    
    
# list comprehension을 이용하여 간단하게 작성하기
def quick_sort(data):
    pivot = data[0]
    left, right = list(), list()
    left = [item for item in data[1:] if pivot > item]
    right = [item for item in data[1:] if pivot < item]
    return quick_sort(left) + [pivot] + quick_sort(right)

퀵 정렬(Quick Sort) 시간 복잡도

• 시간복잡도는 O(nlogn), 병합정렬과 유사하다.
• 최악의 경우
• 맨 처음 pivot이 가장 작거나 가장 크면 모든 데이터를 비교하기 때문에 시간복잡도가 O(n^2)이 된다.

병합 정렬(Merge Sort)란?

• 분할 정복 알고리즘중 하나
• 재귀용법을 활용한 정렬 알고리즘
1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다

분할 정복이란?

• 분할 정복
• 문제를 나눌 수 없을 때까지 나누어서 각각을 풀어 다시 합병하여 문제의 답을 얻는 알고리즘
• 하양식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
• 문제를 잘게 쪼갤 때 부분 문제는 서로 중복되지 않는다.

병합 정렬(Merge Sort) 이해

• 하나의 리스트를 두개의 리스트로 분할하고 분할된 리스트를 정렬한다음 두 개의 정렬된 리스트를 합하여 정렬된 전체 리스트로 만드는 방법
• 병합 정렬의 단계
1. 분할(Divide): 입력 배열을 같은크기의 2개의 부분 배열로 분할한다.
2. 정복(Conquer): 부분 배열을 정렬한다.
3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

병합 정렬(Merge Sort) 구현

def merge_split(data):
    divide = len(data)/2 # 리스트를 반으로 나누기 위한 변수
    left = merge_split(data[:divide]) # 재귀함수를 이용하여 분할이 안될 때 까지 분할
    right = merge_split(data[divide:])
    return merge(left, right)
    
def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0
    
    # left / right가 아직 남아있을 때
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1
    
    # left만 남아있을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
        
    return merged

병합 정렬(Merge Sort) 시간 복잡도

• 단계의 깊이를 depth라고 하고 i로 놓고, 가장 윗 단계는 0으로 정한다.
• 다음 그림은 n/2^2는 2단계 깊이라고 정해놓는다.
• 각 단계에는 2^i개의 노드가 있다.
• 따라서, 각 단계는 항상 2^i * n/2^i = O(n)
• 단계는 항상 logn개 만큼 만들어진다.
• 따라서 시간 복잡도는 O(n) * O(logn) = O(nlogn)이 된다.

삽입 정렬(Insertion Sort)란?

• 삽입 정렬은 두 번째 인덱스부터 시작한다.
• 해당 인덱스의 데이터 값을 앞에있는 데이터부터 비교하여 삽입할 위치를 지정한 후 자료들을 뒤로 이동시켜 해당 자리에 삽입하는 알고리즘

삽입 정렬(Insertion Sort) 알고리즘 구현

1. 첫 번째 반복문 루프는 데이터의 마지막이 자동으로 정렬되기 때문에 데이터의 수 -1로 정해준다. ex) for index in range(len(data) - 1)
2. 두 번째 반복문 루프는 현재 인덱스 + 1 부터 시작해서 앞으로 이동한다. ex) for index2 in range(index + 1, 0, -1)
3. 반복문을 돌며 현재 데이터가 앞의 데이터보다 값이 작다면 데이터를 교환해준다.

def insertion_sort(data):
    for index in range(len(data) - 1):
        for index2 in range(index + 1, 0, -1):
            if data[index2] > data[index2-1]:
                data[index2], data[index2-1] = data[index2-1], data[index2]
            else:
                break;
    return data

삽입 정렬(Insertion Sort) 시간 복잡도

• 버블정렬 알고리즘에는 for문이 두 개 들어가니까 시간복잡도는 O(n^2)
• 최악의 경우, n*(n-1)/2
• 완전 정렬이 되어있는 상태라면 최선은 O(n)