코딩테스트 연습 - 합승 택시 요금 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr A,B가 s에서 출발하는데 어떤 위치까지는 함께 갈 수 있고 그러다가 각자 도착 위치 a,b로 간다고 한다면... 최소 요금은 얼마인가 물론 함께가지 않아도 최소라면 그래도 된다 복잡하게 생각하면 상당히 어렵다.. 어디까지 함께 가야하나?.. 함께 가는 거리가 최소여야하나??... 함께 가는 거리가 최소더라도.. 나머지 A,B까지 가는 거리는 최소로 해야하나???... 함께 가는 거리가 최소가 아니더라도.. 나머지 A..
16958번: 텔레포트 (acmicpc.net) 16958번: 텔레포트 2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔 www.acmicpc.net 이 문제에서 다음과 같이 제출하면.. 시간 초과로 통과하지 못한다 from sys import stdin INF = 1e9 def floyd(graph,city): for k in range(1,n+1): for a in range(1,n+1): if k == a: continue for b in range(1,n+1): if a == b: continue graph[a]..
1. 문제 28131번: K-지폐 (acmicpc.net) 28131번: K-지폐 첫째 줄에 $N$, $M$, $K$가 주어진다. $(2\leq N\leq 10\,000; 1\leq M\leq \min\left(100\,000, N(N-1)\right); 1\leq K\leq 50)$ 둘째 줄에 $S$와 $T$가 공백으로 구분되어 주어진다. $(1\leq S,T\leq N;S\neq T)$ 셋째 줄부터 $M$개의 www.acmicpc.net 2. 풀이 문제 자체는 간단하다 s에서 t로 이동하는데 가중치의 합이 k의 배수가 되는 최단 경로를 찾는 문제 어떤 수가 k의 배수라는 것은, k로 나눈 나머지가 0이라는 사실을 이용해서 찾는다. D[i][j]를 s에서 출발해서 i 정점으로 가는 경로의 가중치 합을 ..
1. 문제1 16167번: A Great Way (acmicpc.net) 16167번: A Great Way 첫 번째 줄에 거점의 수 N과 경로의 개수 R이 주어진다. (2 ≤ N ≤ 100, 1 ≤ R ≤ 200) 모든 거점에는 1부터 N까지 번호가 매겨져 있으며 중앙대학교는 1번, 숭실대학교는 N번이다. 두 번째 줄부터는 R www.acmicpc.net 2. 풀이 다익스트라 알고리즘으로 최단거리만을 요구하는 문제가 기본문제고, 최단거리면서, 그러한 거리가 여러개인 경우 거쳐가는 노드가 최소가 되는 경로를 찾으라고 한다면? 접근 방법은 distance 배열 설정을 조금만 바꿔주면 된다 distance[v]를 출발점에서 v까지 가는데 가는 [비용, 거친 노드 수]로 정의해주자 "비용이 먼저 최소가 되면서..
1. 문제 23286번: 허들 넘기 (acmicpc.net) 23286번: 허들 넘기 첫째 줄에 세 정수 N, M, T가 주어진다. 다음 M개의 줄에 그래프 간선의 정보 u, v, h가 주어지고, u에서 v로 가는 간선이 있고, 높이가 h인 허들이 간선 중간에 놓여 있다는 의미이다. 마지막 T개의 www.acmicpc.net 2. 풀이 출발 정점에서 도착 정점으로 가는 길에 가중치가 가장 큰 간선의 가중치가 최소가 되는 경로를 찾는 문제 경로에서 가중치가 가장 큰 간선을 bottleneck path라고 부른다 이 bottleneck path의 가중치를 최소로 만드는 문제가 minimum bottleneck path problem 여러가지 방법이 있는것 같기는 한데.. 가장 기본은 다익스트라 알고리즘을 살..
1. 문제 그래프 G가 V개의 정점과 E개의 간선으로 이루어지며 간선의 가중치가 0 또는 1이다. 이때 두 정점 사이의 최단 경로를 찾는 효율적인 코드를 작성해야한다면? 2. 다익스트라 알고리즘이 항상 정답인가? 많은 경우에 다익스트라 알고리즘을 선택하지만, O(E+VlogV)가 최상의 구현이지만, 최악의 경우 효과적이지 않다. 많은 사람들이 이 문제를 보면 다익스트라 알고리즘을 선택하고, 효율적이지 않을때, 최적화할려고 노력하지만, 다익스트라 알고리즘이 최상이라고 생각한다면.. 매우 간단하면서 BFS를 이용한 아주 아름다운 0-1 BFS라는 기법을 알 필요가 있다 보조정리(Lemma) : "BFS 수행중에 정점을 포함하는 큐는, BFS 트리의 최대 2개의 연속한 레벨의 원소만을 포함할 수 있다" Lem..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
