알고리즘 문제 해결 전략

근거리 네트워크 (LAN)

algospot.com :: LAN 근거리 네트워크 문제 정보 문제 근거리 네트워크(LAN, Local Area Network)는 가정, 학교, 혹은 회사 등의 제한된 공간 내의 컴퓨터들을 연결하는 네트워크입니다. 알고스팟 대학교에서는 캠퍼스의 일 algospot.com 최소 스패닝 트리 문제 설명 더보기 N개의 정점의 좌표가 주어지고 가중치 없이 연결할 수 있는 정점의 번호가 주어진다. 양방향 간선이지만 u에서 v로 가는 간선 하나만 저장해주면 된다. (u < v) 2중 for문을 통해서 모든 정점끼리 연결될 수 있는 가중치가 포함된 간선을 구해준다. 크루스칼 알고리즘을 적용하기 전에 주어지는 정점들을 Union해버리면 가중치 없이 정점을 미리 연결해줄 수 있다. 그리고 나머지 정점들을 크루스칼 알고리..

선거 공약 (PROMISES)

algospot.com :: PROMISES 선거 공약 문제 정보 문제 경제가 침체기에 빠졌을 때 정치인들이 흔히 내거는 공약으로 대규모 토목 공사를 통한 경기 부양책이 있습니다. 이번에 집권당에서는 향후 N 년간 1년에 하나씩 전국 algospot.com 플로이드-와샬 문제 설명 더보기 우선 기존에 있던 고속도로들을 가지고 플로이드 알고리즘을 통해서 최단거리를 구해준다. 그리고 새로운 고속도로(a에서 b로 가는)가 건설 될 때마다 현재 최단거리와 비교해서 비용이 같거나 오히려 더 크다면 해당 고속도로를 설치할 필요가 없다. 하지만 새로운 고속도로를 설치하는게 이득이 된다면 a에서 b로 가는 고속도로를 추가하고 플로이드 알고리즘을 통해서 모든 간선의 최소비용을 갱신해 준다. r에서 c로 가는 비용을 갱신..

음주 운전 단속 (DRUNKEN)

algospot.com :: DRUNKEN Drunken Driving 문제 정보 문제 As the holiday season approaches, the number of incidents caused by Driving While Intoxicated (known as DWI) increases rapidly. To prevent this, the city of Seoul has proclaimed a war against drunken driving. Every day, www.algospot.com 플로이드-와샬 문제 설명 더보기 플로이드 알고리즘은 아무 정점도 경우하지 않는 최단 거리에서 시작해 경유할 수 있는 정점을 하나씩 추가해 가며 최단 거리를 갱신한다. 이 과정에서 경유하는 정점을 1번부..

소방차 (FIRETRUCKS)

algospot.com :: FIRETRUCKS 소방차 문제 정보 문제 한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 www.algospot.com 다익스트라 문제 설명 더보기 각 소방서마다 불이나는 집까지의 최단거리를 구하고, 그 중에서 가장 가까운 소방서만 선택해서 전체 시간을 구한다면 시간초과가 날 것이다. Key point는 소방서가 시작점이기 때문에 가상의 정점(0번 정점)을 만들고, 0번 정점에서 소방서까지 가는 비용을 0으로 잡고 queue에 넣어주면 된다! -> 0번 정점에서 모든 소방서로 가중치가 0인 간선을 연결한다고 생각하자 우선순위 큐에서 항상 가장 적은 시간이 소요되..