https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net BFS 문제다. 이 문제를 푸는데 2~3일 정도 걸렸다. 문제는 백조 두 마리가 존재하고 이 백조들이 만나는 데까지 소요되는 날을 구하는 문제다. 이 사이에는 얼음이 존재하고, 이 얼음은 물과 접촉해 있을 때 녹는다. 처음 생각한 방법은 단순하게 얼음을 녹이고, 백조의 경로를 찾고를 반복하는 것이었다. 구현해볼 것도 없이 시간 초과가 날 것이기 때문에 바로 패스했다. ..
Algorithm
https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 우선순위 큐 문제다. 8개월 전에도 이 문제를 만났었다. 그 때는 벡터를 이용해 넣을 때마다 정렬하고 중앙값을 뽑아내는 작업으로 당연히 시간초과가 났다. 그리고 오늘 이 문제를 다시 만났다. 이 문제가 우선순위 큐를 이용한다는 것은 알고 있었다. 그러나 시간 복잡도를 계산했을 때 1000만이 넘어가 0.1초 보다 더 걸릴 것이라고 생각했다. 그리고 시간이 그렇게 걸릴 뿐만 아니라 ..
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net DP와 DFS 문제다. DFS를 통해 경로를 탐색하고, 돌아오는 길에 경우의 수를 저장해 값이 존재하는 경우 더 탐색하지 않는 DP를 이용한다. DFS의 return 조건은 도착지에 도달 했을 떄, 이미 방문한 적이 있을 때다. 모든 경로의 전체를 탐색하면 당연히 시간초과가 나기 때문에 이미 방문한 적이 있을 경우에는 탐색을 멈춘다. 탐색을 멈추고, 해당 칸에 저장된 값을 현재 칸에 더한다. 그렇게 쭉..
https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net BFS 문제다. 벽에서 갈 수 있는 칸들을 세는 문제다. 모든 벽에서 BFS를 돌리면 빈 칸을 여러 번 방문하기 때문에 시간초과가 날 것이다. 빈 칸의 영역을 찾아서 크기를 구한 뒤 배열에 저장해뒀다. 그 후 배열을 전체 탐색 하면서 벽인 경우 4방향을 검사해 갈 수 있는 영역의 크기를 더했다. 이 때 이어져 있는 영역이 존재할 수 있으므로, 영역을 찾을 때 영역의 번호를 부..
https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 비트마스킹을 이용한 BFS 문제다. 흔히 우리가 아는 2차원 배열에서 영역을 구하는 문제다. 그러나 인접한 모든 곳으로 지나갈 수 있는 것이 아니고 벽으로 막혀 있는 방의 영역을 구하는 문제다. 이 문제의 특징은 막힌 칸이 있는 것이 아니라 인접한 방 사이를 갈 수 없는 벽이 존재한다. 따라서 입력이 2차원 배열의 크기만큼 각 칸의 벽을 나타내는 정수가 들어온다. 좌1 상2 우4 하8로 2의..
https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 스택 자료구조 문제다. N자리 숫자에서 K개를 지워서 만들 수 있는 가장 큰 수를 찾는 문제다. 앞에서부터 순회해 스택에 숫자를 push한다. push 할 숫자가 stack에 들어있는 숫자보다 크다면 pop을 한다. 스택의 top보다 값이 작을 때까지 or k 범위 내에서 pop을 반복한다. 위 작업이 끝나면 스택에 남은 값들을 pop하면서 남은 문자열과 합쳐 답을 구한다. #include #include using namespace std; int n, m; int arr..
