우노

문제 링크 https://www.acmicpc.net/problem/1912 풀이 i번째 이전까지 연속된 부분 숫자들의 합을 계산하여, 최댓값을 그때그때 기록합니다. i번째 이전까지 연속된 부분 숫자들의 합이, 그냥 i번째 숫자보다 작은 경우, 이전의 기록들은 무의미해집니다. 해당 경우엔, 다시 i번째 숫자부터 연속된 부분 숫자들의 합을 구하면 됩니다. 예제 입력을 사용해, 시뮬레이션을 진행하면 이해가 쉽습니다. [2, 1, -4, 3, 4, -4, 6, 5, -5, 1] 이 주어진 경우 [2, 3, -1, 3, 7, 3, 9, 14, 9, 10] 이 됩니다. 코드 import sys # 정수 n n = int(sys.stdin.readline()) # n개의 정수로 이루어진 수열 arr = list(m..

문제 링크 https://www.acmicpc.net/problem/12852 풀이 DP 테이블과 점화식을 사용해 해결할 수 있습니다. f(x)는 아래 세 가지 값들 중 최솟값이 됩니다. f(x-1) + 1 x가 2로 나눠지는 경우, f(x//2) + 1 x가 3으로 나눠지는 경우, f(x//3) + 1 뒤에 1을 더하는 이유는, 이전 경우의 수로부터 +1 이 되기 때문입니다. 따라서, f(2)부터 f(N)까지 위의 점화식을 사용해 DP 테이블을 채워나가면 됩니다. 또한, 리스트 안에 또 리스트를 넣어, f(x)가 어떤 수들을 거쳐왔는지를 저장해 나가면 됩니다. 따라서, DP 테이블은 아래와 같은 형식으로 채워지게 됩니다. f(0) = [0, []] f(1) = [0, [1]] f(2) = [1, [1,..

문제 링크 https://www.acmicpc.net/problem/1958 풀이 2차원 DP 테이블을 사용한 LCS 문제와 동일한 방식으로, 3차원 DP 테이블을 사용해서 해결할 수 있습니다. 기본적인 LCS 알고리즘은 해당 포스트에선 생략하겠습니다. 코드 작성은 쉬울 수 있으나, 시각적으로는 잘 그려지지 않는 것 같습니다. 코드 import sys # 각 문자열 입력 first = sys.stdin.readline().rstrip() second = sys.stdin.readline().rstrip() third = sys.stdin.readline().rstrip() # DP 테이블 초기화 dp = [[[0] * (len(third)+1) for _ in range(len(second)+1)] fo..

문제 링크 https://www.acmicpc.net/problem/2169 풀이 특정 좌표로 갈 수 있는 방법은 아래와 같습니다. 위에서 오는 것 왼쪽에서 오는 것 오른쪽에서 오는 것 5x5 샘플 데이터를 통해 좌표 값들을 업데이트해보겠습니다. 먼저, 첫 번째 행은, 왼쪽에서 오른쪽로 진행하는 경우 밖에 없으므로, 각 좌표까지의 최대 가치를 먼저 업데이트할 수 있습니다. 이제 나머지 행들을 순서대로 탐색하며 좌표값들을 업데이트해야합니다. 이때, 각 행들을 두 가지 임시 배열(왼쪽 → 오른쪽으로 진행 시 구해진 최댓값, 오른쪽 → 왼쪽으로 진행 시 구해진 최댓값)로 표현한 뒤, 두 임시 배열을 비교함으로써, DP 테이블의 각 좌표를 최대값으로 업데이트할 수 있습니다. 왼쪽 → 오른쪽으로 진행될 경우, 임..

문제 링크 https://www.acmicpc.net/problem/5582 풀이 대표적인 DP 문제이며, 2차원 DP 테이블을 사용해서 풀 수 있습니다. 2차원 DP 테이블의 행과 열을 각각의 문자열로 구성한 뒤, 이중 for문을 통해 각각의 문자들을 비교하며, 각각의 문자가 같다면, 이전 공통 부분 문자열 길이에 1을 더해 저장해나가면 됩니다. 코드 # PyPy3로 제출 import sys # 각각의 문자열 first = sys.stdin.readline().rstrip() second = sys.stdin.readline().rstrip() # DP 테이블 dp = [[0] * (len(second)) for _ in range(len(first))] # 두 문자열에 모두 포함 된 부분 문자열 중 ..

