지난 시간까지 시간 복잡도 O(N ^ 2)인 선택 정렬, 버블 정렬, 삽입 정렬 알고리즘을 공부했습니다. 이어서 평균 시간 복잡도 O(N * logN)인 퀵 정렬에 대해서도 공부하는 시간을 가졌습니다. 이번 시간에 다룰 내용은 병합 정렬(Merge Sort) 입니다. 병합 정렬도 대표적인 '분할 정복' 방법을 채택한 알고리즘입니다. 결과적으로 퀵 정렬과 동일하게 O(N * logN)의 시간 복잡도를 가집니다. 다만 퀵 정렬은 피벗 값에 따라서 편향되게 분할할 가능성이 있다는 점에서 최악의 경우 O(N ^ 2)의 시간 복잡도를 가진다고 하였습니다. 병합 정렬은 정확히 반절씩 나눈다는 점에서 최악의 경우에도 O(N * logN)을 보장합니다. 개념 자체도 굉장히 쉽기 때문에 퀵 정렬을 이해하신 분들이라면 어..

우리들이 흔히 알고 있는 정렬 알고리즘인 선택 정렬, 버블 정렬, 삽입 정렬 알고리즘은 모두 시간 복잡도 O(N^2)을 가지는 알고리즘이었습니다. 사실 이러한 복잡도를 가지는 알고리즘은 데이터의 갯수가 10만 개만 넘어가도 일반적인 상황에서 사용하기가 매우 어려운 알고리즘입니다. 그렇기 때문에 더욱 빠른 정렬 알고리즘이 사용될 필요가 있습니다. 그 대표적인 빠른 알고리즘이 바로 퀵정렬 알고리즘입니다. 퀵정렬은 대표적인 '분할 정복' 알고리즘으로 평균 속도가 O(N * logN) 입니다. 퀵 정렬은 하나의 큰 문제를 두개의 작은 문제로 분할하는 식으로 빠르게 정렬합니다. 더 쉽게 말하자면 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눕니다. "특정한 값을 기준으로 큰 숫자..

Introduction 알고리즘 (Algorithm) ※ 주어진 일(또는 문제)을 처리하여 원하는 결과(output)를 얻기까지의 과정을 명확하고 단계적으로 서술한 것 예) 조리법 : 음식을 만드는 알고리즘 길안내 : 낯선 도시에서 길을 찾아가기 위한 알고리즘 세탁기조작법 : 세탁기 조작을 위한 알고리즘 악보 : 음악연주를 위한 알고리즘 ※ 알고리즘을 찾는 작업의 효시 현대의 컴퓨터가 개발되기 훨씬 전부터 수학의 한 분야로 시작 ※ 목표 특정 유형의 모든 문제들을 해결할 수 있는 방법을 서술하는 일련의 명령들을 찾는 것 ※ 알고리즘의 예 : 유클리디안 알고리즘(Euclidean algorithm) 그리스 수학자 유클리드가 발견함 ※ 일단 작업을 수행하기 위한 알고리즘을 찾은 다음에는 알고리즘이 기초하고 ..

플로이드-워샬(Floyd-Warshall) 알고리즘 모든 정점들간의 상호 최단거리(All Pairs Shortest Path)를 구하는 알고리즘이다. 응용 예시로는 Road Atlas, 네비게이션 시스템, 네트웍 커뮤니케이션 등이 있다. 그렇다면 플로이드-워샬이 무엇이고, 왜 쓰이는지 알아보자. 앞서 배운 다익스트라, 벨만-포드 알고리즘은 시작점이 주어지면 하나의 정점에서 다른 모든 정점으로의 최단경로를 구했다면, 플로이드-워샬 알고리즘은 모든 정점으로부터 모든 정점으로의 최단경로를 구하는대 사용된다. 알고리즘 구현 방식도 다르다. 다익스트라 알고리즘은 vertex set에서 가장 작은 노드를 꺼내서 하나씩 더하면서 최소값을 찾아가는 Greedy한 알고리즘을 사용하지만, 플로이드-워샬은 각 노드를 하나씩..

