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의 개수로 초기값을 모두 저장해놓고, 현재 수를 구성하는 제곱수..