시간복잡도(time complexity) 가장 널리 사용되는 알고리즘의 수행시간 기준 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것. 기본적인 연산 : 더 작게 쪼갤 수 없는 최소 크기의 연산 ex) 두 부호 있는 32비트 정수의 사칙연산 두 실수형 변수의 대소 비교 한 변수에 다른 변수 대입하기 중첩된 반복문의 수행 횟수를 계산 (상수는 대개 무시) 시간 복잡도가 높다 = 입력의 크기가 증가할 때 알고리즘 수행시간이 더 빠르게 증가한다 입력 크기가 충분히 작을 때 시간 복잡도가 높은 알고리즘이 더 빠르게 동작할 수도 있다. = 시간 복잡도는 완전한 속도의 기준은 아니다. 입력의 종류에 따라 수행시간이 달라지는 경우 고려하기 위해 최선/최악/평균적인 경우에 ..

최소 신장 트리의 이해 1. 신장트리란? Spanning Tree, 또는 신장 트리라고 불러옴(Spanning Tree가 보다 자연스러움) 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성(Cycle이 없는 구조)을 만족하는 그래프 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야 함 모든 노드가 서로 연결 트리의 속성을 만족시킴(사이클이 존재하지 않음) 2. 최소 신장 트리 Minimum Spanning Tree, MST라고 불리움 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭함 3. 최소 신장 트리 알고리즘 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함 대표적인 최소 신장 트리 알고리즘 Kruskal's algorith..

1. 최단 경로 문제(Shortest Path Problem)란? 두 노드를 잇는 가장 짧은 경로를 찾는 문제 가중치 그래프(Weighted Graph)에서 간선(Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 최단 경로 문제 종류 단일 출발 및 단일 도착(single-source and single-destination shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u에서 출발, 또다른 특정 노드 v에 도착하는 가장 짧은 경로를 찾는 문제 단일 출발(single-source shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 예를 들어 A, B, C, D..

1. 탐욕 알고리즘(Greedy algorithm)이란? 최적의 해에 가까운 값을 구하기 위해 사용됨(완벽하게 최적의 해는 아님) 여러 경우 중 하나를 결정해야 할 때마다, 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구하는 방식 2. 탐욕 알고리즘 예 문제 1 : 동전 문제 지불해야 하는 값이 4720원일 때 1원 50원 100원 500원 동전으로 지불하는 경우 중 동전의 수가 가장 적은 경우를 구하시오 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 생각하면 됨 def min_coin_count(value, coin_list): #value는 지불값 total_count = 0 details =..

문제 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다. 숫자가 쓰인 카드들이 N x M의 형태로 놓여있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 먼저 뽑고자 하는 카드가 포함되어 있는 형태를 선택한다. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다 내 풀이 def card_game(height, width, card_list): min = 0 for i in..

1. 깊이 우선 탐색(Depth-First Search : DFS) (방향 상관없이) 자신과 연결된 노드의 가장 아래 레벨까지 내려가 탐색하고 그 노드가 리프 노드이면 상위 노드의 다른 리프 노드를 먼저 탐색하고 올라가는 방식 BFS와 탐색의 순서가 다르다 2. DFS 알고리즘 구현 자료구조 스택과 큐를 활용함 need_visit 스택과 visited 큐, 두 개의 자료구조를 생성 스택이기 때문에 pop_back()으로 앞이 아니라 뒤에 있는 데이터를 먼저 가져옴 BFS 자료구조는 두 개의 큐를 활용하고 DFS는 스택과 큐를 활용한다는 차이가 있음을 인지해야 한다 def dfs(graph, start_node): need_visit, visited = list(), list() need_visit.app..

1. BFS와 DFS 란? 대표적인 그래프 탐색 알고리즘(트리 - 사이클이 없는 그래프) 너비 우선 탐색(Breadth-First Search) : 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식 깊이 우선 탐색(Depth-First Search) : 정점의 자식들을 먼저 탐색하는 방식 BFS/DFS 방식 이해를 위한 예제 BFS 방식 : A - B - C - D - G - H - I - E - F - J 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들(형제 노드들)을 먼저 순회함 DFS 방식 : A - B - D - E - F - C - G - H - I - J 한 노드의 자식을 타고(왼쪽으로) 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회..

1. 그래프(Graph) 란? 그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node)와 간선(Edge)로 표현하기 위해 사용 2. 그래프(Graph) 관련 용어 노드(Node) : 위치를 말함, 정점(Vertex)라고도 함 간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨(link 또는 branch라고도 함) 인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드) 참고 용어 정점의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 (ex. 2차) 진입 차수(In-Degree) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(Out-Degree) : 방향 그래프에서 외부로 향하는 간선의 수 ..