클라우드 낚시꾼

시간 복잡도의 분류 위의 모토에 따르면, 시간 복잡도는 아래와 같이 3가지로 분류된다. 1. 최악 경우 시간 복잡도(worst case) 모든 입력에 대해서 기본 연산이 수행되는 최대 횟수 2. 최선 경우 시간 복잡도(best case) 모든 입력에 대해서 기본 연산이 수행되는 최소 횟수 3. 평균 경우 시간 복잡도(average case) 모든 입력에 대해서 기본 연산이 수행되는 평균 횟수 예제로 순차 탐색 알고리즘 각 시간 복잡도를 구해보자. 1. 최악 경우시간 복잡도(worst case) 모든 입력에 대해 가장 마지막에 탐색을 성공하는 N 2. 최선 경우 시간 복잡도(best case) 모든 입력에 대해 가장 첫 번째에 탐색을 성공하는 1 3. 평균 경우 시간 복잡도(average case) 평균 ..

대표적인 점근적 표기 대표적인 점근적 표기는 위와 같다. 사실, 말로는 이해하기 너무 어렵다. 점근적 표기에 대해서 더 알아보자. O(Big-O)-표기 (최악의 시간 복잡도) - O(Big-O) 표기의 정의 모든 n >= n0에 대해서 cg(n) >= f(n)인 양의 상수 n0와 c가 존재한다면, f(n) = O(g(n))이다. - O(Big-O) 표기의 의미 n0와 같거나 큰 모든 n에 대해서 f(n)은 cg(n)보다 크지 않다는 의미이다. 즉, f(n)은 cg(n)에 절대 미치지 못하며, 이때 g(n)을 f(n)의 상한이라고 한다. - f(n) = O(g(n))의 의미 n이 증가함에 따라 g(n)은 f(n)이 절대 미치지 못하는 점근적 상한이다. - Big-O 표기법을 찾는 방법 다항식에서 계수를 제..

그래프란? 그래프는 문제 또는 구조를 시각적으로 표현하기 위해 널리 사용되는 자료구조이다. 지하철 노선도와 SNS 관계망이 대표적인 그래프 활용 예시이다. 그래프는 어떻게 구성되어 있을까? 그래프는 정점과 간선으로 구성된다. 정점(vertex, node)은 그래프에서 표현하고자 하는 항목을 의미하고, 간선(edge)는 두 정점 사이의 관계를 의미한다. 두 정점이 간선으로 연결되어 있다면 인접(adjacent)하다고 한다. 서울 지하철 노선도를 그래프 관점으로 해석해보면 다음과 같다. 지하철 노선도에서 각 지하철 역은 그래프에서 표현하고자 하는 항목이기에 정점이 된다. 각 정점(지하철 역)을 이어주는 노선은 1호선, 2호선, 3호선.. 이라는 정점 사이의 관계를 형성하기에 그래프의 간선이 된다. 특히, 홍..

BFS를 쉽게 말하자면? 위 그래프의 시작 노드는 1 이고, 숫자가 낮은 노드부터 탐색한다고 가정하자. 이 가정 아래, 그래프를 가장 가까운 노드부터 탐색하면 1 -> 2 -> 3 -> 5 -> 4 -> 6 라는 결과를 얻을 수 있다. 이것이 BFS이다. BFS의 가장 주요한 모토는 "그래프를 가까운 노드부터 탐색하자." 라는 것을 잊지 말자! BFS 알고리즘 먼저, BFS를 구현하기 위해서는 FIFO 구조인 큐(Queue) 자료구조를 사용해야 한다. 인접한 노드를 반복적으로 큐에 넣게되면, 자연스럽게 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색을 진행하게 된다. 알고리즘의 정확한 동작방식은 아래와 같다. 1) 탐색 시작 노드를 Queue에 Enqueue 하고 방문 처리한다. 2) Front..