Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
문제 www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 팰린드롬이란 거꾸로 읽어도 동일한 회문을 의미한다. start번째 수부터 end번째 수까지가 팰린드롬임을 확인하려면 일단 arr[start]와 arr[end]가 같아야 한다. 그 후 arr[start+1]에서 arr[end-1] 까지가 팰린드롬이라면 해당 수열은 팰린드롬임을 알 수 있다. 즉, arr[start]에서 arr[end]까지를 확인할 때 arr[start+1]에서 arr[end-1] 까지가 팰린드롬의 여부를 확인하므로 결과 값을..
문제 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 순열 조합과 비슷한 DP문제. 개인 적으로는 결국 조합의 경우 수 모두 찾아보기 때문에 배낭 알고리즘(Knapsack)과 비슷한 부분이 있는 것 같다. 해당 문제에서도 배낭 문제처럼 idx번째 색을 선택한 경우와 선택하지 않는 경우를 아래와 같이 표현할 수 있다. 1. idx 색을 선택: dp[idx-2][k-1] 인접 칸을 한 칸 띄워 idx-2로, 색 한 개를 선택하였으므로 남은 선택 색상 개수를 -1 해..
문제 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 풀이 DP문제 중에서도 배낭 문제에 해당한다. 배낭 알고리즘은 특정 조건을 만족시키는 물건을 선택하는 조합을 구해낼 수 있다. 해당 문제에서 구슬의 무게를 알 수 있는 경우는 두 가지이다. 1. 구슬 VS 추가 평형을 이루는 경우 2. 구슬+추 VS 추가 평형을 이루는 경우 1번의 경우 단순히 현재 weight에서 idx 번째 추를 선택하거나 선택하지 않는 경우를 확인하는 점화식을 거치면 된다..
문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 DP의 유형 중에서도 배낭 문제(Knapsack)의 대표 문제이다. 해당 유형의 문제를 풀기 전에는 배낭 알고리즘을 공부하고 풀어보는 것을 추천한다. 배낭 알고리즘은 여러 물건 중에서 특정한 조건을 만족시키는 조합을 구하는 문제들에 적용이 가능하다. 위의 문제에서 우리는 물건들 중에서 최대 무게를 넘지 않는 가치의 최댓값..
문제 https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net 풀이 간단한 DP문제였지만 bottom-up 방식으로만 접근하다 top-down 방식으로 해보니 쉽게 풀렸다. bottom-up 방식을 연습하는 것은 좋지만 문제마다 top-down 방식이 익숙하다면 먼저 재귀로 푼 후에 변환해보자. 단순히 생각하면 왼쪽 카드에서 가장 큰 수가 나올때 까지 모두 버려버리고 오른쪽 카드의 점수를 획득하는 그리디 방식을 떠올릴 수 도 ..
문제 www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 풀이 간단한 DP문제이지만 수열의 길이가 1인 경우의 예외 처리가 실수를 유발하는 듯하다. 우리가 현재의 숫자에서 확인해야 하는 것은 3가지 경우이다. 1. 다음 숫자가 더 큰 경우 2. 다음 숫자가 더 작은 경우 3. 다음 숫자와 같은 경우 본인의 경우 수열의 마지막 숫자부터 처음 숫자로 가는 역순으로 구성하였다. cache값을 2차원 배열(cache[100000][2])로 선언하여 cache[idx][0]..
문제 www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 풀이 Top_bottom 풀이 해당 순서(order)의 설정된 볼륨(volume)에서 다음 볼륨의 설정 값을 더하거나 빼주는 경우로 분기한다. 이때 두 가지 분기의 결과 중 더 큰 값을 저장하여 같은 값의 연산을 방지해준다. 모든 순서에서의 볼륨값을 탐색하여도 시간 복잡도는 O(NM)이므로 충분히 시간 안에 계산이 가능하다. 만약 현재의 볼륨에서 다음 설정 값으로 모두..
문제 www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 풀이 간단한 DP문제로 간단한 점화식 dp[r][c] = dp[r-1][c] + dp[r][c-1] 으로 경로의 수를 계산할 수 있다. k가 0인 경우와 아닌 경우만 나누어 k가 0이 아니라면 두 가지 문제로 분할해서 계산된 값들을 곱해주면 된다. 하지만 본인의 경우, 아래와 같은 실수로 애먹었다. 경유지인 행, 열 위치 계산을 아래와 같이 진행한다면 큰 오류가 발생한..
문제 www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 다이나믹 프로그래밍 문제이지만 메모이제이션을 적용할 방법이 떠오르지 않아 답을 봐버렸다... 해당 문제는 (r,c)위치가 1이라면 (r-1,c-1), (r-1,c), (r,c-1)위치를 확인하여 가장 작은 값 +1이 (r,c)에서의 가장 큰 정사각형의 변의 길이이다. 즉, 해당 위치를 오른쪽 아래 모서리로 삼는 가장 큰 정사각형의 길이를 저장한다. 이러한 연산을 모든 배열 값에 대해 실행해주면 이전의 값을 사용하여 빠르게 답을 구할 수 있다. 아래와 같은 예제로 예를 들..
문제 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 다이나믹 프로그래밍 문제. 만약 상근이가 0이상 20이하의 수만을 안다는 제한이 없다면 메모제이션할 양이 너무나 커서 구현할 수 없었을 것이다. 상근이는 0이상 20이하의 수 만을 다룰 수 있기 때문에 다음 수와 의 +나 -결과가 범위를 벗어난다면 계산을 진행할 필요가 없었다. 메모이제이션 기법으로 최적화하기 위해서는 어떤 값들이 중복 계산되는지 알아야한다. 아래와 같은 예제가 ..