벨만-포드(Bellman-Ford) 알고리즘 벨만포드 알고리즘도 그래프에서 최소비용을 구할 수 있는 알고리즘 중에 하나이다. 벨만포드 알고리즘은 최소비용을 구하는 알고리즘 중에서도, 한 정점에서 다른 모든 정점으로 가는데 걸리는 최소비용을 구하는데 사용하는 알고리즘이다. 이 점은 다익스트라와 동일하다. 그런데 벨만포그와 다익스트라 알고리즘 중에서 언제 무엇을 사용해야 하는 걸까?? 그리고 시간 복잡도에서 말하겠지만, 벨만포드 알고리즘은 일반적으로 다익스트라 알고리즘보다 더 시간이 오래 걸리는 탐색 방법인데 굳이 이 방법을 써야할까 ?? 우선 벨만포드의 특징 부터 살펴보자 먼저 다익스트라와 마찬가지로 시작점이 존재한다. 하지만 벨만포드의 가장 중요한 포인트는 가중치가 0보다 작을 수 있다는 점이다. 음의 ..

다익스트라Dijkstra 알고리즘 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 알고리즘은 '음의 간선(0보다 작은 값을 가지는 간선)'이 없을 때 정상적으로 동작한다. 다익스트라 알고리즘은 프림 알고리즘 과 동작방식이 비슷하다. 다만 프림알고리즘은 단순히 간선의 길이를 이용해 어떤 간선을 먼저 연결할지 결정하는데 반해, 다익스트라 알고리즘은 '경로의 길이'를 감안해서 간선을 연결한다.다익스트라의 최단 경로 탐색 알고리즘은 사이클이 없는 방향성 그래프에 한해서만 사용 가능. 1. 다익스트라 알고리즘 수도코드 및 알고리즘 원리 S = r로부터의 거리가 계산되고 최단경로가 계산된 집합이다..

최단경로 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미합니다. 다양한 문제 상황 각 지점은 그래프에서 노드(Vertex)로 표현 지점 간 연결된 도로는 그래프에서 간선(Edge)으로 표현 ※조건 1. 유향 그래프 노드(Vertex)와 노드 사이에는 방향성이 있는 간선(Edge)이 주어져야 하며, 무향 그래프인 경우에는 각 간선에 대해 양쪽으로 유향 간선이 있는 유향 그래프로 생각할 수 있다. 즉, 무향 간선(u, v)는 유향 간선 (u, v)와 (v, u)를 의미한다고 가정한다. 무향인 경우에는 최단 경로를 구할 수 없다. 2. 간선 가중치 노드와 노드 사이의 간선에는 무조건 가중치가 부여되어야 한다. ※두 정점 사이의 최단 경로 1. 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 ..

트리를 이용한 처리 같은 집합의 원소들은 하나의 트리로 관리한다. - 자식 노드가 부모 노드를 가리킨다. 트리의 루트를 집합의 대표 원소로 삼는다. ※연결 리스트와 차이점 1) 자식 노드가 대표노드가 아닌 부모노드를 가리킨다. 2) Binary 트리가 아니여서 자식도드를 여러개 가질 수 있다. 3) 연결 리스트에서 Find-Set(x)의 수행시간은 O(1)이였지만, 트리에서 수행시간은 트리의 depth(깊이)와 연관이 있다. 4) 연결 리스트는 대표노드를 가리키는 Point, 다음노드를 가리키는 Point 두개의 포인터를 가진다. 트리에서는 부모노드를 가리키는 Point하나만 가지게 된다. 따라서, 공간적 효율성, 포인터 수정에 효율적, Find-Set(x)에서는 비효율적 이게 된다. 1) Make-Se..

상호 배타적 집합의 처리 상호배타적 집합만을 대상으로 한다. 이때 교집합은 제외된다. Union(합집합)을 지원해주는 연산 작업들에는 ■ Make-Set(x) : 원소 x로만 이루어진 집합을 만든다. ■ Find-Set(x) : 원소 x를 가지고 있는 집합을 알아낸다. ■ Union(x,y) : 원소 x를 가진 집합과 원소 y를 가진 집합의 합집합을 만든다. 집합을 처리하는 방법에는 연결리스트를 이용하는 방법과 트리를 이용하는 방법이 있다. 연결 리스트를 이용한 상호 배타적 집합의 처리 방법을 이해한다. 연결 리스트를 이용해 집합을 처리하는 연산들의 수행 시간을 분석한다. 트리를 이용한 상호 배타적 집합의 처리 방법을 이해한다. 트리를 이요해 집합을 처리하는 연산들의 수행 시간을 분석한다. 연결 리스트를..