우노

문제 링크 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[..

문제 링크 https://www.acmicpc.net/problem/1913 풀이 외각의 크기에 따라, 가운데 좌표를 시작점으로 상하좌우로 이동하는 횟수를 일반화할 수 있습니다. 시작점을 기준으로, 진행순서는 상 → 우 → 하 → 좌 → 상이며, 진행횟수는 n에 따라, 상 n번, 우 n-2번, 하 n-1번, 좌 n-1번이 됩니다. 또한, 진행하고 있는 외각의 크기에 따라 시작점이 항상 (n//2, n//2) 이 될 수 있도록 n을 조절해야합니다. 예를 들어, n이 7로 주어진다면, 현재 진행하고 있는 외각이 변경됨에 따라 시작좌표를 (3, 3) → (2, 2) → (1, 1)로 변경해야합니다. 세부 알고리즘은 아래 코드와 같습니다. 코드 import sys # 자연수 N 입력 n = int(sys.std..

문제 링크 https://www.acmicpc.net/problem/1212 풀이 파이썬 내장함수를 사용하면 됩니다. 입력을 8진수로 변환한 뒤, bin()을 통해 2진수로 변환하고, 맨 앞의 '0b'를 제외한 나머지를 출력하면 됩니다. 추가적으로, 각 숫자가 8 이상인 입력은 들어오지 않습니다. 코드 import sys # 입력을 8진수로 변환 n = int(sys.stdin.readline().rstrip(), 8) # 8진수를 2진수로 변환한 뒤, 맨 앞의 '0b'를 제외한 나머지 출력 print(bin(n)[2:])

문제 링크 https://www.acmicpc.net/problem/21608 풀이 주어진 조건에 따라 순서대로 구현하면 되지만, 조건문에 따라 학생을 앉힐 수 있는 좌석을 비교하는 방법보단, 모든 비어있는 칸을 중심으로 인접한 칸들을 탐색하며, [좋아하는 학생의 수, 비어있는 칸의 개수, 중심 칸의 행 번호, 중심 칸의 열 번호]를 저장하고, 모든 칸을 탐색했을 때, 위 리스트에 대해, 좋아하는 학생의 수와 비어있는 칸의 개수는 내림차순으로 정렬하고, 중심 칸의 행 번호와 중심 칸의 열 번호는 오름차순 정렬한 뒤, 리스트의 가장 첫번째 요소의 행과 열 위치에 해당 학생을 앉히는 방법이 더 효율적입니다. 코드 import sys n = int(sys.stdin.readline()) # 자리 정보 seat..

문제 링크 https://www.acmicpc.net/problem/1339 풀이 해당 문제를 일반화하기 위해선, 각 알파벳의 자릿수를 기억해야합니다. 예를 들어, GCF + ACDEB 가 주어졌을 때, 각 알파벳의 자릿수를 별도로 저장합니다. A는 만의 자릿수를 가지기 때문에 10000 C는 천의 자릿수와 십의 자릿수를 둘 다 가지기 때문에 1010 G는 백의 자릿수를 가지기 때문에 100 D는 백의 자릿수를 가지기 때문에 100 E는 십의 자릿수를 가지기 때문에 10 B는 일의 자릿수를 가지기 때문에 1 F도 일의 자릿수를 가지기 때문에 1 이렇게 알파벳의 자릿수를 별도로 저장한 뒤, 자릿수를 내림차순 정렬하고, 자릿수가 높은 순서대로 숫자를 감소시켜가며 곱셈을 진행합니다. A = 10000 * 9 ..

문제 링크 https://www.acmicpc.net/problem/16953 풀이 B를 A로 바꾸는 방식으로 진행한다. B가 2로 나눠진다면, B를 2로 나누고 나눠지지 않으며, B의 가장 오른쪽이 1이라면, 가장 오른쪽에서 1을 제거한다. B가 2로 나눠지지도 않고, 가장 오른쪽이 1이 아닌 경우도 있다는 것을 주의해야한다. 코드 import sys # A와 B 입력 a, b = map(int, sys.stdin.readline().split()) # 변환 횟수 count = 1 # A보다 B가 클때까지 while (a < b): # B가 2로 나눠진다면, B를 2로 나누고 if (b % 2 == 0): b = b // 2 # 나눠지지 않는다면, else: # B의 가장 오른쪽이 1이라면 if (in..