나그네

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 처음에 가장 ..

13549번: 숨바꼭질 3 문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 다른 숨바꼭질 문제처럼 너비 우선 탐색(BFS)으로 해결할 수 있다. 단, x*2는 0초이므로 가장 우선적으로 해줘야 한다. 그리고 x+1과 x-1도 같은 1초가 걸리지만 뒤로 갔다가 ×2 하는 게 더 시간이 적게 걸릴 것이므로 x-1가 x+1보다 우선순위가 높다. visited 배열을 -1로 초기화해주고 시작지점을 0으로 바..

1697번: 숨바꼭질 문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS로 현재 위치로부터 +1, -1, ×2인 위치를 탐색한다. 만약 범위를 만족하면서 아직 방문하지 않았다면 큐에 추가해 주며 반복한다. visited 배열을 +1씩 해가며 몇 번만에 도달하는지 확인을 했다. visited[k] 값을 출력하면 된다. 코드 #include using namespace std; int n, k; vector..

1865번: 웜홀 문제 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 어느 시작점에서 다시 시작 지점으로 돌아올 때 시간이 되돌아갈 수 있는지 여부를 구하는 문제다. 벨만 포드 알고리즘을 사용해 풀 수 있다. 도로는 양방향이지만 웜홀은 단방향임을 주의해야 한다. 처음엔 dist[1] < 0 이면 YES를 출력하도록 했다. 그러나 2%틀을 받고 모든 정점에서 다 해보는 코드를 짰는데 90% 언저리에서 시간초과가 났다. 결국 벨..