The Gas Station Problem - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:25:25Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:25 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[Dynamic Programming]]		상위 문서: [[Dynamic Programming]]

Pinkgo: /* 개요 */

2025-11-18T04:48:58Z

개요

← 이전 판		2025년 11월 18일 (화) 04:48 판
10번째 줄:		10번째 줄:
	이때 위 문제를 해결하기 위해서 <math>G[i]</math>를 주유소 <math>g_i</math>에 도달하기 위해 필요한 최소 주유 횟수라고 하면 점화식은 아래와 같이 정의된다:		이때 위 문제를 해결하기 위해서 <math>G[i]</math>를 주유소 <math>g_i</math>에 도달하기 위해 필요한 최소 주유 횟수라고 하면 점화식은 아래와 같이 정의된다:
	<math>G[1]=0</math><ref>첫 번째 주유소는 출발점이므로 주유 횟수가 0이다.</ref>		<math>G[1]=0</math><ref>첫 번째 주유소는 출발점이므로 주유 횟수가 0이다.</ref>
	<math>G[i]=\min_{j<i,(m_i-m_j<R)}(G[i]+1)</math>		<math>G[i]=\min_{j<i,(m_i-m_j<R)}(G[j]+1)</math>
	이는 이전 주유소 중에서 i까지 한 번에 갈 수 있는 모든 j에 대해, 가장 적은 주유 횟수의 경우를 선택하고 한 번 추가한다는 것을 의미한다.		이는 이전 주유소 중에서 i까지 한 번에 갈 수 있는 모든 j에 대해, 가장 적은 주유 횟수의 경우를 선택하고 한 번 추가한다는 것을 의미한다.

Pinkgo: /* 개요 */

2025-11-18T04:41:59Z

개요

← 이전 판		2025년 11월 18일 (화) 04:41 판
6번째 줄:		6번째 줄:
	Gas Station Problem은 아래와 같은 문제 정의를 가진다:		Gas Station Problem은 아래와 같은 문제 정의를 가진다:
	가정 1: 뉴욕에서 플로리다까지 가는 길에 주유소 <math>g_1, g_2, \cdots, g_n</math>이 있다.		가정 1: 뉴욕에서 플로리다까지 가는 길에 주유소 <math>g_1, g_2, \cdots, g_n</math>이 있다.
	가정 2: 각 ~~주요소는~~ mile marker <math>m_i</math>에 위치해 있으며, 자동차는 한 번 주유로 R마일을 달릴 수 있다.		가정 2: 각 주유소는 mile marker <math>m_i</math>에 위치해 있으며, 자동차는 한 번 주유로 R마일을 달릴 수 있다.
	목표: 목적지까지 가기 위해 최소 몇 번 주유해야 하는가?		목표: 목적지까지 가기 위해 최소 몇 번 주유해야 하는가?
	이때 위 문제를 해결하기 위해서 <math>G[i]</math>를 주유소 <math>g_i</math>에 도달하기 위해 필요한 최소 주유 횟수라고 하면 점화식은 아래와 같이 정의된다:		이때 위 문제를 해결하기 위해서 <math>G[i]</math>를 주유소 <math>g_i</math>에 도달하기 위해 필요한 최소 주유 횟수라고 하면 점화식은 아래와 같이 정의된다:
13번째 줄:		13번째 줄:
	이는 이전 주유소 중에서 i까지 한 번에 갈 수 있는 모든 j에 대해, 가장 적은 주유 횟수의 경우를 선택하고 한 번 추가한다는 것을 의미한다.		이는 이전 주유소 중에서 i까지 한 번에 갈 수 있는 모든 j에 대해, 가장 적은 주유 횟수의 경우를 선택하고 한 번 추가한다는 것을 의미한다.

	이에 대한 시간복잡도를 계산하면 <math>O(n^2)</math>이다. 이때 모든 i에 대해 가능한 j를 확인하므로 이 문제는 [[BFS]]로도 해결할 수 있다. 각 주유소를 정점, 도달 가능한 관계를 간선으로 보면 unweighted shortest path 문제이기 때문이다. 사실 많은 DP 문제는 실제로 DAG(Directed Acyclic Graph)에서 최단 경로를 찾는 문제의 변형이다.		이에 대한 시간복잡도를 계산하면 <math>O(n^2)</math>이다. 이때 모든 i에 대해 가능한 j를 확인하므로 이 문제는 [[BFS]]로도 해결할 수 있다. 각 주유소를 정점, 도달 가능한 관계를 간선으로 보면 unweighted shortest path 문제이기 때문이다. 사실 많은 DP 문제는 실제로 DAG(Directed Acyclic Graph)에서 최단 경로를 찾는 문제의 변형이다.

	==Minimum Average Station Price==		==Minimum Average Station Price==

2025년 11월 15일 (토) 03:32에 Pinkgo님의 편집

