나그네

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를 해야 하기 때문이다. 맞은 풀이 시간초과가 나지 않기 위해 ..

13913번: 숨바꼭질 4 문제 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 1697번 숨바꼭질 문제의 확장된 버전이다. 최단 시간뿐 아니라 그 경로도 구하는 문제다. [1697 숨바꼭질 문제] | [1697 숨바꼭질 풀이] x+1, x-1, x*2를 탐색할 때 한 번 방문한 점은 다시 방문하지 않으므로 어느 점에 방문할 때 어느 점에서 이동했는지를 기록하는 bef 배열을 만들었다. 존재할 수 없는 -..

14002번: 가장 긴 증가하는 부분 수열 4 문제 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 11053번 가장 긴 증가하는 부분 수열 문제의 확장 버전이다. LIS의 길이뿐 아니라 LIS를 이루는 수열을 구하는 문제다. [11053 가장 긴 증가하는 부분 수열 문제] | [11053 가장 긴 증가하는 부분 수열 풀이] LIS의 길이를 구하는 데까지는 ..

11054번: 가장 긴 바이토닉 부분 수열 문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 주어진 수열에서 점차 증가했다가 감소하는 가장 긴 부분 수열의 길이를 구하는 문제다. 아래 두 문제를 풀어본 후 도전하면 좋을 것 같다. [11053 가장 긴 증가하는 부분 수열 문제] | [11053 가장 긴 증가하는 부분 수열 해설] [11722 가장 긴 감소하는 부분 수열 문제] | [11722 가장 긴 감소하는 부분 수열 해설] 틀린 풀이 1 처음에 가장 ..