YJLee-devlog 🍎

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 Dynamic Programming의 유명한 문제인 편집 거리 문제와 유사한 문제라고 생각이 됨. 편집 거리 문제와 마찬가지로, 팰린드롬을 만들어야 할 입력받은 문자열을 각각 행과 열에 알파벳들을 배치한 후, 같은 문자열에 대해 배치했으므로 주대각선은 모두 더이상 추가해야할 알파벳이 없으므로 모두 0으로 채울 수 있음 그리고 이 문제의 경우 편집거리 문제와 값을 채워나가는 방식이 반대로 아래서 부터 채워나가야 함 값을 채울 때 조건은 입력 받은 문자열을 str이라고 했을 때, str[i] == str[j]라면, 더이상 채울 알파벳이 없으므로, 해당 알파벳을 제외한 안쪽의 알파벳들이 팰린드롬을 이루면 되므로, 왼쪽 아래 대각선의 값을 복사하면 되고,..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 위 문제의 경우 유명한 편집거리 알고리즘과 유사한데, 다른 점은 삽입, 삭제, 교체 연산중 삽입, 삭제 두 가지 연산만 존재한다는 점 따라서 A 문자열의 알파벳들을 행으로, B 문자열의 알파벳들을 열로 배치했을 때, 발생할 수 있는 연산에 대해 저장해 나가는 동적 계획법 알고리즘을 사용할 수 있음 먼저, A[i] == B[j] 라면, 더 이상 수행해야할 연산이 없으므로, 왼쪽 대각선 위에서 값을 그대로 복사하면 되고, A[i]와 B[j]가 같지 않다면, table[i][j]의 위의 값 + 1인 삭제 연산한 값과, 왼쪽 값 + 1인 삽입 연산한 값 중 작은 값을 현재 table[i][j]에 저장하면 됨 따라서, table[i][j] = A[0 ~ i..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 위 문제는 완전탐색, 분할 정복법 등으로 해결할 수 있지만, 문제의 크기가 1,000,000 이므로 조금 더 효율적인 알고리즘을 설계해야 함 따라서 각 원소를 포함하는(오른쪽 끝으로 생각) 연속 부분 중 최대값을 저장해 나가면서 마지막 원소까지 이를 결정하고, 해당 값들이 저장되어있는 배열의 최대값을 찾음으로써 문제를 해결할 수 있음 여기서 주의해야할 점은, 가장 끝에 있는 원소가 최대값이라고 생각하기 쉬운데, 이는 뒤에 있는 원소가 음수가 나올 경우 더 작아질 수 있는 상황이 발생할 수 있으므로, 각 원소를 끝으로하는 연속 부분 중 최대값을 각각 구해놓고 그 중에 최대값을 선택해야 수열의 연속 부분 최대합을 구할 수 있음 따라서, T[i] = i..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 로봇의 시작점에서 오른쪽과 아래쪽으로만 이동할 수 있는 것을 반대로 생각하면, 종착점을 기준으로는 왼쪽과 위쪽에서 더 큰 자원을 수집하면서 종착점까지 도달할 것임을 예측할 수 있음 따라서 큰 문제를 해결하기 위해 작은 문제부터 차근차근 해결해 나가는 동적 계획법으로 문제를 해결할 수 있음 따라서, T[i][j] = 나를 기준으로 왼쪽과 오른쪽 중 더 큰 값을 나에게 더한 값이고, T[i][j] + Max(T[i - 1][j], T[i][j - 1])로 점화식을 세울 수 있음 (0, 0)에서는 위와 왼쪽이 없으므로, (1, 1)부터 원소를 채워놓고 위 점화식을 적용하여 최종적으로 T[N][M]에 누적된 값이 정답이며, O(N * M)의 시간복잡도로 ..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 모든 수는 1^2의 합으로 나타낼 수 있음 하지만 문제에서 요구하는 조건은 제곱수의 개수를 최소화 하여 숫자 N을 나타내야 함 따라서 일일히 시도해 보기에는 문제의 크기가 100,000이므로 시간안에 해결하지 못할 가능성이 큼 그러므로 규칙을 파악해야 하는데, 1의 경우 1^2, 2의 경우 1^2 + 1^2, 3의 경우 1^2 + 1^2 + 1^2, 4의 경우 2^2 5의 경우 1의 경우에 2^2를 1개를 더해주면 되고, 6의 경우 2의 경우에 2^2를 1개 더해주면 됨. 위 패턴을 살펴보면, 미리 구해놓은 개수를 통해 자신을 구할 수 있으므로 동적 계획법을 사용할 수 있음 먼저 1^2의 개수로 초기값을 모두 저장해놓고, 현재 수를 구성하는 제곱수..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 N = 3인 경우, 2 x 1의 타일로 2 x 3의 타일을 채울 수 있는 경우의 수를 구해야 함 오른쪽 끝의 2 x 1 타일이 세워져 있는 경우와, 누워 있는 경우를 생각해보았을 때, 세워져 있는 경우는 앞의 2개의 2 x 1 타일도 세워져 있어야 하는 경우와 앞의 2개의 2 x 1 타일이 층으로 나누어져 있는 경우에 나머지 2 x 1 타일을 1개 세우는 경우로 볼 수 있으므로 즉, 2 x 2의 타일을 채워야 하는 경우의 수와 같음 누워져 있는 경우는 혼자 누워져 있을 수 없으므로 2개가 층으로 나누어져 있고, 앞에 2 x 1 타일 1개가 세워져 있을 수 밖에 없음 즉, 2 x 1의 타일을 채워야 하는 경우의 수와 같음 따라서 위 경우의 수를 모두..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 N이 100,000이기 때문에 O(N^2) 완전탐색으로 문제를 시간안에 해결할 수 없을 뿐더러, 이전에 선택했던 버튼을 다음 차례에서 선택하지 않고, 현재 차례에 선택한 버튼은 다음 차례에서 선택할 수 없고 이전 차례는 다음 차례에서 선택할 수 있는 패턴을 구현하기도 까다로움 따라서 현재 시점을 기준으로 이전 시점을 바라봤을 때, 현재 버튼을 선택하게 되면 이전 버튼에서 현재 버튼을 제외한 나머지 2버튼 중 최대 값을 현재 버튼 값에 더하는 패턴을 찾을 수 있고, 즉 이러한 과정을 N개의 시간에 대해 반복하게 되므로 작은 문제를 해결하여 큰 문제를 해결하는 동적 계획법을 사용할 수 있음 위 과정을 반복하고 최종적으로 N초에 해당 하는 값 중 최대값..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 연속하여 3개의 카드를 가져갈 수 없으므로, 카드를 가져가는 경우는 3가지로 나뉨 1. 현재 카드를 가져가지 않는 경우 2. 현재 카드를 가져가고 이전 카드를 가져가지 않는 경우 3. 현재 카드를 가져가고 이전 카드도 가져가는 경우 위 3가지 경우에 대한 최대값을 각각 저장해놓고 최종적으로 3가지 경우 중 최대값을 찾음으로써 문제를 해결할 수 있으며, 동적 계획법을 사용한 알고리즘 현재 카드를 가져가지 않는 경우에는 이전 카드에 대한 위 3가지 경우 중 최대값을 저장해야함 현재 카드를 가져가고 이전 카드를 가져가지 않는 경우는 현재 카드의 값에 이전 카드를 가져가지 않았을 때의 값을 저장 현재 카드와 이전 카드를 모두 가져가는 경우는 현재 카드의 ..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 처음 문제를 접했을 때, 완전탐색으로 문제를 설계하기가 까다로움 따라서 규칙을 살펴보면, 구슬은 1개 ~ 3개 가져갈 수 있으므로, 1 ~ 3개일 때는 철수가 먼저 가져가므로 이길 수 밖에 없음 4개의 경우 따져보면, 영희가 이길 수 밖에 없음 5개 6개 7개 일때는 철수가 이길 수 있는 경우가 있음 8개의 경우 영희가 이길 수 밖에 없음. 따라서 4로 나누어 떨어지는 경우, 영희가 이기고 아닌 경우는 철수가 이길 가능성이 있는 것을 간단하게 알 수 있지만, 동적계획법을 풀이할 수도 있음 철수와 영희가 공평하게 번갈아 가면서 구슬을 최선을 다해 가져가므로, 현재 시점이 철수가 구슬을 가져가는 시점이라고 가정하면, 이전 시점에서 영희가 구슬을 1개 ..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 직사각형의 2차원 배열의 각 좌표까지의 합 = (0, 0)부터 (N, M) 까지 각 왼쪽 좌표 + 위 좌표 - 왼쪽 대각선 좌표 + 자기자신을 통해 구할 수 있고, 이 합을 담고 있는 배열에서 원하는 좌표 범위의 합을 구할 수 있음 위 그림의 예시의 경우 (0, 0)부터 (3, 3)까지의 합을 (3, 3)에 저장하고 있으므로 (0, 0) ~ (3, 3)의 합 - (0, 0) ~ (3, 1)의 합 - (0, 0) ~ (0, 3)의 합 + (0, 0) ~ (0, 1)의 합(2번 빠지는 부분)을 하게 되면 (1, 2) ~ (3, 3)까지의 합을 구할 수 있음 각 범위의 합을 미리 구해놓음으로써 문제를 해결할 수 있으므로 동적 계획법을 사용한 알고리즘 소..