2025-11-15T03:32:18Z

← 이전 판		2025년 11월 15일 (토) 03:32 판
15번째 줄:		15번째 줄:
	이에 대한 시간복잡도를 계산하면 <math>O(n^2)</math>이다. 이때 모든 i에 대해 가능한 j를 확인하므로 이 문제는 [[BFS]]로도 해결할 수 있다. 각 주유소를 정점, 도달 가능한 관계를 간선으로 보면 unweighted shortest path 문제이기 때문이다. 사실 많은 DP 문제는 실제로 DAG(Directed Acyclic Graph)에서 최단 경로를 찾는 문제의 변형이다.		이에 대한 시간복잡도를 계산하면 <math>O(n^2)</math>이다. 이때 모든 i에 대해 가능한 j를 확인하므로 이 문제는 [[BFS]]로도 해결할 수 있다. 각 주유소를 정점, 도달 가능한 관계를 간선으로 보면 unweighted shortest path 문제이기 때문이다. 사실 많은 DP 문제는 실제로 DAG(Directed Acyclic Graph)에서 최단 경로를 찾는 문제의 변형이다.

	===Minimum Average Station Price===		==Minimum Average Station Price==
	이번에는 문제를 변형하여, 각 주요소마다 단가 <math>p(s)</math>가 다르다고 가정하여 “평균 가격이 최소가 되도록 어느 주유소들에서 멈춰야 하는가?”를 구해야 한다고 가정하자. 이때에는 얼마나 자주 넣는가를 고려하지 않고 방문하는 주유소들의 주유비 평균만 최소화하면 된다고 하자. 이를 해결하기 위해 <math>G[i,k]</math>를 주유소 <math>g_i</math>에 정확히 k번 주유한 뒤 도달할 때의 총 단가 합계라고 하면, 아래와 같이 점화식이 정의된다:		이번에는 문제를 변형하여, 각 주요소마다 단가 <math>p(s)</math>가 다르다고 가정하여 “평균 가격이 최소가 되도록 어느 주유소들에서 멈춰야 하는가?”를 구해야 한다고 가정하자. 이때에는 얼마나 자주 넣는가를 고려하지 않고 방문하는 주유소들의 주유비 평균만 최소화하면 된다고 하자. 이를 해결하기 위해 <math>G[i,k]</math>를 주유소 <math>g_i</math>에 정확히 k번 주유한 뒤 도달할 때의 총 단가 합계라고 하면, 아래와 같이 점화식이 정의된다:
	<math>G[1,0]=0</math>		<math>G[1,0]=0</math>
23번째 줄:		23번째 줄:
	하지만 이 방식은 “싼 곳에서 많이 넣고 비싼 곳에서 덜 넣는” 실제 전략을 반영하지는 못한다.		하지만 이 방식은 “싼 곳에서 많이 넣고 비싼 곳에서 덜 넣는” 실제 전략을 반영하지는 못한다.

	===Cheapest Filling Schedule===		==Cheapest Filling Schedule==
	해당 문단에서는 위 문제를 더욱 현실적으로 변형하여, 한 번에 “정수 갤런” 단위로만 주유가 가능하며, 각 주유소마다 가격이 다를 때, “최소 총비용으로 목적지까지 가는 주유 스케줄은 무엇인가?”를 구해야 한다고 가정하자. 이를 해결하기 위해 <math>G[i,k]</math>를 주유소 <math>g_i</math>에 도착했을 때 k갤런의 기름이 남은 상태로의 최소 비용을 의미한다고 가정하자. 이를 이용하면 점화식은 아래와 같이 구해진다:		해당 문단에서는 위 문제를 더욱 현실적으로 변형하여, 한 번에 “정수 갤런” 단위로만 주유가 가능하며, 각 주유소마다 가격이 다를 때, “최소 총비용으로 목적지까지 가는 주유 스케줄은 무엇인가?”를 구해야 한다고 가정하자. 이를 해결하기 위해 <math>G[i,k]</math>를 주유소 <math>g_i</math>에 도착했을 때 k갤런의 기름이 남은 상태로의 최소 비용을 의미한다고 가정하자. 이를 이용하면 점화식은 아래와 같이 구해진다:
	<math>G[1,0]=0</math>		<math>G[1,0]=0</math>

Pinkgo: 새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: Dynamic Programming ==개요== Gas Station Problem은 아래와 같은 문제 정의를 가진다: 가정 1: 뉴욕에서 플로리다까지 가는 길에 주유소 $g_1, g_2, \cdots, g_n$ 이 있다. 가정 2: 각 주요소는 mile marker $m_i$ 에 위치해 있으며, 자동차는 한 번 주유로 R마일을 달릴 수 있다. 목표: 목적지까지 가기 위해...

2025-11-15T03:30:38Z

