본문 바로가기

Algorithm/자료구조, 알고리즘34

[코딩 + 알고리즘 완주반] 24일차. 백트래킹 # 백트래킹 - 제약조건만족 문제에서 해를 찾기 위한 전략 - 해를 찾기 위해 조건을 점진적으로 체크하다가 해당 후보군이 제약조건을 만족할 수 없다고 판단하는 즉시 backtrack( 다시 이 후보군을 체크하지 않음) 하고 다른 후보군으로 넘어가 최적의 해를 찾는 방법 - 모든 경우의 수를 상태공간트리 (State Space Tree) 를 통해 표현 - 각 후보군을 DFS 방식으로 확인 - Promising : 해당 루트가 조건에 맞는지 검사하는 기법 - Pruning (가지치기) : 조건에 맞지 않으면포기하고 다른 루트로 바로 돌아서서 탐색의 시간을 절약하는 기법 # N-Queen 문제 N*N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 문제 퀸 : 수직, 수평, 대각선 이동 가능 Pr.. 2021. 4. 14.
[코딩 + 알고리즘 완주반] 23일차. 최소 신장 트리 - 프림 알고리즘 (Prim's algorithm) # 프림 알고리즘 시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 간선으로 연결된 정점을 택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방법 ( 크루스칼 알고리즘은 전체에서 가장 작은 간선) 1. 임의의 정점을 선택하여 연결된 노드 집합에 삽입 2. 선택한 정점에 연결된 간선들을 간선 리스트에 삽입 3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출해서 ( 전에 넣었던 간선들 포함 간선리스트에서 가장 최소인 값 ) - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합에 이미 있다면 skip (cycle 방지) - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합에 있지 않다면 해당 간선을 선택 ( 최소신장트리에 삽입 ) (해당 간선에.. 2021. 4. 13.
[코딩 + 알고리즘 완주반] 22일차. 최소 신장 트리 # 신장 트리 (Spanning Tree) 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 모든 노드 포함, 모든 노드 서로 연결, 사이클 존재하지 않음 # 최소 신장 트리 (Minimum Spanning Tree, MST) 가능한 신장 트리 중에서 간선의 가중치 합이 최소인 Spanning Tree Kruskal's algorithm(크루스칼 알고리즘), Prim's algorithm(프림 알고리즘) # Kruskal's algorithm(크루스칼 알고리즘) 가중치가 가장 작은 간선부터 연결 ( 사이클일 경우 넘어감 ) # Union-Find 알고리즘 - 사이클이 생기는지 확인하는 알고리즘 Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘 Di.. 2021. 4. 9.
[코딩 + 알고리즘 완주반] 21일차. 최단 경로 알고리즘 # 최단 경로 문제 두 노드를 잇는 가장 짧은 경로 찾기 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로 # 단일 출발 및 단일 도착 최단 경로 문제 특정 노드에서 특정 노드에 도착하는 가장 짧은 경로 찾기 # 단일 출발 최단 경로 문제 특정노드와 그래프 내 모든 노드 각각의 가장 짧은 경로 찾기 # 전체 쌍 최단 경로 그래프 내 모든 노드 쌍에 대한 최단 경로 찾기 # 다익스트라 알고리즘 - 너비우선 탐색(BFS)과 유사 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리 구하기 (단일 출발 최단 경로 문제) 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며, 최단 거리를 갱신 # 우선순위 큐를 활용한 다익스트라 알고리즘 초기 첫 정점의 거리는 0, 나머지는 무한대로 저장 우선.. 2021. 4. 9.
[코딩 + 알고리즘 완주반] 20일차. 탐욕 알고리즘 (Greedy algorithm) # 탐욕 알고리즘(Greedy Algorithm) 최적의 해에 가까운 값을 구하기 위해 사용 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행 # 문제1 ) 동전 문제 지불해야 하는 값을 동전의 수가 가장 적게 지불하기 가장 큰 동전부터 최대한 지불해야하는 값을 채우는 방식 지불해야 하는 값 : 4720 1원, 50원, 100원, 500원 동전 coin_list = [500, 100, 50, 1] # 큰 동전부터 def min_coin_count(value, coin_list): total_coin_count = 0 details = list() coin_list.sort(reverse=True) for coin in coin_list: coin_num =.. 2021. 4. 6.
[코딩 + 알고리즘 완주반] 20일차. 너비 우선 탐색(Breadth-First Search ), 깊이 우선 탐색(Depth-First Search) # 너비 우선 탐색 (BFS) 정점들과 같은 레벨에 있는 노드들을 먼저 탐색 # 깊이 우선 탐색 (DFS) 정점의 자식들을 먼저 탐색하는 방식 # BFS 알고리즘 구현 자료구조 큐 활용 graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['A', 'D'] graph['C'] = ['A', 'G', 'H', 'I'] graph['D'] = ['B', 'E', 'F'] graph['E'] = ['D'] graph['F'] = ['D'] graph['G'] = ['C'] graph['H'] = ['C'] graph['I'] = ['C', 'J'] graph['J'] = ['I'] def bfs(graph, start_node): visited = list() need.. 2021. 4. 6.
반응형

티스토리툴바