문제 이해 단계 https://www.acmicpc.net/problem/1022 더보기 반시계 방향으로 돌아가는 소용돌이를 구현해야 한다. 특이한 점은 음수 좌표까지 존재하고 이미 그림 상의 좌표는 지정해 놨고 위치도 이미 정해져 있다는 것이다. 우리가 해야 할 것은 가장 왼쪽 위 칸(r1, c1)과 가장 오른쪽 아래 칸(r2, c2) 사이에 있는 사각형 영역을 출력하는 것이다. 출력을 할 때는 왼쪽에 공백을 넣어 오른쪽에 공백을 넣어 출력해야 한다 문제 접근 단계 해당 문제에서 고려해야 할 점이 많다. 반시계로 도는 소용돌이 구현 이러나저러나 결국에는 반시계로 도는 소용돌이를 구현해야 해당 문제를 풀 수 있다. 위에서 정해준 (0,0) 좌표에서 시작하여 반시계방향으로 도는 소용돌이를 만드는 방법을 생..

문제 이해 단계 N개의 물건이 주어지고 각 물건에는 무게(W)와 가치(V)가 주어진다. 최대 K만큼 들 수 있을 때, 가질 수 있는 가치의 최댓값을 구하는 문제 문제 접근 단계 이 알고리즘의 문제는 이름에서 유추해 볼 수 있듯이 배낭 알고리즘이라는 DP 알고리즘 기법 쪽에서는 좀 유명한? 그런 알고리즘이다. 우선 여기서 주어지는 변수는 무게(W), 가치(V) 총 2가지가 있다. 이 두 가지 값은 모두 변하는 값이고, 가치의 최댓값을 구하는 데에 분명 영향을 줄 것이다. 즉, 점화식은 W, V를 이용한 2차원배열로 만들어질 가능성이 높다. 이제 이 점을 유의하면서 예제를 가지고 생각해 보자!! 무게 가치 6 13 4 8 3 6 5 12 이를 위에서 아래로 순차적으로 탐색한다고 가정한다. 그러니까 무게 순으..

문제 이해 단계 https://www.acmicpc.net/problem/15486 날짜 N과 각 날마다 할 수 있는 일 Ti와 그 일을 했을 때 버는 돈 Pi가 각각 주어진다. Ti는 그 일을 할 때마다 드는 날을 뜻하며, 그 일을 하는 동안에는 다른 일을 할 수 없다. 이런 상황일 때 돈을 최대한 벌었을 때의 수익을 구하는 문제이다. 문제 접근 단계 이해부터가 살짝 복잡했는데, N일까지 일을 해서 벌 수 있는 최대수익을 D [N]이라고 하자. 이때 유의해야 할 점은 N일까지라는 것은 N일을 포함하지 않는다. 즉 1~N-1일에 한 일만 포함하는 것이다. 이를 이용해서 1일부터 살펴보자면, 1일까지 일을 해서 번 돈은 당연히 0원일 것이고(D [1] = 0) 1일 때 일해서 번 돈은 3일이 지난 4일째의..

문제 이해 단계 수열이 주어졌을 때 위치를 가만히 둔 채로, 오름차순으로 증가하는 부분 수열은 구한다. 그때 가장 크게 증가하는 부분수열의 길이를 구하는 문제 문제 접근 단계 문제에 나와있는 예시로 생각해 보자 10 20 10 30 20 50 1번째 수(10)에서 가장 긴 부분수열의 길이는 1이다. 2번째 수까지의 경우의 수는 3가지이다. 1. 10 - 20 (2가지) 2. 20 (1가지) 3. 10 (1가지) 이때 가장 긴 부분수열은 1번째인 2이다. 3번째 수까지의 경우의 수는 1. 10 - 20 (2가지) 2. 20 - 10 (2가지) 3. 20 ... 로 2번째보다 길어지려면 20보다 수가 높아야 하는데, 그렇지 못하므로 그대로 최대 길이는 2이다. 4번째 수까지의 경우의 수는 1. 10 - 20..