새 문서: 분류:알고리즘 설계와 분석 분류:컴퓨터 공학 상위 문서: Dynamic Programming ==개요== Gas Station Problem은 아래와 같은 문제 정의를 가진다: 가정 1: 뉴욕에서 플로리다까지 가는 길에 주유소 <math>g_1, g_2, \cdots, g_n</math>이 있다. 가정 2: 각 주요소는 mile marker <math>m_i</math>에 위치해 있으며, 자동차는 한 번 주유로 R마일을 달릴 수 있다. 목표: 목적지까지 가기 위해...

새 문서

[[분류:알고리즘 설계와 분석]]
[[분류:컴퓨터 공학]]
상위 문서: [[Dynamic Programming]]

==개요==
Gas Station Problem은 아래와 같은 문제 정의를 가진다:
가정 1: 뉴욕에서 플로리다까지 가는 길에 주유소 <math>g_1, g_2, \cdots, g_n</math>이 있다.
가정 2: 각 주요소는 mile marker <math>m_i</math>에 위치해 있으며, 자동차는 한 번 주유로 R마일을 달릴 수 있다.
목표: 목적지까지 가기 위해 최소 몇 번 주유해야 하는가?
이때 위 문제를 해결하기 위해서 <math>G[i]</math>를 주유소 <math>g_i</math>에 도달하기 위해 필요한 최소 주유 횟수라고 하면 점화식은 아래와 같이 정의된다:
<math>G[1]=0</math><ref>첫 번째 주유소는 출발점이므로 주유 횟수가 0이다.</ref>
<math>G[i]=\min_{j<i,(m_i-m_j<R)}(G[i]+1)</math>
이는 이전 주유소 중에서 i까지 한 번에 갈 수 있는 모든 j에 대해, 가장 적은 주유 횟수의 경우를 선택하고 한 번 추가한다는 것을 의미한다.

이에 대한 시간복잡도를 계산하면 <math>O(n^2)</math>이다. 이때 모든 i에 대해 가능한 j를 확인하므로 이 문제는 [[BFS]]로도 해결할 수 있다. 각 주유소를 정점, 도달 가능한 관계를 간선으로 보면 unweighted shortest path 문제이기 때문이다. 사실 많은 DP 문제는 실제로 DAG(Directed Acyclic Graph)에서 최단 경로를 찾는 문제의 변형이다.

===Minimum Average Station Price===
이번에는 문제를 변형하여, 각 주요소마다 단가 <math>p(s)</math>가 다르다고 가정하여 “평균 가격이 최소가 되도록 어느 주유소들에서 멈춰야 하는가?”를 구해야 한다고 가정하자. 이때에는 얼마나 자주 넣는가를 고려하지 않고 방문하는 주유소들의 주유비 평균만 최소화하면 된다고 하자. 이를 해결하기 위해 <math>G[i,k]</math>를 주유소 <math>g_i</math>에 정확히 k번 주유한 뒤 도달할 때의 총 단가 합계라고 하면, 아래와 같이 점화식이 정의된다:
<math>G[1,0]=0</math>
<math>G[i,k]=\min_{j<i,(m_i-m_j<R)}(G[j,k-1]+p(j))</math>
즉, 해당 점화식은 이전 주유소 j에서 k-1번째 주유까지의 최소 단가합과 이번에 방문하는 주유소의 단가의 합을 의미한다. 최종적으로는 아래와 같은 식을 통해 평균 주유비가 최소가 되는 k를 찾는다:
<math>\min_{k}\frac{G[n,k]}{k}</math>
하지만 이 방식은 “싼 곳에서 많이 넣고 비싼 곳에서 덜 넣는” 실제 전략을 반영하지는 못한다.

===Cheapest Filling Schedule===
해당 문단에서는 위 문제를 더욱 현실적으로 변형하여, 한 번에 “정수 갤런” 단위로만 주유가 가능하며, 각 주유소마다 가격이 다를 때, “최소 총비용으로 목적지까지 가는 주유 스케줄은 무엇인가?”를 구해야 한다고 가정하자. 이를 해결하기 위해 <math>G[i,k]</math>를 주유소 <math>g_i</math>에 도착했을 때 k갤런의 기름이 남은 상태로의 최소 비용을 의미한다고 가정하자. 이를 이용하면 점화식은 아래와 같이 구해진다:
<math>G[1,0]=0</math>
<math>G[i,k]=\min_c \min_{j<i,(m_i-m_j<R_c)}\{G[j,c]+p(j)\cdot (k-c')\}</math>
위에서 <math>c'</math>은 출발 시 남은 기름량이며, <math>p(j)</math>는 j번째 주유소의 단가를 의미한다. 또한 <math>(m_i-m_j<R_c)</math>은 주유 후 남은 연료로 i까지 도달 가능한 경우만 고려한다는 것을 의미한다.

==각주==