2023년 9월 4일 알고리즘 문제풀이
문제 1 백준 1167
1차 시도
나의 생각
입력값을 list로 받은 후 가장 앞인 0번 index는 어떤 정점의 정보인지를 나타낸다고 생각하였고 그 이후 둘 씩 짝지어서 도착 정점과 거리로 설정하였다. 이를 바탕으로 인접리스트를 만들고 index를 2씩 뛰어넘어 -1이 나오면 더이상 정보가 없으므로 다음 줄로 넘어갔다.
이후에는 두 점간의 거리를 bfs를 통해 탐색하도록 하였다. 모든 점간의 거리를 찾아 최댓값을 도출하였다. 하지만 메모리,시간초과가 뜬다… 다찾아보면 안되나보다.
결과
오답(메모리, 시간 초과)
코드
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
import sys
from heapq import heappop, heappush
v = int(sys.stdin.readline())
tmp = []
for _ in range(v):
tmp.append(list(map(int,sys.stdin.readline().split())))
graph = [[] for _ in range(v+1)]
for l in tmp:
x = 1
while x < len(l):
if l[x] == -1:
break
graph[l[0]].append([l[x],l[x+1]])
x += 2
def bfs(a,b):
visited = [False for _ in range(v+1)]
visited[a] = True
arr = []
heappush(arr,[0,a])
while arr:
cnt, now = heappop(arr)
cnt *= -1
if now == b:
return cnt
for next in graph[now]:
if not visited[next[0]]:
visited[next[0]] = True
heappush(arr,[-1*(cnt+next[1]),next[0]])
ans = 0
for start in range(1,v+1):
for arrive in range(1,v+1):
ans = max(ans,bfs(start,arrive))
print(ans)
2차 시도
나의 생각
문제를 계속 읽다가 트리에 꽂혔다. 트리에서 아무 점이나 골랐을 때, 가장 멀리 있는 점은 루프노트를 기준으로 반대쪽에 가장 끝에 있는 정점일 것이다. 물론 거리는 그때 그때 다르겠지만.. 어쩄든 확실한건 임의의 점을 고른 후 거기서 가장 멀리 있는 점을 찾으면 트리의 한쪽 끝에 있는 정점을 찾을 수 있다! 그 점에서 다시 가장 멀리 있는 점을 구하면? 문제에서 말하는 트리의 지름을 구할 수 있다.
기존 코드에서는 정점간의 거리를 구했지만, 이렇게 하면 한 정점에서 다른 정점까지의 거리를 구하는 것을 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
import sys
from heapq import heappop, heappush
v = int(sys.stdin.readline())
tmp = []
for _ in range(v):
tmp.append(list(map(int, sys.stdin.readline().split())))
graph = [[] for _ in range(v+1)]
for arr in tmp:
x = 1
while x < len(arr):
if arr[x] == -1:
break
graph[arr[0]].append([arr[x], arr[x+1]])
graph[arr[x]].append([arr[0], arr[x+1]])
x += 2
def bfs(a):
visited = [0 for _ in range(v+1)]
q = []
heappush(q, [0, a])
while q:
cnt, now = heappop(q)
cnt *= -1
for next in graph[now]:
if not visited[next[0]] and next[0] != a:
visited[next[0]] = cnt+next[1]
heappush(q, [-1*(cnt+next[1]), next[0]])
max_val = max(visited)
return [max_val, visited.index(max_val)]
tmp = bfs(1)[1]
ans = bfs(tmp)
print(ans[0])
문제 2 백준 1956
1차 시도
나의 생각
두 마을간의 거리를 BFS나 DFS를 통해 구하되 큐를 이용한 최소힙으로 최소간의 거리로 만들고, 도착지점이 맨 처음 출발지점과 같으면 사이클이 완성되었다는 의미이므로 함수가 종료되도록 구현하였다. 시간초과가 떴다. BFS로 해서 안되길래 DFS로도 해봤지만 안됐다..
결과
오답
코드
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
import sys
from heapq import heappush, heappop
v,e = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(v+1)]
for _ in range(e):
a,b,c = map(int,sys.stdin.readline().split())
graph[a].append([b,c])
visited = [0 for _ in range(v+1)]
def dfs(now,cnt,start):
if now == start and cnt:
return cnt
for next, cost in graph[now]:
if not visited[next] or (visited[next] > cost + cnt):
visited[next] = cost + cnt
dfs(next,cnt+cost,start)
ans = []
for i in range(1,v+1):
if dfs(i,0,i):
ans.append(dfs(i,0,i))
if ans:
print(min(ans))
else:
print(-1)
2차 시도
나의 생각
다른 사람의 답을 참고해보니 굳이 길을 탐색할 필요 없었다. 그냥 입력값을 통해 받은 경로의 정보를 통해 3중반복문을 이용하여 최단 거리를 업데이트 하는 방식을 취했다. 이게 플로이드 와샬알고리즘이라고 한다. 예전엔 이게 너무 어려워서 나중에 알아둬야겠다고 생각했는데 되게 간단한 방법이라 당황스럽다. 알아둬야겠다.
그런데 백준에서 pypy3로 제출해야만 통과한다. python으로 제출하면 시간초과가 뜬다. 나의 뜬금없는 똥꼬집이 발현되어 python으로도 제출해서 통과해보고 싶었다. 다음 시도에 설명하겠다.
결과
이해
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import sys
v, e = map(int, sys.stdin.readline().split())
graph = [[1e9 for _ in range(v+1)] for _ in range(v+1)]
for _ in range(e):
a, b, c = map(int, sys.stdin.readline().split())
graph[a][b] = c
for k in range(1, v+1):
for i in range(1, v+1):
for j in range(1, v+1):
if graph[i][j] > graph[i][k] + graph[k][j]:
graph[i][j] = graph[i][k] + graph[k][j]
ans = 1e9
for i in range(1, v+1):
for j in range(1, v+1):
ans = min(ans, graph[i][j]+graph[j][i])
if ans == 1e9:
print(-1)
else:
print(ans)
3차 시도
나의 생각
다익스트라나 여러가지 다른 답안들을 훑어봤는데, 기존 폴로이드 와샬 알고리즘을 썼는데도 Python3로 제출해서 통과한 답안이 있었다. 나와의 차이는 함수로 정의했는가, 아닌가의 차이였다.
아래에 있는 두 코드중 위 코드는 기존 나의 플로이드 와샬 알고리즘을 약간 변형한 코드이다. 둘 중 아래는 main이라는 함수로 정의한 후 호출한 것이다.
기존 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys
v, e = map(int, sys.stdin.readline().split())
graph = [[1e9 for _ in range(v+1)] for _ in range(v+1)]
for _ in range(e):
a, b, c = map(int, sys.stdin.readline().split())
graph[a][b] = c
for k in range(1, v+1):
for i in range(1, v+1):
for j in range(1, v+1):
if graph[i][j] > graph[i][k] + graph[k][j]:
graph[i][j] = graph[i][k] + graph[k][j]
ans = 1e9
for i in range(1,v+1):
ans = min(ans,graph[i][i])
if ans == 1e9:
print(-1)
else:
print(ans)
아래는 함수로 정의한 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys
v, e = map(int, sys.stdin.readline().split())
graph = [[1e9 for _ in range(v+1)] for _ in range(v+1)]
for _ in range(e):
a, b, c = map(int, sys.stdin.readline().split())
graph[a][b] = c
def main():
for k in range(1, v+1):
for i in range(1, v+1):
for j in range(1, v+1):
if graph[i][j] > graph[i][k] + graph[k][j]:
graph[i][j] = graph[i][k] + graph[k][j]
ans = 1e9
for i in range(1,v+1):
ans = min(ans,graph[i][i])
if ans == 1e9:
print(-1)
else:
print(ans)
main()
두 코드를 모두 백준에 제출했을 때 결과가 달랐다.
함수로 정의하여 호출하는 것과 그냥 전개하는 것의 차이는 무엇일까..?
아래에서 설명하겠다.
나의 생각
이해
결과
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys
v, e = map(int, sys.stdin.readline().split())
graph = [[1e9 for _ in range(v+1)] for _ in range(v+1)]
for _ in range(e):
a, b, c = map(int, sys.stdin.readline().split())
graph[a][b] = c
def main():
for k in range(1, v+1):
for i in range(1, v+1):
for j in range(1, v+1):
if graph[i][j] > graph[i][k] + graph[k][j]:
graph[i][j] = graph[i][k] + graph[k][j]
ans = 1e9
for i in range(1,v+1):
ans = min(ans,graph[i][i])
if ans == 1e9:
print(-1)
else:
print(ans)
main()
함수를 정의하는 것과 정의하지 않는 것의 차이
함수를 정의하는 경우 로컬변수로 지정하는 것이고 정의하지 않는 경우는 전역변수로 지정하는 것이다. 우리가 로컬 변수를 지정하는 것은 고정된 크기의 배열에 할당하고 그 index를 가지는 것인 반면, 전역변수로 설정하는 것은 해시 기반 구조인 딕셔너리에 저장된다.
일반적으로 index를 모르는 상황에서 어떤 값을 찾아낼 떄는 해쉬구조가 유리하다. 배열에서는 최악의 경우 배열의 크기인 O(n)의 시간복잡도가 발생하지만 해시 검색은 키에대한 해시 값을 계산해서 데이터에 빠르게 접근하게되어 O(1)의 시간복잡도를 가지기 때문이다.
하지만 변수로 지정하는 지금 상황에서 우리는 index를 알고 있다. 따라서 가지고 있는 index를 통해 배열에 접근하는 것이 해시 기반 데이터 구조보다 더 빠르고 효율적이다. 그 결과 로컬변수를 정의하는 경우가 전역변수를 정의할떄 보다 더 빠르게 알고리즘이 컴파일되는 결과를 나타낸다.
고정된 크기의 배열이 의미하는 바는 함수가 정의될때 고정되었다는 의미이다. 함수를 정의할 때 코드에 나타난 것 만큼 고정된 메모리 공간을 가리키는 index가 할당된다. 그리고 정의된 함수가 컴파일 될때마다 이 메모리 공간이 사용되는 것이다.
조금 더 쉽게 말하자면 함수를 정의할 때
” 이 함수는 변수를 위해 4개의 공간이 필요하구나. 미리 만들어놓자. 자 4개에 대한 index야!”
라고 한 뒤, 이후에 실제 함수가 실행되면
“내가 미리 너가 쓸 4개의 변수를 위한 메모리공간을 할당해놨어! index 이거 쓰면 돼!”
라고 생각하면 된다.
결론적으로 함수를 정의하는 것과 안하는것의 차이는 변수가 로컬이냐 전역이냐의 차이를 의미하고 이로인해 저장하는 데이터 구조의 차이가 발생하기 때문에 생기는 것이였다는 의미이다.
문제 3 백준 1817
1차 시도
나의 생각
스택에 책을 넣을 때 넣으면 박스 무게를 초과할지, 딱 맞을지, 여유로울지를 나누었다. 넣었을 때 초과되면 새 박스를 가져와서 넣고, 딱 맞는다면 넣은 후 새박스를 가져온다. 여유가 있다면 넣기만 한다. 하나 주의하자면 책이 0개일 수도 있다는 것.
결과
정답
코드
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
import sys
n, m = map(int, sys.stdin.readline().split())
if n == 0:
print(0)
else:
books = list(map(int, sys.stdin.readline().split()))
stk = []
cnt = 0
for i in range(len(books)):
if not stk:
stk.append(books[i])
cnt += 1
continue
if sum(stk) + books[i] > m:
stk.clear()
cnt += 1
stk.append(books[i])
elif sum(stk) + books[i] == m:
stk.clear()
else:
stk.append(books[i])
print(cnt)
