archives

잘 설명된 블로그 : http://kks227.blog.me/220796029558 (알고리즘 설명이 진짜 잘 되있네요) 앞의 다익스트라 알고리즘은 a에서 b로 갈때 가중치가 음수가 아니라고 가정한 상태에서 코딩을 한다. 하지만 이 벨만 포드 알고리즘으로 가중치가 음수일 경우까지 판별이 가능하다. 음수 검사까지 하므로 시간복잡도는 늘어나서 O(VE)이다. 사진은 역시 저 블로그에서 가져왔다. 0에서 2까지 가는 최소거리를 찾을때 다익스트라 알고리즘은 음수가 아니라고 가정한 상태이므로 8로 최소값을 잡는다. 그런데 진짜 최소거리는 1을 거쳐서 가는 5다. 이러한 음수판별까지하는게 벨만 포드 알고리즘이다. 그런데 음의 가중치가 있는 그래프를 판별시 항상 무한대 사이클을 염두해 두어야 한다.이 무한대 사이클을..

파이썬으로짜면 시간초과가 나는걸 알기에 c++로 짰다. 파이썬 카테고리인데.... https://www.acmicpc.net/problem/1238 다익스트라 문제. 숫자가 적어서 (가는거 + 오는거) 계산하면 된다. #include #include #include using namespace std; const long long INF = 999999999; int n,m,x,u,v,w; vector adj[1001]; long long dist[1001]; void dijkstra(int src) { for(int i=0;i>n>>m>>x; for(int i=0;i>u>>v>>w; adj[u].push_back(make_pair(v,w)); } int max = -1; for(int i=1;i

설명 잘 된 블로그 : http://kks227.blog.me/220796029558 블로그에 나온 것처럼 그래프에서 어떤 정점에서 다른 정점으로 갈 경우 최소값을 구하는 알고리즘이다. 다익스트라 알고리즘은 모든 비용이 음수가 아닐 경우에만 동작한다. 시간 복잡도 : O(|E|lg|V|) (정점 V, 간선 E) 그림은 위의 블로그에서 퍼왔다. 1. 정점 0이 시작점이고 여기서 출발하여 다익스트라로 각 점까지의 최솟값을 구한다고 하자. 각 점까지의 거리는 초기치를 무한대로 설정해놓는다. 2. 첫 정점에서 갈수 있는 점들을 큐에 저장해놓고 가장 비용이 적은 점부터 방문한다. 방문후 비용을 초기화해준다. 3. 다음 시작점중 비용이 가장 적은 1부터 방문한다. 왜 비용이 적은것부터 방문하냐면, 아래 그림의 3이..

https://docs.python.org/2/library/heapq.html 여기껄 클래스화시켰다. 큐의 순서는 출력해보면 알겠지만 우선순위에 따라서 출력된다.# -*- encoding: cp949 -*- from heapq import * class priority_queue(): def __init__(self): self.pq = [] # list of entries arranged in a heap self.entry_finder = {} # mapping of tasks to entries self.REMOVED = '' # placeholder for a removed task def put(self, task, priority=0): 'Add a new task or update the ..

https://www.acmicpc.net/problem/1753 한 10번넘게 시도해봤는데 다 시간초과가 뜬다. c++로 코드를 바꾸고 일부 설정을 바꾸니 통과하는걸로보아 그냥 파이썬이 느린 것 같다. 코드를 공부하면서 느낀건데 위상 정렬하고 알고리즘이 비슷한거같다. 추가. c++로 코드를 짤 경우 cin>>이 느리덴다. scanf가 빠르고. 또 coutE>>K; for(int i=0;i>u>>v>>w; adj[u].push_back(make_pair(v,w)); } dijkstra(K); for(int i=1;i>S>>K; dijkstra(S); cout

https://www.acmicpc.net/problem/1697 bfs문제. # -*- encoding: cp949 -*- import Queue short = 99999999 def bfs(n,k): global short visited = [[0,0,0] for i in xrange(1000000)] #-, +, *2 의 방법으로 방문했었는지 체크 q = Queue.Queue() q.put([n,0]) #첫번째위치와 거리 0으로 시작하므로 0. for i in xrange(3): #첫번째 위치는 다 방문했다고 초기화 visited[n][i] = 1 while not q.empty(): p = q.get() if p[0]==k: #도착했을때 가장 짧은 경로로 세팅 if short > p[1]: sho..

https://www.acmicpc.net/problem/1991 이진 트리를 구현하면 된다. 근데 일반적인 이진 트리와 조금 다르게 잘 구현하면 된다. 숏코딩을 보면 파이썬으로 내 코드보다 1/7길이로 구현해놨던데 그게 가능한지 궁금하다... # -*- encoding: cp949 -*- from __future__ import print_function class node: def __init__(self, data): self.left = 0 self.right = 0 self.data = data class binarytree: def __init__(self): self._node = node(0) def insert(self, data): self.cur_node = self._node if ..

https://www.acmicpc.net/problem/2193 앞의 1904번 문제하고 비슷하다.#1 = [1]#2 = [10]#3 = [100, 101]#4 = [1000, 1001, 1010]#5 = [10000, 10001, 10010, 10100, 10101] 아랫쪽 파란색은 위쪽 파란색에서 만들어지고 빨간색도 그렇다. 색 표시 안한것들은 -2칸전의 값+01한 값이다. 피보나치처럼 계산하면 될거라는걸 알수있다. # -*- encoding: cp949 -*- #1 = [1] #2 = [10] #3 = [100, 101] #4 = [1000, 1001, 1010] #5 = [10000, 10001, 10010, 10100, 10101] n = int(raw_input()) dp = [0 for i..