📝문제1. 백준 18353번(병사 배치하기)
- 문제
https://www.acmicpc.net/problem/18353
- 코드💻
n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 가장 긴 증가하는 부분 수열 문제로 변환
array.reverse()
# 다이나믹 프로그래밍을 위한 1차원 dp 테이블 초기화
dp = [1] * n
# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1, n):
for j in range(0, i):
if array[j] < array[i]:
dp[i] = max(dp[i], dp[j] + 1)
# 열외시켜야 하는 병사의 최소 수를 출력
print(n-max(dp))- 해설📖
이 문제의 기본 아이디어는 '가장 긴 증가하는 부분 수열(LIS)'로 알려진 전형적인 다이나믹 프로그래밍 문제의 아이디어와 같다. '가장 긴 증가하는 부분 수열' 문제란, 하나의 수열이 주어졌을 때 값들이 증가하는 형태의 가장 긴 부분 수열을 찾는 문제이다.
예를 들어 하나의 수열 array = {10, 20, 10, 30, 20 , 50}가 있다고 하자. 이때 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50}이 될 것이다. 'D[i] = array[i]'를 마지막 원소로 가지는 부분 수열의 최대 길이'라고 정의 하면, 가장 긴 증가하는 부분 수열을 계산하는 점화식은 다음과 같다. 이때 dp 테이블의 값은 모두 1로 초기화한다.
모든 0 <= j < i 에 대하여, D[i] = max(D[i], D[j] + 1) if array[j] < array[i]
최종적으로 테이블의 값은 [1, 2, 1, 3, 2, 4]이고, 이렇게 테이블에 남아 있는 값 중에서 가장 큰 값이 가장 긴 증가하는 부분 수열의 길이이다. 현재 예시에서는 4가 최장 길이가 된다.
현재의 문제는 병사를 배치할 때 전투력이 높은 병사가 앞쪽에 오도록 내림차순 배치를 하고자 한다. 따라서 이 문제를 '가장 긴 감소하는 부분 수열'의 길이를 계산하는 문제로 간주하고, 입력으로 주어진 원소의 순서를 뒤집은 뒤에 '가장 긴 증가하는 부분 수열' 문제를 풀 때의 점화식을 그대로 적용하면 해결할 수 있다.
https://sigcho.tistory.com/123
-> LIS 라는 개념이 잘 이해가 가지 않는다..
📝문제2. 못생긴 수
- 문제
못생긴 수란 오직 2, 3, 5만을 소인수로 가지는 수를 의미합니다. 다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 의미합니다. 1은 못생긴 수라고 가정합니다. 따라서 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... }순으로 이어지게 됩니다. 이때, n번째 못생긴 수를 찾는 프로그램을 작성하세요. 예를 들어 11번째 못생긴 수는 15입니다.
입력 조건
- 첫째 줄에 n이 입력됩니다. (1 <= n <= 1,000)
출력 조건
- n번째 못생긴 수를 출력합니다.
입력 예시1
10
출력 예시1
12
입력 예시2
4
출력 예시2
4
- 코드💻
n = int(input())
ugly = [0] * n # 못생긴 수를 담기 위한 테이블 (1차원 DP 테이블)
ugly[0] = 1 # 첫 번째 못생긴 수는 1
# 2배, 3배, 5배를 위한 인덱스
i2 = i3 = i5 = 0
# 처음에 곱셈 값을 초기화
next2, next3, next5 = 2, 3, 5
# 1부터 n까지의 못생긴 수들을 찾기
for l in range(1, n):
# 가능한 곱셈 결과 중에서 가장 작은 수를 선택
ugly[l] = min(next2, next3, next5)
# 인덱스에 따라서 곱셈 결과를 증가
if ugly[l] == next2:
i2 += 1
next2 = ugly[i2] * 2
if ugly[l] == next3:
i3 += 1
next3 = ugly[i3] * 3
if ugly[l] == next5:
i5 += 1
next5 = ugly[i5] * 5
# n번째 못생긴 수를 출력
print(ugly[n - 1])- 해설📖
이 문제는 가능한 못생긴 수를 앞에서부터 하나씩 찾는 방법으로 해결할 수 있다. 못생긴 수들은 {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,,,}와 같이 끊임없이 존재한다. 이때 못생긴 수에 2, 3 혹은 5를 곱한 수 또한 '못생긴 수'에 해당한다는 점이 포인트이다.
2의 배수 변수, 3의 배수 변수, 5의 배수 변수에 대하여 각각 '가장 작은 못생긴 수'부터 오름차순으로 하나씩 확인하면서, 각 배수를 곱한 값도 '못생긴 수'가 될 수 있도록 처리하면 정답 판정을 받을 수 있다.
예를 들어 먼저 못생긴 수로 1이 있다고 해보자. 이때 각각 2의 배수, 3의 배수, 5의 배수를 구하면 다음과 같다.
- 2의 배수 : 1 x 2 = 2
- 3의 배수 : 1 x 3 = 3
- 5의 배수 : 1 x 5 = 5
이로써 우리는 새롭게 2, 3, 5 또한 못생긴 수에 해당한다는 것을 알 수 있다. 따라서 이를 고려했을 때, 전체 못생긴 수는 {1, 2, 3, 5}가 된다.
첫 번째로 못생긴 수인 1에 이어서 그다음으로 못생긴 수는 2가 된다. 이때 각각 2의 배수, 3의 배수, 5의 배수를 구하면 다음과 같다.
- 2의 배수 : 2 x 2 = 4
- 3의 배수 : 2 x 3 = 6
- 5의 배수 : 2 x 5 = 10
이로써 우리는 4, 6, 10이 못생긴 수에 해당한다는 것을 알 수 있다. 따라서 이를 고려했을 때, 전체 못생긴 수는 {1, 2, 3, 4, 6, 10}이 된다. 이렇게 못생긴 수들을 작은 수부터 차례대로 확인하면서, 각 못생긴 수에 대해서 2의 배수, 3의 배수, 5의 배수를 고려한다는 점을 기억하여 효율적으로 소스코드를 작성하면 다음과 같이 작성할 수 있다.
📝문제3. 편집 거리
- 문제
- 코드💻
str1 = "sunday"
str2 = "saturday"
n = len(str1)
m = len(str2)
dp = [[0] * (1+m) for _ in range(1+n)]
for i in range(1, n+1):
dp[i][0] = i
for j in range(1, m+1):
dp[0][j] = j
for i in range(1, n+1):
for j in range(1, m+1):
if str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + 1
print(dp[n][m])
- 해설📖
- https://bgspro.tistory.com/36
- https://soooprmx.com/%ED%8E%B8%EC%A7%91%EA%B1%B0%EB%A6%AC-%EB%8B%A8%EC%96%B4%EC%9D%98-%EC%9C%A0%EC%82%AC%EB%8F%84-%EB%B6%84%EC%84%9D/
- https://oboki.net/workspace/python/algorithm-edit-distance/
'이것이 코딩 테스트다 with 파이썬(나동빈)' 책과 유튜브 강의를 기반으로 작성한 글입니다.