문제 링크 https://www.acmicpc.net/problem/7579 풀이 0-1 냅색(배낭) 문제이며, 0-1 냅색 알고리즘의 개념을 알고 있다면 문제에 대해 더 쉽게 이해할 수 있습니다. https://www.youtube.com/watch?v=rhda6lR5kyQ 문제의 목표 특정 메모리를 넘는 최소 비용을 찾는 것 DP 테이블이 의미하는 것 0~i 까지의 앱을 종료하거나 종료하지 않았을 때, j 만큼의 cost를 사용함으로써 확보 가능한 최대 메모리값 아래 알고리즘을 진행합니다. 행은 앱의 개수만큼, 열은 cost의 총 비용만큼 만들어줍니다. 행을 차례대로 돌며 아래 알고리즘을 차례대로 수행합니다. j cost보다 현재 앱의 cost가 크다면, 아직 앱이 종료되지 않았으므로, 최대 메모리가..

문제 링크 https://www.acmicpc.net/problem/10942 풀이 2차원 DP 테이블을 채우는게 핵심입니다. DP[i][j]는, i 부터 j 까지의 숫자가 팰린드롬인지 아닌지를 나타냅니다. DP 테이블은 아래 조건을 통해 채워나갑니다. 연속된 숫자가 1개일 경우엔, 무조건 팰린드롬입니다. 연속된 숫자가 2개일 경우엔, 양끝 숫자가 같다면 팰린드롬입니다. 연속된 숫자가 3개 이상일 경우엔, 양끝 숫자가 같고, 그 사이의 숫자들이 팰린드롬이라면, 팰린드롬입니다. 따라서, 1번과 2번 조건을 실행한다면 DP 테이블은 아래와 같이 채워집니다. 이후, 3번 조건을 실행한다면, DP 테이블의 하향 대각선이 차례대로 채워집니다. 연속된 숫자가 3개일 때는, 세번째 하향 대각선 연속된 숫자가 4개일 ..

문제 링크 https://www.acmicpc.net/problem/10164 풀이 학창 시절에 배웠던 경로 찾기 방법을 사용하면 됩니다. 만약, (0, 0) 칸부터 (N-1, M-1) 칸까지의 경로를 찾는다면, 첫 행과 첫 열을 1로 채운 뒤, 빈 칸을 왼쪽 칸과 위쪽 칸의 덧셈 결과로 채워주면 됩니다. 따라서, 해당 방법을 사용해, 시작 지점에서 중간 지점까지의 경로를 구하고 중간 지점에서 마지막 지점까지의 경로를 구한 뒤, 두 값을 곱해주면 됩니다. 코드 import sys # 격자의 행의 수 n과 열의 수 m, ○로 표시된 칸의 번호 n, m, k = map(int, sys.stdin.readline().split()) # 경로 저장용 DP 테이블 graph = [[0]*m for _ in ran..

문제 링크 https://www.acmicpc.net/problem/11726 풀이 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 타일은 1x2 이나 2x1 타일 중 한가지 종류만 사용해서 채워도 괜찮습니다. 해당 문제는 단순한 점화식으로 해결할 수 있습니다. dp[i] = dp[i-1] + dp[i-2] 세부 알고리즘은 아래 예제 코드와 같습니다. 코드 import sys n = int(sys.stdin.readline()) # dp 테이블 dp = [0] * 1001 # 초기값 설정 dp[1] = 1 dp[2] = 2 # bottom-up 진행 for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[..

문제 두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다. 삽입(Insert): 특정한 위치에 하나의 문자를 삽입합니다. 삭제(Remove): 특정한 위치에 있는 하나의 문자를 삭제합니다. 교체(Replace): 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다. 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미합니다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요. 예를 들어 "sunday"와 "saturday"의 최소 편집 거리는 3입니다. 입력 조건 두 문자열 A와 B가 한줄에 하나씩 주..