Q31. 금광
난이도: 🌕🌗
풀이시간: 30분
시간제한: 1초
메모리제한: 128MB
기출: Flipkart 인터뷰
n x m 크기의 금광이 있다. 금광은 1x1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다.
채굴자는 첫 번째 열부터 출발하여 금을 캔다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다.
이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다.
결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하시오.
입력 조건
- 첫째 줄에 테스트 케이스 T 입력 (1≤T≤1,000)
- 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력 (1≤n, m≤20), 둘째 줄에 n x m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력 (1≤각 위치에 매장된 금의 개수≤100)
출력 조건
- 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력. 각 테스트 케이스는 줄 바꿈을 이용해 구분
# 입력 예시
2
3 4
1 3 3 2 2 1 4 1 0 6 4 7
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2
# 출력 예시
19
16<내가 푼 방식>
첫 시작은 1열에서 가장 큰 값 선택. 이때의 열을 r이라고 하자.
다음 열로 넘어가면서 r-1, r, r+1 확인한다. 이때 r-1이나 r+1이 n을 넘어가지 않는지 확인.
<해설>
- 왼쪽 위에서 오는 경우
- 왼쪽 아래에서 오는 경우
- 왼쪽에서 오는 경우
3가지 경우 중 가장 많은 금을 가지고 있는 경우를 테이블에 저장하면 된다.
dp[i][j] = array[i][j] + max(dp[i-1][[j-1], dp[i][[j-1], dp[i+1][j-1])
위에서 array는 초기 금광 정보, dp는 다이나믹 프로그래밍을 위한 2차원 테이블
for tc in range(int(input())):
n, m = map(int, input().split())
array = list(map(int, input().split()))
dp = []
index = 0
for i in range(n):
dp.append(array[index:index+m])
index += m
for j in range(1,m):
for i in range(n):
# 왼쪽 위에서 오는 경우
if i == 0:
left_up = 0
else:
left_up = dp[i-1][j-1]
# 왼쪽 아래에서 오는 경우
if i == n-1:
left_down = 0
else:
left_down = dp[i+1][j-1]
# 왼쪽에서 오는 경우
left = dp[i][j-1]
dp[i][j] = dp[i][j] + max(left_up, left_down, left)
result = 0
for i in range(n):
result = max(result, dp[i][m-1])
print(result)Q32. 정수 삼각형
난이도: 🌕🌗
풀이시간: 30분
시간제한: 2초
메모리제한: 128MB
기출: IOI 1994년도
링크: https://www.acmicpc.net/problem/1932
n = int(input())
array = []
for _ in range(n):
array.append(list(map(int, input().split())))
for i in range(1,n):
for j in range(i+1):
# 대각선 왼쪽
if j == 0:
left = 0
else:
left = array[i-1][j-1]
# 대각선 오른쪽
if j == i:
right = 0
else:
right = array[i-1][j]
array[i][j] = array[i][j] + max(left, right)
print(max(array[n-1]))Q33. 퇴사
난이도: ⭐⭐
풀이시간: 30분
시간제한: 2초
메모리제한: 512MB
기출: 삼성전자 SW 역량테스트
링크: https://www.acmicpc.net/problem/14501
나는 아래처럼 풀었는데 예제 입력 4에서 틀린다.
n = int(input())
consults = []
result = 0
for _ in range(n):
t, p = map(int, input().split())
consults.append((t, p))
for i in range(n):
if i + consults[i][0] > n: continue
price = consults[i][1]
idx = i
while(True):
idx += consults[idx][0]
if idx > n - 1: break
if idx + consults[idx][0] > n: break
price += consults[idx][1]
result = max(result, price)
print(result)<해설>
'dp[i] = i번재 날부터 마지막 날까지 낼 수 있는 최대 이익'이라고 하자.
dp[i] = max(p[i] + dp[t[i] + i]], max_value)
n = int(input())
t = []
p = []
dp = [0] * (n + 1)
max_value = 0
for _ in range(n):
x, y = map(int, input().split())
t.append(x)
p.append(y)
for i in range(n - 1, -1, -1):
time = t[i] + i
# 상담이 기간 안에 끝나는 경우
if time <= n:
dp[i] = max(p[i] + dp[time], max_value)
max_value = dp[i]
# 상담이 기간을 벗어나는 경우
else:
dp[i] = max_value
print(max_value)Q34. 병사 배치하기
난이도: 🌕🌗
풀이시간: 30분
시간제한: 1초
메모리제한: 256MB
기출: 핵심 유형
링크: https://www.acmicpc.net/problem/18353
<시도>
n = int(input())
arr = list(map(int, input().split()))
result = 0
max_value = 0
for i in range(n-1, -1, -1):
a = arr[i]
new_arr = arr[0:i+1]
result = len(new_arr)
for j in range(len(new_arr)-1):
if new_arr[j] < new_arr[j+1]:
result -= 1
#new_arr = [x for x in arr[0:i] if x > a]
#new_arr.append(a)
max_value = max(result, max_value)
print(n - max_value)리스트를 뒤에서부터 읽으면서 원소 하나를 기준으로, 그 원소의 앞 부분이 내림차순인지 확인했는데 백준 제출해보니 틀렸다!
<해설>
📌 '가장 긴 증가하는 부분 수열(LIS; Longest Increasing Subsequence)'로 알려진 전형적인 다이나믹 프로그래밍 문제의 아이디어와 동일
➡ 하나의 수열이 주어졌을 때 값들이 증가하는 형태의 가장 긴 부분 수열을 찾으면 된다.
'D[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이'라고 정의하면 점화식은 아래와 같다.
모든 0≤j<i에 대해, D[i] = max(D[i], D[j]+1) if array[j] < array[i])
지금 푸는 문제는 내림차순 배치를 하고자 하므로, 입력으로 주워진 원소의 순서를 뒤집은 뒤에 위의 점화식을 적용하면 해결할 수 있다.
n = int(input())
arr = list(map(int, input().split()))`
# 순서를 뒤집어 '가장 긴 증가하는 부분 수열' 문제로 변환
arr.reverse()
# 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
dp = [1] * n
# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1, n):
for j in range(0, i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j] + 1)
print(n - max(dp))Q35. 못생긴 수
난이도: 🌕🌗
풀이시간: 30분
시간제한: 1초
메모리제한: 128MB
기출: Google 인터뷰
못생긴 수: 오직 2,3,5만을 소인수(prime factor)로 가지는 수
즉, 오직 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<해설>
📌 못생긴 수에 2,3,5를 곱한 수 또한 못생긴 수에 해당
2의 배수 변수, 3의 배수 변수, 5의 배수 변수에 대하여 각각 '가장 작은 못생긴 수'부터 오름차순으로 하나씩 확인하면서, 각 배수를 곱한 값도 '못생긴 수'가 될 수 있도록 처리하면 된다.
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 i in range (1, n):
# 가능한 곱셈 결과 중에서 가장 작은 수 선택
ugly[i] = min(next2, next3, next5)
# 인덱스에 따라서 곱셈 결과를 증가
if ugly[i] == next2:
i2 += 1
next2 = ugly[i2] * 2
if ugly[i] == next3:
i3 += 1
next3 = ugly[i3] * 3
if ugly[i] == next5:
i5 += 1
next5 = ugly[i5] * 5
print(ugly[n-1])Q36. 편집 거리
난이도: 🌕🌗
풀이시간: 30분
시간제한: 2초
메모리제한: 128MB
기출: Goldman Sachs 인터뷰
두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 한다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있다.
- 삽입(Insert): 특정한 위치에 있는 하나의 문자를 삽입
- 삭제(Remove): 특정한 위치에 있는 하나의 문자를 삭제
- 교체(Replace): 특정한 위치에 있는 하나의 문자를 다른 문자로 교체
이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미한다.
문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하시오.
입력 조건
- 두 문자열 A와 B가 한 줄에 하나씩 주어진다.
- 각 문자열은 영문 알파벳으로만 구성되어 있으며, 각 문자열의 길이는 1보다 크거나 같고, 5,000보다 작거나 같다.
출력 조건
- 최소 편집 거리 출력
# 입력예시 1
cat
cut
# 출력예시 1
1
# 입력예시 2
sunday
saturday
# 출력예시 2
3<해설>
최소 편집 거리를 담을 2차원 테이블을 초기화한 뒤에, 최소 편집 거리를 계산해 테이블에 저장하는 과정으로 문제를 해결할 수 있다.
다이나믹 프로그래밍 점화식
- 두 문자가 같은 경우: dp[i][j] = dp[i-1][j-1]
- 두 문자가 다른 경우: dp[i][j] = 1 + min(dp[i][j - 1], dp[i-1][j], dp[i-1][j-1])
1의 경우, 행과 열에 해당하는 문자가 서로 같다면, 왼쪽 위에 해당하는 수를 그대로 대입한다는 의미.
2의 경우, 행과 열에 해당하는 문자가 서로 다르다면, 왼쪽(삽입), 위쪽(삭제), 왼쪽 위(교체)에 해당하는 수 중에서 가장 작은 수에 1을 더해 대입한다는 의미.
# 최소 편집 거리 계산을 위한 다이나믹 프로그래밍
def edit_dist(str1, str2):
n = len(str1)
m = len(str2)
# 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
dp = [[0] * (m + 1) for _ in range(n + 1)]
# DP 테이블 초기 설정
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]
# 문자가 다르다면, 3가지 경우 중에서 최솟값 찾기
else: # 삽입(왼쪽), 삭제(위쪽), 교체(왼쪽 위) 중에서 최소 비용을 찾아 대입
dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
return dp[n][m]
str1 = input()
str2 = input()
print(edit_dist(str1, str2))이러한 유형은 스트링 편집 거리(string edit distance) 알고리즘이라고 부른다고 한다.
두 문자열의 유사도를 측정하기 위해 사용하는 알고리즘으로 Levenshtein distance(LD)라고도 한다. 출처
해설을 봐도 이해가 잘 되지 않아서 편집 거리 알고리즘에 대해 더 찾아봤다.
여기가 알고리즘 설명을 잘해둔 것 같다.
