알고리즘/알고리즘 이론 (9) 썸네일형 리스트형 [알고리즘 이론] 6. 시간복잡도 1. 알고리즘 수행 시간의 척도 알고리즘 수행 시간을 지배하는 것은 반복문입니다. 입력의 크기가 커질수록 반복문이 수행되는 횟수가 알고리즘 수행 시간을 지배하게 되고, 따라서 반복문이 수행되는 횟수로 알고리즘의 수행 시간을 측정합니다. 따라서 이번 시간에는 다양한 알고리즘과, 그 알고리즘의 시간복잡도에 대해서 다루겠습니다. 2. 선형 시간 알고리즘(linear time) var count = 1 for (i in 1 until N) { count *= i } for (j in 1 until 50) { count += j } N의 값이 커짐에 따라 아래의 반복문에서 50만큼 반복하는 것은 크게 고려하지 않아도 됩니다. 따라서 이때 알고리즘의 수행 시간은 N에 정비례합니다. 이렇게 입력값에 정비례하여 수행 .. [자료구조 with 코틀린] 3. Queue 1. 개념 먼저 들어간 데이터가 먼저 나오는 자료구조입니다. FIFO(First In First Out)이라고도 합니다. 안드로이드에서 Looper를 사용할 때 메시지 큐에 사용되는 자료구조입니다. 2. 시간복잡도 a. 탐색 앞선 스택과 마찬가지로, 특정 데이터를 찾을 때까지 탐색해야 하므로 O(N)의 시간복잡도를 가집니다. b. 삽입 및 삭제 모두 O(1)의 시간복잡도를 가집니다. 3. 구현 LinkedList를 사용하여 구현하는 것이 좋습니다. 삽입 및 삭제에 O(1)의 시간복잡도를 가지기 때문입니다. class Queue { private var head : Node? = null inner class Node( var data: E, var next: Node? ) fun enqueue(item:.. [자료구조 with 코틀린] 2. Stack 1. 개념 나중에 들어간 데이터가 먼저 나오는 자료구조입니다. 이를 LIFO(Last In First Out)이라고도 합니다. 안드로이드 액티비티를 관리하는 데 사용되는 자료구조입니다. 2. 시간복잡도 1) 탐색 Random Access가 안 되며 특정 데이터를 찾을 때까지 탐색을 수행해야 하므로 O(N)의 시간복잡도를 가집니다. 2) 삽입 및 삭제 삽입 및 삭제에는 O(1)의 시간복잡도를 가집니다. 3. 공간복잡도 N개 만큼의 스택이 쌓이기 때문에 O(N)입니다. 4. 구현 구현하기에 앞서, 스택을 구현할 때에는 ArrayList를 사용하는 것이 좋습니다. ArrayList의 경우 index를 사용하면 마지막에 데이터를 추가하고 삭제하는 데 O(1)의 시간복잡도를 갖기 때문입니다. 따라서 전 Array.. [자료구조 with 코틀린] 1. LinkedList 1. 개념 하나의 노드에 데이터와 포인터가 있으며, 이를 연결하는 방식으로 데이터를 저장하는 선형 자료구조입니다. 2. 시간복잡도 1) 검색 논리적 저장 순서와 물리적 저장 순서가 다르기 때문에, 첫 노드부터 순회해서 탐색해야 합니다. 따라서 검색 시 O(N)의 시간복잡도를 가집니다. 2) 삽입 및 삭제 배열처럼 연속적으로 데이터가 저장된 것이 아니라 포인터를 사용했기에, 삽입과 삭제에 O(1)의 시간복잡도를 가집니다. 그러나 특정 데이터를 삭제하려는 경우, 이 데이터를 찾는 데 O(N)의 비용이 발생합니다. 3) 메모리 할당 새로운 노드가 추가될 때마다 추가로 할당됩니다. 즉, 런타임에 할당되며, 동적 메모리 할당이라고도 합니다. 3. 구현 class LinkedList { private var hea.. [알고리즘 이론] 5. 너비 우선 탐색(BFS) 안녕하세요? 닉네임간편입니다. 이번 시간에는 너비 우선 탐색에 대해 알아보겠습니다. 1. 너비 우선 탐색이란? 너비 우선 탐색(Breadth-First Search)은 시작점에서 가까운 정점 순서대로 탐색을 하는 알고리즘입니다. 위 그림을 예시로 들어 설명하겠습니다. 시작점은 정점 1이며, 동일한 거리에 있다면 왼쪽부터 방문하도록 하겠습니다. 1) 1 -> 2 -> 3 정점 1에 인접한 정점 2와 3을 먼저 방문합니다. 정점 3을 방문한 이후 정점 1에 인접한 간선이 없으므로 해당 단계의 탐색을 종료합니다. 2) 3 -> 4 -> 5 -> 6 정점 2와 3에 인접한 정점을 왼쪽부터 순서대로 방문합니다. 정점 6을 방문한 이후 정점 2, 3에 인접한 간선이 없으므로 이 단계의 탐색을 종료합니다. 3) 6 .. [알고리즘 이론] 4. 깊이 우선 탐색(DFS) 안녕하세요? 닉네임간편입니다. 저번 시간에는 그래프에 대해 알아보았습니다. 이번 시간에는 그래프를 이용한 탐색 알고리즘을 배워보겠습니다. 그래프의 탐색 알고리즘에서 가장 많이 사용되는 것에는 깊이 우선 탐색과 너비 우선 탐색이 있으며, 이번 시간에는 깊이 우선 탐색에 대해 알아보겠습니다. 1. 깊이 우선 탐색이란? 깊이 우선 탐색(Depth First Search)은 그래프의 모든 정점을 발견하는 방법 중 하나로, 이름 그대로 최대한 깊이 탐색한 이후 더 이상 탐색할 것이 없다면 그 이전으로 돌아가 탐색을 이어가는 것입니다. 위 그림을 예시로 설명하겠습니다. 현재 탐색을 정점 1에서부터 시작한다고 하겠습니다. 또한 인접한 간선이 여러 개일 경우 왼쪽을 먼저 탐색한다고 설정하겠습니다. 1) 1 -> 2 정.. [알고리즘 이론] 3. 그래프 안녕하세요? 닉네임간편입니다. 이번 시간에는 많이 사용되는 자료구조인 그래프에 대해 알아보겠습니다. 1. 그래프란? 그래프(graph)는 일종의 연결 관계를 나타내는 것으로써, 위 그림처럼 사람 간의 관계나 지하철 노선도 등이 현실에서 사용되는 그래프의 예시입니다. 수직적인 구조가 아니기 때문에 다양한 구조를 표현할 수 있어 많이 사용되는 자료구조입니다. 그래프는 기호로 G(V, E)로 표현되며 이때 V는 정점(vertex)을 의미하고 E는 간선(edge)을 의미합니다. 정점은 어떤 지점을 말하는 것으로, 위 그림에서 사람에 해당됩니다. 간선은 정점을 연결한 선으로, 위 그림에선 점선이 됩니다. 그래프는 정점과 간선들로 구성되어있으며, 정점이나 간선에 가중치 등을 부여해 다양한 방식으로 활용할 수 있습니.. [알고리즘 이론] 2. 그리디 알고리즘 안녕하세요? 닉네임 간편입니다. 이번 시간에는 그리디 알고리즘에 대해서 알아보겠습니다. 1. 그리디란? 탐욕법으로도 불리는 그리디(Greedy) 알고리즘은 답을 도출하기 위해서 수행되어야 할 동작들을 여러 부분으로 나눈 후, 각 부분마다 최선의 경우만 선택하는 알고리즘입니다. 즉, 어떤 선택을 할 때 지금 당장의 경우만 고려해 가장 최적의 답을 찾아내는 알고리즘입니다. 예를 들어 목표 액수를 지불할 때 필요한 최소 화폐 개수를 구하는 문제를 생각해볼 수 있습니다. 우리에게 5000원, 1000원, 500원, 100원이 있고, 7000원을 지불해야 한다고 가정하겠습니다. 그렇다면 이때 5000원을 선택하면 가장 금액이 높으면서 가장 적은 화폐 개수로 지불할 수 있으므로, 5000원을 선택해 지불합니다. 그.. 이전 1 2 다음
