분류 전체보기

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

[백준-11399] ATM 파이썬, 탐욕알고리즘을 이용한 최적해 찾기

# 문제 # 풀이 탐욕 알고리즘(Greedy Algorithim)을 이용해서 최적해를 구하는 방법의 문제라고 생각했다. 탐욕 알고리즘은 현재 상황이 가장 최적이라고 생각하고 문제를 풀어나가는 방법인데, 항상 최적의 해를 구하는 것은 아니다. 때때로는 근사한 값을 구할 수 있다. 위와 같이 6이 최적이라고 판단했지만 사실은 17->23으로 가는 것이 더 최대값을 구할 수 있는 경우가 생기기 때문이다. 이번 문제에서는 위와 같은 경우는 고려하지 않았도 됐기 때문에 그냥 풀었다. for문을 두 번 돌려서 풀면 당연히 편하겠지만 시간복잡도가 O(n^2)으로 늘어나기 때문에 O(n)으로 풀 수 있는 방법이 있을까 고민했고 아래와 같이 반복문을 한번만 돌려서 정답을 구 할 수 있었다. # 코드 import sys ..

[알고리즘] 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..

[백준-1920] 수 찾기 파이썬, 파이썬 한줄 입력받기 및 정수형 리스트 변환, 리스트 슬라이스 시간복잡도

# 문제 # 실패한풀이 ## 선형 탐색 선형탐색 알고리즘으로 찾았을 시에는 시간초과 오류 발생 ## 이진탐색 [알고리즘] 이진탐색 파이썬 및 시간복잡도 # 내용 정렬된 데이터 셋에서 탐색을 시도함 함수가 실행될때마다 탐색하는 범위가 반토막이 되기 때문에 순차탐색에 비해 월등히 속도가 빠름 # 코드 # 이진탐색은 데이터셋이 정렬되어 있어야 devforyou.tistory.com 저번에 정리한 내용으로 풀었으나 시간초과 오류 발생, 원인을 분석했을때 재귀함수가 호출할때 리스트를 슬라이싱해주는데 여기서 시간이 초과되는거 같았다. 리스트를 넘겨주지 않고 기존에 데이터를 활용하고 인덱스만 바꿔주는 방법으로 재시도했다. # 성공한 풀이 이진탐색을 똑같이 활용 했으나, 기존 리스트를 그대로 넘겨주는 방법을 사용했다...