나그네

2458번: 키 순서 문제 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 풀이 학생들 간 키를 비교해 자신이 몇 번째인지 알 수 있는 학생의 수를 구하는 문제다. 플로이드-워셜 알고리즘을 사용해 주어진 간선은 1, 나머지는 INF로 두고 플로이드-워셜을 돌린다. 정점 u, v의 키를 비교할 때 dist[u][v]가 INF가 아니라면 u보다 v가 키가 큰 것이고 dist[v][u]가 INF가 아니라면 v보다 u가 키가 큰 것이다. 둘 다 아니라면..

13168번: 내일로 여행 문제 https://www.acmicpc.net/problem/13168 13168번: 내일로 여행 첫 번째 줄에는 한국에 있는 도시의 수 N(1 ≤ N ≤ 100)과 1인당 내일로 티켓의 가격 R(1 ≤ R ≤ 1,000,000)이 주어집니다. 두 번째 줄에는 N개의 도시의 이름이 주어집니다. 도시의 이름은 알파벳 대소 www.acmicpc.net 풀이 여러 도시와 도시 간 이동 가능한 교통수단을 입력받고 정해진 순서대로 특정 도시들을 여행하는 최소 비용을 구하는 문제다. 단, 여기서 '내일로'라는 티켓을 구매하면 특정 교통수단은 0원이거나 반값이 된다. 이때 '내일로' 티켓을 구매하는 것이 더 비용이 적게 드는지 구하는 문제다. 특정 도시를 정점으로 사용하기 위해 map을 ..

1956번: 운동 문제 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 풀이 어느 점에서 다른 한 점까지 갔다가 다시 출발점으로 돌아오는 사이클의 길이의 최솟값을 찾는 문제다. 플로이드 워셜 알고리즘으로 각 정점 간 거리를 구하고 모든 경우의 수를 탐색하며 최솟값을 찾는 방식으로 풀었다. 코드 #include using namespace std; #define INF 1e9 int main() { ios::sy..

1613번: 역사 문제 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 풀이 여러 사건의 선후 관계를 판단하는 문제다. 플로이드-워셜 알고리즘을 사용해 풀 수 있다. a가 b보다 먼저 일어났다고 할 때 dist[a][b] = 1, 나머지는 INF로 플로이드를 돌린다. 그리고 x, y의 선후 관계를 알고 싶을 때, dist[x][y]가 INF가 아니라면 x가 먼저 일어난 일이고(-1 출력), INF면 x가 먼저 일어난 일은 아니다. 이때 ..

1389번: 케빈 베이컨의 6단계 법칙 문제 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 풀이 플로이드-워셜 알고리즘을 사용해 각 사람이 다른 사람에 이르기까지의 단계를 각각 구해 케빈 베이컨의 수를 구하고, 최솟값을 가지는 사람의 번호를 출력하는 문제다. 코드 #include using namespace std; #define INF 1e9 int main() { ios::sync_with_..

11403번: 경로 찾기 문제 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 (i, j)의 값이 0이면 연결되어 있지 않은 것이고 1이면 i->j 연결되어 있는 것이다. 따라서 dist[i][j]에 입력을 받아 0이면 연결되어 있지 않으므로 INF로, 1이면 1을 저장해 준다. 플로이드-워셜 알고리즘으로 모든 최단거리를 구하고 i->j로 갈 수 있는 경우엔 1을, INF라면 0을 출력해 주면 된다. 코드 #include using namespace std; #define INF ..

11404번: 플로이드 문제 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 기본적인 플로이드-워셜 알고리즘을 사용하면 풀 수 있는 문제다. 단, INF인 경우 0을 출력해줘야 한다. 코드 #include using namespace std; #define INF 1e9 int main() { ios::sync_with_stdio(false); cin.tie(NULL); int N, M, dist[101][101]; cin >> N >> ..

2812번: 크게 만들기 문제 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 N자리 숫자에서 숫자 K개를 지워 얻을 수 있는 가장 큰 수를 구하는 문제다. 결과는 N-K자리 숫자가 되는데 앞자리 수가 클수록 큰 수가 될 것은 자명하다. 차례로 순회하며 이번 수보다 앞에 있으면서 작은 수를 지우면 될 것이다. 만약 수를 더 지워야 하면 가장 끝자리 수를 지우면 된다. 스택을 사용해 해결할 수 있고 스택과 같은 형태이면서 값 접근이 용이한 벡터를 사용해 풀었다. 코드 #include using namespace std..

9019번: DSLR 문제 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 D, S, L, R 쿼리를 사용해 A에서 B로 가는 최소 쿼리를 구하는 문제다. BFS로 문제를 해결할 수 있으며 시간초과에 유의해야 한다. visited 배열은 몇 번째 방문인지 나타내는 정수와 해당 정수까지 도달하는 최단 쿼리를 담고 있다. 처음에 L, R 쿼리 때문에 A, B를 string으로 수를 입력받아 또 정수로 바꾸고.. 이런 과정을 거쳤으..

2206번: 벽 부수고 이동하기 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 (1,1)부터 (N, M)까지 최단 경로를 구하는 문제다. 단, 벽이 있는 곳은 지나갈 수 없으며 단 한 번만 벽을 부술 수 있다. 틀린 풀이 벽이 있는 모든 점에 대해 그 벽이 없을 때의 경로를 탐색하는 방법으로 코드를 작성했고 시간초과가 났다. 벽의 개수만큼 BFS를 해야 하기 때문이다. 맞은 풀이 시간초과가 나지 않기 위해 ..