https://school.programmers.co.kr/learn/courses/30/lessons/67259# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이요약: 다익스트라, 구조체 코드 #include #include #include #include using namespace std; int dw[4]={1,-1,0,0}; int dh[4]={0,0,1,-1}; int dist[1000][1000][2]; int INF = 98765432; struct edge { int cost; int w; int h; bool vertical; //우..
우선 백준 1005번을 보고 오자. https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 이 문제에 대한 올바른 문제해결 방법은 '위상정렬' 이다. 위상정렬은 보통 어떤 작업에 순서가 정해져있을 때, 순서를 결정하기 위해 사용하는 알고리즘입니다. 예를들어 스타크래프트에서 어떤 상위 건물을 지으려면, 하위 건물들을 몇가지 지어야 하는 경우가 있는데, 이처럼 어떤 작업 진행전에 해야하는 '순서' 가 존재할시 위상정렬을 사용한다. 위상정렬을 사용하기..
경로를 탐색해나가는 것에 더 나아가, 경로를 저장한 후 출력하라는 문제들이 종종 있다. 오늘은 어떤 경우에, 어떤식으로 경로를 저장해나가는지 케이스 별로 알아보자 1. 다익스트라,벨만포드 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 백준 문제 11779 번을 풀어보며 알아보자. 이 문제는 다익스트라 문제이지만, 벨만포드도 "경로 추적" 은 동일한 메커니즘으로 돌아간다. 혹시 벨만포드로 된 문제를 풀고 싶다면 ..
많은 문제들이 최소 비용, 최단거리 등에 집착한다. 하지만 막상 수많은 최단거리, 최소 비용에 대한 문제들을 보면 어떤 알고리즘을 써서 풀어야하지...? 하는 생각이 들고 생각나는대로 문제를 풀면 시간초과 혹은 오답이 나오면 멘붕이 오곤한다.. 이번 글에선 "최단 거리" 에 대해서와, 언제, 어떤걸 써야하는지에 대해 간략하게 정리해 보겠다. 디테일한 설명전 간단한 요약을 먼저 하자면 bfs: 간선에 가중치가 없다(단위길이) , 즉 비용이 아닌 거치는 횟수가 요구될 때. 다익스트라: 특정 시작점 모든 지점 간의 최단거리 플로이드와샬: 모든 시작점 모든 지점 간의 최단거리 벨만포드: 최단거리에서 음수 간선, 등으로 인하여 계속해서 최단거리를 줄여나가는지 "감지" 해야하는 경우 정도로 요약할 수있다. 1)가중..