문제 이해 단계 N의 길이를 가진 수열에서 최대 K개만큼 원소를 삭제할 수 있을 때, 최대한 많이 짝수끼리 연속되게 만드는 문제이다. 그때의 개수를 구하는 문제이다. 문제 접근 단계 처음에는 1차원에다가, 짝수와 홀수를 구분하여 탐색하는 BFS를 떠올렸다. 그런데 일반적인 탐색으로 하기에는 제거할 홀수의 경우의 수가 너무 많다. 그리고 그 경우의 수를 모두 체크하기엔 너무 연산이 복잡하고 또 시간이 오래 걸린다. 또한 여기서는 어떤 시작 인덱스나 숫자를 정해주지 않아서 그것 또한 찾아야 하기 때문에 이 방법은 어울리지 않는다고 생각했다. 그다음으로 떠올린 것은 다이내믹 프로그래밍이다. 왜냐하면 이런 제한시간이 짧고, 많은 경우의 수가 있는 경우에는 충분히 가능성 있기 때문이다. 연속된 짝수를 계산하기 위..

문제 이해 단계 입력값으로 N이 입력된다. 선택할 수 있는 봉지는 3kg와 5kg이다. 이 봉지들을 이용하여 정확히 Nkg을 나눠 담을 때 가장 적은 봉지가 나오게 하는 문제이다. 문제 접근 단계 현재에서 가장 이득이 되는 선택을 하는 그리디로 풀 수도 있지만, 다이나믹 프로그래밍(DP)으로도 풀 수 있다. 왜냐하면, 작은 부분에서의 답이 큰 부분의 답이 되기 때문이다. N = 15 일 때를 가정해 보자. 15kg는 12 + 3 또는, 10 + 5에서 만들어진 숫자이다. 즉 12,10에서 만들어진 숫자인데, 12와 10은 (9,7), (7,5)에서 만들어진 숫자이다. 이런 식으로 작은 부분의 연산값이 큰 부분의 값이 된다. 이런 특징을 띄고 있기 때문에 DP로 풀 수 있다는 것이다. N에서 가장 적은 봉..

문제 이해 단계 2차원 격자가 주어지고, 각 정점의 연결 정보들이 주어진다. 시작 위치 S와 도착 위치가 E가 주어졌을 때 S에서 E로 가는 최단 거리를 구하고, 그 후 S에서 E로 갔을 때, 방문하지 않았던 정점만을 사용하여 다시 E에서 S로 최단거리로 돌아간다. 이때의 최단 거리의 합을 구하는 문제이다. 문제 접근 단계 해당 문제를 어떻게 푸는지에 대한 키워드는 1. 최단 경로의 거리를 구한다는 것 2. 산책을 할 수 있는 경로의 데이터만 주어진 다는 것이다. 1번의 키워드에서 경로를 탐색하여 최소 횟수를 찾는 DFS나 BFS를 사용해야 한다는 것을 알았다. DFS와 BFS 중 어떤 것으로 풀어야 효율적 일지 고민 중이었는데 2번 키워드에서 힌트를 얻었다. 산책을 할 수 있는 경로만 주어진다는 것은 ..

문제 이해 단계 https://www.acmicpc.net/problem/16973 NxM 크기의 격자판이 주어지고, 크기가 HxW인 직사각형이 주어진다. 이동할 수 있는 칸은 0, 이동할 수 있는 칸은 1로 되어 있다. 직사각형의 가장 왼쪽 위의 칸이 처음에 주어지고, 도착 좌표가 주어진다. 이때 이 직사각형의 왼쪽 위가 도착좌표까지 갈 때 최단거리를 구하는 것 문제 접근 단계 직사각형의 크기가 있다는 점만 제외하고는 벽과 격자판이 존재한다는 점과 특정 지점까지 이동하는 최단 거리를 구해야 한다는 점에서 대표적인 BFS 문제라는 점이라는 것을 알 수 있다. 중요한 것은 직사각형이기 때문에 체크해야 할 부분이 하나가 아니라 여러 개로 늘어났다. 직사각형 왼쪽 위 칸이 도착 지점으로 가야 하므로, 이 문제..