정화 코딩
EDOC 2024-1 6회차 과제 (동적 계획법 알아보기 4) 본문
093. Dance Dance Revolution (백준 2342번)
https://www.acmicpc.net/problem/2342
import sys
input = sys.stdin.readline
data = list(map(int, input().split()))
n = len(data) - 1
l = [0 for _ in range(n + 1)]
r = [0 for _ in range(n + 1)]
p = [0 for _ in range(n + 1)]
for i in range(n):
if l[i] == data[i] or r[i] == data[i]:
l[i + 1] = l[i]
r[i + 1] = r[i]
p[i + 1] = p[i] + 1
elif l[i] == 0:
l[i + 1] = data[i]
r[i + 1] = r[i]
p[i + 1] = p[i] + 2
elif r[i] == 0:
l[i + 1] = l[i]
r[i + 1] = data[i]
p[i + 1] = p[i] + 2
else:
ldif = abs(l[i] - data[i])
if ldif == 3:
ldif = 1
rdif = abs(r[i] - data[i])
if rdif == 3:
rdif = 1
if ldif < rdif:
l[i + 1] = data[i]
r[i + 1] = r[i]
p[i + 1] = p[i] + ldif + 2
else:
l[i + 1] = l[i]
r[i + 1] = data[i]
p[i + 1] = p[i] + rdif + 2
print(p[n])처음에는 그리디 알고리즘이 생각났다. 순간마다 가장 힘이 적게 들도록 선택하면 최종 값도 최적이 될 것 같았기 때문이다. 하지만 제출해보니 틀렸다. (오답)
이 문제를 그리디 알고리즘으로 풀면 안 되는 이유는, 해당 순간에는 최적이 아닐지라도 최종적으로는 최적이 되도록 하는 선택이 있을 수 있기 때문이다. 예를 들어, 왼쪽 발은 2에 있고 오른쪽 발은 1에 있는 상황에서 지시 사항으로 4와 1이 추가로 들어왔다고 생각해보자. 매 순간에서 최선의 선택을 하는 그리디 알고리즘으로 해결하면 오른쪽 발을 4로 옮기고 왼쪽 혹은 오른쪽 발을 다시 1로 옮겨야 하므로 사용되는 힘은 3 + 3 = 6이다. 하지만 만약 해당 순간에서는 비효율적인 것처럼 보이더라도 4가 들어왔을 때 오른쪽 발을 옮기지 않고 왼쪽 발을 옮겨서 다음에 들어오는 1을 위해 오른쪽 발은 1에 유지하면 사용되는 힘은 4 + 1 = 5이다. 이러한 경우가 있을 수 있기 때문에 그리디 알고리즘이 아닌 다이나믹 프로그래밍을 사용해야 한다.
import sys
input = sys.stdin.readline
p = [[0, 2, 2, 2, 2], # 0에서 다른 칸으로 움직일 때 드는 힘
[2, 1, 3, 4, 3], # 1에서 다른 칸으로 움직일 때 드는 힘
[2, 3, 1, 3, 4], # 2에서 다른 칸으로 움직일 때 드는 힘
[2, 4, 3, 1, 3], # 3에서 다른 칸으로 움직일 때 드는 힘
[2, 3, 4, 3, 1]] # 4에서 다른 칸으로 움직일 때 드는 힘
data = list(map(int, input().split()))
n = len(data) - 1
# dp[n][l][r] : n번째 지시 사항까지 완료한 후 왼발의 위치가 l이고 오른발의 위치가 r일 때 최소 누적 합
dp = [[[sys.maxsize for _ in range(5)] for _ in range(5)] for _ in range(n + 1)]
dp[0][0][0] = 0
for i in range(1, n + 1):
for j in range(5):
if j != data[i - 1]:
for k in range(5):
dp[i][data[i - 1]][j] = min(dp[i - 1][k][j] + p[k][data[i - 1]], dp[i][data[i - 1]][j])
for j in range(5):
if j != data[i - 1]:
for k in range(5):
dp[i][j][data[i - 1]] = min(dp[i - 1][j][k] + p[k][data[i - 1]], dp[i][j][data[i - 1]])
ans = sys.maxsize
for i in range(5):
ans = min(ans, dp[n][i][data[n - 1]])
ans = min(ans, dp[n][data[n - 1]][i])
print(ans)dp[n][l][r] : n번째 지시 사항까지 완료한 후 왼발의 위치가 l이고 오른발의 위치가 r일 때 최소 누적 합
n번째 지시 사항이 x라고 하면, 왼쪽 발이 x에 있는 경우(dp[n][x][_])와 오른쪽 발이 x에 있는 경우(dp[n][_][x]) 중 최소 값이 n번째 지시 사항까지 완료할 때 사용되는 최소 힘이 되는 것이다. (정답)
094. 행렬 곱셈 순서 (백준 11049번)
https://www.acmicpc.net/problem/11049
import sys
input = sys.stdin.readline
# bottom-up 방식
n = int(input())
m = []
# dp[i][j] : i번째 행렬부터 j번째 행렬까지 곱할 때 필요한 곱셈 연산의 수
dp = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(n):
a, b = map(int, input().split())
m.append([a, b])
for i in range(1, n):
for j in range(n - i):
dp[j][j + i] = sys.maxsize
for k in range(j, j + i):
dp[j][j + i] = min(dp[j][j + i], dp[j][k] + dp[k + 1][j + i] + m[j][0] * m[k][1] * m[j + i][1])
print(dp[0][n - 1])컴퓨터 알고리즘 수업에서 배운 bottom-up 방식으로 푼 풀이이다. (정답)
dp[i][j] : i번째 행렬부터 j번째 행렬까지 곱할 때 필요한 곱셈 연산의 수
점화식 ⇒ dp[i][j] : dp[i][k] + dp[k+1][j] + m[i][0] * m[k][1] * m[j][1]
점화식을 말로 풀어보면 다음과 같다. k를 i부터 (j-1)까지 증가시켜가면서 i번째 행렬부터 k번째 행렬까지 곱할 때 필요한 곱셈 연산의 수(이미 계산된 값)와 (k+1)번째 행렬부터 j번째 행렬까지 곱할 때 필요한 곱셈 연산의 수(이미 계산된 값)의 합 중 최소를 찾는다. 거기에 그 두 행렬를 곱할 때 필요한 곱셈 연산의 수인 m[i][0] * m[k][1] * m[j][1]를 더해주어야 한다.
import sys
input = sys.stdin.readline
# top-down & memoization 방식
n = int(input())
m = []
# dp[i][j] : i번째 행렬부터 j번째 행렬까지 곱할 때 필요한 곱셈 연산의 수
dp = [[-1 for _ in range(n)] for _ in range(n)]
for _ in range(n):
a, b = map(int, input().split())
m.append([a, b])
def execute(s, e):
if dp[s][e] != -1:
return dp[s][e]
if s == e:
return 0
if s + 1 == e:
return m[s][0] * m[s][1] * m[e][1]
res = sys.maxsize
for i in range(s, e):
res = min(res, m[s][0] * m[i][1] * m[e][1] + execute(s, i) + execute(i + 1, e))
dp[s][e] = res
return dp[s][e]
print(execute(0, n - 1))교재에 나와있는 top-down & memoization 방식으로 푼 풀이이다. (정답)
나머지는 전부 비슷한데 재귀적으로 푼 것 뿐이다. 계산하지 않은 값은 -1로 두어 구분하도록 하고, 한번도 계산하지 않았던 값에 대해서만 계산하고 이미 계산한 적이 있다면 저장된 값을 가져와야 한다.
그런데 두 풀이 모두 python으로 제출하면 시간 초과가 나오고 pypy로 제출해야 맞았습니다가 나온다. pypy로 제출한 경우에서 굳이 비교해보자면 bottom-up 방식이 top-down 방식보다 조금 더 빠른 것을 확인할 수 있었다.
095. 외판원 순회 (백준 2098번)
https://www.acmicpc.net/problem/2098
import sys
input = sys.stdin.readline
n = int(input())
w = []
for _ in range(n):
w.append(list(map(int, input().split())))
dp = [[0 for _ in range(1 << n)] for _ in range(n)]
def tsp(c, v):
if v == (1 << n) - 1: # 모든 도시를 방문한 경우
if w[c][0] == 0:
return(sys.maxsize)
else:
return w[c][0]
if dp[c][v] != 0: # 이미 방문한 도시인 경우
return dp[c][v]
mint = sys.maxsize
for i in range(n):
# 방문한 적이 없고, 갈 수 있는 도시인 경우
if ((v & (1 << i)) == 0 and w[c][i] != 0):
# 방문한 도시에 추가하여 다시 tsp 함수 호출
mint = min(mint, tsp(i, (v | (1 << i))) + w[c][i])
dp[c][v] = mint
return dp[c][v]
print(tsp(0, 1)) # 1번 도시(인덱스 0)부터 시작한다고 가정특정 노드에서 특정 노드까지의 최단 경로도 아니고 원래 위치로 다시 돌아오는 최단 순회 경로는 풀어본 적이 없어서 감도 안 오고 어렵게 느껴졌다. 그래서 태그를 슬쩍 보니 비트마스킹??? 들어본 적은 있지만 뭔지는 몰라서 이참에 알아보자.
비트 연산자
AND 연산 (&) : 둘 다 1이면 1 반환 (ex) 1010 & 1111 = 1010
OR 연산 (|) : 하나라도 1이면 1 반환 (ex) 1010 | 1111 = 1111
XOR 연산 (^) : 둘이 같으면 0, 다르면 1 반환 (ex) 1010 ^ 1111 = 0101
NOT 연산 (~) : 반전 (0이면 1, 1이면 0 반환) (ex) ~1010 = 0101
왼쪽 shift (<<) : 왼쪽으로 특정 칸만큼 이동 (ex) 001010 << 2 = 101000
오른쪽 shinft (>>) : 오른쪽으로 특정 칸만큼 이동 (ex) 001010 >> 2 = 000010
비트마스킹
컴퓨터는 내부적으로 bit 단위로 연산을 한다. 이러한 비트의 특성을 이용해서 이진수 표현을 자료구조로 쓰는 기법을 비트마스킹이다.
비트마스킹을 통한 집합 표현
비트마스킹을 이용하면 집합을 쉽게 표현할 수 있다. 구체적으로, 원소의 개수가 n개인 집합이 있다고 하면, 원소에 0부터 n-1까지 번호를 부여해서 부분 집합으로 나타낼 수 있다. 번호에 해당하는 비트 하나가 하나의 원소 상태며, 비트가 1이면 해당 원소가 집합에 포함되어 있다는 의미고, 0이면 포함되지 않는다는 의미이다. 예를 들어, 0부터 4까지의 수가 있을 때 1, 3, 4로 이루어진 집합은 01011로 표현할 수 있는 것이다.
비트마스킹의 장점
1. 빠른 수행 시간
2. 간결한 코드
3. 적은 메모리 사용량
관련 문제
백준 11723번: 집합 (https://www.acmicpc.net/problem/11723)
다시 이 문제로 돌아와서...
외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 문제라고 한다.
w[i][j] : 도시에서 도시로 가기 위한 비용 (갈 수 없으면 값이 0이다.)
dp[c][v] : 현재 도시가 c, 현재까지 방문한 모든 도시 리스트가 v일 때, 앞으로 남은 모든 도시를 경유하는 데 필요한 최소 비용
→ 현재까지 방문한 도시 리스트 v를 비트마스킹으로 표현한다. (ex) 1~4번 도시 중 1, 3번 도시 방문 → 0101(2) = 5(10)
⇒ 점화식: 방문하지 않은 도시 i에 대해 반복하면서, dp[c][v] = min(dp[c][v], dp[i][v | (1 << i)] + w[c][i])
참고로, 어느 도시를 시작 도시로 둘 것인지는 중요하지 않고 그냥 임의로 두면 된다. 어차피 어디서 시작하든 모든 도시를 돌며 한바퀴를 도는 경로를 찾는 것이기 때문이다. (내가 처음에 헷갈렸던 부분) (정답)
096. 가장 긴 증가하는 부분 수열 5
https://www.acmicpc.net/problem/14003
import sys
input = sys.stdin.readline
n = int(input())
a = [0] + list(map(int, input().split()))
dp = [0 for _ in range(n + 1)]
b = [0 for _ in range(n + 1)]
idx = 0
maxl = 1
b[1] = a[1]
dp[1] = 1
def binarysearch(l, r, now):
while l < r:
mid = (l + r) // 2
if b[mid] < now:
l = mid + 1
else:
r = mid
return l
for i in range(2, n + 1):
if b[maxl] < a[i]:
maxl += 1
b[maxl] = a[i]
dp[i] = maxl
else:
idx = binarysearch(1, maxl, a[i])
b[idx] = a[i]
dp[i] = idx
idx = maxl
ans = [0 for _ in range(idx + 1)]
for i in range(n, 0, -1):
if dp[i] == idx:
ans[idx] = a[i]
idx -= 1
print(maxl)
for i in range(1, maxl + 1):
print(ans[i], end = ' ')어려워서 책에서 점화식을 어떻게 정의했는지까지만 참고했다.
dp[i] : 0부터 i까지 i를 포함하는 가장 길게 증가하는 수열의 길이
앞의 계산을 뒤의 계산에서 활용하기 위해서 마지막 요소를 포함시켜 점화식을 정의하는 방식이다. dp에서 몇번 봤던 방식인 것 같다. 아무튼 여기까지는 알겠으나 태그를 보니 이분 탐색이 있었다. 이분 탐색은 너무 뜬금없게 느껴지고 어떻게 같이 활용하는 것인지 어려워서 가장 긴 증가하는 부분 수열 1~4를 먼저 풀어보기로 했다.
→ https://jungh150c.tistory.com/109
(정답)
'Group > EDOC' 카테고리의 다른 글
| EDOC 2024-1 7회차 정모 (동적 계획법 알아보기 4) (0) | 2024.05.25 |
|---|---|
| EDOC 2024-1 7회차 정모 준비 (이분 탐색, 다이나믹) (0) | 2024.05.22 |
| EDOC 2024-1 5회차 과제 (동적 계획법 알아보기 3) (0) | 2024.05.12 |
| EDOC 2024-1 5회차 정모 (동적 계획법 알아보기 2) (0) | 2024.05.12 |
| EDOC 2024-1 5회차 정모 준비 (정렬, 다이나믹) (0) | 2024.05.08 |
