우노

들어가기 앞서, 일반적인 피보나치 재귀 함수 코드는 아래와 같습니다. def fibo(x): if (x == 1 or x==2): return x else: return fibo(x-1) + fibo(x-2) 만약, 위와 같은 피보나치 재귀 함수를 사용해 f(6)을 구한다면, f(3) 몇 번 호출될까요? f(3)은 아래와 같이, 3번 호출됩니다. f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(2) f(1) f(4) f(3) f(2) f(1) f(2) 따라서, 위와 같이 단순히 재귀 함수를 통해 매번 계산하는 방식은, 비효율적입니다. f(n) 에서 n 이 커질수록, 반복해서 호출하는 수가 많아지기 때문입니다. 피보나치 재귀 함수의 시간 복잡도는 O(2^n) 입니다. 따라서, 이..

선택 정렬 개념 정렬 되지 않은 데이터들 중 가장 작은 데이터를 선택하고, 정렬 되지 않은 데이터들 중 가장 왼쪽에 있는 데이터와 교환하는 알고리즘입니다. 특징 시간복잡도는 현재 데이터의 정렬 상태와 상관이 없습니다. 시간복잡도 항상 O(N^2) 매번, 정렬 되지 않은 데이터들을 비교 연산하며, 가장 작은 수를 찾습니다. N + (N - 1) + (N - 2) + … + 2 = N x (N-1 ) / 2 가장 작은 수를 찾아서 데이터를 교환합니다. N - 1 두 시간 복잡도를 더하면, O(N^2) 가 됩니다. 구현 코드 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j i..

DFS 모든 경로를 전부 탐색할 경우에 사용됩니다. 또는, 경로 이동 시 가중치가 붙거나 제약이 있을 경우에 사용됩니다. BFS 최단 경로만 탐색할 경우에 사용됩니다.

DFS DFS 는 스택 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같습니다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 스택의 최상단 노드와 인접한 노드들을 탐색하며, 방문하지 않은 인접 노드를 스택에 삽입하고 방문 처리한 뒤, 2번 과정을 재귀적으로 다시 실행합니다. 만약, 최상단 노드와 인접한 노드들 중 방문할 수 있는 노드가 없다면, 최상단 노드를 제거합니다. 2번의 과정을 더 이상 수행할 수 없을때까지 반복합니다. BFS BFS 는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같습니다. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다. 큐의 최하단 노드를 제거하며, 해당 노드와 인접한 노드들을 탐색하고, 방문하지 않은 인접 노드들을 전부 큐에 삽입한 뒤 방문 처리를..

들어가기 앞서, 코딩 테스트에서, 문제의 제한 시간은 일반적으로 1~5초 가량이다. 일반적인 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 1초에 실행할 수 있는 연산량은 1억번이다. 따라서, 문제를 풀기 전, 문제의 시간 복잡도를 확인한다면, 얼마나 효율적인 알고리즘을 작성해야하는지 눈치 챌 수 있다. 예를 들어, 주어진 N의 범위가 최대 5,000이며, 주어진 제한 시간이 1초라면, 시간 복잡도가 O(N^3)인 알고리즘의 연산 횟수는 10억을 넘어가며, 10초 이상의 시간이 걸리므로, 사용하기 어렵다. N 의 범위와 시간 복잡도에 따른 연산 횟수 N 의 범위가 1,000 일 경우 O(N) : 1,000 O(NlogN) : 10,000 O(N^2) : 1,000,000 O(N^3) : 1,000,000..

그래프란? 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조를 의미합니다. 그래프 탐색이란? 하나의 정점으로부터 시작하여, 차례대로 모든 정점들을 한 번씩 방문하는 것을 의미합니다. 너비 우선 탐색(BFS, Breadth First Search)이란? 루트 노드 또는 임의의 노드에서 시작하여, 일정 노드와 인접한 노드들을 우선으로 탐색하는 방법입니다. 주로, 어떤 두 노드 사이의 최단 경로를 구할 때 사용되며, 주로, 큐(Queue)라는 자료구조를 사용해 구현됩니다. 너비 우선 탐색 예제 BFS 는, 아래와 같은 간단한 알고리즘에 의해 작동됩니다. 큐에서 하나의 노드를 꺼냅니다. 해당 노드와 연결된 노드들 중, 방문하지 않은 노드들을 큐에 삽입하며, 방문 처리합니다. 반복합니다...

최대 유량 문제 (Maximum Flow Problem) 특정한 지점에서 다른 지점으로, 얼마나 많은 유량(flow)을 동시에 보낼 수 있는지 계산하는 문제입니다. 네트워크 플로우(Network Flow)라고도 합니다. 기본 용어 용량 (Capacity) c(u, v) : 정점 u 에서 v 로 전송할 수 있는 최대 용량 유량 (Flow) f(u, v) : 정점 u 에서 v 로 실제 흐르고 있는 유량 잔여 용량 (Residual Capacity) r(u, v) = c(u, v) – f(u, v) 간선의 용량과 살제로 흐르는 유량의 차이 소스 (Source) s : 모든 유량이 시작되는 정점 싱크 (Sink) t : 모든 유량이 도착하는 정점 증가 경로 소스에서 싱크로 유량을 보낼 수 있는 경로 기본 속성 ..

다익스트라(Dijkstra) 최단 경로 알고리즘이란? 다익스트라(Dijkstra) 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘입니다. ‘음의 간선'이 없을 때 정상적으로 동작합니다. 물론, 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로, 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 합니다. 다익스트라 최단 경로 알고리즘은 그리디 기반입니다. 그리디 매번 ‘가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복합니다. 구체적인 동작 과정 출발 노드를 설정한 뒤, 방문합니다. 최단 거리 배열을 초기화합니다. 아직 방문하지 않은 전체 노드들 중에서, 최단 거리..

개요 PageRank 개요 PageRank 란? 하이퍼링크 네트워크란? PageRank 의 응용 PageRank 의 핵심 아이디어 Random Walk Interpretation PageRank 심플버전 PageRank 심플버전 설명 Power Iteration PageRank 오리지널 PageRank Score 심플 버전의 문제점 Random Teleport PageRank 오리지널 버전 설명 PageRank 란? Google 검색 엔진의 기반 알고리즘이다. 하이퍼링크를 이용해 웹 페이지 중요도를 측정한다. 하이퍼링크 네트워크란? Web 을 Directed graph 로 보는 형태이다. Node : 웹페이지 Edge : 하이퍼링크 PageRank 의 응용 모든 그래프에서, 노드의 중요도 측정에 사용한다..