시간복잡도 -> 실행 시간이라는 관점에서 알고리즘의 효율 측정 -> 문제를 해결하려고 할 때마다 시간복잡도를 분석하는 습관을 들이면 좋은 개발자가 될 수 있다 -> 이때 가장 중요한 건 연산자의 숫자 혹은 연산과정의 수 -> 예를 들어 N이라는 인자가 주어졌을 때 1부터 N까지를 더하는 함수를 sumOfN을 정의 def sumOfN(N): theSum = 0 for i in range(1,N+1): theSum += i return theSum ->함수 sumOfN에서 주요 연산 횟수를 보면 아래와 같습니다 def sumOfN(N): theSum = 0 for i in range ( 1, N+1): theSum += i return thesSum 함수 sumOfN의 시간 복잡도는 아래와 같이 표시 가능 ..

탐욕 알고리즘의 이해 1. 탐욕 알고리즘 이란? - Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움 - 최적의 해에 가까운 값을 구하기 위해 사용됨 - 여러 경우 중 하나를 결정해야할 때마다, **매순간 최적이라고 생각되는 경우를 선택**하는 방식으로 진행해서, 최종적인 값을 구하는 방식 2. 탐욕 알고리즘 예 문제1: 동전 문제 - 지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오. - 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능 - 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨 문제2: 부분 배낭 문제 (Fractional Knapsack Problem) - 무게 제한이 k인 배..

최소 신장 트리의 이해 1. 프림 알고리즘 (Prim's algorithm) - 대표적인 최소 신장 트리 알고리즘 - Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘) - 프림 알고리즘 - 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식 - Kruskal's algorithm 과 Prim's algorithm 비교 - 둘다, 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) - Kruskal's algorithm은 가장 가중치가 작은 간선부터 선택하면서 M..

음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다. 방향그래프, 무방향 그래프 모두 상관 없으나, 가중치가 음수인 edge가 단 하나라도 존재하면 이 알고리즘은 사용할 수 없다. 에츠허르 다익스트라가 고안한 알고리즘으로, 그가 처음 고안한 알고리즘은 O(V^2)O(V2)의 시간복잡도를 가졌다. 이후 우선순위 큐(=힙 트리)등을 이용한 더욱 개선된 알고리즘이 나오며, O((V+E)logV)O((V+E)logV)(V는 정점의 개수, E는 한 정점의 주변 노드)의 시간복잡도를 가지게 되었다.[1] O((V+E)logV)O((V+E)logV)의 시간복잡도를 가지는 이유는 각 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 O(..

백 트래킹 기법의 이해 1. 백 트래킹 (backtracking) - 백트래킹 (backtracking) 또는 퇴각 검색 (backtrack)으로 부름 - 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략 - 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법 - 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보군)를 상태공간트리(State Space Tree)를 통해 표현 - 각 후보군을 DFS 방식으로 확인 - 상태 공간 트리를 탐색하면서,..

프림 알고리즘 파이썬 코드 0. 모든 간선 정보를 저장 (adjacent_edges) 1. 임의의 정점을 선택, '연결된 노드 집합(connected_nodes)'에 삽입 2. 선택된 정점에 연결된 간선들을 간선 리스트(candidate_edge_list)에 삽입 3. 간선 리스트(candidate_edge_list)에서 최소 가중치를 가지는 간선부터 추출해서, - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 스킵함(cycle 발생을 막기 위함) - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리(mst)'에 삽입 - 해당 간선에 연결된 인접 정점의 간선들 중, '연결된 노드 집합(conn..