•알고리즘(Algorithm )/스터디

[알고리즘] 백트래킹(BackTracking)기법

[알고리즘] DFS(깊이 우선 탐색) 파이썬 [알고리즘] BFS(넓이 우선탐색) 파이썬 구현 , 파이썬으로 그래프 노드 표현하기 # 내용 그래프에서 많이쓰이는 넓이 우선탐색 방법(BFS) 시작 노드로부터 갈 수 있는 노드들을 차례로 방문예정 큐 devforyou.tistory.com # DFS 깊이 우선탐색 방식인 DFS은 스택을 이용하여 가능한 모든 경로의 끝부분까지 탐색한다. 그렇기 때문에 중간에 틀린 길일지라도 끝까지 탐색하기 때문에 경우의 수를 줄이지 못한다. # 백트래킹 Promising을 통해 해당 루트가 조건에 맞는지를 검사한다. Pruning(가지치기)을 통해 족너에 맞지 않으면 해당 path을 더이상 검사하지 않고 다른 루트로 돌아가서 탐색한다. 즉 DFS의 기반으로 깊이 우선탐색을 진행..

[알고리즘] 프림(Prim's) 알고리즘 파이썬, 최소신장트리(MST) 찾기, 파이썬 heapq, defaultdic

[알고리즘] 크루스칼(Kruskal) 알고리즘 파이썬, 최소신장트리(MST), union-find기법(union-by-rank, path-compr # 설명 ## 최소신장트리 그래프나 트리 내에서 최소신장트리를 찾을때 사용되는 알고리즘이다. 최소 신장트리(MST)는 그래프상의 모드 노드가 연결된 상태이면서 사이클(순환)구조가 없는 경우를 devforyou.tistory.com # 설명 크루스칼 알고리즘과는 다른 점은, 모든 엣지를 알고있어서 정렬한 후 엣지를 선택했던 이전과는 다르게, 주어진 시작노드로부터 인접 간선을 통하여 노드를 연결하는 것이 다르다. 후보군 간선 리스트(최소힙)를 만든 후, 노드가 선택될때 마다 후보군에 추가한다. 추가한 후보군에서 가장 작은 간선을 선택하여 연결한다. 연결을 확정짓..

[알고리즘] 크루스칼(Kruskal) 알고리즘 파이썬, 최소신장트리(MST), union-find기법(union-by-rank, path-compression)

# 설명 ## 최소신장트리 그래프나 트리 내에서 최소신장트리를 찾을때 사용되는 알고리즘이다. 최소 신장트리(MST)는 그래프상의 모드 노드가 연결된 상태이면서 사이클(순환)구조가 없는 경우를 뜻 한다. ## union-find 기법 결국 순환구조를 찾기 위해서는 어떠한 방법이 필요한데, 그때 이용되는 방법이 union-find기법이다. 각각의 노드들이 간선이 연결됨에 따라서 하나의 부분집합으로 생각한다. 즉 초기에는 (1), (2), (3), (4), (5,) (6)의 부분집하들이 존재하고, (1,2),(3,4),(5,6)와 같이 정점이 연결됨에 따라서 부분집합으로 표기하는 방법이다. 순환구조가 생긴다는 것은 집합내에 같은 원소가 존재해버리는 경우다, 예를 들어 (1,2,3)과 (3,4,5)의 두개의 그..

[알고리즘] 다익스트라(Dijkstra Algorithm) 알고리즘 파이썬, 최소힙(min-heap) 사용하기

# 파이썬 언어 # 무한대값 만들기 CONST_INFINITE = float('inf') import heapq # heapq라이브러리를 사용하여 최소 힙 만들기 min_heap = [] # push O(log n) heapq.heappush(min_heap,[10,'A']) # pop O(1) heapq.heappop(min_heap) heapq에서는 최소힙만 지원하기 때문에, max_heap을 사용하기 위해서는 값을 insert할때 ' - '을 곱해주고 꺼낼때 다시 ' - '를 곱하는 편법을 이용한다고 한다. 뭐 우선순위 큐에서 람다식으로 우선순위를 정해주는 방법도 있을거 같기는 하다. # 사용된 그래프 # 설명 학교에서 자료구조시간에 다익스트라 알고리즘을 배울때는, 힙을 사용하지 않는 방법에 대해서..

[알고리즘] DFS(깊이 우선 탐색) 파이썬

[알고리즘] BFS(넓이 우선탐색) 파이썬 구현 , 파이썬으로 그래프 노드 표현하기 # 내용 그래프에서 많이쓰이는 넓이 우선탐색 방법(BFS) 시작 노드로부터 갈 수 있는 노드들을 차례로 방문예정 큐에 넣은 후, 방문완료 큐에 넣는다. 방문예정큐로부터 뽑아 방문하지 않았다면, devforyou.tistory.com # 내용 BFS와 같이 탐색을 하지만, DFS는 말 그대로 깊이 우선탐색이다. 노드들을 계속 타고 타고 타고 들어가는 것이라고 생각하면 된다. 재귀함수로도 구현이 가능하다는 생각이 들었다. 근데 재귀로 짜면 끝에서부터 찾아오는 느낌이 될거 같다. 물론 구현은 가능하겠지만, 적합하지는 않을거 같다는 생각이 들었다. BFS와 매우 유사하지만, 방문해야할 노드들을 스택으로 표현하냐 큐로 표현하냐에 ..

[알고리즘] BFS(넓이 우선탐색) 파이썬 구현 , 파이썬으로 그래프 노드 표현하기

# 내용 그래프에서 많이쓰이는 넓이 우선탐색 방법(BFS) 시작 노드로부터 갈 수 있는 노드들을 차례로 방문예정 큐에 넣은 후, 방문완료 큐에 넣는다. 방문예정큐로부터 뽑아 방문하지 않았다면, 해당 노드에서 갈 수 있는 노드들을 뽑고, 방문완료 큐에 넣는 과정을 계속해서 반복하며, 더이상 방문할 노드가 없으면 끝이다. 파이썬에서는 그래프를 딕셔너리로 편하게 표현 할 수 있다. 큐를 사용해도 되고, 파이썬의 강력한 list를 사용해 큐처럼 활용 가능하다. 파이썬의 리스트가 제공하는 extend를 사용하면 리스트를 맨뒤에 연장시켜준다. # 사용 그래프 # 코드 # bfs ( 넓이 우선 탐색 ) def make_graph() : graph = dict() graph["A"] = ["B","C","D"] gra..