알고리즘 (12) 썸네일형 리스트형 [알고리즘 이론] 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.. [백준] 10026 적록색약 파이썬 풀이 안녕하세요? 닉네임간편입니다. 이번 시간에는 백준 10026 적록색약 문제를 풀어보겠습니다. 풀이는 파이썬으로 했고, Python3 기준으로 시간이 136ms가 나와 Pypy3으로는 돌리지 않았습니다. [문제 링크] https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. 접근방식 NxN 그리드의 모든 구간을 탐색해서 영역을 구해야 하기 때문에, 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 모두 사용할 수 있습니다. 그러나 전 좀 더.. [알고리즘 이론] 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)을 의미합니다. 정점은 어떤 지점을 말하는 것으로, 위 그림에서 사람에 해당됩니다. 간선은 정점을 연결한 선으로, 위 그림에선 점선이 됩니다. 그래프는 정점과 간선들로 구성되어있으며, 정점이나 간선에 가중치 등을 부여해 다양한 방식으로 활용할 수 있습니.. 이전 1 2 다음
