전체 글

[Python] deque를 사용한 1차원 리스트 회전하기 - rotate()

파이썬의 deque를 사용하면 1차원 리스트를 회전 시킬 수 있습니다. deque는 왼쪽과 오른쪽 모두에서 삽입, 삭제가 가능하기 때문입니다. rotate()함수를 사용하면 가능합니다. 인자로 넣어주는 값이 음수인지 양수인지에 따라 회전의 방향이 다릅니다. 음수는 왼쪽 양수는 오른쪽에 있어 시계방향으로 회전한다고 생각하면 외우기 쉬울것 같습니다. from collections import deque arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ] arr = deque(arr) arr.rotate(3) print(arr) #1 result = list(arr) print(result) #2 결과) deque([7, 8, 9, 1, 2, 3, 4, 5, 6]) #1 [7, 8, 9, 1, 2..

[Python] 파이썬 PS를 위한 문법 정리 - 2차원 리스트 회전

디시인사이드 PS 마이너 갤러리에서 좋은 글을 찾아 그중에 저에게 필요한 내용을 정리하였습니다. PS용 파이썬 문법 정리1 PS용 파이썬 문법 정리2 링크된 글에는 없지만 저에게 필요하다고 생각되는 부분도 추가하였습니다. 1. 무한값 생성 import sys inf = sys.maxsize print(inf) 결과) 9223372036854775807 from sys import maxsize max_value = maxsize 이렇게 사용도 가능하다. 2. set 자료 값 찾을 때 사용 : 해시 구조이기 때문에 in 연산 시 O(1)의 시간 복잡도를 가집니다. 시간 복잡도 : O(n) data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] for i in range(100): if i i..

[Algorithm] 다익스트라 알고리즘

데이크스트라 또는 다익스트라 알고리즘이라 불리는 알고리즘을 알아보겠습니다. 다익스트라 알고리즘은 특정 노드에서 다른 노드로의 최단경로를 구하는 알고리즘입니다. 다익스트라 알고리즘에는 그리디와 다이나믹 프로그래밍이 녹아들어 있습니다. 이전 최소거리를 기억한다는 점에서는 다이나믹 프로그래밍이 현재 시점에서 항상 최소값을 찾는다는점이 그리디 알고리즘이 녹아있음을 알 수 있습니다. 다익스트라 알고리즘은 음의 간선이 존재하지 않을때 정상적으로 작동하는 알고리즘입니다. 모든 간선의 값은 0이상이며 그래서 GPS등에 활용할 수 있는 실생활에 적합한 알고리즘입니다. 다익스트라 알고리즘의 과정을 그림으로 알아보겠습니다. 시작 노드 A에서 도착 노드 F까지의 과정을 알아보겠습니다. 간선은 노드간 이동값(거리)입니다. 노드..

[Algorithm] 플로이드 워셜 알고리즘

플로이드 워셜 알고리즘 : 시작 노드에서 도착 노드로 갈때 특정 노드를 거쳐가는것이 더 빠르다면 최소값을 갱신해 주는 알고리즘 플로이드 워셜 알고리즘에는 다이나믹 프로그래밍이 녹아들어 있습니다. 두 알고리즘 모두 문제를 해결할때 점화식을 사용하기 때문입니다. 점화식은 다음과 같습니다. Dab = min(Dab, Dak + Dkb) a에서 b로 가는 값을 a에서 b로 가는 값과 a에서 k를 거쳐 b로 가는 값중 작은 값으로 갱신하라는 의미입니다. 플로이드 워셜 알고리즘은 이미 값을 가지고 있는 노드간의 거리에 특정 노드 k를 거쳐가는 과정을 수행해 줘야 하기에 3중 for을 사용합니다. 그래서 시간 복잡도는 O(N3)이 됩니다. 다음은 플로이드 워셜 알고리즘의 최소값 갱신 과정입니다. 이렇게 최소값을 갱신..

[Algorithm] 0-1 BFS

0-1 BFS : 가중치가 0과 1만 있는 그래프에서 작동하는 알고리즘 0-1 bfs는 시간 복잡도 O(V+ E)로 다익스트라 알고리즘의 O(ElogE) 또는 O(VlogV) 보다 빠릅니다. 가중치가 0인 정점이 존재하기 때문에 정점의 방문 횟수가 더 많더라도 가중치가 더 낮은 경우를 고려해야 합니다. 결괏값이 방문 횟수가 아니라 가중치의 최소를 구하는 문제에서는 가중치가 낮은 경로부터 찾아야 합니다. 정점 1에서 2로 이동 = 방문 횟수 1, 가중치 1 정점 1에서 3, 4를 거쳐 2로 이동 = 방문 횟수 4, 가중치 0 탐색을 할때 가중치가 낮은 노드를 먼저 돌아야 하므로 가중치가 낮은 노드는 큐의 앞(front)에 삽입합니다. 파이썬의 우선순위 큐에서는 리스트의 앞에 삽입하는 기능이 없으므로 deq..

[Python] 파이썬 max, min 함수 - max(map(max, graph))

파이썬 기본내장 함수에는 max함수와 min함수가 있습니다.  이번 포스팅에서는 사용법에 대해 알아보도록 하겠습니다.  기본적으로 max(리스트 or 튜플 or 요소), min(리스트 or 튜플 or 요소) 형태로 사용합니다.  number = [ 2, 5, 1, -19, 100, 200, -99 ]print(max(number))print(min(number))  결과)200-99  print(max(-10, 100))print(min(2, 9))  결과)1002  map 함수와의 응용 - 2차원 배열number = [ [ 2, 5, 1, -19, 100, 200, -99 ], [ 4, 2, 1, -20, 300, 150, 400 ], [ -1, -2, -10, -1..