코르시카's Blog

참조 : www.fun-coding.org/Chapter21-backtracking-live.html 파이썬과 컴퓨터 사이언스(고급 알고리즘): 백 트래킹 기법의 이해 - 잔재미코딩 1. 백 트래킹 (backtracking)¶ 백트래킹 (backtracking) 또는 퇴각 검색 (backtrack)으로 부름 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략 해를 찾기 위해, 후보군에 제약 조건을 www.fun-coding.org

■ 프림 알고리즘 1) 정의 : 시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법 > 앞단계에서 만들어진 MST(Minimum spanning tree)의 인접 정점 중, 최소 간선으로 연결된 정점을 선택하여 트리를 확장(낮은 가중치 선택) > 트리가 V-1의 간선을 가질 때 까지 반복 > 시간복잡도 : O(V^2), 적은 노드 V 일 때 유리 2) 사용 그래프 구조 : > 인접행렬 ( 노드에 시간복잡도가 비례하므로! ) ■ 알고리즘 def get_min_node(node_num, visited, distances): # 임의의 미방문 노드 설정 for i in range(node_num): if not visited[i]: v = i break for i in range(node_nu..

■ 플로이드와샬 1) 정의 : 3중 for문을 통해 모든 정점사이의 최단 경로를 찾는 탐색 알고리즘 > (다대다 정점간 최단경로 모두 찾아야 할 때) > 최대 O(N^3) 시간복잡도 > 간선모두 탐색하며 dynamic 하게 업데이트 하므로 인접행렬로 구현 ■ 과정 1) 한 노드에서 다른 노드로 갈 수 있으면 최소 비용 / 간선이 없으면 INF로 초기 배열을 설정 2) 3중 for문을 통해 "거쳐가는 정점"을 기준으로, 다른 경로를 선택할 때 비용이 줄면, 값을 갱신 (다이나믹 프로그래밍) 3) 1~2 반복으로 모든 정점 사이의 최단경로를 탐색 1) 초기 배열 세팅 INF = float('inf') adj = [ [0, 5, INF, 8], [7, 0, 9, INF], [2, INF, 0, 4], [INF..

■ 그래프 정리 다음 참조 : korshika.tistory.com/42 graph(map) 구현(python) ■ 그래프 1) 기본 구조 노드 - '정점' 이라고도 함 간선 - 노드 사이의 도로 ■ 예시 그래프 ■ 그래프 표현법 인접 행렬 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식 > 이름이 "행렬"이기 korshika.tistory.com ■ 크루스칼 알고리즘 1) 정의 : 최소 비용으로 모든 그래프가 cycle이 없도록 연결되게 하는 연결방식을 찾는 알고리즘 > 존재하는 간선들 중 선택 된 간선의 개수는 노드V 간선E 일시, V-1 개가 선택 됨 2) 사용 그래프 구조 : > 인접리스트 사용 > 필요한건 순위로 정렬된 간선 비용과 그것을 이루는 노드이므로, 필요한 데이터만 담겨있는 인접리..

■ 이진 탐색 1) 정의 : 배열 전체의 중간값을 target 값과 비교 중간값이 target 값보다 크면 왼쪽 부분만 선택 왼쪽부분의 중간값을 다시 target 과 비교 ■ 코드 구현 > plain 절차지향 def binary_search(m_list, target): m_list.sort() left = 0 right = len(m_list)-1 while left target: right = mid - 1 else: left = mid + 1 return False target = 25 m_list = [30, 94, 27, 92, 21, 37, 25, 47, 25, 53, 98, 19, 32, 32, 7] print(binary_search(m_list, target)) > 재귀 def binar..

■ 다익스트라 알고리즘 1) 정의 : 자료구조로 graph 사용, " 노드 + 가중치를 가진 간선 "을 이용하여 최단경로를 계산 2) graph 자료구조 참조 참조 : korshika.tistory.com/42?category=957674 3) 시간복잡도 : O( E * log(E) ) ≒ O( E * log( V) ) > "최대의 경우" 모든 간선 E에 대해서 dist_history= [ ]가 한번씩 계산이 되기 때문에 간선을 queue에 작업하는 평균 시간 복잡도 O( log(E) )를 곱하면 최대 O( E * log(E) ) 에 비례, > 일반적으로 노드는 간선보다 적기 때문에, O( E * log( V) ) 라고 쓸 수도 있다 ■ 코드 구현 1) 코드 이해코드 설명 참조 : Link 2) 코드 -..

참조 : cyc1am3n.github.io/2019/04/26/bfs_dfs_with_python.html [Daily PS] 파이썬으로 구현하는 BFS와 DFS 파이썬으로 BFS와 DFS를 구현하는 내용입니다. cyc1am3n.github.io map 글 참조 2021.03.25 - [알고리즘/탐색] - map 구현(python) ■ BFS (Breadth First Search) 1) 정의 : 너비우선 탐색 탐색점 노드와 같은 depth에 있는 노드부터 queue 이용 먼저 탐색 > queue 이용 > 현재 노드에서 인접한 노드 먼저 탐색 > 복잡도 : O(N) // OS 상의 이유로 BFS가 성능이 조금 더 좋다 // 성능의 이유로 재귀보다는 자료구조 이용한 탐색 추천 graph_list = {1:..

■ 그래프 1) 기본 구조 노드 - '정점' 이라고도 함 간선 - 노드 사이의 도로 ■ 예시 그래프 ■ 그래프 표현법 인접 행렬 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식 > 이름이 "행렬"이기 때문에 모든 노드에 대응하는 정보를 가짐 > 모든 노드의 연결 상태를 기록 > 구현이 간단 > 간선 값 종류 ① 0 / 1 로 비연결 / 연결 ② inf / integer 로 비연결 / 연결(w 가중치) graph = [ [0, 7, 5], [7, 0, float('inf')], [5, float('inf'), 0] ] 노드 V개, 간선 E개의 경우 시간복잡도 ① 특정 노드(i, j) 연결 여부 0 / 1 OR inf / integer 확인하여 O(1) ②특정 노드에 연결된 노드 탐색 한 노드 전체를 ..