2023년 8월 15일 알고리즘 문제풀이
문제 1 백준 1697
1차 시도
나의 생각
처음엔 재귀나 피보나치 등 여러 방법을 고민했다. 결국 다이나믹 프로그래밍으로 푸는게 적절하다고 생각했다. 맨처음 n에서 1초후 갈 수 있는 곳은 2n, n+1, n-1 이다. 이들을 큐에 저장하고 이들까지 도달하는데 걸린 시간도 같이 저장한다. 이 큐에서 하나씩 순회하며 2배한 좌표, +1, -1 한 좌표에 시간을 업데이트하고 큐에 다시 저장하는 것을 반복했다.
하지만 예시를 입력하면 올바른 정답이 나오지 않았다. 디버깅해봐야겠다.
결과
오답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys
n, k = map(int, sys.stdin.readline().split())
sys.setrecursionlimit = 10**6
dp = [0 for _ in range(10**6+1)]
queue = []
queue.append([n,0])
while True:
x,t = queue.pop()
if 2*x == k or x+1 == k or x-1 == k:
print(t)
break
if 2*x < 10**6 and not dp[2*x]:
dp[2*x] = t+1
queue.append([2*x,t+1])
if x+1 < 10**6 and not dp[x+1]:
dp[x+1] = t+1
queue.append([x+1,t+1])
if x-1 > 0 and x-1 < 10**6 and not dp[x-1]:
dp[x-1] = t+1
queue.append([x-1,t+1])
2차 시도
나의 생각
찾았을 때를 다음 계산할 대상을 기준으로 하고 있었다. 따라서 생각하기 편하도록 현재 x가 k인지만 확인하도록 코드를 수정하였다. 그 결과 오답에서 index 오류가 발생했다. 이것저것 범위를 조절하다보니 마지막 x-1이 0보다 크다가 아니라 크거나 같다로 두니 정답이였다! 존재할수 있는 범위는 0부터라는 조건으로 인한 문제였다. 또한 queue에서 pop이 아니라 popleft해야 한다! dp배열을 업데이트할 때 아직 도착하지 않은 곳만 업데이트하는데 낮은 시간부터 처리해야 그 지점까지 도달할 수 있는 가장 빠른 시간이 저장된다.
로직을 정리하면 다음과 같다.
- 수빈이와 동생이 위치할 수 있는 좌표(0부터 1000000)만큼의 배열
DP를 만든다. queue을 만든다.queue에는 좌표와 시간을 원소로하는 배열을 집어넣는다. 따라서 현재 수빈이의 위치n과 0초를 [n,0] 으로 넣는다.- 반복문을 통해
popleft한다. 순간이동과 +1, -1할 좌표가 범위 내에 있는지, 이미 이전 시간에 도착한 적이 없는지 검사한다. - 조건에 만족한다면 순간이동한 좌표, 1 더한 좌표와 빠진 좌표에 현재 시간 + 1을 업데이트한다. 또한 그 내용을
queue에 저장한다. - 찾을때까지 반복한다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import sys
from collections import deque
n, k = map(int, sys.stdin.readline().split())
sys.setrecursionlimit = 10**6
dp = [0 for _ in range(10**6)]
queue = deque()
queue.append([n, 0])
while True:
x, t = queue.popleft()
if x == k:
print(t)
break
if 2*x < 10**6 and not dp[2*x]:
dp[2*x] = t+1
queue.append([2*x, t+1])
if x+1 < 10**6 and not dp[x+1]:
dp[x+1] = t+1
queue.append([x+1, t+1])
if x-1 >= 0 and x-1 < 10**6 and not dp[x-1]:
dp[x-1] = t+1
queue.append([x-1, t+1])
문제 2 백준 13205
1차 시도
나의 생각
순위를 담은 배열을 탐색한다. 해당 순위가 중간 이하라면, 비밀번호를 만드는 함수를 실행한다. 비밀번호를 만드는 함수는 그 다음 순위를 탐색하며 연속으로 이어나간다.
만약 다음 순위가 중간 이상이거나, 비밀번호의 길이가 L2 이상이거나 더이상 뒤 순위가 없다면 종료된다. L1 이상으로 충분한 길이의 비밀번호면 반환하고 아니면 False처리 되는 함수이다.
모든 순위를 순회하며 만들어진 비밀번호를 배열에 넣고 최소힙을 통해 가장 적합한 비밀번호를 찾았다. 그리고 같은 비밀번호의 갯수를 count했다.
채점에서는 시간초과가 발생하였고, 직접 컴파일했을땐 정답이 나타나지 않았다. 큰 틀은 맞았을까..
결과
오답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import sys
from heapq import heappop, heappush
t = int(sys.stdin.readline())
for _ in range(t):
k,n,l_1,l_2 = map(int,sys.stdin.readline().split())
ranks = list(map(int,sys.stdin.readline().split()))
mid = k//2 +1
def make_password(x):
tmp_arr = []
while len(tmp_arr)<l_2 and x < n:
if ranks[x] >= mid:
tmp_arr.append(ranks[x])
else:
break
x += 1
if len(tmp_arr) >= l_1:
return tmp_arr
else:
return False
arr = []
min_val = mid
for i in range(n):
if ranks[i] >= min_val:
min_val = ranks[i]
if make_password(i):
heappush(arr,make_password(i))
print(arr.count(arr[0]))
2차 시도
나의 생각
비밀번호는 길이가 긴게 우선이라고 생각했다. 따라서 문제에서 제시한 비밀번호의 조건이 어겨지지 않는 이상 길수록 더 서열이 높다고 생각하였다. 길이가 같다면 앞에서부터 비교하여 같은 순서에서 순위가 더 낮을 때 서열이 높은 우선순위라고 판단했다. 이 모든걸 반복문으로 처리하려다보니 당연히 시간초과가 났다.
비밀번호 배열에서 가장 낮은 순위의 값을 찾고 start로 설정한다. 그리고 중간순위 값을 mid로 설정한다.
비밀번호를 만드는 make_password함수는 다음과 같은 원리이다. 원소로 받은 x는 순위가 나타난 배열 arr의 index이다. index가 x인 원소부터 하나씩 뒤로 가면서 비밀번호를 tmp_arr에 저장하는 배열이다. 문제에서 나타나는 조건대로 중간순위보다 높은 순위(숫자로는 낮은 값)이거나, 비밀번호의 최대 길이인 l_2보다 길면 반복문은 종료된다. l_1보다 짧지 않다면 비밀번호를 반환한다.
그다음 change함수는 두 비밀번호 배열을 비교한다. 앞에서부터 비교하여 같은 index의 순위가 다를 때 숫자가 더 큰 다시 말해 순위가 더 낮은 비밀번호를 반환한다. 완전히 같을땐 False를 반환한다.
위의 두 함수를 이용해 앞에서부터 모든 경우를 순회하였다. 시간복잡도를 줄일 방법을 고민해야겠다…
결과
오답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import sys
t = int(sys.stdin.readline())
for _ in range(t):
k, n, l_1, l_2 = map(int, sys.stdin.readline().split())
ranks = list(map(int, sys.stdin.readline().split()))
for i in range(n, -1, -1):
if i in ranks:
start = i
break
mid = k//2 + 1
def make_password(x):
tmp_arr = []
while len(tmp_arr) < l_2 and x <= n-1:
if ranks[x] >= mid:
tmp_arr.append(ranks[x])
else:
break
x += 1
if len(tmp_arr) >= l_1:
return tmp_arr
else:
return
def change(a, b):
d = len(a)
for i in range(d):
if a[i] > b[i]:
return a
elif a[i] < b[i]:
return b
return False
arr = []
cnt = 1
for i in range(n):
if ranks[i] != start:
continue
if make_password(i):
if not arr:
arr.append(make_password(i))
else:
if len(make_password(i)) > len(arr[0]):
arr.pop()
arr.append(make_password(i))
cnt = 1
elif len(make_password(i)) == len(arr[0]):
if change(make_password(i), arr[0]) == arr[0] or not change(make_password(i), arr[0]):
cnt += 1
else:
cnt = 1
arr.pop()
arr.append(make_password(i))
print(cnt)
3차 시도
추후 업데이트..
문제 3 백준 1486
1차 시도
나의 생각
어떤 좌표로 갈 때 방법이 다양할 수 있다는 것이 많이 헷갈렸다. 예를 들어 1에서 10까지 올라갈 때 1씩 9번 올라가는 것은 9만큼 시간이 걸리지만 한번에 올라가면 81의 시간이 걸린다. 즉 좌표 이동횟수와 소모시간은 무관하다는 것이다. 그래서 동서남북으로 탐색하며 현재 있는 곳 까지의 소모시간에서 다음 값을 더하여 다음 좌표에 업데이트 하였다. 단, 이미 업데이트가 된 곳은 넘어갔다. 예를 들어 현재 (2,2)까지 10의 시간이 걸렸고 높이가 5인 상황에서 다음 높이가 7인 (2,3)까지 걸리는 시간은? 10 + (7-5)의 제곱 = 14. 이런 방식이었다.
풀다보니 호텔로 돌와야 하는데 가는 길과 오는 길이 같다는 조건이 없었다. 또한 높이차가 t이상이면 이동할 수 없다는 조건도 뒤늦게 발견했다.. 그래서 그 로직을 추가했다. 우선 높이 차를 위한 조건문을 추가했다. 또 2차원 배열의 원소를 길이가 2인 배열로 하여 거기까지 가는 시간과 거기서부터0,0으로 오는 시간을 기록했다. 즉 time[p][q] 는 [ 호텔에서 (p,q)까지 가는데 걸리는 시간, (p,q)에서 호텔까지 오는데 걸리는 시간]을 표현하도록 하였다.
결과적으로 오답처리 되었다. 갈떄와 올때를 따로 적긴 했지만 그 둘을 업데이트 하는 과정이 갈때를 기준으로만 로직이 작성되었다. 아마 올 때의 값들은 최솟값이 아닌것 같다. 차라리 출발지를 parameter로 받아서, 다른 좌표까지 가는데 소모 시간을 나타내는 2차원 배열을 반환하는 함수를 만들어야겠다. 올때 갈때 출발지만 바뀌면 될듯하다.
결과
오답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import sys
from collections import deque
n, m, t, d = map(int, sys.stdin.readline().split())
graph = []
for _ in range(n):
graph.append(list(sys.stdin.readline().rstrip()))
alphabet = [
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y',
'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'
]
def change(x):
ans = alphabet.index(x)
return ans
time = [[[0, 0] for _ in range(m)] for _ in range(n)]
da = [0, -1, 0, 1]
db = [1, 0, -1, 0]
arr = deque()
arr.append([0, 0])
height = 0
while arr:
a, b = arr.popleft()
for i in range(4):
updated = False
na = a + da[i]
nb = b + db[i]
if na >= 0 and na < n and nb >= 0 and nb < m:
if not na and not nb:
continue
arrive = graph[na][nb]
start = graph[a][b]
dif_height = change(arrive) - change(start)
if abs(dif_height) > t:
continue
if dif_height > 0:
current_time_go = dif_height**2
current_time_back = 1
else:
current_time_go = 1
current_time_back = dif_height**2
current_time_go += time[a][b][0]
current_time_back += time[a][b][1]
if not time[na][nb][0] or current_time_go < time[na][nb][0]:
time[na][nb][0] = current_time_go
updated = True
if not time[na][nb][1] or current_time_back < time[na][nb][1]:
time[na][nb][1] = current_time_back
updated = True
if updated:
arr.append([na,nb])
if time[na][nb][0] + time[na][nb][1] <= d:
height = max(height, change(graph[na][nb]))
print(height)
2차 시도
나의 생각
이게 됐다는게 신기하다! 차근차근 설명해보겠다.
우선 편하게 하기 위해 입력값을 받고 나서 높이를 다 숫자로 바꿔주었다. 시간은 최솟값으로 업데이트하는게 중요하니 기존에 배열 time을 생성할때 0으로 두지 않고 큰 값인 10**9로 두었다. 또 기존에는 time 배열이 하나였는데, 이번엔 함수 내로 넣었다.
함수는 출발좌표를 parameter로 받는다. time배열에서 출발좌표의 값만 0으로 설정한다. 그리고 기존처럼 bfs 방식으로 갈 후보들을 배열에 담았는데 이번엔 deque을 쓰지 않고 heapq를 사용했다. 왜냐하면, 각 경우에서 기존에 업데이트 되어있는 소모시간보다 큰 값인 경우 계산할 필요없이 넘어가버리면 되기 때문이다. 최소 힙을 사용하고, 좌표와 함께 0번 index로 소모 시간을 넣어준다. 그럼 최소 heap이기 때문에 해당 좌표까지 걸리는 시간이 가장 작은 것부터 heappop된다.
heappop 된 좌표의 동서남북을 탐색한다. 범위 내에 있는지 확인한 후, 높이차가 문제에서 주어진 t보다 작은지도 체크한다. 이동할 때 높아지는지 작아지는지에 따라 알맞게 추가되는 소모 시간도 계산한다. 기존에 업데이트되있던 시간과 비교하여 작은 값으로 다시 업데이트해준다. 업데이트 되었다면, 힙에 넣어서 탐색 후보로 선정한다.
힙을 모두 순회하면 완성된 time을 반환한다. 이 time은 parameter로 받은 좌표에서 각 좌표까지 소모되는 최소 시간을 나타낸다.
이 함수에 호텔위치인 [0,0]을 넣으면 호텔에서 각 좌표까지 걸리는 최소 시간을 알 수 있다. 이 시간이 시간 제한인 d보다 작은 경우는 모두 ans에 담았다. 담을때 좌표만 담는 것이 아니라 해당 좌표 의 높이의 음수값을 0번 index에 넣어줬다. 가장 높은 위치를 구해야하기 때문에 높이에 관한 최대합을 이용하기 위해서이다!
그럼 높이가 높은 순서대로 heappop할 수 있다. 하면서 그 좌표까지의 소모 시간 + 그 좌표에서 호텔까지 소모시간을 더해서 시간제한 d를 넘지 않는다면 답으로 출력한다.
다른 사람은 어떻게 풀었나 싶어서 찾아봤는데, 다익스트라 알고리즘으로 풀어야 한다고 한다. 들어는 봤는데 뭔지 몰랐다. 근데 이 방법이 그 방법인것 같다. 잘됐다ㅋ
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import sys
from heapq import heappop, heappush
n, m, t, d = map(int, sys.stdin.readline().split())
graph = []
for _ in range(n):
graph.append(list(sys.stdin.readline().rstrip()))
alphabet = [
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y',
'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'
]
def change(x):
ans = alphabet.index(x)
return ans
for i in range(n):
for j in range(m):
graph[i][j] = change(graph[i][j])
da = [0, -1, 0, 1]
db = [1, 0, -1, 0]
def search(p, q):
time = [[10**9 for _ in range(m)] for _ in range(n)]
time[p][q] = 0
arr = []
heappush(arr, [0, p, q])
while arr:
x, a, b = heappop(arr)
if time[a][b] < x:
continue
for i in range(4):
na = a + da[i]
nb = b + db[i]
if na >= 0 and na < n and nb >= 0 and nb < m:
start = graph[a][b]
arrive = graph[na][nb]
dif_height = arrive - start
if abs(dif_height) <= t:
if dif_height > 0:
current_time = x + (dif_height)**2
else:
current_time = x + 1
if time[na][nb] > current_time:
time[na][nb] = current_time
heappush(arr, [current_time, na, nb])
return time
go_time = search(0, 0)
ans = []
for i in range(n):
for j in range(m):
if go_time[i][j] < d:
heappush(ans, [-1*graph[i][j], i, j])
k = len(ans)
for i in range(k):
h, a, b = heappop(ans)
h *= -1
back_time = search(a, b)
total = back_time[0][0] + go_time[a][b]
if total <= d:
print(h)
break
