전체 글

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

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

[백준-9663] N-Queen 파이썬, 백트랙킹, 파이썬 전역변수, enumerate

# 문제 # 풀이 백트래킹기법을 사용하여 문제를 풀었다. 기존 탐색이나 반복문으로 풀게 되면 중간에 퀸을 놓을 수 없는 경우에도 그 다음에 대한 탐색을 실시할 것이다. 그렇기 때문에 중간에 이미 틀린 길이라면 이 후 반복을 중지하고 그 뒤로 돌아가야한다. 그렇게 하기 위해 백트래킹 기법을 사용해서 문제를 풀었다. 첫 행의 열들은 각각의 시작점이 된다. 그 기점으로 시작해서 가지가 뻗어나가기 때문에 시작위치를 지정해주었다. 이후 dfs를 이용해서 재귀함수로 다시 호출해나가는 방법으로 문제를 풀었다. for candidate_col in range(N): if is_available(cur_row, candidate_col, upper_queen_info): upper_queen_info.append(can..

[알고리즘] 프림(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할때 ' - '을 곱해주고 꺼낼때 다시 ' - '를 곱하는 편법을 이용한다고 한다. 뭐 우선순위 큐에서 람다식으로 우선순위를 정해주는 방법도 있을거 같기는 하다. # 사용된 그래프 # 설명 학교에서 자료구조시간에 다익스트라 알고리즘을 배울때는, 힙을 사용하지 않는 방법에 대해서..