728x90 반응형 분류 전체보기326 [백준 11657][파이썬] 타임 머신 (벨만 포드) https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 음의 간선을 포함하고 있기 때문에 다익스트라가 아닌 벨만 포드 알고리즘을 사용한다. 무조건 음의 간선을 포함한다고 문제가 생기는 것은 아니다. 정확히는 음의 간선이 포함된 사이클이 최단 거리를 - ∞로 만들 때 문제가 발생한다. 다음과 같은 음의 사이클은 문제가 되지 않는다. 사이클을 반복하면 비용이 증가하기 때문에 최단 거리를 구하는 .. 2023. 6. 13. [Network] AS, OSPF, BGP https://growth-coder.tistory.com/194 이전 포스팅에서 라우팅 알고리즘에 관한 포스팅을 작성했었다. 라우터의 예시로 다음과 같은 그림을 제시했었다. 하지만 실제 라우터가 위와 같은 모습은 아닐 것이다. destination이 굉장히 많기 때문에 위와 같은 모습이라면 라우팅 테이블이 굉장히 커질 것이다. 그래서 라우터들은 region 단위로 집계하는데 이러한 집합을 Autonomous System (AS)라고 한다. 실제 라우팅은 AS안에서 이루어지는 라우팅과 AS끼리 이루어지는 라우팅으로 나뉜다. intra-AS routing 같은 AS 안에서 host끼리 이루어지는 라우팅이다. 같은 AS 안이라면 반드시 같은 intra-domain protocol을 사용해야 하고. 서로 다른.. 2023. 6. 12. [OS] CPU scheduling 알고리즘 1. FCFS(First Come First Served) 스케줄링 요청한 순서대로 프로세스에게 cpu를 할당해준다. 비선점 방식이다. 다음과 같이 프로세스들이 요청을 했다고 하자. 다음과 같은 순서대로 실행될 것이다. 이 방식은 수행 시간이 큰 프로세스가 모두 수행되는 동안 다른 프로세스가 기다려야 한다는 단점이 존재한다. 2. SJF(Shortest Job First) 스케줄링 SJF 알고리즘은 cpu 수행 시간이 짧은 프로세스부터 cpu를 할당해주는 방식이다. (수행 시간이 같으면 요청한 순서대로) 비선점 방식이다. 다음과 같이 프로세스의 요청이 동시에 들어왔다고 하자. 수행 시간이 짧은 프로세스부터 실행하기 때문에 아래와 같이 실행될 것이다. 평균 대기 시간이 짧다는 장점이 있다. 3. SRTF(.. 2023. 6. 11. [Network] Routing Algorithms 최적의 경로를 찾는 대표적인 라우팅 알고리즘 두 가지를 알아보려고 한다. 1. link state (Dijkstra's Algorithm) link state 알고리즘은 다익스트라 알고리즘을 사용한다. 다익스트라 알고리즘은 음의 가중치를 허용하지 않으며 목적지 노드까지의 최단 경로를 구할 때 사용한다. 이를 사용하려면 모든 link의 state를 알아야 해서 link state broadcasting 방식으로 값이 바뀌거나 하면 모든 노드에게 값을 알려준다. 즉 모든 라우터의 정보를 알아야 한다. 이 다익스트라 알고리즘을 사용하면 특정 노드에서 다른 모든 노드로 가는 최단 경로를 알 수 있다. https://growth-coder.tistory.com/41 [Algorithm] 다익스트라 (Dijkstr.. 2023. 6. 10. 이전 1 ··· 30 31 32 33 34 35 36 ··· 82 다음 728x90 반응형
